Datenparallelität - Data parallelism

Sequentielle oder datenparallele Jobausführung

Datenparallelität ist die Parallelisierung über mehrere Prozessoren in parallelen Computerumgebungen . Es konzentriert sich auf die Verteilung der Daten auf verschiedene Knoten, die die Daten parallel verarbeiten. Es kann auf reguläre Datenstrukturen wie Arrays und Matrizen angewendet werden, indem jedes Element parallel bearbeitet wird. Es steht im Gegensatz zur Aufgabenparallelität als einer anderen Form der Parallelität.

Ein datenparalleler Job auf einem Array von n Elementen kann gleichmäßig auf alle Prozessoren aufgeteilt werden. Nehmen wir an, wir möchten alle Elemente des gegebenen Arrays summieren und die Zeit für eine einzelne Additionsoperation beträgt Ta-Zeiteinheiten. Im Fall einer sequentiellen Ausführung beträgt die vom Prozess benötigte Zeit n × Ta Zeiteinheiten, da alle Elemente eines Arrays zusammengefasst werden. Wenn wir andererseits diesen Job als datenparallelen Job auf 4 Prozessoren ausführen, würde sich die benötigte Zeit auf ( n / 4) × Ta + reduzieren, um Overhead-Zeiteinheiten zusammenzuführen. Die parallele Ausführung führt zu einer Beschleunigung von 4 gegenüber der sequentiellen Ausführung. Es ist wichtig zu beachten, dass die Lokalität von Datenreferenzen eine wichtige Rolle bei der Bewertung der Leistung eines datenparallelen Programmiermodells spielt. Die Lokalität der Daten hängt von den vom Programm durchgeführten Speicherzugriffen sowie von der Größe des Caches ab.

Geschichte

Die Nutzung des Konzepts der Datenparallelität begann in den 1960er Jahren mit der Entwicklung der Solomon-Maschine. Die Solomon-Maschine, auch als Vektorprozessor bezeichnet , wurde entwickelt, um die Leistung mathematischer Operationen durch Arbeiten an einem großen Datenarray (Betrieb mehrerer Daten in aufeinanderfolgenden Zeitschritten) zu beschleunigen. Die Parallelität von Datenoperationen wurde auch ausgenutzt, indem mehrere Daten gleichzeitig mit einer einzigen Anweisung bearbeitet wurden. Diese Prozessoren wurden als "Array-Prozessoren" bezeichnet. In den 1980er Jahren wurde der Begriff eingeführt, um diesen Programmierstil zu beschreiben, der häufig zum Programmieren von Verbindungsmaschinen in datenparallelen Sprachen wie C * verwendet wurde . Datenparallelität lässt sich heute am besten anhand von Grafikprozessoren (GPUs) veranschaulichen , die beide Techniken verwenden, um mehrere Daten räumlich und zeitlich mit einem einzigen Befehl zu bearbeiten .

Beschreibung

In einem Multiprozessorsystem, das einen einzelnen Befehlssatz ( SIMD ) ausführt, wird Datenparallelität erreicht, wenn jeder Prozessor dieselbe Aufgabe für verschiedene verteilte Daten ausführt. In einigen Situationen steuert ein einzelner Ausführungsthread Vorgänge für alle Daten. In anderen steuern unterschiedliche Threads die Operation, führen jedoch denselben Code aus.

Betrachten Sie beispielsweise die Matrixmultiplikation und -addition auf sequentielle Weise, wie im Beispiel erläutert.

Beispiel

Unten ist der sequentielle Pseudocode zum Multiplizieren und Addieren von zwei Matrizen, wobei das Ergebnis in der Matrix C gespeichert ist . Der Pseudo-Code für die Multiplikation berechnet das Skalarprodukt zweier Matrizen A , B und speichert das Ergebnis in die Ausgangsmatrix C .

Wenn die folgenden Programme nacheinander ausgeführt würden, würde die zur Berechnung des Ergebnisses benötigte Zeit von (unter der Annahme, dass Zeilen- und Spaltenlängen beider Matrizen n sind) und für die Multiplikation bzw. Addition betragen. ${\ displaystyle O (n ^ {3})}$${\ displaystyle O (n)}$

// Matrix multiplication
for (i = 0; i < row_length_A; i++)
{		
    for (k = 0; k < column_length_B; k++)
    {
        sum = 0;
        for (j = 0; j < column_length_A; j++)
        {
            sum += A[i][j] * B[j][k];
        }
        C[i][k] = sum;
    }
}

// Array addition
for (i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
}

Wir können die Datenparallelität im vorhergehenden Code ausnutzen, um sie schneller auszuführen, da die Arithmetik schleifenunabhängig ist. Die Parallelisierung des Matrixmultiplikationscodes wird mithilfe von OpenMP erreicht . Eine OpenMP-Direktive "omp parallel for" weist den Compiler an, den Code in der for-Schleife parallel auszuführen. Zur Multiplikation können wir die Matrix A und B entlang der Zeilen bzw. Spalten in Blöcke unterteilen. Dies ermöglicht es uns, jedes Element in der Matrix C einzeln zu berechnen, wodurch die Aufgabe parallel ausgeführt wird. Zum Beispiel: Ein [mxn] Punkt B [nxk] kann fertiggestellt werden, anstatt parallel mit m * k- Prozessoren ausgeführt zu werden. ${\ displaystyle O (n)}$${\ displaystyle O (m * n * k)}$

Datenparallelität bei der Matrixmultiplikation

// Matrix multiplication in parallel
#pragma omp parallel for schedule(dynamic,1) collapse(2)
for (i = 0; i < row_length_A; i++){
    for (k = 0; k < column_length_B; k++){
        sum = 0;
        for (j = 0; j < column_length_A; j++){
            sum += A[i][j] * B[j][k];
        }
        C[i][k] = sum;
    }
}

Aus dem Beispiel ist ersichtlich, dass viele Prozessoren erforderlich sein werden, wenn die Matrixgrößen weiter zunehmen. Die Ausführungszeit niedrig zu halten ist die Priorität, aber mit zunehmender Matrixgröße sind wir mit anderen Einschränkungen konfrontiert, wie der Komplexität eines solchen Systems und den damit verbundenen Kosten. Wenn wir also die Anzahl der Prozessoren im System einschränken, können wir immer noch dasselbe Prinzip anwenden und die Daten in größere Blöcke aufteilen, um das Produkt aus zwei Matrizen zu berechnen.

Nehmen wir für das Hinzufügen von Arrays in einer datenparallelen Implementierung ein bescheideneres System mit zwei Zentraleinheiten (CPU) A und B an. CPU A könnte alle Elemente aus der oberen Hälfte der Arrays hinzufügen, während CPU B alle Elemente aus hinzufügen könnte die untere Hälfte der Arrays. Da die beiden Prozessoren parallel arbeiten, würde das Durchführen der Array-Addition die Hälfte der Zeit in Anspruch nehmen, um denselben Vorgang seriell mit nur einer CPU auszuführen.

Das unten im Pseudocode ausgedrückte Programm foo , das auf jedes Element im Array eine beliebige Operation anwendet, d veranschaulicht die Datenparallelität:

if CPU = "a" then
    lower_limit := 1
    upper_limit := round(d.length / 2)
else if CPU = "b" then
    lower_limit := round(d.length / 2) + 1
    upper_limit := d.length

for i from lower_limit to upper_limit by 1 do
    foo(d[i])

In einem SPMD- System, das auf einem 2-Prozessor-System ausgeführt wird, führen beide CPUs den Code aus.

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

Schritte zur Parallelisierung

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

Datenparallelität vs. Aufgabenparallelität

Datenparallelität vs. Modellparallelität

Gemischte Daten- und Aufgabenparallelität

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

Gemischte Daten- und Aufgabenparallelität hat viele Anwendungen. Es wird insbesondere in folgenden Anwendungen eingesetzt:

1. Gemischte Daten und Aufgabenparallelität finden Anwendung in der globalen Klimamodellierung. Parallele Berechnungen mit großen Datenmengen werden durchgeführt, indem Datengitter erstellt werden, die die Erdatmosphäre und die Ozeane darstellen, und Aufgabenparallelität wird zur Simulation der Funktion und des Modells der physikalischen Prozesse verwendet.
2. In der zeitbasierten Schaltungssimulation . Die Daten werden auf verschiedene Teilschaltungen aufgeteilt und Parallelität wird durch Orchestrierung aus den Aufgaben erreicht.

Datenparallele Programmierumgebungen

Heutzutage stehen verschiedene datenparallele Programmierumgebungen zur Verfügung, von denen die am häufigsten verwendeten sind:

1. Message-Passing-Schnittstelle : Dies ist eine plattformübergreifende Message-Passing-Programmierschnittstelle für parallele Computer. Es definiert die Semantik von Bibliotheksfunktionen, damit Benutzer tragbare Nachrichtenübermittlungsprogramme in C, C ++ und Fortran schreiben können.
2. Open Multi Processing (Open MP): Es handelt sich um eine Anwendungsprogrammierschnittstelle (Application Programming Interface, API), die Shared Memory- Programmiermodelle auf mehreren Plattformen von Multiprozessorsystemen unterstützt.
3. CUDA und OpenACC : CUDA und OpenACC (jeweils) sind Parallel-Computing-API-Plattformen, mit denen ein Softwareentwickler die Recheneinheiten der GPU für die allgemeine Verarbeitung verwenden kann.
4. Threading-Bausteine und RaftLib : Beide Open-Source-Programmierumgebungen, die eine gemischte Daten- / Aufgabenparallelität in C / C ++ - Umgebungen über heterogene Ressourcen hinweg ermöglichen.

Anwendungen

Datenparallelität findet ihre Anwendung in einer Vielzahl von Bereichen, die von Physik, Chemie, Biologie, Materialwissenschaften bis hin zur Signalverarbeitung reichen. Die Wissenschaften implizieren Datenparallelität zur Simulation von Modellen wie Molekulardynamik, Sequenzanalyse von Genomdaten und anderen physikalischen Phänomenen. Die treibenden Kräfte bei der Signalverarbeitung für Datenparallelität sind Videokodierung, Bild- und Grafikverarbeitung sowie drahtlose Kommunikation, um nur einige zu nennen.

Siehe auch

• Aktive Nachricht
• Parallelität auf Befehlsebene
• Skalierbare Parallelität
• Parallelität auf Thread-Ebene
• Paralleles Programmiermodell

Anmerkungen

Verweise

• Hillis, W. Daniel und Steele, Guy L. , Data Parallel Algorithms Communications der ACM Dezember 1986
• Blelloch, Guy E, Vektormodelle für datenparalleles Rechnen MIT Press 1990. ISBN   0-262-02313-X