Beschleunigung durch algorithmische Fortschritte im Vergleich zur Hardware

14

Ich erinnere mich an eine Studie oder einen Artikel vor einiger Zeit, in dem behauptet wurde, dass der größte Teil der in Computerprogrammen in den letzten Jahrzehnten beobachteten Beschleunigung auf besseren Algorithmen und nicht auf schnellerer Hardware beruht. Kennt jemand die Studie oder den Artikel?

John
quelle
8
Wahrscheinlich besser für cs.stackexchange geeignet.
Yuval Filmus
es ist in der Tat ein großer Paradigmenwechsel innerhalb der letzten paar Jahre WRT moores Gesetzes, Taktfrequenzen und Parallelität und die in vielen Artikeln / Papieren bedeckt worden ist ....
VZN

Antworten:

8

Dies ist eine ungewollt komplexe Frage. Diese Idee, dass Software-Gewinne Hardware-Gewinne übertroffen haben, wurzelt anscheinend in einem echten Regierungsbericht, nähert sich aber (wie Ihre Frage zeigt) möglicherweise dem Status einer kleinen städtischen Legende, weil sie missverstanden oder falsch interpretiert wird. Die Schlagzeilen für Zusammenfassung / Sound-Bite stimmen nicht wirklich mit der tatsächlichen Aussage im Bericht überein.

siehe [1] oder [2] welche Zustände

In einem im vergangenen Dezember veröffentlichten Bericht einer unabhängigen Gruppe von Wissenschafts- und Technologieberatern des Weißen Hauses wurden Forschungsergebnisse zitiert, die belegen, dass der Leistungszuwachs bei der Durchführung von Computeraufgaben, die sich aus Verbesserungen der Softwarealgorithmen ergeben, häufig weit über dem der schnelleren Prozessoren liegt.
... Der
Beraterbericht des Weißen Hauses zitierte jedoch Forschungsergebnisse, darunter eine Studie über den Fortschritt einer Benchmark-Produktionsplanungsaufgabe über einen Zeitraum von 15 Jahren. In dieser Zeit verbesserte sich die Geschwindigkeit, mit der die Berechnungen abgeschlossen wurden, um den Faktor 43 Millionen. Davon entfiel ein Faktor von rund 1.000 auf schnellere Prozessoren, so die Untersuchung des deutschen Wissenschaftlers und Mathematikers Martin Grotschel. Ein Faktor von 43.000 war jedoch auf Verbesserungen der Effizienz von Softwarealgorithmen zurückzuführen.

Aber das Problem von Software und Hardware ist weit entfernt von dieser eindimensionalen Vereinfachung, viel komplexer, und Lohrs Blog hat es genauer formuliert - Software und Hardware bilden eine Art symbiotische Yin-Yang-Verschmelzung, und beide sind sehr bedeutend vorangekommen, sogar erstaunlich weit fortgeschritten die Jahrzehnte.

Vorbehalt / Kleingedrucktes: Bei bestimmten Softwarealgorithmen, die in einigen Fällen sehr umfangreich waren, kann man keine individuellen Gewinne erzielen und diese über alle Algorithmen hinweg verallgemeinern.

Das aktuelle Zitat aus dem Bericht finden Sie auf Seite 71:

Noch bemerkenswerter - und noch weniger bekannt - ist, dass in vielen Bereichen die durch Verbesserungen der Algorithmen bedingten Leistungssteigerungen sogar die dramatischen Leistungssteigerungen aufgrund der höheren Prozessorgeschwindigkeit bei weitem übertroffen haben. Die Algorithmen, die wir heute für die Spracherkennung, für die Übersetzung natürlicher Sprachen, für das Schachspiel und für die Logistikplanung verwenden, haben sich im letzten Jahrzehnt bemerkenswert weiterentwickelt. Es ist jedoch schwierig, die Verbesserung zu quantifizieren, da es sowohl um die Qualität als auch um die Ausführungszeit geht.

Daher ist dieser Regierungsbericht stark recherchiert und poliert, die grundlegende Behauptung von massiven Gewinnen aufgrund theoretischer Software-Fortschritte in einigen Bereichen ist richtig und fördert (theoretische / algorithmische) Forschung teilweise auf dieser Grundlage.

In den letzten Jahren gab es jedoch einige andere neue / grundlegende / massive Phänomene / Trends / Verschiebungen oder das, was Intels Grove als "Wendepunkte" bezeichnet, die im Hardware- und im Software-Design auftreten. aka "gamechangers":

  • Der Aufstieg von "Exascale" Supercomputing ist aufgrund von Hardware-Skalierungsbeschränkungen möglicherweise nicht so einfach wie bei "Petascale"
  • Die Taktraten, ein Hauptantrieb für frühere Geschwindigkeitszuwächse, haben abgenommen (teilweise aufgrund von Wärme- / Kühlungsbeschränkungen)
  • Die Hardware befindet sich in einem massiven Wandel hin zu weniger rechenintensiven, energieeffizienteren Geräten, z. B. Mobilgeräten, Rechenzentren / Virtualisierung / Cloud usw
  • Die Verbesserung der Parallelität von Software und Hardware (z. B. "Multicore") wird daher für Leistungsverbesserungen immer wichtiger (wobei die Theorie viel darüber zu sagen hat, wie Algorithmen parallelisiert werden sollen).

[1] skeptic.se, schlägt der Fortschritt bei den Algorithmen den Fortschritt bei der Hardware

[2] Software-Fortschritt schlägt Moores Law NYT-Blog von Lohr

[3] BERICHT AN DEN PRÄSIDENTEN UND DEN KONGRESS, IN DEM EINE DIGITALE ZUKUNFT GESTALTET WIRD: BUNDESGEGENSTÄNDIGE FORSCHUNG UND ENTWICKLUNG IN DER NETZWERK- UND INFORMATIONSTECHNOLOGIE Dez 2010

vzn
quelle
Nachtrag. Es gibt wahrscheinlich einige gute (Gegen-) Beispiele für wichtige Algorithmen, deren Implementierungseffizienz über die Jahrzehnte nicht weiterentwickelt wurde. Ideen? Ein Kandidatenbereich könnten Matrixalgorithmen sein, die nicht parallelisierbar sind, oder andere Algorithmen, die von Natur aus nicht parallelisierbar zu sein scheinen. Außerdem haben einige Algorithmen theoretische Verbesserungen in der Komplexität der unteren Schranken erfahren, aber die Algorithmen sind tatsächlich nicht implementiert oder für typische nicht durchführbar Eingänge etc ... zB Matrixmultiplikation?
vzn
1
Dies ist eine großartige Antwort - voller Details, Nuancen und sachkundiger Diskussionen!
Joshua Grochow