20.4.2007, 11.30 Uhr: Vorbesprechung in Raum 236 (Geb. 50.34)
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 |
||
Termine
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 .
Folien
1. Treffen 20.4.2007 Organisatorisches und Einführung
Arbeitsblätter
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
