Parallelverarbeitung spielt bei der Bewältigung großer Berechnungsprobleme eine zunehmend wichtige Rolle. Mit der Entwicklung dafür geeigneter Hardware ging die Untersuchung prinzipieller Möglichkeiten und Grenzen anhand einer Reihe unterschiedlich abstrakter Modelle einher. In diesem Buch werden einige von ihnen vorgestellt. Die jeweils erzielbaren Geschwindigkeitssteigerungen werden anhand einfacher Beispiele und mit Hilfe komplexitätstheoretischer Methoden aufgezeigt. Die behandelten Modelle wurden so ausgewählt, daß ihre Verwandtschaft mit verschiedenen Entwürfen und Realisierungen von Parallelrechnern, die im zweiten Teil des Buches skizziert werden, erkennbar ist.

Klappentext

Motivationen fUr da.., Verfassen von Blichern gibt es zweifellos viele. Wodurch aber wird die Wahl eines Thenlas bestimmt? Kenntnisse und Vorlieben spielen sicher­ lich eine Rolle, aber es muB doch noch die lJberzeugung hinzukommen, daB das behandelte Gebiet nicht nur fUr die Autoren von Bedeutung sei. U nd so geht es lIns mit "Parallelverarbeitung". Einzelne Grlinde dafUr sind im Buch aufgefUhrt, kurz gesagt glauben wir, daB sich eine Begegnung mit ihr nicht vermeiden laBt lind daB darliberhinaus zumindest einige ihrer Prinzipien genligend Interesse beanspruchen dlirfen. Daher haben wir eine EinfUhrung verfaBt, die zu einem Einstieg in dieses Gebiet verhelfen soli. Unter dem Aspekt des Erkennens gewisser (einfacher) Musterklassen werden im ersten Teil verschiedene Modelle von Automaten, die unterschiedliche Modi der Parallelverarbeitung reprasentieren, eingefUhrt, lind sie werden mit dem "Referenzmodell" der (sequentiellen) Turingmaschine sowie teilweise untereinan­ der verglichen. 1m zweiten Teil wird dargestellt, welche Bezlige diese Modelle zu Rechnerarchitekturen besitzen. Da es uns darauf ankam, die Konzepte herauszuarbeiten, werden ein Teil des Stoffes informell vorgestellt und "technisch aufwendige" Beweise oft nur skizziert. Perso­ nen mit Grundkenntnissen aus den Bereichen Formale Sprachen, Komplexitats­ theorie und Rechnerarchitektur, wie sie liblicherweise zum Ende des Infonnatik­ Grundstudiums zu erwarten sind, sollte die Lektlire keine Schwierigkeiten bereiten.

Inhalt
I: Modelle.- 1 Turingmaschinen.- 2 Zellularräume.- 3 Systeme von Turing-Automaten.- 4 Parallele Registermaschinen.- 5 Uniforme Schaltkreisfamilien.- 6 Pipelineverarbeitung in Trellis- und Zellularautomaten.- 7 Maschinenklassen, Berechnungshypothesen, Realisierbarkeit.- II: Maschinen.- 8 SIMD-Rechner.- 9 MIMD-Rechner.- 10 Pipelinerechner.- A Einige allgemeine Definitionen und Schreibweisen.- B Literaturverzeichnis.- C Stichwortverzeichnis.