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 .

1. Treffen 20.4.2007 Organisatorisches und Einführung