Wie vergleichen sich die Berechnungskosten einer mpi_allgather-Operation mit einer Gather / Scatter-Operation?

11

Ich arbeite an einem Problem, das mithilfe einer einzelnen mpi_allgather-Operation oder einer mpi_scatter- und einer mpi_gather-Operation parallelisiert werden kann. Diese Operationen werden innerhalb einer while-Schleife aufgerufen, sodass sie häufig aufgerufen werden können.

In der Implementierung mit einem MPI_allgather-Schema sammle ich einen verteilten Vektor auf alle Prozesse zur Lösung doppelter Matrix. In der anderen Implementierung sammle ich den verteilten Vektor auf einem einzelnen Prozessor (dem Wurzelknoten), löse das lineare System auf diesem Prozessor und streue den Lösungsvektor zurück auf alle Prozesse.

Ich bin gespannt, ob die Kosten für eine Sammeloperation erheblich höher sind als die Kosten für Streu- und Sammeloperationen zusammen. Spielt die Länge der Nachricht eine wichtige Rolle für ihre Komplexität? Unterscheidet es sich zwischen den Implementierungen von mpi?

Bearbeiten:

Paul
quelle
Bitte beschreiben Sie die Struktur der Kommunikation und die damit verbundenen Größen. Ein MPI_Scattergefolgt von MPI_Gatherliefert nicht die gleiche Kommunikationssemantik wie MPI_Allgather. Möglicherweise liegt eine Redundanz vor, wenn Sie die Operation in irgendeiner Weise ausdrücken?
Jed Brown
Paul, Jed hat recht, meintest du ein MPI_Gathergefolgt von einem MPI_Bcast?
Aron Ahmadia
@JedBrown: Ich habe ein bisschen mehr Informationen hinzugefügt.
Paul
@AronAhmadia: Ich denke nicht, dass ich einen MPI_Bcast verwenden sollte, da ich einen Teil des Vektors an jeden Prozess sende, nicht an den gesamten Vektor. Mein Grundgedanke ist, dass eine kürzere Nachricht im Allgemeinen schneller zu senden ist als eine größere Nachricht. Macht das Sinn?
Paul
Ist die Matrix bereits redundant verteilt? Ist es schon berücksichtigt? Teilen sich mehrere Prozesse den gleichen Cache und Speicherbus? (Dies würde sich auf die Geschwindigkeit der Lösung redundanter Systeme auswirken.) Wie groß / teuer sind die Systeme? Warum seriell lösen?
Jed Brown

Antworten:

9

Erstens hängt die genaue Antwort ab von: (1) Verwendung, dh Funktionseingabeargumenten, (2) Qualität und Details der MPI-Implementierung und (3) der von Ihnen verwendeten Hardware. Oft hängen (2) und (3) zusammen, z. B. wenn der Hardwareanbieter MPI für sein Netzwerk optimiert.

Im Allgemeinen ist das Zusammenführen von MPI-Kollektiven für kleinere Nachrichten besser, da die Startkosten nicht trivial sein können und die durch das Blockieren von Kollektiven verursachte Synchronisation minimiert werden sollte, wenn die Rechenzeit zwischen den Aufrufen variiert. Bei größeren Nachrichten sollte das Ziel darin bestehen, die Menge der gesendeten Daten zu minimieren.

Zum Beispiel sollte theoretisch MPI_Reduce_scatter_blockbesser sein als MPI_Reducegefolgt MPI_Scatter, obwohl das erstere oft in Bezug auf das letztere implementiert wird, so dass es keinen wirklichen Vorteil gibt. Bei den meisten MPI-Implementierungen besteht eine Korrelation zwischen Implementierungsqualität und Nutzungshäufigkeit, und Anbieter optimieren offensichtlich die Funktionen, für die dies im Maschinenvertrag erforderlich ist.

Auf der anderen Seite, wenn man sich auf einem Blue Gene befindet, ist das MPI_Reduce_scatter_blockVerwenden MPI_Allreduce, das mehr Kommunikation als MPI_Reduceund MPI_Scatterkombiniert macht, tatsächlich ziemlich viel schneller. Dies ist etwas, das ich kürzlich entdeckt habe und das einen interessanten Verstoß gegen das Prinzip der Leistungsselbstkonsistenz in MPI darstellt (dieses Prinzip wird ausführlicher in den "Selbstkonsistenten MPI-Leistungsrichtlinien" beschrieben ).

Beachten Sie im speziellen Fall von Scatter + Gather versus Allgather, dass im ersten Fall alle Daten zu und von einem einzigen Prozess gehen müssen, was es zum Engpass macht, während im Allgather Daten sofort in alle Ränge hinein- und aus ihnen herausfließen können , weil alle Ränge einige Daten haben, die an alle anderen Ränge gesendet werden können. In einigen Netzwerken ist es jedoch nicht unbedingt eine gute Idee, Daten von allen Knoten gleichzeitig zu senden.

Der beste Weg, um diese Frage zu beantworten, besteht darin, die folgenden Schritte in Ihrem Code auszuführen und die Frage experimentell zu beantworten.

#ifdef TWO_MPI_CALLS_ARE_BETTER_THAN_ONE
  MPI_Scatter(..)
  MPI_Gather(..)
#else
  MPI_Allgather(..)
#endif

Eine noch bessere Option besteht darin, Ihren Code während der ersten beiden Iterationen experimentell messen zu lassen und dann für die verbleibenden Iterationen diejenige zu verwenden, die schneller ist:

const int use_allgather = 1;
const int use_scatter_then_gather = 2;

int algorithm = 0;
double t0 = 0.0, t1 = 0.0, dt1 = 0.0, dt2 = 0.0;

while (..)
{
    if ( (iteration==0 && algorithm==0) || algorithm==use_scatter_then_gather )
    {
        t0 = MPI_Wtime();
        MPI_Scatter(..);
        MPI_Gather(..);
        t1 = MPI_Wtime();
        dt1 = t1-t0;
    } 
    else if ( (iteration==1 && algorithm==0) || algorithm==use_allgather)
    {
        t0 = MPI_Wtime();
        MPI_Allgather(..);
        t1 = MPI_Wtime();
        dt2 = t1-t0;
    }

    if (iteration==1)
    {
       dt2<dt1 ? algorithm=use_allgather : algorithm=use_scatter_then_gather;
    }
}
Jeff
quelle
Das ist keine schlechte Idee ... messen Sie beide und bestimmen Sie, welche schneller ist.
Paul
Die meisten modernen HPC-Umgebungen optimieren viele MPI-Anrufe. Manchmal führt dies zu unglaublichen Beschleunigungen, manchmal zu extrem undurchsichtigen Verhaltensweisen. Achtung!
Meawoppl
@ Jeff: Ich habe gerade festgestellt, dass ich ein wichtiges Detail ausgelassen habe ... Ich arbeite mit einem Cluster im Texas Advanced Computing Center, wo sie ein Fat-Tree-Topologie-Netzwerk verwenden. Würde dies den Leistungsunterschied zwischen dem All-Gather- und dem Gather-Broadcast-Ansatz beeinflussen?
Paul
Die @ Paul-Topologie ist hier nicht der dominierende Faktor, aber ein Fettbaum hat eine beträchtliche Halbierungsbandbreite, was das Allgather billig machen sollte. Sammeln sollte jedoch immer billiger sein als allgather. Für größere Nachrichten kann es jedoch weniger als ein Faktor von 2 sein.
Jeff
5

Jeff hat absolut Recht, wenn es nur darum geht, zu messen - wir sind schließlich Wissenschaftler, und dies ist eine empirische Frage - und gibt ausgezeichnete Ratschläge zur Durchführung solcher Messungen. Lassen Sie mich jetzt eine gegenteilige (oder vielleicht ergänzende) Ansicht vertreten.

Es ist zu unterscheiden, ob ein weit verbreiteter Code geschrieben oder auf ein bestimmtes Ziel abgestimmt wird. Im Allgemeinen erstellen wir zuerst unseren Code, damit a) wir ihn auf einer Vielzahl von Plattformen verwenden können und b) der Code über Jahre hinweg wartbar und erweiterbar ist. Aber manchmal machen wir das andere - wir haben eine Zuweisung für ein Jahr auf einer großen Maschine, und wir rüsten auf einige erforderliche große Simulationen auf, und wir benötigen eine bestimmte Leistungsbasis, um das zu erreichen, was wir während dieser Zeit erledigen müssen der Zeitpunkt der gewährten Zuteilung.

Wenn wir Code schreiben, ist es viel wichtiger, ihn allgemein nutzbar und wartbar zu machen, als ein paar Prozent der Laufzeit auf einem bestimmten Computer zu sparen. In diesem Fall ist es fast immer richtig, die Routine zu verwenden, die am besten beschreibt, was Sie tun möchten - dies ist im Allgemeinen der spezifischste Anruf, den Sie tätigen können, um das zu tun, was Sie wollen. Wenn beispielsweise ein Straight Allgather oder Allgatherv das tut, was Sie wollen, sollten Sie dies verwenden, anstatt Ihre eigenen aus Scatter / Gatter-Operationen herauszurollen. Die Gründe sind:

  • Der Code stellt jetzt klarer dar, was Sie versuchen, und macht ihn für die nächste Person, die im folgenden Jahr zu Ihrem Code kommt, verständlicher, ohne eine Ahnung zu haben, was der Code tun soll (diese Person könnten Sie sein).
  • Auf MPI-Ebene sind Optimierungen für diesen spezifischeren Fall verfügbar, die nicht allgemeiner sind, sodass Ihre MPI-Bibliothek Ihnen helfen kann. und
  • Der Versuch, seine eigenen zu rollen, wird wahrscheinlich nach hinten losgehen. Selbst wenn die Leistung auf Computer X mit der MPI-Implementierung Y.ZZ besser ist, kann die Leistung erheblich schlechter sein, wenn Sie auf einen anderen Computer wechseln oder Ihre MPI-Implementierung aktualisieren.

Wenn Sie in diesem Fall feststellen, dass ein MPI-Kollektiv auf Ihrem Computer unangemessen langsam arbeitet, ist es am besten, einen Fehlerbericht beim MPI-Anbieter einzureichen. Sie möchten Ihre eigene Software nicht komplizieren, indem Sie versuchen, im Anwendungscode zu umgehen, was auf MPI-Bibliotheksebene ordnungsgemäß behoben werden sollte.

Allerdings . Wenn Sie sich im "Tuning" -Modus befinden - Sie haben einen funktionierenden Code, müssen Sie in kurzer Zeit (z. B. eine einjährige Zuweisung) auf sehr große Maßstäbe hochfahren und Ihren Code profilieren und herausgefunden haben, dass dieser bestimmte Teil Ihres Codes ein Engpass ist, dann ist es sinnvoll, mit der Durchführung dieser sehr spezifischen Einstellungen zu beginnen. Hoffentlich sind sie keine langfristigen Teile Ihres Codes - im Idealfall verbleiben diese Änderungen in einem projektspezifischen Zweig Ihres Repositorys - aber möglicherweise müssen Sie sie ausführen. In diesem Fall kann die Codierung von zwei verschiedenen Ansätzen, die durch Präprozessoranweisungen unterschieden werden, oder ein "Autotuning" -Ansatz für ein bestimmtes Kommunikationsmuster sehr sinnvoll sein.

Ich bin also nicht anderer Meinung als Jeff. Ich möchte nur einen Kontext hinzufügen, in dem es darum geht, wann Sie sich genug mit solchen relativen Leistungsfragen befassen sollten, um Ihren Code zu ändern, um damit umzugehen.


quelle
Ich denke, ich bin an dieser Stelle mehr an Portabilität als an Optimierung interessiert, aber ich bin immer gespannt, ob es eine andere Implementierung gibt, die genauso portabel, aber schneller ist :)
Paul