Parallele Algorithmen

  • Typ: Vorlesung (V)
  • Zielgruppe: Master
  • Semester: WS 24/25
  • Ort:

    Geb. 50.34, Hörsaal -101

  • Zeit:

    Montag 15:45 - 17:15

  • Dozent:

    Prof. Dr. Peter Sanders
    Lukas Hübner
    Tim Niklas Uhl
    Hans-Peter Lehmann

  • SWS: 2/1
  • LVNr.: 2400053
  • Prüfung:

    Prüfungsleistung besteht aus Übungsleistung + mündlicher Prüfung

  • Hinweis: Präsenz

Das Passwort für den ILIAS-Kurs erhalten Sie in der ersten Vorlesung.

Inhalt

Modelle und ihr Bezug zu realen Maschinen:

  • shared memory - PRAM
  • Message Passing, BSP
  • Schaltkreise

Analyse: Speedup, Effizienz, Skalierbarkeit

Grundlegende Techniken:

  • SPMD
  • paralleles Teilen-und-Herrschen
  • kollektive Kommunikation
  • Lastverteilung

Konkrete Algorithmen (Beispiele)

  • Kollektive Kommunikation (auch für große Datenmengen):Broadcast,Reduce,Präfixsummen,all-to-all exchange
  • Matrizenrechnung
  • sortieren
  • list ranking
  • minimale Spannbäume
  • Lastverteilung: Master Worker mit adaptiver Problemgröße, random polling, zufällige Verteilung

Erfolgskontrollen

Gewichtung: 80% mündliche Prüfung, 20% Übung