Datenparallelität

Sequentielle und datenparallele Jobausführung

Datenparallelität ist eine Parallelisierung zwischen mehreren Prozessoren in Parallele Computing Umgebungen. Es konzentriert sich auf die Verteilung der Daten über verschiedene Knoten hinweg, die parallel auf den Daten arbeiten. Es kann auf reguläre Datenstrukturen wie Arrays und Matrizen angewendet werden, indem an jedem parallelen Element gearbeitet wird. Es steht im Gegensatz zu Aufgabe Parallelität als eine andere Form der Parallelität.

Ein Daten paralleler Job auf einer Reihe von einer Reihe von n Elemente können gleichermaßen unter allen Prozessoren aufgeteilt werden. Nehmen wir an, wir möchten alle Elemente des angegebenen Arrays zusammenfassen, und die Zeit für einen einzigen Additionsvorgang ist TA -Zeiteinheiten. Im Falle einer sequentiellen Ausführung wird die Zeit des Prozesses sein n× ta -Zeiteinheiten, da es alle Elemente eines Arrays zusammenfasst. Andererseits, wenn wir diesen Job als Daten parallel auf 4 Prozessoren ausführen, auf die die Zeit verkürzt wird (zu verkaufen wäre (n/4) × TA + Überkopfzeiteinheiten verschmelzen. Die parallele Ausführung führt zu einer Beschleunigung von 4 über die sequentielle Ausführung. Eine wichtige Sache zu beachten ist, dass die Ort der Datenreferenzen spielt eine wichtige Rolle bei der Bewertung der Leistung eines Daten -Parallel -Programmiermodells. Datenort hängt von den vom Programm ausgeführten Speicherzugriffsangeboten sowie von der Größe des Cache ab.

Geschichte

Die Ausbeutung des Datenkonzepts der Parallelität begann in den 1960er Jahren mit der Entwicklung der Solomon -Maschine.[1] Die Solomon -Maschine, auch a genannt Vektorprozessor, wurde entwickelt, um die Leistung mathematischer Operationen durch Arbeiten an einem großen Datenarray zu beschleunigen (in aufeinanderfolgenden Zeitschritten mit mehreren Daten betrieben). Parallelität von Datenoperationen wurde auch durch Betrieb mit mehreren Daten mit einer einzigen Befehnung genutzt. Diese Prozessoren wurden als "Array -Prozessoren" bezeichnet.[2] In den 1980er Jahren wurde der Begriff eingeführt [3] Um diesen Programmierstil zu beschreiben, der häufig zum Programmieren verwendet wurde Verbindungsmaschinen in Daten parallele Sprachen wie C*. Heutzutage ist die Parallelität der Daten am besten in der Veranschaulichung in Grafikverarbeitungseinheiten (GPUs), bei denen sowohl die Techniken des Betriebs mit mehreren Daten im Raum und in der Zeit mit einem einzigen Befehl verwendet werden.

Beschreibung

In einem Multiprozessor -System, das einen einzigen Satz von Anweisungen ausführt (Simd), Datenparallelität werden erreicht, wenn jeder Prozessor dieselbe Aufgabe für verschiedene verteilte Daten ausführt. In einigen Situationen steuert ein einzelner Ausführungs -Thread Vorgänge für alle Daten. In anderen Fällen steuern verschiedene Threads den Vorgang, führen jedoch den gleichen Code aus.

Zum Beispiel überlegen Matrix-Multiplikation und Addition auf sequentielle Weise, wie im Beispiel erläutert.

Beispiel

Unten finden Sie den sequentiellen Pseudo-Code für die Multiplikation und die Zugabe von zwei Matrizen, bei denen das Ergebnis in der Matrix gespeichert ist C. Der Pseudo-Code zur Multiplikation berechnet das Punktprodukt von zwei Matrizen A, B und speichert das Ergebnis in die Ausgangsmatrix C.

Wenn die folgenden Programme nacheinander ausgeführt würden, wäre die Zeit, die zur Berechnung des Ergebnisses benötigt wird (Angenommen, Zeilenlängen und Säulenlängen beider Matrizen sind n) und zur Multiplikation bzw. Addition.

// Matrix-Multiplikation zum (i = 0; i < row_length_a; i++) {		   zum (k = 0; k < column_length_b; k++)   {   Summe = 0;   zum (j = 0; j < column_length_a; j++)   {   Summe += A[i][j] * B[j][k];   }   C[i][k] = Summe;   } } 
// Array Addition zum (i = 0; i < n; i++) {   c[i] = a[i] + b[i]; }

Wir können Daten parallelist im vorhergehenden Code ausnutzen, um sie schneller auszuführen, da die Arithmetik Schleife unabhängig ist. Die Parallelisierung des Matrix -Multiplikationscodes wird durch Verwendung erreicht OpenMP. Eine OpenMP -Richtlinie, "OMP parallel für" anweist den Compiler, den Code in der für die Loop parallele Schleife auszuführen. Zur Multiplikation können wir die Matrix A und B in Blöcke entlang von Zeilen bzw. Säulen teilen. Dies ermöglicht es uns, jedes Element in Matrix C einzeln zu berechnen, wodurch die Aufgabe parallel gemacht wird. Zum Beispiel: A [m x n] Punkt B [n x k] kann fertig sein Anstatt von bei parallel ausgeführt mit Verwendung m*k Prozessoren.

Datenparallelität bei der Matrixmultiplikation
// Matrixmultiplikation parallel #PRAGMA omp parallel für den Zeitplan (dynamisch, 1) Zusammenbruch (2) zum (i = 0; i < row_length_a; i++) {   zum (k = 0; k < column_length_b; k++) {   Summe = 0;   zum (j = 0; j < column_length_a; j++) {   Summe += A[i][j] * B[j][k];   }   C[i][k] = Summe;   } }

Aus dem Beispiel kann beobachtet werden, dass viele Prozessoren benötigt werden, wenn die Matrixgrößen weiter zunehmen. Die Ausführungszeit niedrig zu halten, ist Priorität, aber mit zunehmender Matrixgröße stehen wir mit anderen Einschränkungen wie der Komplexität eines solchen Systems und seinen damit verbundenen Kosten konfrontiert. Wenn wir die Anzahl der Prozessoren im System einschränken, können wir daher immer noch dasselbe Prinzip anwenden und die Daten in größere Stücke teilen, um das Produkt zweier Matrizen zu berechnen.[4]

Nehmen wir für die Zugabe von Arrays in einer Datenparallele -Implementierung ein bescheideneres System mit zwei an Zentrale Verarbeitungseinheiten (CPU) A und B, CPU A könnte alle Elemente aus der oberen Hälfte der Arrays hinzufügen, während CPU B alle Elemente aus der unteren Hälfte der Arrays hinzufügen könnte. Da die beiden Prozessoren parallel arbeiten, würde die Aufgabe der Ergänzung von Array eine halbe Zeit dauern, bis die gleiche Operation in der Serie allein unter Verwendung einer CPU durchgeführt wird.

Das Programm ausgedrückt in Pseudocode unten - was einen willkürlichen Betrieb anwendet, Foo, auf jedem Element im Array d- Illustrated Daten Parallelität:[NB 1] 

wenn Cpu = "a" dann     Lower_limit: = 1 ober_limit: = rund (D.Length / 2)sonst wenn CPU = "B" dann     Lower_limit: = rund (d.länge / 2) + 1 ober_limit: = d.längezum I von Lower_limit nach ober_limit von 1 tun     foo (d [i])

In einem (n SPMD System, das auf 2 Prozessorsystem ausgeführt wird, führt beide CPUs den Code aus.

Die Datenparallelität betont die verteilte (parallele) Natur der Daten im Gegensatz zur Verarbeitung (Aufgabenparallelität). Die meisten realen Programme fallen irgendwo auf ein Kontinuum zwischen Aufgabenparallelität und Datenparallelität.

Schritte zur Parallelisierung

Der Prozess der Parallelisierung eines sequentiellen Programms kann in vier diskrete Schritte unterteilt werden.[5]

Typ Beschreibung
Zersetzung Das Programm ist in Aufgaben unterteilt, die kleinste Ausbeutungseinheit der Übereinstimmung.
Abtretung Aufgaben werden Prozessen zugeordnet.
Orchestrierung Datenzugriff, Kommunikation und Synchronisation von Prozessen.
Kartierung Prozesse sind an Prozessoren gebunden.

Datenparallelität vs. Aufgabe Parallelität

Datenparallelität Aufgabe Parallelität
Gleiche Operationen werden bei verschiedenen Untergruppen derselben Daten ausgeführt. Unter denselben oder unterschiedlichen Daten werden verschiedene Operationen durchgeführt.
Synchronberechnung Asynchrone Berechnung
Beschleunigung ist mehr, da an allen Datensätzen nur ein Ausführungs -Thread betrieben wird. Die Beschleunigung ist geringer, da jeder Prozessor einen anderen Thread oder einen anderen Prozess auf demselben oder unterschiedlichen Datensatz ausführt.
Die Parallelisierung ist proportional zur Eingabedatengröße. Die Parallelisierung ist proportional zur Anzahl der zu erledigenden unabhängigen Aufgaben.
Für optimal gestaltet Lastausgleich auf Multi -Prozessor -System. Lastausgleich hängt von der Verfügbarkeit der Hardware- und Planungsalgorithmen wie der statischen und dynamischen Planung ab.

Datenparallelität vs. Modellparallelität

Datenparallelität Modellparallelität
Das gleiche Modell wird für jeden Thread verwendet, aber die Daten, die zu jedem von ihnen angegeben sind, werden geteilt und geteilt. Gleiche Daten werden für jeden Thread verwendet, und das Modell wird unter Threads aufgeteilt.
Es ist schnell für kleine Netzwerke, aber für große Netzwerke sehr langsam, da große Datenmengen auf einmal zwischen den Prozessoren übertragen werden müssen. Für kleine Netzwerke und für große Netzwerke ist es langsam.
Datenparallelität wird ideal in Array- und Matrixberechnungen und Faltungsnetzwerken verwendet Modellparallelität findet seine Anwendungen im tiefen Lernen

[6]

Gemischte Daten und Aufgabenparallelität

Daten und Aufgabenparallelität können gleichzeitig implementiert werden, indem sie für dieselbe Anwendung miteinander kombiniert werden. Dies wird als gemischte Daten und Aufgabenparallelität bezeichnet. Eine gemischte Parallelität erfordert ausgefeilte Planungsalgorithmen und Softwareunterstützung. Es ist die beste Art von Parallelität, wenn die Kommunikation langsam ist und die Anzahl der Prozessoren groß ist.[7]

Gemischte Daten und Aufgabenparallelität haben viele Anwendungen. Es wird besonders in den folgenden Anwendungen verwendet:

  1. Gemischte Daten und Aufgabenparallelität findet Anwendungen in der globalen Klimamodellierung. Große Daten parallele Berechnungen werden durchgeführt, indem Datennetze erstellt werden, die die Atmosphäre der Erde darstellen, und die Parallelität der Aufgaben wird zur Simulation der Funktion und des Modells der physikalischen Prozesse verwendet.
  2. Im zeitbasierten Schaltungssimulation. Die Daten werden zwischen verschiedenen Unterkreisen unterteilt und die Parallelität wird durch Orchestrierung aus den Aufgaben erreicht.

Daten parallele Programmierumgebungen

Eine Vielzahl von Daten parallele Programmierumgebungen sind heute verfügbar, von denen am häufigsten verwendet werden:

  1. Schnittstelle zur Nachrichtenübergabe: Es handelt sich um eine plattformübergreifende Meldung, die die Programmierschnittstelle für parallele Computer überholt. Es definiert die Semantik der Bibliotheksfunktionen, damit Benutzer tragbare Nachrichtenübergabeprogramme in C, C ++ und FORTRAN schreiben können.
  2. Multi -Verarbeitung offen[8] (Open MP): Es handelt sich um eine Anwendungsprogrammierschnittstelle (API), die unterstützt geteilte Erinnerung Programmiermodelle auf mehreren Plattformen von Multiprozessorsystemen.
  3. CUDA und OpenACC: CUDA bzw. OpenACC (jeweils) sind parallele Computer -API -Plattformen, mit denen ein Software -Ingenieur die Recheneinheiten der GPU zur allgemeinen Zwecke verwenden kann.
  4. Fadenbausteine und Raftlib: Beide Open -Source -Programmierumgebungen, die gemischte Daten/Aufgabenparallelität in C/C ++ - Umgebungen in heterogenen Ressourcen ermöglichen.

Anwendungen

Die Datenparallelität findet seine Anwendungen in einer Vielzahl von Feldern, die von Physik, Chemie, Biologie, Materialwissenschaften bis hin zur Signalverarbeitung reichen. Wissenschaften implizieren Daten parallelität für die Simulation von Modellen wie molekulare Dynamik,[9] Sequenzanalyse von Genomdaten [10] und anderes physikalisches Phänomen. Antriebende Kräfte in der Signalverarbeitung für Datenparallelität sind Videocodierung, Bild- und Grafikverarbeitung, drahtlose Kommunikation [11] um ein paar zu nennen.

Siehe auch

Anmerkungen

  1. ^ Einige Eingabedaten (z. B. wann D.Length bewertet 1 und runden Runden in Richtung Null [Dies ist nur ein Beispiel, es gibt keine Anforderungen an die Art von Runden, zu denen verwendet wird]). untere Grenze größer sein als ObergrenzeEs wird angenommen, dass die Schleife sofort beendet (d. H. Null Iterationen treten auf), wenn dies geschieht.

Verweise

  1. ^ "Der Salomon -Computer".
  2. ^ "SIMD/Vektor/GPU" (PDF). Abgerufen 2016-09-07.
  3. ^ Hillis, W. Daniel und Steele, Guy L., Daten parallele Algorithmen Kommunikation der ACMDezember 1986
  4. ^ Barney, Blaise. "Einführung in das parallele Computer". Computing.llnl.gov. Abgerufen 2016-09-07.
  5. ^ Solihin, Yan (2016). Grundlagen der parallelen Architektur. Boca Raton, FL: CRC Press. ISBN 978-1-4822-1118-4.
  6. ^ "So parallel tiefe Lernen auf GPUs Teil 2/2: Modellparallelität" parallelisieren ". Tim Dettmers. 2014-11-09. Abgerufen 2016-09-13.
  7. ^ "The Netlib" (PDF).
  8. ^ "Openmp.org". openmp.org. Archiviert von das Original Am 2016-09-05. Abgerufen 2016-09-07.
  9. ^ Boyer, L. L; Pawley, G. S. (1988-10-01). "Molekulare Dynamik von Partikeln, die mit paarweisen Kräften mit einem massiv parallele Computer interagieren". Journal of Computational Physics. 78 (2): 405–423. Bibcode:1988jcoph..78..405b. doi:10.1016/0021-9991 (88) 90057-5.
  10. ^ Yap, T.K.; Frieder, O.; Martino, R. L. (1998). "IEEE XPLORE -Dokument - Parallele Berechnung in der biologischen Sequenzanalyse". IEEE -Transaktionen auf parallelen und verteilten Systemen. 9 (3): 283–294. Citeseerx 10.1.1.30.2819. doi:10.1109/71.674320.
  11. ^ Singh, H.;Lee, Ming-Hoau;Lu, Guangming;Kurdahi, F.J.;Bagherzadeh, N.;Filho, E. M. Chaves (2000-06-01). "Morphosys: Ein integriertes rekonfigurierbares System für datenparallele und rechenintensive Anwendungen". IEEE -Transaktionen auf Computern. 49 (5): 465–481. doi:10.1109/12.859540. ISSN 0018-9340.