Barriere (Informatik)

Im Parallele Computing, a Barriere ist eine Art von Art von Synchronisation Methode. Eine Barriere für eine Gruppe von Threads oder Prozessen im Quellcode bedeutet, dass jeder Thread/Prozess an diesem Punkt gestoppt wird und erst dann fortgesetzt wird, bis alle anderen Threads/Prozesse diese Barriere erreichen.

Viele kollektive Routinen und Richtlinienbasis parallele Sprachen stellen implizite Hindernisse auf. Zum Beispiel eine Parallele tun einhängen Forran mit OpenMP dürfen bis nach Abschluss der letzten Iteration keinen Thread fortsetzen. Dies ist für den Fall, dass das Programm unmittelbar nach Abschluss auf das Ergebnis der Schleife basiert. Im NachrichtenübergangJede globale Kommunikation (wie Reduktion oder Streuung) kann eine Barriere bedeuten.

Im Gleichzeitiges Computer, eine Barriere kann in a sein erzogen oder Verringerter Zustand. Der Begriff verriegeln wird manchmal verwendet, um sich auf eine Barriere zu beziehen, die im erhöhten Zustand beginnt und nicht wieder in den gesenkten Zustand ist. Der Begriff Latch wird manchmal verwendet, um auf einen Verriegelung zu verweisen, der automatisch abgesenkt wird, sobald eine vorbestimmte Anzahl von Threads/Prozessen eingetroffen ist.

Implementierung

Die Grundbarriere hat hauptsächlich zwei Variablen, von denen einer den Pass/Stopp -Zustand der Barriere aufzeichnet, von denen die andere die Gesamtzahl der in der Barriere eingegebenen Threads hält. Der Barriereszustand wurde initialisiert, um durch die ersten Fäden in die Barriere zu "stoppen". Immer wenn ein Thread eintritt, basierend auf der Anzahl der bereits in der Barriere bereits in der Barriere erteilten Threads legt der Thread den Barriereszustand so fest, dass alle Threads aus der Barriere herauskommen können. Wenn der eingehende Faden nicht der letzte ist, ist er in der Barriere gefangen und testet weiter, wenn sich der Barriereszustand von "Stop" zu "Pass" geändert hat, und er steigt nur dann aus, wenn sich der Barriereszustand an ändert. "passieren". Der folgende C -Code zeigt diese Prozedur.[1][2] 

Struktur barrier_type {   // Wie viele Prozessoren haben die Barriere eingegeben   // initialisieren auf 0   int ankommen_counter;   // Wie viele Prozessoren haben die Barriere verlassen?   // initialisieren auf p   int Leave_counter;   int Flagge;   std::Mutex sperren; };  // Barriere für P -Prozessoren Leere Barriere(barrier_type* b, int p) {   b->sperren.sperren();   wenn (b->ankommen_counter == 0)   {   b->sperren.Freischalten();   während (b->Leave_counter ! = p); // Warten Sie, bis sich alle vor dem Löschen verlassen können   b->sperren.sperren();   b->Flagge = 0; // Erste Einkunft löscht die Flagge   }   b->ankommen_counter++;   wenn (b->ankommen_counter == p) // Letzte Ankunft setzt Flag   {   b->ankommen_counter = 0;   b->Leave_counter = 0;   b->Flagge = 1;   }   b->sperren.Freischalten();    während (b->Flagge == 0); // Warte auf Flag   b->sperren.sperren();   b->Leave_counter++;   b->sperren.Freischalten(); }

Das potenzielle Problem ist:

  1. Aufgrund aller Threads, die wiederholt auf die globale Variable für Pass/Stopp zugreifen, ist der Kommunikationsverkehr eher hoch, was die verringert Skalierbarkeit.

Dieses Problem kann gelöst werden, indem die Threads neu gruppieren und eine Multi-Level-Barriere verwendet werden, z. Kombinieren der Baumbarriere. Auch Hardware -Implementierungen können den Vorteil von höher haben Skalierbarkeit.

Sinnesreverse zentralisierte Barriere

Anstatt denselben Wert zur Darstellung von Pass/Stopp zu verwenden, verwenden sequentielle Barrieren die Gegentorte für den Pass/Stopp -Status. Wenn bei der Barriere 1 beispielsweise 0 verwendet wird, um die Gewinde zu stoppen, verwendet Barriere 2 1, um die Gewinde zu stoppen, und Barriere 3 verwendet 0, um Threads erneut zu stoppen und so weiter.[3] Der folgende C -Code zeigt dies.[1][4][2] 

Struktur barrier_type {   int Zähler; // initialisieren auf 0   int Flagge; // initialisieren auf 0   std::Mutex sperren; };  int local_sense = 0; // privat pro Prozessor  // Barriere für P -Prozessoren Leere Barriere(barrier_type* b, int p) {   local_sense = 1 - local_sense;   b->sperren.sperren();   b->Zähler++;   int angekommen = b->Zähler;   wenn (angekommen == p) // Letzte Ankunft setzt Flag   {   b->sperren.Freischalten();   b->Zähler = 0;   // Speicherzaun, um sicherzustellen, dass die Änderung zum Konter   // wird vor dem Wechsel zur Flagge gesehen   b->Flagge = local_sense;   }   anders   {   b->sperren.Freischalten();   während (b->Flagge ! = local_sense); // Warte auf Flag   } }

Kombinieren der Baumbarriere

Eine kombinierende Baumbarriere ist eine hierarchische Methode zur Umsetzung der Barriere zur Lösung der Skalierbarkeit Indem Sie den Fall vermeiden, dass sich alle Themen am selben Ort drehen.[3]

In der K-Tree-Barriere sind alle Threads gleichermaßen in Untergruppen von K-Threads unterteilt und innerhalb dieser Untergruppen werden eine Synchronisation in der ersten Runde durchgeführt. Sobald alle Untergruppen ihre Synchronisationen durchgeführt haben, tritt der erste Thread in jeder Untergruppe in die zweite Ebene für die weitere Synchronisierung ein. In der zweiten Ebene bilden die Threads wie in der ersten Ebene neue Untergruppen von K -Threads und synchronisieren Sie innerhalb von Gruppen, wodurch ein Thread in jeder Untergruppe auf die nächste Ebene gesendet wird und so weiter. Schließlich gibt es in der endgültigen Ebene nur eine Untergruppe, die synchronisiert werden muss. Nach der Synchronisation der endgültigen Ebene wird das Freisetzungsignal auf die oberen Ebenen übertragen und alle Fäden werden über die Barriere hinausgehen.[4][5]

Implementierung der Hardwarebarriere

Die Hardware -Barriere verwendet Hardware, um das obige grundlegende Barrieremodell zu implementieren.[1]

Die einfachste Hardware -Implementierung verwendet dedizierte Kabel, um Signal zu übertragen, um eine Barriere zu implementieren. Dieser dedizierte Draht führt oder/und der Betrieb, um als Pass-/Blockflags und Gewindezähler zu fungieren. Für kleine Systeme ist ein solches Modell funktioniert und die Kommunikationsgeschwindigkeit ist kein Hauptanliegen. In großen Multiprozessorsystemen kann dieses Hardware -Design eine hohe Latenz aufweisen. Die Netzwerkverbindung zwischen Prozessoren ist eine Implementierung, um die Latenz zu senken, was zur Kombination von Baumbarriere analog ist.[6]

Siehe auch

Verweise

  1. ^ a b c Solihin, Yan (2015-01-01). Grundlagen der parallelen Multicore -Architektur (1. Aufl.). Chapman & Hall/CRC. ISBN 978-1482211184.
  2. ^ a b "Implementierung von Hindernissen". Carnegie Mellon Universität.
  3. ^ a b Culler, David (1998). Parallele Computerarchitektur, ein Hardware/Software -Ansatz. ISBN 978-1558603431.
  4. ^ a b Nanjegowda, Ramachandra; Hernandez, Oscar; Chapman, Barbara; Jin, Haoqiang H. (2009-06-03). Müller, Matthias S.; Supinsski, Bronis R. DE; Chapman, Barbara M. (Hrsg.). OpenMP in Zeiten extremer Parallelität entwickeln. Vorlesungsnotizen in Informatik. Springer Berlin Heidelberg. pp.42–52. doi:10.1007/978-3-642-02303-3_4. ISBN 9783642022845.
  5. ^ Nikolopoulos, Dimitrios S.; Papatheodorou, Theodore S. (1999-01-01). Eine quantitative architektonische Bewertung von Synchronisationsalgorithmen und Disziplinen auf CCNUMA -Systemen: Der Fall des SGI -Ursprungs2000. Verfahren der 13. Internationalen Konferenz über Supercomputing.ICS '99.New York, NY, USA: ACM.S. 319–328. doi:10.1145/305138.305209. ISBN 978-1581131642. S2CID 6097544.
  6. ^ N.R.Adiga et al.Ein Überblick über den Blugene/L -Supercomputer. Verfahren der Konferenz über Hochleistungsnetzwerke und -Computer, 2002.

Externe Links

"Parallele Programmierung mit Barrieresynchronisation". SourceAllies.com. März 2012.