Rechneraufbau und Rechnerstrukturen, m. DVD-ROM

Kapitel 13 Grund-Konzepte und -Modelle für die Parallelverarbeitung (S. 407)

13.1 VLSI-Algorithmen. Systolische Netze

Die technischen Möglichkeiten zur Herstellung sehr großer integrierter Schaltungen forcieren die Entwicklung von Modellen für Parallelrechner. Eines der beliebtesten ist das klassische Modell der systolischen Netze. Hier wird in gewissem Sinne das Funktioneren des Blutkreislaufs, der durch den systolischen Druck gekennzeichnet ist, simuliert. Wir unterstellen hierzu (ähnlich wie in Abschnitt 5.4), dass die VLSITechnologie Schaltelemente zur Verfügung stellt, welche gewisse (einfache) Funktionen — wie Addition, Multiplikation oder Vergleich von (nicht notwendigen binären) Zahlen — ausführen können und welche auch eine gewisse Speicherkapazität besitzen.

Diese Schaltelemente, für welche wir hier auch die Bezeichnung " Prozessoren" verwenden, seien ferner billig herzustellen und, falls nötig, auch in hinreichend großer Zahl auf einem Chip verfügbar. Wie in der Einführung erwähnt, liegt der praktische Nutzen in der Möglichkeit, größere Aufgaben unter Umständen so in Teilaufgaben zerlegen zu können, dass deren Bearbeitung parallel erfolgen kann.

Dies hat in den letzten Jahrzehnten zur Entwicklung spezifischer Algorithmen für eine Reihe von Problemen (wie z. B. Suchen und Sortieren, Matrizenmultiplikation, Operationen auf Datenbanken, Pattern Matching, Polynom-Multiplikation, Bildverarbeitung) geführt, welche nicht nur schneller arbeiten als die vorher bekannten (sequentiellen) Algorithmen, viele dieser parallelen Algorithmen sind zudem auch darauf ausgelegt, direkt in geeigneter (VLSI-) Hardware ausgeführt zu werden, die softwaremäßige Realisierung (durch ein Programm) tritt dabei in den Hintergrund.

Wir stellen an die Hardware, welche zur Lösung eines bestimmten Problems zur Verfügung stehe, leicht zu erfüllende Anforderungen:

1. Es gibt Prozessoren mit je drei Ein- bzw. Ausgängen (welche an den Ausgängen über Delays verfügen, so dass jedes Ergebnis wenigstens für die Dauer eines Taktes gespeichert werden kann) der in Abbildung 13.1 gezeigten Art. (Diese Anforderung erfolgt nur exemplarisch im Hinblick auf ein von uns angestrebtes Beispiel, Varianten sind denkbar).

2. Die Arbeit eines Prozessors oder mehrerer gekoppelter Prozessoren des unter 1. beschriebenen Typs erfolgt getaktet, also unter der Synchronisation einer globalen Clock. Dies bedeutet insbesondere, dass Inputs in einem festgelegten Taktrhythmus eingelesen und Outputs im gleichen Rhythmus ausgegeben werden. Es sind verschiedene Arten der Kopplung von Prozessoren denkbar. Wir stellen einige davon hier und in den nachfolgenden Abschnitten dieses Kapitels (sowie im nächsten Kapitel) vor, wobei für das Folgende wesentlich ist, dass es zwischen einzelnen, beteiligten Prozessoren nur " lokale" Verbindungen gibt, so dass sich insgesamt eine regelmäßige Struktur ergibt:

(a) Prozessor-Reihe ( " Pipeline"): " Innere" Prozessoren haben jeweils zwei Nachbarn (vgl. Abbildung 13.2).

(b) Prozessor-Feld (Maschen-Verbindung, vgl. Kapitel 14 und dort speziell die Architektur des Rechners Illiac IV): " Innere" Prozessoren haben jeweils vier Nach- barn (vgl. Abbildung 13.3). Man erkennt, dass in diesem Feld eine Parkettierung der Ebene durch Quadrate (oder allgemeiner durch Rechtecke) zugrunde liegt. Hierdurch wird die Kopplung von inneren Prozessoren mit genau vier Nachbarn motiviert.