Ist die algorithmische Analyse durch Flop-Counting überholt?

43

In meinen Kursen zur numerischen Analyse habe ich gelernt, die Effizienz von Algorithmen zu analysieren, indem ich die Anzahl der erforderlichen Gleitkommaoperationen (Flops) im Verhältnis zur Größe des Problems gezählt habe. In Trefethen & Baus Text zur Numerischen Linearen Algebra finden sich beispielsweise sogar 3D-Bilder der Flop-Zählungen.

Jetzt ist es in Mode zu sagen, dass "Flops frei sind", weil die Speicherlatenz zum Abrufen von Dingen, die sich nicht im Cache befinden, so viel größer ist als die Kosten eines Flops. Aber wir bringen den Schülern immer noch bei, Flops zu zählen, zumindest in Kursen zur numerischen Analyse. Sollten wir ihnen beibringen, stattdessen Speicherzugriffe zu zählen? Müssen wir neue Lehrbücher schreiben? Oder ist der Speicherzugriff zu maschinenspezifisch, um Zeit darauf zu verwenden? Wie sieht der langfristige Trend dahingehend aus, ob Flops oder Speicherzugriff der Engpass sind?

Hinweis: Einige der folgenden Antworten scheinen eine andere Frage zu beantworten: "Soll ich meine Implementierung zwangsweise umschreiben, um ein paar Flops zu sparen oder die Cache-Leistung zu verbessern?" Was ich aber frage, ist eher wie folgt: " Ist es sinnvoller, die algorithmische Komplexität in Bezug auf arithmetische Operationen oder Speicherzugriffe abzuschätzen ?"

David Ketcheson
quelle
1
> "Ist es sinnvoller, die algorithmische Komplexität in Bezug auf arithmetische Operationen oder Speicherzugriffe abzuschätzen?" . Aus praktischer Sicht sind eingebettete Systeme immer noch eher durch die FPU-Geschwindigkeit als durch die Speicherbandbreite begrenzt. Selbst wenn das Zählen von Flops nach HPC-Standards als veraltet angesehen wurde, ist es dennoch für andere Communities von praktischem Nutzen.
Damien

Antworten:

31

Ich denke, das (erste Ordnung) Richtige ist, das Verhältnis von Flops zu Bytes zu betrachten, das im Algorithmus benötigt wird, den ich nenne . Sei F m a x die maximale Floprate des Prozessors und B m a x die maximale Bandbreite. Wenn F m a xβFmaxBmeinX, dann wird der Algorithmus Bandbreite begrenzt. WennBmeinxβ>Fmeinexist der Algorithmus beschränkt Flop.FmeinXβ>BmeinXBmeinXβ>FmeinX

Ich denke, dass das Zählen von Speicherzugriffen obligatorisch ist, aber wir sollten auch darüber nachdenken:

  • Wie viel lokaler Speicher ist erforderlich

  • Wie viel Parallelität wir haben

Dann können Sie Algorithmen für moderne Hardware analysieren.

Matt Knepley
quelle
3
Ich stimme Matt zu, aber ich möchte darauf hinweisen, dass in der Literatur mittlerweile als "arithmetische Intensität" und "numerische Intensität" definiert ist. Ich denke, das Roofline-Modell von Williams, Waterman und Patterson ist wahrscheinlich ein guter Anfang, um über diese Probleme nachzudenken. Ich denke, dies sollte rechtzeitig auf das Speicher / Flop-Zugriffsverhältnis eines Algorithmus ausgedehnt werden. β
Aron Ahmadia
2
David macht mehr 8 Jahre zuvor.
Matt Knepley
3
Okay, es gibt also ein besseres, komplexeres Modell (wie immer). Aber dieses Modell gibt eine Antwort, die maschinenabhängig ist. Was sollen wir den Schülern als erste Analyse beibringen?
David Ketcheson
3
Der Punkt ist, dass die Maschine auf eine einzige Zahl reduziert wurde, das Verhältnis von Spitzenflops zu Spitzenbandbreite, ebenso wie der Algorithmus. Das ist so einfach wie es nur geht. Ohne ein Rechenmodell ist jede Komplexitätsschätzung nutzlos und dies ist die einfachste realistische.
Matt Knepley
1
Ich denke, Sie verstehen das Problem falsch. Wir haben bereits optische Transportmittel, die große Lasten tragen können. Das Problem ist, das auf einen Chip zu bekommen. Sie haben nur so viele Drähte und eine Top-Taktrate. Optischer Transport würde dieses Problem nur auf einem optischen Chip lindern.
Matt Knepley
22

Ich verstehe nicht, warum man der "Gewinner" sein muss; Dies ist kein Nullsummenspiel, bei dem Flopcounts und Speicherzugriffe die anderen überdecken müssen. Sie können beide unterrichten, und ich denke, sie haben beide ihren Nutzen. Schließlich ist es schwer zu sagen, dass Ihr -Algorithmus mit O ( N ) -Speicherzugriffen notwendigerweise schneller sein wird als Ihr O ( N log N ) -Algorithmus mit O ( N 2 ) -Zugriffen. Es hängt alles von den relativen Kosten der verschiedenen Teile ab (der nervige Vorfaktor, den wir in diesen Analysen immer ignorieren!).O(N4)O(N)O(NLogN)O(N2)

Aus einer breiteren Perspektive denke ich, dass die Analyse der algorithmischen Leistung "allumfassend" sein sollte. Wenn wir den Menschen beibringen, echte HPC-Entwickler und -Anwender zu sein, müssen sie verstehen, welche Kosten die Programmierung in der realen Welt verursacht. Die abstrakten Analysemodelle, die wir haben, berücksichtigen nicht die Zeit des Programmierers. Wir sollten in Bezug auf die "Gesamtzeit bis zur Lösung" denken und nicht nur auf die Anzahl der Flops und die algorithmische Effizienz. Es ist wenig sinnvoll, drei oder vier Programmierertage zu verwenden, um eine Routine neu zu schreiben, die eine Sekunde Computerzeit pro Job spart, es sei denn, Sie planen, einige Millionen Berechnungen auszuführen. Ebenso rechnet sich die Investition von ein paar Tagen, um ein oder zwei Stunden Rechenzeit zu sparen, schnell. Dieser neuartige Algorithmus kann erstaunlich sein,

Aeismail
quelle
7
O(NLogN)O(N2)
2
O(NLogN)O(N2)
9

Wie bereits erwähnt, hängt die Antwort natürlich davon ab, ob es sich bei dem Engpass um die CPU- oder die Speicherbandbreite handelt. Bei vielen Algorithmen, die mit einem Dataset beliebiger Größe arbeiten, ist der Engpass normalerweise die Speicherbandbreite, da das Dataset nicht in den CPU-Cache passt.

Darüber hinaus weist Knuth darauf hin, dass die Speicherzugriffsanalyse den Test der Zeit mit größerer Wahrscheinlichkeit bestehen wird, wahrscheinlich weil sie im Vergleich zu den Komplexitäten moderner CPU-Pipelines und der Verzweigungsvorhersage relativ einfach ist (auch unter Berücksichtigung der Cache-Freundlichkeit).

Knuth verwendet bei der Analyse von BDDs den Begriff Gigamems in Band 4A von TAOCP. Ich bin mir nicht sicher, ob er es in früheren Bänden verwendet. In seinem jährlichen Weihnachtsbaumvortrag im Jahr 2010 machte er die oben erwähnte Bemerkung, dass er den Test der Zeit bestehen sollte.

Interessanterweise tun Sie es falsch. Dies zeigt, dass es nicht immer einfach ist, die Leistung auf der Grundlage von Speicheroperationen zu analysieren, da Elemente wie der VM-Druck ins Spiel kommen, wenn die Daten nicht alle auf einmal in den physischen RAM passen.

Jason Davies
quelle
8

Wie Sie die Kosten eines Algorithmus bestimmen, hängt davon ab, auf welcher "Ebene" des wissenschaftlichen Rechnens Sie arbeiten und welche (enge oder breite) Klasse von Problemen Sie in Betracht ziehen.

Wenn Sie über Cache-Optimierung nachdenken, ist dies eindeutig relevanter für z. B. die Implementierung von numerischen linearen Algebra-Paketen wie BLAS und ähnlichen Bibliotheken. Das gehört also zur Low-Level-Optimierung, und es ist in Ordnung, wenn Sie einen festen Algorithmus für ein bestimmtes Problem und mit ausreichenden Einschränkungen für die Eingabe haben. Zum Beispiel könnte die Cache-Optimierung relevant sein, um eine schnelle Implementierung der konjugierten Gradienteniteration zu erhalten, wenn die Matrix als ausreichend dünn versprochen wird.

Auf der anderen Seite, je breiter die Klasse der Probleme ist, desto weniger können Sie auf dem tatsächlichen Computer vorhersagen (zum Beispiel wissen Sie nicht, wie dünn die Eingabematrizen Ihrer CG-Implementierung wirklich sein werden). Je breiter die Klasse von Computern ist, auf denen Ihr Programm ausgeführt werden soll, desto weniger können Sie die Cache-Architektur vorhersagen.

Darüber hinaus könnte es auf einer höheren Ebene des wissenschaftlichen Rechnens relevanter sein, die Problemstruktur zu ändern. Wenn Sie beispielsweise Zeit damit verbringen, einen guten Vorkonditionierer für ein lineares Gleichungssystem zu finden, übertrifft diese Art der Optimierung normalerweise jede Optimierung auf niedriger Ebene, da die Anzahl der Iterationen drastisch reduziert wird.

Zusammenfassend ist die Cache-Optimierung nur dann sinnvoll, wenn durch Parallelität und Reduzierung der asymptotischen Anzahl von FLOPs nichts mehr zu optimieren ist.

Ich halte es für sinnvoll, die Haltung der theoretischen Informatik anzupassen: Letztendlich bringt die Verbesserung der asymptotischen Komplexität eines Algorithmus mehr als die Mikrooptimierung einiger vorhandener Codezeilen. Daher wird das Zählen von FLOPs immer noch bevorzugt.

shuhalo
quelle
msgstr "Cache - Optimierung ist nur dann sinnvoll, wenn durch Parallelität und Reduzierung der asymptotischen Anzahl von FLOPs nichts mehr zu optimieren ist". Ich stimme dir nicht zu. Wenn Sie einen großen Ausdruck einer großen Anzahl von Zahlen berechnen möchten, ist es besser, jeweils einen Schritt mit allen Zahlen durchzuführen, als alle Schritte für jede Zahl. Beide haben die gleiche Anzahl von FLOPS, aber einer ist besser im Speicherzugriff. Bonus, wenn Sie die Größe der Gruppe auswählen, die in den Cache passt (oder der Compiler übernimmt dies für Sie). Das macht numexpr in Python: github.com/pydata/numexpr
Davidmh
6

Ich habe mich immer geweigert, überhaupt an das Zählen von Flops, Speicherzugriffen oder was auch immer Sie haben zu denken. Das ist ein Konzept aus den 1960er Jahren, als das, was Sie getan haben, ziemlich vorgegeben war und nur, wie Sie es getan haben, der algorithmischen Optimierung überlassen war. Stellen Sie sich vor, Sie lösen ein Finite-Elemente-Problem auf einem einheitlichen xyz-Netz, indem Sie entweder die Gaußsche Eliminierung der Jacobi-Iteration verwenden.

Jetzt können Sie dies zur Hölle optimieren und ein paar Flops sparen, wodurch Sie 10% der Laufzeit gewinnen. Oder Sie können überlegen, ob Sie eine Multigrid-Methode und einen optimalen Blockvorkonditionierer implementieren möchten, um einen Faktor 10 in der Laufzeit zu erzielen. Dies sollten wir unseren Schülern beibringen - überlegen Sie, welche komplexen, äußeren Algorithmen Sie davon überzeugen können, einen besseren inneren Algorithmus zu finden. Ihr Chef (Keyes) hat diese Folien zum Fortschritt bei MHD-Berechnungen, die genau diesen Punkt ziemlich offensichtlich machen.

Wolfgang Bangerth
quelle
Eigentlich habe ich nach der Art von übergeordnetem Denken gefragt, die Sie vorschlagen, und nicht nach Optimierung auf untergeordneter Ebene. Mit welcher Metrik sollten Sie bestimmen, ob Multigrid und Ihr Vorkonditionierer schneller sind als die Alternativen?
David Ketcheson
Ich würde nicht wissen, wie man FLOPS oder andere Anweisungen für komplexe Algorithmen zählt, die über Zehntausende oder Tausende von Codezeilen laufen. Überlegen Sie beispielsweise, wie komplex die Analyse- und Konstruktionsphase von AMG-Algorithmen ist. Es gibt so viele Teile dieser Algorithmen, und alle hängen von den tatsächlichen Daten ab, dass Sie die Anzahl der Vorgänge nicht vorhersagen können.
Wolfgang Bangerth
1
Ich glaube, ich habe zuerst falsch verstanden, worauf du hinauswollst, aber ich bin immer noch nicht einverstanden mit deinem Standpunkt. "Äußere Algorithmen" können (und ich würde argumentieren, sollten) immer noch mit Blick auf asymptotische Komplexität entworfen werden. Sicherlich würden Sie nicht behaupten, dass ein Abfall von einem quadratischen Algorithmus zu einem nahezu linearen Algorithmus bestenfalls zu einer Reduzierung der Laufzeit um 10% führen würde. Doch wie kann man die asymptotische Komplexität anders quantifizieren als durch Flops und / oder Memory-Ops?
Jack Poulson
7
Ich denke, diese Herangehensweise an Algorithmen ist Mist. Sie müssen die Analyse vereinfachen, indem Sie nur die Kosten erster Ordnung betrachten und das Modell so vereinfachen, dass es nachvollziehbar ist, aber zu sagen, dass Sie so etwas wie MG oder Cholesky nicht analysieren können, weil es zu kompliziert ist, ist völlig falsch.
Matt Knepley
1
Nun, aber was bedeutet es, MG oder Cholesky zu analysieren, wenn jeder FLOP, den Sie zählen, hinter mehreren Latenzschichten verborgen ist, die durch Hyperthread-Prozessoren, Caches, langsamen RAM, Multiscalar-Prozessoren und automatische Vektorisierung verursacht werden? Der Punkt, den ich anspreche, ist, dass Sie innerhalb eines Faktors von 5-10 die Laufzeit Ihrer Algorithmen nicht mehr vorhersagen können, ohne sie zeitlich festzulegen. Das war in den 50ern und 60ern völlig anders, als die Leute mit dieser FLOP-Zählung begannen.
Wolfgang Bangerth
1

Ja, obsolet Eine algorithmische Analyse durch Flops oder eine andere Methode ist unter Berücksichtigung der Größe des vorliegenden Problems nur so nützlich wie das abstrakte Modell der Maschine. Die tatsächliche Leistung hängt sowohl von der Implementierung als auch von der Hardware ab, und die Anwendbarkeit eines abstrakten Modells für letztere auf die Realität nimmt mit der Zeit ab. Wenn Sie beispielsweise die Implementierung eines komplexen Algorithmus, wie der Molekulardynamik, weiter parallelisieren, werden verschiedene Aspekte auf unterschiedlicher Hardware ratenbegrenzend, und die algorithmische Analyse hat nichts mit den Beobachtungen zu tun. In gewisser Hinsicht ist es nur wichtig, die Leistung der Implementierung (en) des Algorithmus (der Algorithmen) auf dem fraglichen Hardwaretyp (den fraglichen Hardwaretypen) zu messen.

Sind solche Abstraktionen als Lernwerkzeug nützlich? Ja, wie viele Modelle, die für den Unterricht verwendet werden, sind sie nützlich, solange sie mit dem Verständnis der Einschränkungen des Modells einhergehen. Klassische Mechanik ist in Ordnung, solange Sie zu schätzen wissen, dass sie bei kleinen Entfernungen oder großen Geschwindigkeiten nicht funktioniert ...

Abraham
quelle
-1

Beantworten Sie Ihre Frage nicht wirklich, sondern fügen Sie eine weitere zu berücksichtigende Variable hinzu: Berücksichtigen Sie die Merkmale der Programmiersprache. Zum Beispiel verwendet Python sortden Timsort- Algorithmus, der (neben anderen nützlichen Eigenschaften) entwickelt wurde, um die Anzahl der Vergleiche zu minimieren, die für Python-Objekte möglicherweise langsam sein können. Auf der anderen Seite ist das Vergleichen von zwei Floats in C ++ blitzschnell, aber das Austauschen ist teurer, sodass sie andere Algorithmen verwenden.

Andere Beispiele sind die dynamische Speicherzuweisung (trivial in einer Python-Liste, sowohl in Laufzeit- als auch in Entwicklerzeit .append()) im Vergleich zu FORTRAN oder C, wo, obwohl dies möglich und bei richtiger Implementierung schneller ist, erheblich mehr Programmierzeit und -aufwand erforderlich sind. Siehe Python ist schneller als FORTRAN.

Davidmh
quelle
Dies ist wahr, aber, wie Sie sagen, beantwortet die Frage nicht. Es geht um ein anderes Thema.
David Ketcheson
Nun, bei einer angemessenen Analyse ist dies zu berücksichtigen, wenn entschieden wird, welcher Algorithmus implementiert werden soll.
Davidmh