Parallelverarbeitung

Aus Wikibooks

[Bearbeiten] Zusammenfassung des Projekts

• Zielgruppe: Studierende und Interessierte, die sich für die Grundlagen der Parallelverarbeitung begeistern.

• Lernziele: Ein grundsätzliches Verständnis für die vielfältigen Modelle, Algorithmen und typischen Herangehensweisen bei dem Entwurf und der Implementierung paralleler Programme.

• Buchpatenschaft/Ansprechperson:

• Sind Co-Autoren gegenwärtig erwünscht? Eine Beteiligung ist gegenwärtig auf jeden Fall erwünscht.

• Richtlinien für Co-Autoren:

• Projektumfang und Abgrenzung zu anderen Wikibooks: Abgesehen von dem Betriebssystembuch, in dem Threads und Prozesse behandelt werden, gibt es keine Überschneidungen mit anderen Wikibooks.

• Themenbeschreibung:

• Aufbau des Buches: Parallele Programme (Entwurf, Sprachen), Theorie (Modelle, Algorithmen, Abschätzungen?) und Technik (Architekturen).

Inhaltsverzeichnis 1 Zusammenfassung des Projekts 2 Einleitung 3 Algorithmen 3.1 Analyse paralleler Algorithmen 3.2 Reduktion 3.3 Matrixmultiplikation

[Bearbeiten] Einleitung

Mit der gegenwärtigen Entwicklung preisgünstiger Multicore-Prozessoren im Endanwenderbereich, ist für jeden die Parallelisierung eigener Programme greifbar geworden. Die Parallelverarbeitung ist dabei Segen und Fluch zugleich: Es stehen Leistungssteigerungen, die Lösung größerer Probleme und höhere Durchsatzraten einer wachsenden Komplexität und höherer Fehleranfälligkeit der Programme gegenüber.

Durch methodisches Vorgehen und einer korrekte Analyse können diese Probleme reduziert oder sogar vermieden werden. Das Ziel dieses Buch ist es, einen Überblick über bekannte Methoden, Algorithmen und Entwurfspraktiken zu geben.

[Bearbeiten] Algorithmen

In diesem Kapitel werden konkrete Beispielalgorithmen für die wichtigsten Algorithmenklassen vorgestellt und eventuelle Abschätzungen zu Zeit- und Platzbedarf angegeben.

[Bearbeiten] Analyse paralleler Algorithmen

Um die Wirksamkeit paralleler Algorithmen zu beurteilen, kann man sich der theoretischen Analyse oder dem praktischen Benchmarking bedienen. Um eine Analyse durchzuführen müssen dazu die zu quantifizierenden Maße bekannt sein. Üblicherweise bedient man sich hierbei der Anzahl ausgeführter Instruktionen auf einem eigens gewählten Maschinenmodell. In Abhängigkeit von der Prozessorenzahl p, wird die Zeit T(p) definiert als die maximale Anzahl Instruktionen die für diesen speziellen Algorithmus benötigt wird. Um Aussagen zu Beschleunigung und Effizienz treffen zu können, wird noch die Zeit T_s für den besten bekannten sequentiellen Algorithmus ermittelt.

Die Beschleunigung ergibt sich nun durch

.

Diese absolute Art der Beschleunigung ist eine gänzlich andere Größe als die relative Beschleunigung

die den Overhead der bei der Parallelisierung entsteht, außer acht lässt.

Wie gut die Beschleunigung mit der Anzahl der Prozessoren skaliert, wird anhand der Effizienz

ermittelt.

[Bearbeiten] Reduktion

Ein wichtiges Hilfsmittel für die parallele Beschleunigung, ist die Reduktion. Die Reduktion ist eine Abbildung die mit Hilfe eines assoziativen Operators eine Liste von n Elementen zu einem einzigen Element reduziert. Beispielsweise hätte die Reduktion der Liste [3,2,6,3] mit der Additionsoperation das Ergebnis 14.

Der wichtigste Ansatz zur Parallelisierung der Reduktion ist die Nutzung einer baumartigen Struktur. Unter Verwendung von n Prozessoren sinkt der Aufwand zur Berechnung der Reduktion von

O(n) auf O(log₂n).

[Bearbeiten] Matrixmultiplikation

Die Multiplikation zweier quadratischer Matrizen A und B der Größe n ist das Paradebeispiel für die Möglichkeiten der Parallelverarbeitung. Bekanntlich berechnet sich ein Eintrag der Ergebnismatrix zu

.

Für die n² Einträge der Ergebnismatrix ergibt sich im sequentiellen Fall dementsprechend eine Laufzeit von

für die Anzahl der Multiplikationen.

Der beste sequentielle Algorithmus für die Multiplikation zweier Matrizen geht auf den Strassen-Algorithmus von Volker Strassen zurück, der mit einer Laufzeit von

bedeutend schneller ist.

Wie kann nun der Einsatz mehrerer Prozessoren dies beschleunigen? Da jedes Element der Matrix unabhängig von den anderen ist, ist ein denkbarer Ansatz n² Prozessoren auf jedes dieser Elemente anzusetzen und parallel die Skalarmultiplikation durchzuführen. Wie man sieht benötigt man bei echter Parallelität lediglich die Zeit für die Skalarmultiplikation und erhält somit eine Laufzeit in

O(n).

Unter Zuhilfenahme von n³ Prozessoren lässt sich der Aufwand zur Berechnung auf O(log₂n) reduzieren. Zu jedem Eintrag in der Ergebnismatrix können n Prozessoren die Multiplikation der a_ik und b_kj in Zeit O(1) erledigen. Das Aufaddieren der Multiplikationsergebnisse geschieht dann mittels Reduktion in O(logn) Zeit.

Dieses Lehrbuch ist erst vor kurzem angelegt worden und steht in den ersten Wochen unter begleitender Beobachtung. Das soll den Autor motivieren, sich weiterhin zu engagieren. Nützliche Hinweise findest du im Wikibooks-Lehrbuch. Bei technischen Problemen kannst Du hier Hilfe erhalten. Wie mit/bei neuen Buchprojekten zu verfahren ist, kannst Du unter Wikibooks:Qualitätsmanagement/ Buchkandidat erfahren. Diskussionen zu diesem Buch führst Du auf dieser Seite. (20090616)