Algorithm Engineering - Multicore-Programmierung mit der (MC)STL
- Typ: Praktikum
- Lehrstuhl: Prof. Dr. Peter Sanders
- Ort: SR 211, Geb. 50.34
-
Zeit:
Dienstag 14.00 bis 15.30 Uhr
- Beginn: 20.04.2007
-
Dozent:
P. Sanders, J. Singler
- SWS: 2
- LVNr.: 24872
-
Prüfung:
Nein
Thematik
Der Leistungszuwachs moderner Prozessoren stammt nicht mehr von gesteigerter Taktfrequenz, sondern von mehreren Prozessor-Kernen auf einem Chip. Um dieses Potenzial zu nutzen, müssen Programme explizit parallele Algorithmen einsetzen. In unserem Forschungsprojekt MCSTL (Multi-Core Standard Template Library) implementieren wir eine parallelisierte Bibliothek grundlegender Algorithmen, kompatibel zur weitverbreiteten C++ Standard Template Library. Diese arbeitet auf Maschinen mit gemeinsamem Speicher (Shared-Memory), insbesondere also Multicore-Rechnern.
In diesem Praktikum werden zunächst die MCSTL und die bereits vorhandenen Algorithmen vorgestellt, sowie parallele Programmierung eingeführt. Dann werden in Zweier-Teams Aufgaben bearbeitet, die parallele Algorithmen implementieren. Dabei wird auch die MCSTL verwendet und/oder erweitert. Ein wichtiger Aspekt hierbei ist die Laufzeit-Messung und die Interpretation der Ergebnisse, mittels der Tuning-Parameter verbessert werden können.
Eine vorläufige Liste möglicher Themen umfasst:
-Parallele Matrix/Vector-Multiplikation (auch Strassen)
-Heap-Konstruktion
-erweiterte Sort-Benchmarks
-Valarrays(SIMD)
-Set Intersection
-Dynamic Programming (Edit Distance, CYK-Algorithmus, Early-Algorithmus)
-Integer Sorting
-Parallele Suffix-Array-Konstruktion, LCP, String-Sorting
-Filtered Kruskal
-Maximum-Matching, Dominating Set
Die Programmierung erfolgt in C++ (Einführung wenn notwendig), Programmiererfahrung muss bereits vorhanden sein. Arbeitsplatz-Rechner sowie diverse Multicore-/Multiprozessor-Maschinen sind verfügbar.
Die Teilnehmer treffen sich alle zwei Wochen, um Ergebnisse und Erfahrungen auszutauschen.
Ansprechpartner ist .
In diesem Praktikum werden zunächst die MCSTL und die bereits vorhandenen Algorithmen vorgestellt, sowie parallele Programmierung eingeführt. Dann werden in Zweier-Teams Aufgaben bearbeitet, die parallele Algorithmen implementieren. Dabei wird auch die MCSTL verwendet und/oder erweitert. Ein wichtiger Aspekt hierbei ist die Laufzeit-Messung und die Interpretation der Ergebnisse, mittels der Tuning-Parameter verbessert werden können.
Eine vorläufige Liste möglicher Themen umfasst:
-Parallele Matrix/Vector-Multiplikation (auch Strassen)
-Heap-Konstruktion
-erweiterte Sort-Benchmarks
-Valarrays(SIMD)
-Set Intersection
-Dynamic Programming (Edit Distance, CYK-Algorithmus, Early-Algorithmus)
-Integer Sorting
-Parallele Suffix-Array-Konstruktion, LCP, String-Sorting
-Filtered Kruskal
-Maximum-Matching, Dominating Set
Die Programmierung erfolgt in C++ (Einführung wenn notwendig), Programmiererfahrung muss bereits vorhanden sein. Arbeitsplatz-Rechner sowie diverse Multicore-/Multiprozessor-Maschinen sind verfügbar.
Die Teilnehmer treffen sich alle zwei Wochen, um Ergebnisse und Erfahrungen auszutauschen.
Ansprechpartner ist .
Literatur
- Lippman, Lajoie, Moo; C++ Primer (deutsch), Addison-Wesley
- Bjarne Stroustroup; Die C++ Programmiersprache, Addison-Wesley
- Rohit Chandra; Parallel Programming in OpenMP, Morgan Kaufmann
- Michael Quinn; Parallel Programming in C with MPI and OpenMP, McGraw-Hill
- Vorlesung "Paralellel Algorithmen" (insbesondere Folien zu MCSTL)
- Bücher zu OpenMP in den Bibliotheken (leider nicht wirklich brauchbar bzw. verfügbar)
- offizielle OpenMP-Spezfikation
- OpenMP-Tutorial (Präsentation)
- OpenMP-Tutorial (Web)
- von Java nach C++
- STL-Referenz