1. Einführung

In der Algorithmik (hier an der TU Chemnitz z.B. in den drei Kursen Algorithmen und Programmierung, Datenstrukturen und Theoretische Informatik I) fragen wir uns: welche Probleme können wir mit einem Rechner schnell und mit vertretbarem Speicherplatzaufwand lösen, und mit welchen Methoden? Üblicherweise behandelt so eine Veranstaltung Probleme wie Sortieren, Multiplizieren von großen Zahlen oder Matrizen, Erreichbarkeit in Graphen und auch schwierigere Probleme wie minimale Spannbäume, maximale Flüsse und Flussnetzwerken und allgemeine Optimierungsprobleme wie Linear Programming. Dabei wird sehr schnell klar, dass die Lösungswege (Algorithmen) unabhängig von konkreten Programmiersprachen sind und daher im Verlauf der drei oben genannten Veranstaltungen der Fokus immer weiter weg von der konkreten Programmierung und hin zu allgemeinen Konzepten geht. Nur am Rande geht es in diesen Kursen auch um die Frage, für welches Rechnermodell wir denn diese Algorithmen entwerfen. Diese Nachlässigkeit ist im Nachhinein gerechtfertigt, weil sich alle Modelle als mehr oder weniger äquivalent zur Mehrband-Turingmaschine (siehe z.B. Kapitel 7 in Theoretische Informatik II) herausstellen. Diese Sichtweise kehr natürlich vieles unter den Teppicht, zum Besipiel I/O-Komplexität, Cache-Management und Pipelining. Aber im Allgemeinen gilt: wir machen uns wenig Gedanken über Rechnermodelle oder gar Programmiersprachen, wenn wir Algorithmen entwerfen.

Im Bereich der parallelen Algorithmen untersuchen wir nun, wie man mit dem Einsatz von sehr vielen Rechnern, die alle gleichzeitig arbeiten, ein Problem noch schneller lösen kann - ob man es also effizient parallelisieren kann. Dafür muss man im Verlgeich zur "normalen" Algorithmik neue Denkweisen und Techniken entwickeln. Wir müssen uns auch mehr Gedanken machen über unser Rechnermodell, und da ist es leider auch nicht "das Richtige". Daher werden wir in diesem Kurs verschiedene Modelle betrachten und somit auch für "einfache Probleme" verschiedene Lösungen erarbeiten. Ich werde nun ein paar Modelle für paralleles Rechnen skizzieren, die wir behandeln werden.

  • Boolesche Schaltkreise. Die kennen Sie bestimmt schon aus anderen Veranstaltungen. Schön an Ihnen ist, dass sie erstens inhärent parallel arbeiten und zweitens physikalisch realisierbar sind. Wir werden am Anfang von Kapitel 2 ein paar Schaltkreise sehen, dann aber schnell feststellen, dass sie uns einen zu eingeengten Blickwinkel geben.
  • Parallel Random Access Machine (PRAM). In diesem Modell gibt es viele Prozessoren, die synchron getaktet sind und einen gemeinsamen Speicher lesen und schreiben können. Es ist das am Besten untersuchte Modell für paralleles Rechnen. Wir werden lernen, wie man viele klassische algorithmen Probleme Sortieren, Zusammenhangskomponenten in Graphen, Determinanten von Matrizen berechnen, Matchings in bipartiten Graphen etc. effizient auf einer PRAM löst. Wir werden uns über PRAMs als Modell Gedanken machen:
    • Welche Komplexitätsmaße sind interessant? Wir betrachten hier zwei Maße: vor Allem natürlich die Zeit, die benötigt wird, bis die Prozessoren das Problem gelöst haben, aber auch die Gesamtarbeit, also die Anzahl der Rechnerschritte, die die Prozessoren gemeinsam getätigt haben.
    • Können wir davon ausgehen, dass wir unbeschränkt viele Prozessoren haben? Auf den ersten Blick nein, auf den zweiten Blick ja.
    • Wie wird der gemeinsame Speicher verwaltet? Dürfen verschiedene Prozessoren gleichzeitig eine Speicherzelle lesen? Gleichzeitig in eine Zelle schreiben? Die Antwort auf diese Fragen wird zu leicht verschiedenen PRAM-Modellen führen die aber glücklicherweise alle mehr oder weniger äquivalent sind.
    • In welchem Verhältnis stehen PRAMs zu Modellen, die wir bereits kennengelernt haben, wie Booleschen Schaltkreisen oder Turingmaschinen? Hier wartet eine Überraschung auf uns: wenn wir ein wenig großzügig mit unserem Begriff von Effizienz sind, dann sind die Probleme, die sich gut parallelisieren lassen, genau diejenigen, die auf einer traditionellen Mehrband-Turingmaschine mit wenig Speicherplatz lösbar sind. Es gibt also einen Zusammenhang zwischen sequentiellem Platz und paralleler Zeit.

    Soweit ich es überblicken kann, sind Fortschritt und Interesse im Bereich der PRAM-Algorithmen und den Neunzigern und Nullerjahren stagniert, was wohl auch daran lag, dass dieses Modell physikalisch nicht gut realisierbar ist, oder genauergesagt die in der Realität zeitraubensten Faktor vernachlässigt: die Kommunikation der Prozessoren mit dem Speicher und untereinander. In der Praxis stellt sich nämlich heraus, dass der Engpass gar nicht die Zahl der einzelnen Rechenschritte ist, sondern die Speicheroperationen. Noch gravierender wird das, wenn wir moderne Szenarien betrachten, in denen es nicht um viele Prozessoren in einem Rechner mit einem Speicher geht, sondern um tausende von separaten Rechern, die über ein Netzwerk kommunizieren. Und in diesem Szenario ist häufig die Kommunikation zeitraubender als alles andere. Dies motiviert ein weiteres Modell:

  • Massiv parallele Algorithmen (MPA). In diesem Modell haben wir es mit einer großen Anzahl von Rechnern zu tun, von denen jeder üben einen lokalen Speicher verfügt. Der Speicher ist aber nicht groß genug, um die Gesamtmenge der Eingabedaten zu halten (denken Sie an Web-Suche und den Web-Graphen, der so groß ist, dass Sie ihn nur verteilt speichern können). In diesem Modell ignorieren wir vollkommen die Laufzeit der Berechnungen, die lokal auf den einzelnen Rechnern stattfinden und interessieren uns vor Allem dafür, wie oft die Rechner untereinander Daten austauschen müssen: für die Anzahl der Kommunikationsrunden. Dieses Modell ist recht jung - die ersten wissenschaftlichen Artikel stammen aus den frühen Zehnerjahren. Das Problem dabei ist, dass es meines Wissens noch nicht wirklich Lehrbücher zu dem Thema gibt und wir uns auf Vorlesungsskripte und Paper stützen müssen.

Literatur