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

  • 20.4.2007, 11.30 Uhr: Vorbesprechung in Raum 236 (Geb. 50.34)
  • 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 .

    Folien

    Literatur