Wie berechne ich den parallelen Overhead eines parallelen Codes, der auf einem einzelnen Prozessor ausgeführt wird, wenn kein sequentieller Code verfügbar ist?

Ich stelle die Leistung der linearen Löser von PETSc vor. So wie ich es verstehe,

speedup = \frac{Sequential Time}{Parallel Time} .

$\text{speedup}=\frac{\text{Sequential Time}}{\text{Parallel Time}}.$

Ich weiß, dass das Ausführen des parallelen Codes auf einem Prozessor als Proxy für die sequentielle Leistung verwendet werden kann. Ich denke jedoch nicht, dass dies aufgrund des parallelen Overheads ein gutes Maß für einen äquivalenten sequentiellen Code ist. Häufig ist die Leistung eines sequentiellen Codes schneller als die parallele Leistung eines einzelnen Prozessors. Ich nehme an, ich könnte nach numerischen Bibliotheken suchen, die denselben Löser implementieren, aber es gibt keine Garantie dafür, dass der Algorithmus wirklich gleichwertig ist.

So wie ich es verstehe,

$\text{Parallel performance on one processor} = \text{Sequential Time} + \text{Parallel Overhead}$

Wenn es also eine Möglichkeit gibt, den parallelen Overhead zu quantifizieren, können wir ihn von der parallelen Zeit auf einem Prozessor subtrahieren, um ein besseres Maß für die sequentielle Zeit zu erhalten.

Meine Fragen wären dann also:

Gibt es eine Möglichkeit, den parallelen Overhead eines parallelen Codes zu berechnen, der auf einem einzelnen Prozessor ausgeführt wird, wenn kein sequentieller Code verfügbar ist?
Ist es wirklich notwendig? Ist die parallele Leistung auf einem Prozessor gut genug, um die sequentielle Leistung im Allgemeinen anzunähern?

performance petsc parallel-computing Paul
quelle

Die Beschleunigung ist ein relatives Maß und sagt nicht viel über die absolute Leistung aus. Die Beschleunigung kann entweder an einer reinen sequentiellen Implementierung gemessen werden, die dieselbe nützliche Arbeit leistet, oder an einer parallelen Implementierung (mit dem von Ihnen angegebenen Overhead). In jedem Fall kann die Beschleunigung aufgrund des parallelen Overheads und / oder möglicher unterschiedlicher Ausführungspfade im Befehlssatz der Anwendung sehr unterschiedlich sein. Warum möchten Sie den parallelen Overhead schätzen?

Allan P. Engsig-Karup

@ AllanP.Engsig-Karup: Ich denke, meine Hauptmotivation ist es, zu wissen, wie man eine vernünftige Schätzung des sequentiellen Codes erhält, wenn ich nur parallelen Code habe.

Paul

@Paul: Ich werde später versuchen, eine tatsächliche Antwort zu geben, aber es werden oft Kompromisse geschlossen, um einen skalierbaren Algorithmus zu erhalten. Die Beschleunigung sollte wirklich im Verhältnis zur besten seriellen Implementierung gemessen werden, die bei gleichem Eingang denselben Ausgang erzeugt (modulo kleine Störungen).

Jack Poulson

@ Jack: Stimme zu. Meiner Meinung nach sind relative Beschleunigungen nur dann sehr nützlich, wenn auch absolute Zeitangaben gemacht werden.

Allan P. Engsig-Karup

@ Jack: Ich bin anderer Meinung. Die beste serielle Implementierung gehört möglicherweise nicht Ihnen. Die Geschwindigkeit eines Codes sollte wahrscheinlich an seiner eigenen seriellen Leistung gemessen werden. Dann sollte Ihre Implementierung sowohl relativ als auch absolut an anderen Implementierungen gemessen werden. Die Verwendung einer nicht verwandten seriellen Implementierung im Zähler ist wahrscheinlich irreführend.

Bill Barth

Antworten:

Ich denke, solange Sie sagen, woran Sie die Beschleunigung messen, wird Ihnen niemand etwas vorwerfen, wenn Sie die Zeit nutzen, die die parallele Version des Codes benötigt, um auf einem Prozessor ausgeführt zu werden. Wenn Sie auch die Gesamtzeit für einen Ihrer Fälle angeben (z. B. die Uni-Prozessor-Zeit), können die Benutzer Ihre Implementierung mit anderen in der Literatur oder mit ihren eigenen vergleichen.

Bei einigen Problemen kann angesichts der Speicher- oder Zeitbeschränkungen nicht einmal ein Uniprozessor-Ergebnis berechnet werden. Angesichts dessen verstehen die meisten Leute, wenn sie sich die Ergebnisse der Beschleunigung ansehen, dass die Dinge relativ zur kleinsten Anzahl verfügbarer Prozessoren berechnet werden und dass das Uniprozessor-Datum der parallele Code ist, der auf einem Prozessor ausgeführt wird.

Es gibt keine festen Regeln, aber Sie sollten genau angeben, was Sie tun, und Ihrem Leser genügend Informationen geben, um andere Größen zu berechnen, die ihn interessieren könnten.

Bill Barth
quelle

Ich bin nicht mit PETSc-Interna vertraut (im Gegensatz zu anderen PETSc-Experten hier), aber imho sollte es keinen parallelen Overhead mit PETSc geben, solange Sie Ihren Job als einen einzelnen Prozess ausführen (dh keine Partitionierung usw.).

Denken Sie daran, dass PETSc auch ohne MPI installiert werden kann, was bedeutet, dass der geringe MPI-Overhead, der möglicherweise vorhanden ist (vorausgesetzt, es werden tatsächlich MPI-Anrufe getätigt, wenn auf einem Kern ausgeführt wird, was ich sehr bezweifle), ebenfalls abgezinst werden kann.

Dies trifft offensichtlich zu, wenn paralleler Overhead hauptsächlich Kommunikation und nicht algorithmisch ist.

stali
quelle

Das mag für Petsc zutreffen, aber es gilt wahrscheinlich nicht für Parallelcode im Allgemeinen.

Paul