Parallele Programmiermodell

Im Computer, a Parallele Programmiermodell ist ein Abstraktion von Parallele Computer Architektur, mit der es bequem ausdrücken kann Algorithmen und ihre Komposition in Programme. Der Wert eines Programmiermodells kann an seiner beurteilt werden Allgemeinheit: Wie gut kann eine Reihe verschiedener Probleme für eine Vielzahl verschiedener Architekturen ausgedrückt werden, und dessen Leistung: Wie effizient die kompilierten Programme ausführen können.[1] Die Implementierung eines parallelen Programmiermodells kann die Form von a haben Bibliothek aufgerufen von a Sequentielle Sprache, als Erweiterung einer vorhandenen Sprache oder als völlig neue Sprache.

Konsens über ein bestimmtes Programmiermodell ist wichtig, da es zu unterschiedlichen parallelen Computern führt, die mit Unterstützung des Modells erstellt werden, wodurch ermittelt wird Portabilität von Software. In diesem Sinne werden Programmiermodelle als bezeichnet als Überbrückung zwischen Hardware und Software.[2]

Klassifizierung paralleler Programmiermodelle

Klassifizierungen paralleler Programmiermodelle können weitgehend in zwei Bereiche unterteilt werden: Prozessinteraktion und Problemzersetzung.[3][4][5]

Prozessinteraktion

Die Prozessinteraktion bezieht sich auf die Mechanismen, mit denen parallele Prozesse miteinander kommunizieren können. Die häufigsten Formen der Interaktion sind gemeinsamer Speicher und Nachrichtenübergang, aber auch die Interaktion kann implizit sein (für den Programmierer unsichtbar).

Geteilte Erinnerung

Hauptartikel: Gemeinsamer Gedächtnis (Interprozesskommunikation)

Der gemeinsame Speicher ist ein effizientes Mittel, um Daten zwischen den Prozessen zu übergeben. In einem Shared-Memory-Modell teilen parallele Prozesse einen globalen Adressraum, den sie asynchron lesen und schreiben. Asynchroner gleichzeitiger Zugang kann zu Rennbedingungenund Mechanismen wie Schlösser, Semaphoren und Monitore kann verwendet werden, um diese zu vermeiden. Konventionell Multi-Core-Prozessoren Unterstützen Sie den gemeinsam genutzten Speicher direkt, das viele parallele Programmiersprachen und Bibliotheken wie z. Cilk, OpenMP und Fadenbausteine, sind so konzipiert, dass sie ausgenutzt werden.

Nachrichtenübergang

Hauptartikel: Nachrichtenübergang

In einem Nachrichten-Passing-Modell tauschen parallele Prozesse Daten durch Übergabe von Nachrichten aneinander aus. Diese Mitteilungen können asynchron sein, wobei eine Nachricht gesendet werden kann, bevor der Empfänger bereit ist oder synchron ist, wo der Empfänger bereit sein muss. Das Kommunizieren von sequentiellen Prozessen (CSP) Formalisierung des Nachrichtenübergangs verwendet synchrone Kommunikationskanäle, um Prozesse zu verbinden, und führte zu wichtigen Sprachen wie z. B. Occam, Limbo und gehen. Dagegen die Schauspielermodell Verwendet asynchron D, Scala und Salsa.

Verteilte globale Adressraum

Hauptartikel: Verteilte globale Adressraum

PGAS -Modelle (Partitioned Global Address Space) bieten einen Mittelweg zwischen gemeinsam genutztem Speicher und Nachrichtenübergabe. PGAs bietet eine globale Speicherplatzabstraktion für die Speicheradresse, die logisch verteilt ist, wobei ein Teil für jeden Prozess lokal ist. Parallelprozesse kommunizieren durch asynchronische Operationen (z. B. liest und schreibt) auf dem globalen Adressraum in einer Weise, die an gemeinsame Speichermodelle erinnert. Durch die semantische Aufteilung des globalen Adressraums in Teile mit Affinität zu einem bestimmten Prozessen ermöglichen sie Programmierern, auszunutzen Referenzort und ermöglichen eine effiziente Implementierung auf Verteilter Speicher Parallele Computer. PGAs werden von vielen vielen parallelen Programmiersprachen und Bibliotheken angeboten, wie z. FORTRAN 2008, Kapelle, UPC ++, und Shmem.

Implizite Interaktion

Hauptartikel: Implizite Parallelität

In einem impliziten Modell ist für den Programmierer keine Prozessinteraktion sichtbar, und stattdessen ist der Compiler und/oder die Laufzeit für die Ausführung verantwortlich. Zwei Beispiele für implizite Parallelität sind mit Domänenspezifische Sprachen wo die Parallelität in hochrangigen Operationen vorgeschrieben ist und mit Funktionale Programmiersprachen Weil das Fehlen von Nebenwirkungen Ermöglicht nicht abhängige Funktionen parallel.[6] Diese Art von Parallelität ist jedoch schwer zu handhaben[7] und funktionale Sprachen wie z. Gleichzeitiger Haskell und Gleichzeitiger ML Bereitstellung von Funktionen, um die Parallelität explizit und korrekt zu verwalten.

Problemzersetzung

Ein parallele Programm besteht aus gleichzeitig ausführenden Prozessen. Die Problemzersetzung bezieht sich auf die Art und Weise, wie die konstituierenden Prozesse formuliert werden.[8][9]

Aufgabe Parallelität

Hauptartikel: Aufgabe Parallelität

Ein aufgabenparalleles Modell konzentriert sich auf Prozesse oder Ausführungsfäden. Diese Prozesse sind häufig verhaltensweisen unterschiedlich, was den Bedarf an Kommunikation hervorhebt. Die Parallelität der Aufgaben ist eine natürliche Möglichkeit, die Kommunikation mit Botschaft zu äußern. Im Flynns Taxonomie, Aufgabenparallelität wird normalerweise als klassifiziert als Mimd/Mpmd oder Misd.

Datenparallelität

Hauptartikel: Datenparallelität

Ein datenparalleles Modell konzentriert sich auf die Durchführung von Vorgängen in einem Datensatz, in der Regel ein regelmäßig strukturiertes Array. Eine Reihe von Aufgaben wird bei diesen Daten arbeiten, jedoch unabhängig von disjunkten Partitionen. Im Flynns Taxonomie, Datenparallelität werden normalerweise als klassifiziert als Mimd/SPMD oder Simd.

Implizite Parallelität

Hauptartikel: Implizite Parallelität

Wie bei der impliziten Prozessinteraktion zeigt ein implizite Modell der Parallelität dem Programmierer nichts als Compiler, die Laufzeit oder die Hardware verantwortlich. Zum Beispiel in Compilern, Automatische Parallelisierung ist der Prozess des Konvertierens sequentieller Code in Parallelcode und in der Computerarchitektur. Superscalar -Ausführung ist ein Mechanismus, bei dem Parallelität auf Befehlsebene wird ausgenutzt, um parallel Operationen durchzuführen.

Terminologie

Parallele Programmiermodelle stehen eng mit dem zusammen mit Berechnungsmodelle. Ein Modell der parallele Berechnung ist ein Abstraktion Wird verwendet, um die Kosten von Rechenprozessen zu analysieren, muss jedoch nicht unbedingt praktisch sein, da es in Hardware und/oder Software effizient implementiert werden kann. Ein Programmiermodell im Gegensatz dazu impliziert ausdrücklich die praktischen Überlegungen zur Hardware- und Software -Implementierung.[10]

Eine parallele Programmiersprache kann auf einer oder einer Kombination von Programmiermodellen basieren. Zum Beispiel, Hochleistungs -Forran basiert auf gemeinsam genutzten Interaktionen und datenparalleler Problemabbauung, und gehen Bietet Mechanismus für gemeinsame Interaktion mit gemeinsamem Memory und Nachrichten.

Beispiel Parallele Programmiermodelle

Name Interaktionsklasse Klasse der Zersetzung Beispielimplementierungen
Schauspielermodell Asynchrone Nachricht passieren Aufgabe D, Erlang, Scala, SALSA
Bulk -synchroner Parallele Geteilte Erinnerung Aufgabe Apache Giraph, Apache Hama, BSplib
Kommunizieren von sequentiellen Prozessen Synchrone Nachricht Passierung Aufgabe Ada, Occam, Verilogcsp, gehen
Schaltungen Nachrichtenübergang Aufgabe Verilog, VHDL
Datenfluss Nachrichtenübergang Aufgabe Lüster, Tensorflow, Apache Flink
Funktional Nachrichtenübergang Aufgabe Gleichzeitiger Haskell, Gleichzeitiger ML
LOGP -Maschine Synchrone Nachricht Passierung Unbestimmt Keiner
Parallel -Zufallszugriffsmaschine Geteilte Erinnerung Daten Cilk, CUDA, OpenMP, Fadenbausteine, XMTC
SPMD PGAs Verteilte globale Adressraum Daten FORTRAN 2008, Einheitlich parallel c, UPC ++, Shmem
Globale Sicht Aufgabe Parallelität Verteilte globale Adressraum Aufgabe Kapelle, X10

Siehe auch

Verweise

  1. ^ Skilicorn, David B., "Modelle für praktische parallele Berechnung", International Journal of Parallel Programing, 20.2 133–158 (1991), https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf
  2. ^ Leslie G. Valiant, "Ein Überbrückungsmodell für parallele Berechnung", Kommunikation des ACM, Band 33, Ausgabe 8, August 1990, Seiten 103–111.
  3. ^ John E. Savage, Berechnungsmodelle: Erforschung der Leistung des Computers, 2008, Kapitel 7 (Parallelberechnung), http://cs.brown.edu/~jes/book/ Archiviert 2016-11-05 bei der Wayback -Maschine
  4. ^ Ian Foster, entwerfen und bauen parallele Programme, 1995, Abschnitt 1.3, "Ein paralleles Programmiermodell", http://www.mcs.anl.gov/~itf/dbpp/text/node9.html
  5. ^ Blaise Barney, Einführung in Parallel Computing, "Models", 2015, Lawrence Livermore National Laboratory,https://computing.llnl.gov/tutorials/parallel_comp/#models
  6. ^ Hammond, Kevin. Parallele funktionale Programmierung: Eine Einführung. Im internationalen Symposium über parallele symbolische Berechnung, p. 46. ​​1994.
  7. ^ McBurney, D. L. und M. Ronan Sleep. "Transsputerbasierte Experimente mit der ZApp-Architektur." Parallel Architekturen und Sprachen Europa. Springer Berlin Heidelberg, 1987.
  8. ^ Ian Foster, entwerfen und bauen parallele Programme, 1995, Abschnitt 2.2, "Partitioning", http://www.mcs.anl.gov/~itf/dbpp/text/node16.html
  9. ^ Blaise Barney, Einführung in Parallel Computing, "Partitioning", 2015, Lawrence Livermore National Laboratory, https://computing.llnl.gov/tutorials/parallel_comp/#designPartitioning
  10. ^ Skilicorn, David B. und Domenico Talia, Modelle und Sprachen für parallele Berechnung, ACM Computing Surveys, 30.2 123–169 (1998), https://www.cs.utexas.edu/users/browne/cs392cf2000/papers/modelsofparallelComputation-skillicorn.pdf

Weitere Lektüre

  • Blaise Barney, Einführung in das parallele ComputingLawrence Livermore National Laboratory
  • Murray I. Cole., Algorithmische Skelette: Strukturiertes Management paralleler Berechnung (PDF)Universität Glasgow
  • J. Darlinton; M. Ghanem; H. W. bis (1993), "Strukturierte parallele Programmierung", In Programmiermodellen für massiv parallele Computer. IEEE Computer Society Press: 160–169, doi:10.1109/pmmp.1993.315543, ISBN 0-8186-4900-3, S2CID 15265646
  • Ian Foster, Entwerfen und Bau paralleler Programme, Argonne National Laboratory