Log-Log-Diagramme für parallele Skalierung / Effizienz

17

In meiner eigenen Arbeit beschäftige ich mich hauptsächlich mit der Verbesserung der Skalierbarkeit von Algorithmen. Eine der bevorzugten Methoden zur Darstellung von paralleler Skalierung und / oder paralleler Effizienz besteht darin, die Leistung eines Algorithmus / Codes über die Anzahl der Kerne zu zeichnen, z

künstliche parallele Skalierungskurve

Dabei repräsentiert die Achse die Anzahl der Kerne und die y- Achse eine Metrik, z. B. die pro Zeiteinheit geleistete Arbeit. Die verschiedenen Kurven zeigen parallele Wirkungsgrade von 20%, 40%, 60%, 80% und 100% bei 64 Kernen.xy

Leider werden diese Ergebnisse in vielen Veröffentlichungen mit einer Log-Log- Skalierung aufgezeichnet , z. B. die Ergebnisse in diesem oder diesem Artikel. Das Problem bei diesen Log-Log-Diagrammen ist, dass es unglaublich schwierig ist, die tatsächliche parallele Skalierung / Effizienz zu bewerten, z

Bildbeschreibung hier eingeben

Welches ist das gleiche Diagramm wie oben, aber mit Log-Log-Skalierung. Beachten Sie, dass es jetzt keinen großen Unterschied zwischen den Ergebnissen für 60%, 80% oder 100% parallele Effizienz gibt. Ich habe ein bisschen mehr ausführlich darüber geschrieben hier .

Hier ist meine Frage: Welche Gründe gibt es für die Anzeige von Ergebnissen bei der Protokoll-Protokoll-Skalierung? Ich verwende regelmäßig die lineare Skalierung, um meine eigenen Ergebnisse anzuzeigen, und werde regelmäßig von Schiedsrichtern darauf aufmerksam gemacht, dass meine eigenen parallelen Skalierungs- / Effizienzergebnisse nicht so gut aussehen wie die (logarithmischen) Ergebnisse anderer, aber für das Leben von mir Ich kann nicht verstehen, warum ich den Plotstil wechseln soll.

Pedro
quelle

Antworten:

16

Derzeit schreiben wir eine Arbeit, die eine Reihe vergleichbarer Handlungen enthält, und wir hatten mehr oder weniger das gleiche Problem. In diesem Artikel wird die Skalierung verschiedener Algorithmen über die Anzahl der Kerne verglichen, die auf einem BlueGene zwischen 1 und 100.000 liegen. Der Grund für die Verwendung von Loglog-Plots in dieser Situation ist die Anzahl der beteiligten Größenordnungen. Es gibt keine Möglichkeit, 6 Größenordnungen auf einer linearen Skala zu zeichnen.

Und tatsächlich sind die Algorithmen beim Zeichnen der Zeit über die Anzahl der Kerne im Protokoll nicht sehr unterscheidbar, wie Sie im folgenden Diagramm sehen können. Timings einer Reihe von Algorithmen im Log-Maßstab.  Die verschiedenen Algorithmen sind schwer zu unterscheiden.

Ep=T1/(pTp)T1TpppEpp

Ep=Tref/(pTp)Tref

Das Auftragen der relativen parallelen Effizienz auf einer Semilog-Skala zeigt ziemlich deutlich die Skalierung eines Algorithmus und zeigt auch, wie die Algorithmen relativ zueinander arbeiten. Relative parallele Effizienz mehrerer Algorithmen über die Anzahl der Kerne.

Olenz
quelle
2
x
Beachten Sie, dass die Diagramme nicht annähernd so beeindruckend aussehen wie andere Skalierungsdiagramme, da sie auf der Protokollskala ziemlich schnell abfallen. Theoretisch können Sie die Effizienz auch in einem Protokolldiagramm darstellen, um weitere Details am rechten Rand zu sehen. Beachten Sie jedoch, dass dies bedeutet, dass Sie sehr niedrige Wirkungsgrade im Detail betrachten, was wahrscheinlich nicht von großem Interesse ist.
Olenz
14

Georg Hager schrieb darüber in Fooling the Masses - Stunt 3: Die Log-Skala ist dein Freund .

Log-Log-Diagramme mit starker Skalierung sind zwar im oberen Bereich nicht sehr anspruchsvoll, ermöglichen jedoch die Darstellung der Skalierung über viele weitere Größenordnungen. Um zu sehen, warum dies nützlich ist, betrachten Sie ein 3D-Problem mit regelmäßiger Verfeinerung. Auf einer linearen Skala können Sie die Leistung in etwa zwei Größenordnungen darstellen, z. B. 1024 Kerne, 8192 Kerne und 65536 Kerne. Es ist für den Leser unmöglich, anhand des Diagramms zu erkennen, ob Sie etwas Kleineres erstellt haben, und realistisch gesehen vergleicht das Diagramm meist nur die beiden größten Durchläufe.

Angenommen, wir können 1 Million Gitterzellen pro Kern in den Speicher einpassen, bedeutet dies, dass wir nach zweimaliger Skalierung um den Faktor 8 immer noch 16.000 Zellen pro Kern haben können. Das ist immer noch eine beträchtliche Subdomänengröße, und wir können erwarten, dass dort viele Algorithmen effizient ausgeführt werden. Wir haben das visuelle Spektrum des Diagramms (1024 bis 65536 Kerne) abgedeckt, sind aber noch nicht einmal in das Regime eingetreten, in dem eine starke Skalierung schwierig wird.

Nehmen wir stattdessen an, dass wir mit 16 Kernen begonnen haben, ebenfalls mit 1 Million Gitterzellen pro Kern. Wenn wir jetzt auf 65536 Kerne skalieren, werden wir nur 244 Zellen pro Kern haben, was viel anspruchsvoller sein wird. Eine logarithmische Achse ist die einzige Möglichkeit, das Spektrum von 16 Kernen bis 65536 Kernen eindeutig darzustellen. Natürlich können Sie auch weiterhin eine lineare Achse verwenden und eine Beschriftung mit der Aufschrift "Die Datenpunkte für 16, 128 und 1024 Kerne überlappen sich in der Abbildung" verwenden. Jetzt verwenden Sie jedoch Wörter anstelle der Abbildung.

Eine Protokoll-Protokoll-Skala ermöglicht es Ihrer Skalierung auch, Maschinenattribute wie das Überschreiten eines einzelnen Knotens oder Racks "wiederherzustellen". Es liegt an Ihnen, ob dies wünschenswert ist oder nicht.

Jed Brown
quelle
xy
1
Es ist viel schwieriger, ein einzelnes Problem um den Faktor 4096 zu skalieren, als zwei verschiedene Problemgrößen um den Faktor 64 zu skalieren . In dem Beispiel, das ich gegeben habe, ist es einfach, die zwei unabhängigen Fälle besser als 95% Wirkungsgrad zu machen, aber den einzelnen kombinierten Fall weniger als 30% Wirkungsgrad zu haben. In Wissenschaft und Industrie gibt es keinen vorbestimmten Grund für die gewünschte Durchlaufzeit, in den engen Größenbereich zu fallen, in dem der Algorithmus "komfortabel" ist.
Jed Brown
Ich stimme voll und ganz zu, dass die Skalierung von eins auf Tausende die große Herausforderung ist! Der Grund, warum ich unterschiedliche Größen als unterschiedliche Probleme betrachte, ist, dass dies für den Endbenutzer unterschiedliche Bedeutungen hat. In der Medizin haben die meisten Biologen kein BlueGene im Keller, aber einige Multi-Core-Workstations oder sogar eine zeitlanges Stipendium für einen mittelgroßen Cluster (kleine Anzahl von Knoten) und Leute, die sich große ansehen CFD-Probleme interessieren jedoch nicht viel für den Einzelknotenfall, da das Problem nicht in den Speicher passt. Es geht nicht um den Komfort des Algorithmus, sondern um das Setup des Benutzers.
Pedro
2

Ich stimme mit allem überein, was Jed in seiner Antwort zu sagen hatte, aber ich wollte Folgendes hinzufügen. Ich bin ein Fan davon geworden, wie Martin Berzins und seine Kollegen Skalierung für ihr Uintah-Framework zeigen. Sie zeichnen eine schwache und starke Skalierung des Codes auf Log-Log-Achsen auf (unter Verwendung der Laufzeit pro Schritt der Methode). Ich denke, es zeigt, wie gut der Code skaliert (obwohl die Abweichung von der perfekten Skalierung ein wenig schwer zu bestimmen ist). Siehe Seite 7 und 8, Abbildungen 7 und 8 dieses * Papiers. Sie geben auch eine Tabelle mit den Nummern an, die den einzelnen Skalierungsfiguren entsprechen.

Ein Vorteil davon ist, dass, sobald Sie die Zahlen angegeben haben, ein Rezensent nicht viel sagen kann (oder zumindest nicht viel, was Sie nicht widerlegen können).

* J. Luitjens, M. Berzins. "Verbessern der Leistung von Uintah: Ein umfangreiches adaptives Meshing-Computer-Framework", In Proceedings des 24. IEEE International Parallel and Distributed Processing Symposium (IPDPS10), Atlanta, GA, S. 1-10. 2010. DOI: 10.1109 / IPDPS.2010.5470437

Bill Barth
quelle
Könnten Sie das Bild vielleicht direkt in Ihre Antwort einbetten?
Aron Ahmadia
Während ich ihre Figur wohl fairerweise ausleihen würde, würde ich den Traffic lieber auf die Website der Autoren lenken. Vielleicht erstelle ich ein paar Zahlen und meine eigene Grafik und komme später mit einer Zahl zurück.
Bill Barth
Aus dieser Perspektive können Sie das Bild so umbrechen, dass es auf die Website des Autors verweist, und die Textmenge im Link erhöhen. Wenn Sie mehr darüber diskutieren möchten, kann ich einen Meta- / Chat-Thread eröffnen.
Aron Ahmadia
@BillBarth Ihr Link leitet Sie jetzt auf ihre Homepage weiter. Könnten Sie das Problem beheben oder das gewünschte Bild einbetten?
Jed Brown
1
@JedBrown Link bearbeitet. Vollständige Referenz hinzugefügt. DOI fügte hinzu.
Bill Barth