Przyspieszenie dzięki postępom algorytmicznym w porównaniu ze sprzętem


14

Pamiętam jakiś czas temu badanie lub artykuł, w którym twierdziłem, że większość przyspieszenia obserwowanego w programach komputerowych w ciągu ostatnich kilku dekad wynika z lepszych algorytmów niż z szybszego sprzętu. Czy ktoś zna badanie lub artykuł?


8
Prawdopodobnie lepsze dopasowanie do cs.stackexchange.
Yuval Filmus

rzeczywiście istnieje duża zmiana paradygmatu w ciągu ostatnich kilku lat prawa, prędkości zegara i równoległości, która została
opisana

Odpowiedzi:


8

to niezamierzenie złożone pytanie. ta idea, że ​​zyski oprogramowania wyprzedziły zyski sprzętowe, jest najwyraźniej zakorzeniona w prawdziwym raporcie rządowym, ale (jak wskazuje twoje pytanie) być może zbliża się do statusu małej legendy miejskiej z powodu niezrozumienia lub błędnej interpretacji. nagłówki streszczenia / zgryzienia nie są tak naprawdę zgodne z faktycznym punktem podanym w raporcie.

patrz [1] lub [2], który stwierdza

Raport niezależnej grupy doradców naukowych i technologicznych dla Białego Domu, opublikowany w grudniu ubiegłego roku, cytuje badania pokazujące, że wzrost wydajności w wykonywaniu zadań obliczeniowych wynikający z ulepszeń algorytmów oprogramowania często znacznie przewyższa przyrosty związane z szybszymi procesorami.
...
Ale raport doradczy Białego Domu przytacza badania, w tym studium postępów w ciągu 15 lat w zakresie wzorcowego zadania planowania produkcji. W tym czasie szybkość wykonywania obliczeń poprawiła się 43-krotnie. Według badań Martina Grotschela, niemieckiego naukowca i matematyka, z ogólnej liczby około 1000 czynnik przypisano szybszym procesorom. Jednak czynnik 43 000 spowodowany był poprawą wydajności algorytmów oprogramowania.

ale kwestia oprogramowania kontra sprzętu jest bardzo daleka od tego jednowymiarowego uproszczenia, o wiele bardziej złożona, a blog Lohrs ma to dokładniejsze - oprogramowanie i sprzęt tworzą rodzaj symbiotycznej fuzji yin-yang i oba rozwinęły się znacznie, a nawet oszałamiająco ponad dekady.

zastrzeżenie / drobny druk: nie można uzyskać indywidualnych korzyści w poszczególnych algorytmach programowych, które w niektórych przypadkach były bardzo znaczne, i uogólnić je we wszystkich algorytmach.

cytat z raportu znajduje się na stronie 71:

Jeszcze bardziej niezwykłe - i jeszcze mniej powszechnie rozumiane - jest to, że w wielu obszarach wzrost wydajności dzięki ulepszeniom algorytmów znacznie przekroczył nawet dramatyczne przyrosty wydajności ze względu na zwiększoną szybkość procesora. Algorytmy, których używamy dzisiaj do rozpoznawania mowy, tłumaczenia języka naturalnego, gry w szachy, planowania logistyki, znacznie się rozwinęły w ciągu ostatniej dekady. Trudno jest jednak oszacować poprawę, ponieważ dotyczy ona zarówno jakości, jak i czasu wykonania.

więc ten raport rządowy jest wysoce zbadany i dopracowany, podstawowe twierdzenie o ogromnych zyskach z powodu teoretycznych postępów oprogramowania w niektórych obszarach jest poprawne i częściowo promuje (teoretyczne / algorytmiczne) badania częściowo na tej podstawie.

istnieje jednak kilka innych nowych / ostatnich fundamentalnych / masywnych zjawisk / trendów / zmian w ostatnich latach lub tego, co Intels Grove nazywa „punktami przegięcia”, które występują w projektowaniu sprzętu w porównaniu z oprogramowaniem. aka „gamechangers”:

  • wzrost superkomputerów „Exascale” może nie być tak łatwy, jak w przypadku „Petascale” z powodu ograniczeń związanych ze skalowaniem sprzętu
  • Prędkości zegara, główny napęd wcześniejszych przyrostów prędkości, ustabilizowały się (częściowo z powodu ograniczeń związanych z ogrzewaniem / chłodzeniem)
  • sprzęt przechodzi masowe przejście w kierunku mniej intensywnych obliczeniowo, bardziej energooszczędnych urządzeń, np. mobilnych, centrów danych / wirtualizacji / chmury itp.
  • poprawa równoległości w oprogramowaniu i sprzęcie (np. „wielordzeniowy”) staje się zatem coraz ważniejsza dla poprawy wydajności (gdzie teoria ma wiele do powiedzenia na temat tego, jak zrównoleglać algorytmy)

[1] septic.se, postęp w algorytmach pokonuje postęp w sprzęcie

[2] Postęp oprogramowania wyprzedza blog Moores Law NYT autorstwa Lohr

[3] SPRAWOZDANIE DLA PREZYDENTA I KONGRESU PROJEKTUJĄCEGO CYFROWĄ PRZYSZŁOŚĆ: FEDERALNIE BADANE BADANIA I ROZWÓJ W SIECI I TECHNOLOGII INFORMACYJNEJ Grudzień 2010


uzupełnienie. prawdopodobnie istnieją dobre (przeciwne) przykłady ważnych algorytmów, które w ogóle nie rozwinęły się pod względem wydajności implementacji przez dziesięciolecia. pomysły? jednym obszarem kandydującym mogą być algorytmy matrycowe, które nie są zrównoleglalne lub inne algorytmy, które wydają się z natury niemożliwe do zrównoleglenia ... również niektóre algorytmy uległy teoretycznej poprawie w dolnej granicy złożoności, ale algorytmy nie są w rzeczywistości wdrożone lub nie są wykonalne dla typowych wielkości wejściowe itp ... np. mnożenie macierzy?
vzn

1
To świetna odpowiedź - pełna szczegółów, niuansów i fachowej dyskusji!
Joshua Grochow
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.