Der erfolgreiche Einsatz von Rechnern bei der Lösung von Problemen in
fast allen Lebensbereichen beruht u.a. auf der technologischen
Entwicklung, die zu schnelle- ren Rechnern mit größerem Speicher führte,
auf der größeren Benutzerfreundlich- keit der Rechner und auf
effizienteren Algorithmen zur Lösung der betrachteten Probleme. Dieses
Buch befaßt sich mit dem Entwurf effizienter Algorithmen für
grundlegende Probleme, die häufig als Teilprobleme in komplexeren
Problemen auftreten. Während auf der unteren Ebene der Hardware von
Rechnern, also in Schaltkreisen, Schaltwerken und VLSI-Chips, schon
immer mit einem hohen Grad an Parallelität gearbeitet wurde, konnte auf
höherer Ebene lange Zeit nur sequentiell gerechnet werden. Dies ändert
sich nun durch die Entwicklung von Rechnern mit immer mehr Prozessoren.
Das Buch legt daher einen Schwerpunkt auf Algorithmen, die gleich-
zeitig bezüglich paralleler Rechenzeit und Hardwaregröße (bei
Hardwarelösungen) bzw. bezüglich paralleler Rechenzeit, Zahl der
benutzten Prozessoren und Spei- cherplatz (bei Softwarelösungen)
effizient sind. Es werden effiziente Algorithmen für den Entwurf
optimaler P LA's diskutiert. Danach werden die grundlegenden
arithmetischen Funktionen Addition, Subtrak- tion, Multiplikation und
Division, die symmetrischen Funktionen, die auch als Zählfunktionen
bezeichnet werden können, und Speicherzugriffsfunktionen behan- delt. In
diesem Teil des Buches werden vor allem Hardwarelösungen präsentiert.
Für das Rechnen mit Matrizen, einfache Probleme auf Graphen,
Sortierprobleme und Probleme der Elementaren Zahlentheorie werden
effiziente Softwarelösungen vorgestellt. Das Buch enthält außerdem
allgemeine Methoden der automatischen Parallelisierung sequentieller
Algorithmen, Reduktionskonzepte zum Vergleich der Komplexität der
behandelten Probleme und effiziente Simulationen zwischen den benutzten
Rechenmodellen.
