Univ-Logo Universität Karlsruhe (TH) – Fakultät für Informatik
 
Institut für Theoretische Informatik

Algorithmik II
 
ph

Vorlesumg

Parallele Algorithmen

Von billigen Mikroprozessoren, die Multithreading unterstützen bis zu Peer-to-Peer-Netzwerken mit Millionen beteiligter Computer wird Parallelverarbeitung von einer Spezialanwendung für wissenschaftliches Rechnen zunehmend zur Conditio sine qua non, wenn es um effektive Ausnutzung moderner Computertechnik geht.

Earthsim

Diese Vorlesung erklärt grundlegende algorithmische Techniken zur Beherrschung paralleler Rechner.

  • Einfache Programmiermodelle, die den Entwurf portabler und skalierbarer paralleler Algorithmen erlauben.
  • Grundlegende Kommunikationsmuster zwischen Prozessoren und ihre effektive Implementierung.
  • Lastverteilung: wie kann man komplizierte Berechnungen so verteilen, dass alle Prozessoren gleich viel zu tun haben?
  • Wie parallelisiert man grundlegende sequentielle Algorithmen: Sortieren, Datenstrukturen, Graphenalgorithmen, …

Die Vorlesung ist so angelegt, dass sie mit Vorlesungen aus den Vertiefungsgebieten Parallelverarbeitung und Algorithmik gleichermaßen gut kombinierbar ist, d. h. geringe Überlappungen und keine Vorraussetzungen jenseits der Algorithmentechnik.

Zeit: Mittwochs, Mittwochs, 15.45–17.15, SR 235, Informatikgebäude
Materialien

  1. Vorlesungsfolien bis 25.5.05
  2. Vortrag zu all-to-all auf SMP-Clustern und das Papier dazu.
  3. PRAM Vorlesung
  4. Paper zu parallelen priority queues
  5. Vorlesungsfolien ab 8.6.05

Web: Thomas Käufl, kaeufl@ira.uka.de
Letzte Änderung: 28. Apr. 2005