Algorithm Engineering - Multicore-Programmierung mit der (MC)STL

  • Type: lab course
  • Chair: Prof. Dr. Peter Sanders
  • Location: SR 211, Geb. 50.34
  • Time:

    Dienstag 14.00 bis 15.30 Uhr

  • Start: 20.04.2007
  • Lecturer:

    P. Sanders, J. Singler

  • SWS: 2
  • Lv-No.: 24872
  • Exam:

    Nein

FTX von 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 Tempolate Library) implementieren wir eine parallelisierte Bibliothek grundlegender Algorithmen, kompatibel zur weitverbreiteten C++ Standard Template Library.

    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), Bitarray
    -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 Teilnehmer treffen sich alle zwei Wochen, um Ergebnisse und Erfahrungen auszutauschen.

    Die Programmierung erfolgt in C++ (Einführung wenn notwendig), Programmiererfahrung muss bereits vorhanden sein.

    Die Teilnehmer treffen sich alle zwei Wochen, um Ergebnisse und Erfahrungen auszutauschen.
    Ansprechpartner ist .

    Folien

    Arbeitsblätter