Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

17.04.1987 - 

Experimente mit DAP-2 an der Universität Erlangen:

Parallelcomputer steigern die Rechenleistung

Eine besondere Spezies der Parallelrechner stellen die Feldrechner dar. Bei ihnen sind die Prozessorelemente in einer Matrix angeordnet. Die Kommunikationsverbindungen lassen sich flexibel aufbauen, wodurch diese Anordnungen sehr vielseitig eingesetzt werden können. Die Erlanger Universität experimentiert mit einer solchen Maschine, der ersten ihrer Art in der Bundesrepublik.

George Boole (1815 - 1864) und Charles Babbage (1792 - 1871) in England sind durch die Formalisierung der Logik beziehungsweise durch erste apparative Techniken ohne Zweifel die Urväter heutiger Rechenanlagen. Jedoch erst die elektrische und elektronische Realisierung seit den 30er Jahren (Konrad Zuse in Deutschland) beziehungsweise den 40er Jahren (John von Neumann in den USA) hat zu den Umwälzungen geführt, die seit knapp 30 Jahren ohne Unterbrechung über uns kommen. Da Rechenmaschinen insbesondere hilfreich sind bei der Entwicklung leistungsfähigerer und kostengünstigerer neuer Rechenmaschinen in Verbindung mit der automatischen Fertigung von Schaltkreisen sehr hoher Packungsdichte, wird diese Entwicklung zusätzlich beschleunigt. Auch die Verbesserungen der Halbleitertechnik und die Einbeziehung anderer physikalischer Effekte tragen nach wie vor zur Leistungssteigerung neuerer Rechnerentwicklungen bei.

Immer mehr jedoch treten neben dem Bemühen um die Verbesserung der Technologie Strukturfragen in den Vordergrund. In Anlehnung an klassische Begriffe spricht man dabei von der Architektur von Rechensystemen. Es hat sich schon früh gezeigt, daß die Auslastung und Verfügbarkeit von Systemen durch angemessene Strukturen wesentlich verbessert werden kann.

Koppelt man mehrere Rechner eines Typs in enger Nachbarschaft miteinander kann man - meist parallele - Verbindungen höherer Übertragungsleistung vorsehen. Da die Rechner aus den normalerweise räumlich getrennten Komponenten Speicher und Prozessor bestehen, bedeuten die Kopplungen Verbindungen zwischen diesen Komponenten. Das können Punkt-zu-Punkt-Verbindungen sein oder sogenannte Busleitungen an denen mehrere Komponenten angeschlossen sind. Im letzteren Fall sind die zu übermittelnden Informationen für den jeweiligen Empfänger gekennzeichnet durch zusätzliche Angaben.

Derartige Multiprozessorsysteme bieten durch die unterschiedlichen Verbindungsarten mit unterschiedlicher Übertragungsleistung und dem unterschiedlichen Vernetzungsgrad ein weites Feld zur Systemkonfiguration mit zahlreichen, teilweise noch ungelösten Problemen der Programmorganisation. Untersuchungen dieser Art werden meist mit Hilfe von Baukastensystemen durchgeführt mit denen man die jeweiligen Verbindungsstrukturen bei Bedarf schnell aufbauen kann. Das Institut für Mathematische Maschinen und Datenverarbeitung der Universität Erlangen-Nürnberg befaßt sich seit mehreren Jahren mit der Effizienz und Fehlertoleranz solcher Systeme. Multiprozessorsysteme dieser allgemeinen Struktur haben bisher allerdings noch keine kommerzielle Bedeutung erlangt..

Die Rechnerhersteller haben in der Vergangenheit zur Steigerung der Rechenleistung durch Parallelverarbeitung vielmehr zwei andere Möglichkeiten aufgegriffen, die zu regulären Strukturen führten:

Vektor- oder Pipeline-Rechner gehören zur Zeit zu den leistungsfähigsten Rechnern auf dem Markt. Anbieter sind zum Beispiel Control Data, Cray Research, Fujitsu und Hitachi. Derartige Rechner erreichen Rechenleistungen von 200 - 1000 MFlops, das sind 1 Milliarde Gleitkomma-Operationen pro Sekunde. Sie werden durch eine fließbandähnliche Verarbeitung erzielt. Das Skalarprodukt zweier Vektoren ergibt sich zum Beispiel in der Form u x v =u1 x v1 + u2 x v2 +...+ un x vn.

Jeder Summand ui x vi stellt darin eine Teilaufgabe dar, die ihrerseits wieder aus mehreren Teilschritten besteht, wie: Zerlegen in Exponent und Mantisse, Multiplikation der Mantissen, Ermittlung des Produktexponenten, Normalisierung des Produktes, Summation, Normalisierung der Summe und schließlich Zusammensetzung des Ergebnisses aus der resultierenden Mantisse und dem zugehörigen Exponenten. Jede dieser Teilaufgaben wird von speziellen Bearbeitungsstationen wie an einem Fließband ausgeführt.

Die Station mit der längsten (kritischen) Bearbeitungszeit bestimmt das Tempo und den Durchsatz am Fließband. Nach einer Anlaufphase und vor Erreichen der Auslaufphase arbeiten demnach alle Stationen des "Fließbandes" an der Berechnung des Skalarproduktes. Es strömen also Operandenpaare ui, vi mit (der kritischen) Geschwindigkeit aus dem Speicher in das Rechenwerk. Meist ist bei solchen Rechenanlagen die Verarbeitungsleistung durch die Schreib-/Lesegeschwindigkeit bestimmt und nicht durch das Pipeline-Rechenwerk. Für den Durchsatz solcher Systeme ist sehr oft auch bestimmen, ob die Komponenten der Vektoren u und v auf benachbarten Speicherplätzen stehen, um die Zugriffszeiten klein zu halten. Die Parallelverarbeitung besteht bei solchen Pipeline-Rechnern darin, daß zu einem bestimmten Zeitpunkt die einzelnen Bearbeitungsstellen zwar gleichzeitig tätig sind, aber für verschiedene Operanden.

Feldrechner schließlich stellen eine zweite kommerzielle Variante von Parallelrechnern dar. Ihr Marktanteil ist jedoch zur Zeit noch geringer als bei den Pipeline-Rechnern. Das mag daran liegen, daß die amerikanischen Firmen diese zweite Möglichkeit der Parallelverarbeitung erst neuerdings aufgreifen, um eine zusätzliche Leistungssteigerung zu erzielen. Angestrebt werden dabei Systeme, die etwa 1000mal schneller sind, also 1 TFlop pro Sekunde, das sind 10e12 = eine Billion Gleitkomma-Operationen pro Sekunde. Die britische Computerfirma ICL (International Computer Limited) hat bereits Anfang der 70er Jahre Überlegungen für einen derartigen Feldrechner angestellt, den DAP (Distributed Array Processor). Die Pilotversion war zwei Jahre später fertig und bestand aus einem Feld von 32x32 = 1024 Prozessoren mit je 1024 = 2e10 Binärstellen (1 Kilobit) als Speicher. Sechs Jahre später wurden 1980 die ersten Systeme in England ausgeliefert mit 64 x 64 = 4096 Prozessoren und 4 KBit = 4096 Binärstellen je Prozessor als Speicher. Dieser Speicher wurde teilweise später auf 16 KBit pro Prozessor = 8 Megabyte Gesamtspeicher erhöht.

Bei all diesen Systemen war der DAP Bestandteil eines normalen Großrechners (Host). In dieser Form war der Speicher des DAP Bestandteil des Speichers des Host-Rechners. Der Host konnte also diesen Speicher zur Arbeitsvorbereitung mit Befehlen und Daten für den DAP füllen und die Ergebnisse des DAP aus diesem Speicher wieder abholen und ausgeben. In dieser Form war der DAP ein Speicher mit eigener Verarbeitungseinheit.

Seit Frühjahr 1986 wurden zehn Exemplare des Prototyps DAP-2 in England ausgeliefert. Einen davon erhielt die Universität Erlangen-Nürnberg im Rahmen eines Forschungsprojektes der Deutschen Forschungsgemeinschaft zur Untersuchung paralleler Rechenmöglichkeiten bei technisch-wissenschaftlichen Problemen.

Der DAP-2 in Erlangen hat 32 x 32 = 1024 Prozessoren mit je 8 KBit Speicher entsprechend 1 Megabyte Gesamtspeicher. Der Maschinenzyklus beträgt 155 Nanosekunden, der Rechner kann also 6,6 Milliarden 1-Bit-Operationen pro Sekunde ausführen. Als Host-Rechner dient ein Perq 2 mit einem hochauflösenden Bildschirm (1024 mal 768 Punkte) für Grafikausgabe und einem Unix-Betriebssystem. Die Übertragungsrate zwischen DAP-2 und Perq 2 beträgt 1,5 Megabyte pro Sekunde.

Der kompakte Aufbau des DAP-2 wurde erreicht durch Ausführung der Prozessoren in Gate-Array-Technik.

Es ist geplant, einen DAP-3 in VLSI-Technik zu realisieren. In dieser Form kann der DAP-3 an verschiedene Hostrechner (zum Beispiel die MicroVAX-II von Digital Equipment) angeschlossen werden. Der DAP-3 ist ähnlich strukturiert wie der DAP2. Er unterscheidet sich von diesem durch die Größe des Prozessorfelds und der Speicherausbau.

1024 Ergebnisse gleichzeitig

Jeder Prozessor (Processor Element) besitzt vier 1-Bit-Register: Q, A, C, D. Q ist der Akkumulator, C nimmt eventuelle Überträge auf. A ist das Activity-Register. Wenn A = 0 gesetzt wurde, beteiligt sich der betroffene Prozessor nicht an der nächsten Operation. Es sei daran erinnert, daß ja zu einer Taktzeit alle 1024 Prozessoren denselben Befehl zur Ausführung erhalten. Den jeweiligen Operanden im Speicher findet jeder Prozessor in seinem Bereich von 8-KBit-/16-KBit-Größe. In diesem Bereich wird jedes Bit adressiert mit 28-Bit-Adressen. Das entspricht einem maximalen Bereich von 2e28 = 256 MBit Adreßumfang.

Da alle Prozessoren zu einem gegebenen Zeitpunkt in ihrem Speicher dasselbe Bit adressieren, spricht man von der zugehörigen Speicherebene von 32 x 32 = 1024 Bit und nennt diese Art der Bearbeitung Matrix-Modus. Will man zum Beispiel zwei Matrizen mit ganzen Zahlen, bestehend aus n Stellen, addieren: Z = X + Y, so bearbeitet jeder Prozessor gleichzeitig mit den 1023 anderen Prozessoren seine Daten der Reihe nach:

X0 +Y0+C------> Z0,

X1 +Y1+C------> Z1,

Xi + Yi + C-----> Zi,

Xn-1 + Yn-1 + C -> Zn-1,

Übertrag jew. nach C

Dies ist also eine serielle Addition der Operanden X und Y, die aus n Elementarschritten besteht. Da zu jedem Zeitpunkt bis zu 1024 Teilergebnisse berechnet werden, ergibt sich der Faktor 1024/n gegenüber einem gleichschnellen Rechner mit parallelem Addierwerk. Ein wesentlicher Vorteil dieser seriellen Bearbeitung ist, daß man nicht festgelegt ist auf die Länge der Operanden wie bei üblichen Registermaschinen, die heute üblicherweise 8, 16, 32 oder 64 Bit Lang sind.

Diese bitweise Verarbeitung ist auch darüber hinaus von grundlegender Bedeutung. Zumindest der Systemprogrammierer kann auf diese Weise Programmhilfsmittel herstellen für den allgemeinen Gebrauch, die wesentlich schneller sind als übliche Algorithmen. Man bezeichnet solche Techniken als Bit-Algorithmen. Die Ermittlung der Quadratwurzel aus einer ganzen Zahl ist ein solcher Algorithmus. Er ist schneller als eine Multiplikation.

Auch andere Funktionen wie die trigonometrischen Funktionen sin, cos, tg, deren Umkehrfunktionen, der Logarithmus und die Exponentialfunktion als eine Umkehrfunktion sind effizient berechenbar. Logarithmus und Exponentialfunktion ist nötiger etwa zwei Multiplikationszeiten, sin und cos zusammen weniger als drei solche Zeiten.

Im Matrixmodus berechnen die 1024 Prozessoren also gleichzeitig und voneinander unabhängig ihre Ergebnisse. Will man jedoch mehrere Prozessoren zusammen einsetzen zur gemeinsamen Berechnung eines Ergebnisses, so wird eine Kommunikationsmöglichkeit zwischen den Prozessoren notwendig.

Man spricht dann statt vom Matrixmodus vom Vektormodus. Die einzelnen Binärstellen eines Operanden wurden benachbarten Prozessoren zugeordnet. Zum Beispiel nimmt man bei üblichen Zahlenlängen von 32 Bit die 32 Prozessoren einer Prozessorzeile für die Durchführung einer Operation. Auf diese Weise können unter Einsatz aller 32 x 32 Prozessoren gleichzeitig 32 solche Operationen ausgeführt werden. Bei der Addition Z = X+Y werden also alle Binärstellen der Operanden X und Y gleichzeitig addiert und in maximal sechs Schritten (log2 32= 6) die eventuell entstehenden Überträge abgebaut.

Für derartige Anforderungen sind die Prozessoren und ihre Register in nächster Nachbarschaft (Nord, Ost, Süd, West) miteinander verbunden (Bild).

Es gibt Schiebebefehle, die alle Registerinhalte der 32 x 32 Register einer Registerebene um eine Position nach Norden, Osten, Süden oder Westen verschieben. Das kann planar geschehen, dabei werden Nullen nachgezogen und aus dem Feld hinausgeschobene Binärstellen (Bits) gehen verloren. Bei zyklischem Schieben andererseits werden die Ränder zyklisch miteinander verbunden (Ringshift). Eine dritte Möglichkeit besteht darin, die Registerebene spaltenweise zu verketten, so daß (32,1) mit (1,2), (32,2) mit (1,3), ..., (32,31) mit (1,32) verbunden sind in Form eines langen Vektors mit. 32 x 32 = 1024 Stellen. Bei zyklischer Verkettung dieser Art ist zusätzlich (1,1) mit (32,32) verbunden, so daß ein Ring mit 1024 Stellen entsteht.

Mit Hilfe derartiger Elementarmöglichkeiten sind eine Vielzahl von Algorithmen realisiert, die dem Benutzer in einer erweiterbaren Programmbibliothek zur Verfügung stehen. Hierzu gehören auch sehr effiziente Sortierverfahren.

Für einen Benutzer des DAP taucht zu allererst die Frage auf, ob er seine bisherigen Programme - die er für konventionelle Rechner geschrieben hat - beziehungsweise die Algorithmen, die diesen Programmen zugrunde liegen, weiterverwenden kann, oder ob er neue Algorithmen entwickeln muß.

Die Antwort ist weder ein klares Ja noch ein klares Nein; sie ist problemabhängig. Dies soll ein einfaches Beispiel verdeutlichen, nämlich die Lösung linearer Gleichungsysteme nach Gauß-Jordan: An seriellen Rechnern ist es üblich, Ax = b dadurch zu lösen, daß man die Matrix A auf Dreiecksform bringt und dann durch Rückrechnung die Variablen Xn, ..., X1 bestimmt.

Für den seriellen Rechner ist dies hinsichtlich der Anzahl der auszuführenden arithmetischen Operationen die effizienteste Rechenweise. Für den DAP jedoch gilt, daß bei diesem Verfahren ein Großteil der Prozessoren pausiert und damit die Leistungsfähigkeiten sinkt. Durch eine geringfügige Modifikation des Verfahrens kann man die Rückrechnung einsparen.

Der kleine Unterschied, der am DAP (sehr wohl aber an seriellen Rechnern) keine zusätzliche Rechenzeit kostet, ist einfach erklärt.

Beim Gauß-Jordan-Verfahren wird im i-ten Rechenschritt ein Vielfaches der i-ten Zeilen von den Zeilen i+1, i+2, ... n subtrahiert.

Im modifizierten Verfahren für den DAP wird im i-ten Zeile von allen Zeilen <>i subtrahiert. Auf diese Weise kommt man statt zu der Dreiecksmatrix mit Rückrechnung zur Einheitsmatrix ohne Rückrechnung.

Bei der Anpassung vorhandener Algorithmen beziehungsweise Programmen geht man sinnvollerweise in drei Schritten vor:

1. Schritt:

Umwandlung offensichtlicher Parallelität, wie sie zum Beispiel in DO-Schleifen auftritt.

2. Schritt:

Umwandlung versteckter Parallelität, zum Beispiel wie sie bei der Bearbeitung von Teilen einer Matrix - etwa in Zeilen oder Spalten - auftritt

3. Schritt:

Integration spezieller DAP-Fortran-Funktionen, wie Schiebeoperationen auf Matrizen, Maximum/Minimumsuche, Mischen.

Die dabei erzielten Beschleunigungswerte gegenüber konventionellen Großrechnern hängen stark von der Problemstellung beziehungsweise von den verwendeten Algorithmen ab. Generell kann man aber sagen, daß der CPU-Bedarf um eine Zeitdimension sinkt, das heißt, lag er früher im Minutenbereich, liegt er jetzt im Sekundenbereich.

Dr. Karl Dieter Reinartz ist Akademischer Direktor am Lehrstuhl für Informatik VII der Universität Erlagen-Nürnberg; Dr. Werner Erhard ist Wissenschaftlicher Mitarbeiter am gleichen Lehrstuhl.