Groß synchronen Parallel

Der Groß Synchrone Parallele abstrakte Computer eine Brückenmodell für die Gestaltung von parallelen Algorithmen. Es dient einem Zweck ähnlich dem Parallel Random Access Maschinenmodell. BSP unterscheidet sich von PRAM, indem man nicht die Kommunikation und Synchronisation für selbstverständlich. Ein wichtiger Teil der Analyse einer BSP-Algorithmus beruht auf der Quantifizierung der Synchronisation und Kommunikation benötigt wird.

Geschichte

Die BSP-Modell wurde von Leslie Valiant von der Harvard University in den 1980er Jahren entwickelt. Der endgültige Artikel wurde im Jahr 1990 veröffentlicht.

Zwischen 1990 und 1992, Leslie Valiant und Bill McColl von der Universität Oxford arbeitete an Ideen für einen verteilten Speicher BSP-Programmiermodell, in Princeton und Harvard. Zwischen 1992 und 1997, führte McColl ein großes Forschungsteam in Oxford, die verschiedene BSP-Programmierbibliotheken, Sprachen und Tools, und auch zahlreiche massiv parallelen BSP Algorithmen entwickelt. Mit Interesse und Dynamik wächst, führte McColl dann eine Gruppe von Oxford, Harvard, Florida, Princeton, Bell Labs, Kolumbien und Utrecht, die entwickelt und veröffentlicht die BSPlib Norm für BSP-Programmier 1996.

Valiant entwickelt eine Erweiterung der BSP-Modell in den 2000er Jahren, die zur Veröffentlichung des Multi-BSP-Modell im Jahr 2011.

Das Model

Eine BSP-Computer aus

  • Bauteile, die Verarbeitung und / oder lokale Speichertransaktionen,
  • Ein Netzwerk, das Routen von Nachrichten zwischen Paaren solcher Komponenten, und
  • ein Hardware-Einrichtung, die für die Synchronisation aller oder einer Teilmenge der Komponenten ermöglicht.

Dies wird üblicherweise als eine Reihe von Prozessoren, die folgen, können verschiedene Threads der Berechnung, wobei jeder Prozessor mit schnellen lokalen Speicher ausgestattet und mit einem Kommunikationsnetzwerk miteinander verbunden interpretiert. Eine BSP-Algorithmus stützt sich stark auf dem dritten Merkmal; eine Berechnung schreitet in einer Reihe von globalen supersteps, das aus drei Komponenten besteht:

  • Gleichzeitige Berechnung: Jeder teilnehmende Prozessor kann lokale Berechnungen durchzuführen, das heißt, jeder Prozess kann nur Verwendung in der lokalen schnellen Speicher des Prozessors gespeicherten Werte zu machen. Die Berechnungen erfolgen asynchron von all den anderen, kann aber mit der Kommunikation überschneiden.
  • Kommunikation: Die Prozesse, Datenaustausch zwischen sich Remote-Datenspeichermöglichkeiten zu erleichtern.
  • Barrier-Synchronisation: Wenn ein Prozess diesen Punkt erreicht hat, wartet er, bis alle anderen Prozesse haben die gleiche Barriere erreicht.

Die Rechen- und Kommunikationsmaßnahmen nicht haben, um in der Zeit bestellt werden. Die Kommunikation erfolgt in der Regel in Form von einseitigen Schreib- und Direkt Remote Memory Access-Anrufe, anstatt gepaart zweiseitige Sende- und Empfangsnachrichtenweiterleitung Anrufe. Die Barrieresynchronisations schließt die Superschritt: sie gewährleistet, dass alle einseitigen Kommunikation ordnungsgemäß abgeschlossen. Systeme auf Basis von zweiseitigen Kommunikations um diesen Synchronisationskosten implizit für jede Nachricht gesendet. Das Verfahren für die Barrieresynchronisation basiert auf der Hardware-Einrichtung der BSP-Computer. In Valiant ursprünglichen Papier, prüft in regelmäßigen Abständen diese Anlage, wenn das Ende des aktuellen Superschritt wird global erreicht. Die Periode dieser Überprüfung wird durch bezeichnet.

Die folgende Abbildung zeigt diese in einer schematischen Form. Die Verfahren sind nicht als mit einer bestimmten linearen Ordnung angesehen und kann auf Prozessoren in irgendeiner Weise zugeordnet werden.

Die BSP-Modell ist auch gut geeignet, um die automatische Speicherverwaltung für verteilte-Memory-Computing durch overdecomposition des Problems und Überzeichnung der Prozessoren zu ermöglichen. Die Berechnung ist in mehrere logische Prozesse unterteilt, als es physische Prozessoren und Prozesse werden nach dem Zufallsprinzip Prozessoren zugeordnet. Diese Strategie kann er statistisch auf fast perfekte Lastverteilung führen, beide Arbeit und Kommunikation werden.

Communication

In vielen parallelen Programmiersysteme werden Kommunikationen auf der Ebene der einzelnen Maßnahmen berücksichtigt: Senden und Empfangen einer Nachricht, Speicher auf die Speicherübertragung, etc. Dies ist schwer zu verarbeiten, da es viele gleichzeitige Kommunikationsmaßnahmen in einem Parallelprogramm, und ihre Wechselwirkungen sind in der Regel komplex. Insbesondere ist es schwierig, viel über die Zeit jede einzelne Kommunikations Aktion in Anspruch nehmen zu sagen.

Das BSP Modell berücksichtigt Kommunikationsmaßnahmen en masse. Dies hat die Wirkung, die auf der Zeit, um einen Satz von Daten zu kommunizieren eine obere Schranke gegeben werden kann. BSP berücksichtigt alle Kommunikationsmaßnahmen eines Superschritt als eine Einheit, und übernimmt alle einzelnen Nachrichten gesendet als Teil dieses Geräts eine feste Größe haben.

Die maximale Anzahl der ankommenden oder abgehenden Nachrichten für einen Superschritt wird mit bezeichnet. Die Fähigkeit eines Kommunikationsnetzwerkes, um Daten zu liefern ist, durch einen Parameter erfasst, so definiert, dass es Zeit für einen Prozessor, um Nachrichten von der Größe 1 zu liefern.

Eine Botschaft der Länge offenbar länger dauert, aber senden Sie als eine Botschaft der Größe 1, hat der BSP-Modell nicht unterscheiden zwischen einer Nachrichtenlänge oder Nachrichten der Länge 1. In beiden Fällen sind die Kosten wird gesagt, um zu sein.

Der Parameter ist abhängig von den folgenden Faktoren ab:

  • Die verwendeten Protokolle in dem Kommunikationsnetzwerk zu interagieren.
  • Pufferverwaltung durch die beiden Prozessoren und dem Kommunikationsnetz.
  • Die Routing-Strategie in dem Netzwerk verwendet.
  • Die BSP-Laufzeitsystem.

In der Praxis wird empirisch für jede Parallelrechner ermittelt. Beachten Sie, dass nicht die normierte Einzelwortlieferzeit, aber die Einzelwortlieferzeit unter kontinuierlicher Verkehrssituation.

Barriers

Die einseitige Kommunikation des BSP Modell erfordert Sperrsynchronisierung. Barrieren sind potenziell kostspielige, aber vermeiden Sie die Möglichkeit, deadlock oder Livelock, da Barrieren können kreisförmige Datenabhängigkeiten nicht erstellen. Werkzeuge, um sie zu erkennen und mit ihnen umzugehen sind nicht erforderlich. Barrieren erlauben auch neue Formen der Fehlertoleranz.

Die Kosten für die Barrieresynchronisation wird durch ein paar Probleme beeinflußt:

  • Die Kosten durch die Variation in der Zeit bis zur Fertigstellung der beteiligten gleichzeitige Berechnungen eingeführt. Nehmen wir das Beispiel, wo alle bis auf einen der Prozesse haben ihre Arbeit für diese Superschritt abgeschlossen ist, und werden für den letzten Prozess, der immer noch eine Menge Arbeit zu vervollständigen warten. Das Beste, was eine Implementierung tun können, ist sicherzustellen, dass jeder Prozess funktioniert auf etwa die gleiche Problemgröße.
  • Die Kosten für das Erreichen einer weltweit konsistenten Zustand in allen Prozessoren. Dies ist abhängig von dem Kommunikationsnetzwerk, sondern auch, ob es Spezialhardware verfügbar zum Synchronisieren, und auf dem Weg, in dem Interrupts werden von den Prozessoren gehandhabt werden.

Die Kosten für eine Barrieresynchronisation wird mit bezeichnet. Man beachte, dass wenn der Synchronisationsmechanismus der BSP-Computer als von Streiterin vorgeschlagen. In der Praxis wird ein Wert von empirisch bestimmt.

Auf großen Computern Barrieren sind teuer, und dies ist immer so auf großen Skalen. Es gibt eine große Menge an Literatur über das Entfernen Synchronisationspunkte aus bestehenden Algorithmen, sowohl im Kontext von BSP Rechen- und darüber hinaus. Beispielsweise erlauben viele Algorithmen für die lokale Erfassung des globalen Ende eines Superschritt einfach durch Vergleichen lokale Information an die Anzahl von Nachrichten bereits erhalten. Dies treibt die Kosten für eine globale Synchronisation gegenüber dem minimal erforderlichen Latenz der Kommunikation, auf Null. Doch auch dies ist minimaler Latenzzeit voraussichtlich für künftige Supercomputer-Architekturen und Netzwerkverbindungen weiter zu erhöhen; die BSP-Modell, zusammen mit anderen Modellen für parallele Berechnung, Anpassung erfordern, um diesem Trend gerecht zu werden. Multi-BSP ist eines BSP-basierte Lösung.

Die Kosten für ein BSP-Algorithmus

Die Kosten für eine Superschritt wird als die Summe von drei Termen bestimmt wird; die Kosten für die am längsten laufende lokale Berechnung der Kosten für die globale Kommunikation zwischen den Prozessoren, und die Kosten der Barrieresynchronisation am Ende des Superschritt. Die Kosten für einen Superschritt für Prozessoren:

 wobei die Kosten für die lokale Berechnung ausgeführt, und die Anzahl der Einträge von Prozess gesendet oder empfangen werden. Beachten Sie, dass homogene Prozessoren werden hier angenommen. Es ist üblich, daß der Ausdruck, der als in dem geschrieben werden können und Maxima. Die Kosten für den Algorithmus ist dann die Summe der Kosten der einzelnen Superschritt.

 wobei die Anzahl der supersteps.

,, Und sind in der Regel als Funktionen, die mit der Größe variieren Problem modelliert. Diese drei Eigenschaften einer BSP-Algorithmus werden in der Regel in Bezug auf die asymptotische Notation, zB beschrieben.

Erweiterungen und Verwendungen

Interesse an BSP in den letzten Jahren angestiegen, mit Google Annahme es als eine wichtige Technologie für die graphische Analysen bei massiv über Technologien wie Pregel und MapReduce. Auch mit der nächsten Generation von Hadoop MapReduce Entkopplung des Modells aus dem Rest der Hadoop-Infrastruktur, gibt es jetzt aktiven Open-Source-Projekte, explizite BSP-Programmierung, sowie andere Hochleistungsparallelprogrammiermodelle, oben auf Hadoop hinzuzufügen. Beispiele sind Apache Hama und Apache Giraph.

BSP wurde von vielen Autoren wurde erweitert, um Bedenken über BSP Untauglichkeit für die Modellierung von spezifischen Architekturen oder rechnerische Paradigmen, anzugehen. Ein Beispiel hierfür ist das zersetzbare BSP Modell. Das Modell ist auch in der Schaffung einer Reihe von neuen Programmiersprachen und Schnittstellen, wie Schütt Synchrone Parallel ML, BSPLib, Apache Hama und Pregel verwendet.

Bemerkenswerte Implementierungen der BSPLib Standard sind die Universität Paderborn BSP-Bibliothek und der Oxford BSP Toolset von Jonathan Hill. Moderne Implementierungen BSPonMPI und MulticoreBSP. MulticoreBSP für C ist besonders bekannt für seine Fähigkeit, ausgehend verschachtelten BSP läuft, so dass für explizite Mehr BSP-Programmierung.

(0)
(0)
Kommentare - 0
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha