Gemeinsamer Speicher und Datenparallelität

Parallelität mit gemeinsamem Speicher bedeutet, dass mehrere Threads auf einen gemeinsamen Adressraum zugreifen, während Datenparallelität dieselbe Operation gleichzeitig auf viele Datenelemente anwendet.

Definition

Im Shared-Memory-Modell kommunizieren parallele Ausführungsthreads implizit durch Lesen und Schreiben eines gemeinsamen Speichers und koordinieren sich über Synchronisationsprimitive; Datenparallelität ist der Spezialfall, bei dem dieselbe Berechnung unabhängig voneinander auf die Elemente einer Datenstruktur angewendet wird.

Scope

Dieses Thema behandelt das Modell des gemeinsamen Adressraums und seine Programmierschnittstellen (Threads, OpenMP), die Synchronisationsprimitive, die Threads koordinieren (Sperren, Barrieren, Atomics) und die Gefahren, die sie verwalten (Datenkonflikte, Deadlock, False Sharing), datenparallele und schleifenparallele Konstrukte sowie aufgabenbasierte Laufzeitsysteme mit Work-Stealing-Schedulern. Es behandelt die Programmierseite, deren theoretische Grundlagen unter Shared-Memory-Modellen erscheinen.

Core questions

• Wie koordinieren Threads den Zugriff auf gemeinsame Daten ohne Race Conditions oder Deadlock?
• Wie können Schleifen- und Array-Operationen für die parallele Ausführung ausgedrückt werden?
• Wie werden dynamisch generierte Aufgaben effizient über Kerne verteilt?

Key theories

Synchronisation und Speicherkonsistenz

Korrekte Shared-Memory-Programme basieren auf Synchronisationsprimitiven und einem Verständnis des Speichermodells, das regelt, wann die Schreibvorgänge eines Threads für einen anderen sichtbar werden, wobei Fehlmanagement zu Race Conditions oder Deadlock führen kann.

Direktivenbasierte Datenparallelität

OpenMP ermöglicht es Programmierern, sequenziellen Code mit Direktiven zu annotieren, die Schleifen und Regionen über einen gemeinsamen Adressraum parallelisieren, was einen portablen, inkrementellen Weg zur Shared-Memory-Parallelität bietet.

Work-Stealing-Aufgabenplanung

Aufgabenbasierte Laufzeitsysteme planen dynamisch erstellte Aufgaben, indem untätige Prozessoren Arbeit von ausgelasteten stehlen, wodurch eine nachweislich gute Lastverteilung und ein begrenzter Overhead für irreguläre parallele Berechnungen erreicht werden.

Clinical relevance

Shared-Memory- und datenparallele Programmierung ist die Art und Weise, wie alltägliche Software Multicore-CPUs nutzt und wie wissenschaftliche Kerne, Simulationen und array-intensive Workloads auf einem einzelnen Knoten Beschleunigungen erzielen, was sie zur am weitesten verbreiteten Form der parallelen Programmierung macht.

History

Das Shared-Memory-Multiprocessing reifte mit dem Threads-Modell und dem OpenMP-Standard von 1998 für portable, direktivenbasierte Parallelität; Work-Stealing-Scheduler aus dem Cilk-Projekt (ab 1996) lieferten effiziente aufgabenbasierte Parallelität, und diese Ideen liegen heute der Multicore-Programmierung über verschiedene Sprachen hinweg zugrunde.

Key figures

• Maurice Herlihy
• Nir Shavit
• Charles Leiserson
• Vipin Kumar

Seminal works

• herlihy2008
• grama2003
• blumofe1996

Frequently asked questions

Was ist ein Datenkonflikt (Data Race) und warum ist er gefährlich?

Ein Datenkonflikt tritt auf, wenn zwei Threads gleichzeitig und ohne Synchronisation auf denselben Speicherort zugreifen und mindestens einer davon schreibt. Das Ergebnis ist undefiniert und kann zwischen den Ausführungen variieren, was zu intermittierenden, schwer reproduzierbaren Fehlern führt, weshalb Synchronisation in Shared-Memory-Programmen unerlässlich ist.