Können MPI-Nachrichten priorisiert werden?

8

Soweit ich weiß, stimmt die Reihenfolge, in der nicht blockierende Punkt-zu-Punkt-MPI-Nachrichten (Isend und Irecv) empfangen werden, mit der Reihenfolge überein, in der sie gesendet werden. Gibt es Techniken, um bestimmten Nachrichten Vorrang vor anderen zu geben?

Zum Beispiel haben wir einen mehrstufigen Algorithmus, bei dem die hochauflösenden Lösungen mit nicht blockierenden Aufrufen gesendet werden und Berechnungen auf den groben Ebenen durchgeführt werden, während die feinen Nachrichten gesendet werden. Wenn es jedoch an der Zeit ist, Lösungen mit niedriger Auflösung zu senden, möchten wir, dass diese Vorrang haben (sie blockieren im Wesentlichen).

Ich kann mir auch vorstellen, dass dies für andere Algorithmen nützlich sein könnte, wenn wir zur Exascale übergehen: Einige Nachrichten befinden sich auf dem "kritischen Pfad", andere nicht.

Matthew Emmett
quelle

Antworten:

12

Ich denke die Antwort darauf ist nein. Sobald Sie sie in den MPI-Stapel verschoben haben, sind sie nicht mehr unter Ihrer Kontrolle, und die MPI-Semantik bestimmt, wie die Nachrichten gesendet werden.

Sie können Nachrichten sicherlich priorisieren, indem Sie sie vor dem Senden in Ihren Code einreihen und dann häufig überprüfen, welche Nachrichten am wichtigsten sind. Aber ich bin überhaupt nicht davon überzeugt, dass Sie einen Nutzen daraus ziehen werden. Gibt es Hinweise darauf, dass Ihre feinen Nachrichten nicht vollständig sind, wenn Sie bereit sind, die groben zu senden? Wenn dies nicht der Fall ist, möchten Sie möglicherweise zunächst untersuchen, ob dies überhaupt erforderlich ist.

Bill Barth
quelle
Derzeit werden die feinen Nachrichten gesendet, bevor wir die groben Nachrichten senden müssen. Im Moment sind wir also in Ordnung. Die Überlappung der Kommunikation ist etwas besorgniserregend - vielleicht haben wir ein Problem, wenn Flops wirklich frei werden. Auf jeden Fall könnte es einfacher sein, unseren Algorithmus ein wenig anzupassen, anstatt ein Prioritätswarteschlangensystem über MPI zu implementieren. Wir werden sehen!
Matthew Emmett
Ich versuche herauszufinden, wie es Ihrem Algorithmus egal ist, wann die feinen Nachrichten auftauchen, aber es ist schwierig, wann die groben Nachrichten auftauchen. Warum nicht einfach die feinen Nachrichten für immer verzögern (und sie nicht senden)? Vermutlich am Ende jeder Anwendung / Iteration müssen alle Nachrichten erforderlich sein? Was befürchten Sie, wenn sich die Nachrichten überschneiden?
Bill Barth
Wir arbeiten an einem mehrstufigen zeitparallelen Algorithmus, bei dem die Grobebenen serielle Abhängigkeiten aufweisen: Die Grobberechnung bei Iteration k auf Prozessor p hängt von der Grobberechnung bei Iteration k auf Prozessor p-1 ab. Die Feinstufen sind unterschiedlich: Die Iteration k auf dem Prozessor p hängt von der Iteration k-1 auf dem Prozessor p-1 ab. Wenn die groben Nachrichten verlangsamt werden, nimmt die Effizienz des Algorithmus ab, aber eine Überlappung ist nicht katastrophal.
Matthew Emmett
7

Derzeit enthält MPI keine Bestimmungen zur Priorisierung von Nachrichten und auch nicht den kommenden MPI 3.0-Standard. Es liegt an der MPI-Implementierung, zu entscheiden, wie die Nachrichten übertragen werden sollen. ZB kleinere Nachrichten können aufgrund bestimmter Bypässe in der Kommunikationstechnik (hoch Implementierung und systemabhängig) gesendet schneller. Sie könnten der Lage sein , die Tatsache auszunutzen , dass die meisten MPI - Implementierungen große Nachrichten in Stücke und kleinere Nachrichten brechen könnte zwischen den Stücken der Großen schlüpfen können. Aber auch dies ist stark von der Implementierung abhängig und ich würde mich nicht darauf verlassen.

Ich habe ein einfaches Experiment mit Open MPI 1.5.3 über eine InfiniBand-Verbindung durchgeführt. Das Programm sendet eine sehr große Nachricht (1 GiB) mit MPI_Isendund dann zwei kurze Nachrichten (16 Byte) mit MPI_Sendund wartet danach, bis der große Sendevorgang abgeschlossen ist MPI_Wait. Auf der anderen Seite MPI_Irecvwird zuerst ein für den großen Empfang und dann zwei nachfolgende MPI_RecvOperationen gebucht , gefolgt von MPI_Waitdem großen Empfang. Ich konnte die beiden Kurznachrichten durchgehend empfangen, bevor der Empfang der großen Nachricht abgeschlossen war. Hier ist die Ausgabe meines Tests:

[0] Rank 0 running on host1
[0] Starting big send at 0.000019s
[0] Starting small send at 0.215448s
[0] Starting small send 2 at 0.224105s
[0] Starting wait at 0.224114s
[0] Finished wait at 0.935843s
[1] Rank 1 running on host2
[1] Starting big receive at 0.000020s
[1] Starting small recv at 0.000037s
[1] Starting small recv 2 at 0.548396s
[1] Starting wait at 0.548418s
[1] Finished wait at 0.935780s

Beide kleinen Sends sind erfolgreich, bevor der asynchrone Sendevorgang abgeschlossen ist, wie aus der Wartezeit von ~ 700 ms hervorgeht. Ich würde sagen, dass der erste kleine Empfang einige Zeit (~ 300 ms) erfolgreich ist, nachdem der große Empfang im Hintergrund gestartet wurde. Ich habe dies nur mit MPI_COMM_WORLDoder mit einem separaten Kommunikator für die kleinen Nachrichten versucht - die Ergebnisse sind die gleichen. Knoten haben einen QDR IB HCA mit jedem in Betrieb --mca btl_base_verbose 50bestätigt , dass keine alternativen Kommunikationskanäle in Gebrauch sind.

Hristo Iliev
quelle
5

Dies wird weder von MPI noch von anderen mir bekannten Kommunikations-Middleware unterstützt. Dies liegt wahrscheinlich daran, dass es von keiner mir bekannten Hardware unterstützt wird, mit Ausnahme von Blue Gene, wo es Pakete mit hoher Priorität für Kontrollnachrichten gibt, die unter bestimmten Bedingungen andere Nachrichten überholen. Diese sind jedoch nicht für den allgemeinen Gebrauch bestimmt, da sie nur die Kommunikation von 64 Bytes ermöglichen (zumindest bei Blue Gene / P).

Die gute Nachricht ist, dass Sie das nicht brauchen. Der Aufwand für die Implementierung wird sich nicht lohnen, und Sie werden feststellen - vorausgesetzt, Sie untersuchen jemals die Details auf niedriger Ebene -, dass die Nichtimplementierung von Prioritäten im Netzwerk es MPI ermöglicht, bei den meisten Anwendungen die beste Leistung zu erzielen.

Jeff
quelle
Ich bin mir nicht sicher, ob ich den letzten Absatz verstehe. Meinen Sie damit, dass MPI durch Fairness im Netzwerk alle Nachrichten früher übermitteln kann, als wenn einige eine höhere Priorität als andere hätten? Dies scheint nicht intuitiv zu sein, aber zugegebenermaßen kenne ich die Details von MPI und modernen Interconnects auf niedriger Ebene nicht - ich kann dies nur auf mein Wissen über IP-Netzwerke und Dinge wie Paketfilter und Prioritätswarteschlangen beziehen. Trotzdem danke für die Antwort!
Matthew Emmett
@MatthewEmmett Siehe Prioritätsinversion . MPI kennt die Nachrichtenabhängigkeiten der Anwendung nicht. Wenn Sie also eine höhere Priorität in einer Nachricht festlegen, kann dies dazu führen, dass die Abhängigkeiten der Anwendung beeinträchtigt werden, wodurch sie länger dauert. Es ist schwierig, die Prioritätsinversion zu verringern.
Jed Brown
2

Es ist etwas seltsam, dass Sie dies im Zusammenhang mit der Reihenfolge der Nachrichten erwähnen. Zitiere dich:

Soweit ich weiß, stimmt die Reihenfolge, in der nicht blockierende Punkt-zu-Punkt-MPI-Nachrichten (Isend und Irecv) empfangen werden, mit der Reihenfolge überein, in der sie gesendet werden.

An dieser Stelle sei darauf hingewiesen, dass MPI nur garantiert, dass übereinstimmende Nachrichten zwischen Prozessen in der Reihenfolge empfangen werden, in der sie gesendet wurden. Sie möchten wirklich nicht, dass sich diese Art der Bestellung ändert, da dies Ihren Code verständlicher macht und Sie als Anwendungsprogrammierer erheblich entlastet.

Wenn Sie jedoch Nachrichten mit unterschiedlichen Tags gesendet haben, werden die Übereinstimmungskriterien geändert, und Sie können problemlos die zweite vor der ersten empfangen. Einzelheiten finden Sie im zweiten Beispiel im entsprechenden Teil des Standards . Ich hoffe , wenn Sie zwei Teile Ihres Codes gleichzeitig senden, trennen Sie die groben und feinen Nachrichten bereits mithilfe von Tags und versuchen nicht, zusätzlich zur Reihenfolge der Nachrichten ein eigenes Protokoll zu implementieren. Für die meisten mir bekannten MPI-Programmierer ist dies eine Selbstverständlichkeit.

Unter der Annahme, dass Sie dies tun, befürchten Sie wahrscheinlich, dass feinkörnige Nachrichten mit hohem Volumen Ihr Netzwerk verstopfen, wenn Sie grobe Nachrichten senden möchten. Mein allgemeiner Rat dazu lautet: Wenn es sich nicht um ein Leistungsproblem handelt, das Sie derzeit tatsächlich messen können, sollten Sie sich noch nicht darum kümmern, es zu beheben. Sie scheinen in einem der obigen Kommentare zu bestätigen, dass es sich noch nicht um ein Problem handelt.

Eine mögliche Lösung, die Sie in Betracht ziehen könnten , wäre die Verwendung eines nicht blockierenden Kollektivs (NBC) wie Bcast oder Barrier, um alle zu benachrichtigen, dass die Grobphase abgeschlossen ist und bereit ist, die Lösung zu senden. Höchstwahrscheinlich wird der ABC-Verkehr nicht priorisiert, aber benachrichtigte Prozesse können zumindest das Senden feiner Lösungen stoppen, bis die groben Sendungen abgeschlossen sind. NBCs werden in MPI-3 sein oder Sie könnten versuchen, libNBC zu verwenden, wenn Sie nicht so lange warten können.

Auch dies scheint jedoch eine Menge Arbeit für etwas zu sein, das noch nicht nach einem Leistungsproblem klingt.

Todd Gamblin
quelle
Ja, ich sende die groben Nachrichten mit anderen Tags als die feinen Nachrichten. Ich war besorgt (wie Sie vermutet haben), dass die hochvolumigen Nachrichten das Netzwerk verstopfen könnten, aber wir haben dies noch nicht gesehen - es ist nur etwas, worüber ich mich gewundert habe. Vielen Dank für Ihren Vorschlag zu NBCs.
Matthew Emmett