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.

Höchste Rechenleistungen erfordern neue Architekturen


18.10.1991 - 

Hypercubes als Basis für die massiv-parallelen Systeme

Die Anforderungen an die Leistung der Supercomputer sind in den letzten Jahren sowohl für technisch-wissenschaftliche als auch kommerzielle Anwendungen wie zum Beispiel Datenbanken beträchtlich gestiegen. Um diesen Anforderungen überhaupt noch gerecht werden zu können, bedarf es jetzt schon, mehr noch in Zukunft, verstärkt des Einsatzes von Parallelrechner-Systemen.

Bei Gflops kommt man noch mit Einzelprozessoren aus, doch schon hier ist die Leistung nur durch parallele Hardware innerhalb der CPU möglich. Tflops sind dann nur noch über massiv-parallele Systeme realisierbar. Das liegt vor allem daran, daß die Einzelprozessoren im Gflops-Bereich an physikalische Grenzen stoßen. Diese Grenzen sind für Mikroprozessor-Chips massiv-paralleler Systeme jedoch noch in weiter Ferne. Nun gibt es im wesentlichen zwei Arten paralleler Systeme, sie unterscheiden sich durch die Organisation des Speichers.

Shered- oder Distributed Memory

Bei "Shared-Memory"-Systemen greifen alle Prozessoren auf ein und denselben Speicher zu. Sie kommunizieren über gemeinsame Datenstrukturen im Shared Memory. Die Datentransfer-Rate aller Prozessoren von beziehungsweise zu dem Shared Memory ist der begrenzende Faktor für die Gesamtleistung des Systems. Kann die Speicherbandbreite nicht mitwachsen, wenn die Anzahl der Prozessoren erhöht wird, so ist die Erweiterbarkeit von Shared-Memory-Systemen stark eingeschränkt.

Tatsächlich hat in den letzten Jahren die Prozessorleistung weitaus schneller zugenommen als die Speicherbandbreite, ja sie läuft dieser in manchen Fällen sogar davon. Dies liegt vor allem an der Komplexität des Netzwerks, welches die Prozessoren mit dem Shared Memory verbindet. Es zeigt sich, daß es fast unmöglich ist, Prozessorleistung und Speicherbandbreite in Shared-Memory-Systemen gleichförmig zu entwickeln. Dies ist einer der wesentlichen Gründe, warum Tflops-Computer mit Shared-Memory-Architektur nicht zu realisieren sind.

In einem "Distributed-Memory"-System besitzt jeder Prozessor seinen eigenen lokalen Speicher. Ein Netzwerk aus Kommunikationskanälen (IPC channels: Inter-Processor Communication channels) verbindet alle Prozessoren untereinander; es ermöglicht den Austausch von Daten und Programmen (Messages). Da sich die Maximalleistung des Gesamtsystems aus der Summe der Leistung der Einzelprozessoren ergibt, werden an die Speicherbandbreite des lokalen Speichers bei weitem nicht so hohe Anforderungen gestellt wie bei den Shared-Memory-Systemen. Das bedeutet, daß man beim Speicher

nicht mehr an die physikalischen Grenzen der Chip-Technologie zu gehen braucht. Von wesentlicher Bedeutung für die Leistungsfähigkeit und Erweiterbarkeit von Parallelsystemen mit Distributed Memory ist nun aber die Verbindungsstruktur der Prozessoren untereinander, da Informationen zwischen den einzelnen Prozessoren über dieses Netzwerk aus IPC-Kanälen ausgetauscht werden.

Im weiteren werden nur Distributed-Memory-Systeme mit MIMD-Struktur betrachtet (MIMD = Multiple Instruction, Multiple Data). Sie sind weitaus flexibler einsetzbar als SIMD-Systeme (SIMD = Single Instruction, Multiple Data), bei denen ein und dieselbe Instruktion auf allen Prozessoren zeitgleich ausgeführt werden muß. SIMD-Systeme lassen sich vereinfacht auch als Vektorrechner für extrem lange Vektoren klassifizieren.

Die scheinbar offensichtlichste Verbindungsstruktur würde jeden Prozessor mit jedem anderen Prozessor verbinden ("Full Interconnect") - dabei werden Messages über einen IPC-Kanal direkt vom Quellprozessor zum Zielprozessor transferiert. Obwohl die maximale Weglänge für dieses Netzwerk gleich 1 und damit optimal ist, hat es zwei entscheidende Nachteile: Erstens wächst die Anzahl der Verbindungen quadratisch mit der Anzahl der Prozessoren. Für ein massiv-paralleles System mit 256 Prozessoren sind schon 39 640 Verbindungen notwendig. Zweitens würde die Erweiterung eines bestehenden Netzes um einen einzelnen Prozessor bedeuten, daß bei jedem bereits vorhandenen Prozessor ein weiterer IPC-Kanal hinzugefügt werden muß, eine technisch kaum zu realisierende Aufgabe.

Ein realisierbares Netzwerk wird weniger dicht (weniger IPC-Kanäle) sein als das "Full Interconnect", sich dafür aber wesentlich leichter erweitern lassen. Hier kristallisieren sich nun zwei Topologien heraus: Gitter und Hypercube.

Innerhalb eines zweidimensionalen Gitters wird jeder Prozessor mit seinen Nachbarn verbunden. Um die Unsymmetrie dieser Struktur aufzuheben - die Prozessoren auf den Rändern haben teilweise nur zwei oder drei Nachbarn, die anderen aber vier - werden die Ränder zusätzlich miteinander verbunden. So ergibt sich eine torusähnliche Netztopologie; jeder Prozessor ist mit vier weiteren verbunden. Diese Topologie läßt sich leicht realisieren: vier IPC-Kanäle pro Prozessor stellen keine zu großen Anforderungen an das Design. Daher wird sie vor allem dann eingesetzt, wenn für den Einzelprozessor Standard-Chips verwendet werden. So kann der zusätzliche Hardware-Aufwand auf dem Board für die IPC-Kanäle klein gehalten werden. Der Nachteil ist offenkundig: Beim Gitter handelt es sich um eine statische Topologie. Koppelt man zwei torusähnliche Netze miteinander, so werden keine zusätzlichen Verbindungen neu geschaffen, sondern nur vorhandene umfunktioniert. Dieses Netzwerk wächst nicht mit, wenn die Anzahl der Prozessoren erhöht wird.

Eine weitaus leistungsfähigere Topologie, welche dynamisch bis zu einer Obergrenze mit der Anzahl der Prozessoren mitwächst, sind die Hypercubes.

Wie der Torus ist die Hypercube-Architektur symmetrisch. Jeder Prozessor besitzt dieselbe Anzahl von IPC-Kanälen, und keiner hat eine Sonderstellung. Die Anzahl der Prozessoren in einem Hypercube beträgt immer eine Zweierpotenz 2n, dabei wird n als Dimension oder Ordnung des Hypercubes bezeichnet. Am leichtesten läßt sich die Hypercube-Architektur induktiv beschreiben: Ein Hypercube der Dimension n wird aus zwei Hypercubes der Dimensionen n-1 dadurch erzeugt, daß jeder Prozessor im einen Hypercube mit dem korrespondierenden Prozessor im anderen Hypercube verbunden wird. Hier wird deutlich, wie sich mit wachsender Anzahl von Prozessoren auch die Anzahl der

Verbindungen erhöht: wird aus zwei Hypercubes der Dimension n-1 ein Hypercube der Dimension n erzeugt, so werden 2(n-1) neue Verbindungen erzeugt. Eine weitere interessante Eigenschaft ist, daß die Dimension n zusätzlich auch die maximale Weglänge Maxn (die Distanz zweier am weitesten entfernten Prozessoren) bestimmt. Es gilt: Maxn = n. Beim Übergang von der Ordnung n-1 zur Ordnung n erhöht sich trotz Verdoppelung der Prozessoranzahl die maximale Weglänge nur um 1.

Die Hypercube-Architektur kann weitaus dichter als ein Gitter sein. In einem Hypercube der Dimension n ist jeder Prozessor mit n weiteren Prozessoren verknüpft. Ein Hypereube der Ordnung 4 hat 16 Prozessoren, von denen jeder mit vier weiteren verbunden ist. Die Dichte dieses Hypercubes ist somit gleich der Dichte eines Gitters mit 16 Prozessoren. Für Systeme mit mehr als 16 Prozessoren wächst jedoch die Anzahl der Verbindungsleitungen weitaus schneller als in einem Gitter, da jeder Prozessor mit mehr als vier Nachbarn verbunden wird. Man kann sich leicht vorstellen, daß gerade bei massivparallelen Systemen die Netzdichte ein entscheidendes Qualitätsmerkmal für den gesamten Message-Transfer darstellt.

Aufgrund der hohen Netzdichte sind die Hypercubes nicht so leicht in der Hardware zu implementieren wie das Gitter. Der Aufwand an zusätzlichen Hardware-Komponente

außerhalb des Chips auf dem Board realisiert werden soll. Hersteller, welche einen Hypercube auf der Basis von diskreten Komponenten entwickelt haben, kommen in Schwierigkeiten, wenn Systeme der Ordnung größer als 7 entwickelt werden sollen.

Die einzig bisher erfolgreiche Art und Weise, eine Hypercube-Topologie für mehrere tausend Prozessoren zu bauen, besteht darin, die IPC-Kanäle direkt auf dem Chip unterzubringen, und so die Anzahl der diskreten Bauteile zu verringern. Die Vorteile

liegen auf der Hand:

1. Da der Prozessorchip alle IPC-Kanäle enthält, ergibt sich eine niedrige Anzahl von Bauelementen (Faktor 10 zu herkömmlicher Bauweise), eine minimale Fläche für das Prozessor-Board und damit eine hohe Verfügbarkeit.

2. Daten müssen nicht zwischen dem Prozessor und einer Routing-Unit auf einem Board transferiert werden, da die Routing-Unit schon in dem Chip integriert ist.

3. Aufgrund der hohen Dichte ist die Distanz zwischen zwei Prozessoren selbst für große Dimensionen gering, und die Wahrscheinlichkeit einer Kollision sehr niedrig. Kollisionen treten immer dann auf, wenn versucht wird zwei unterschiedliche Messages über denselben IPC-Kanal eines Prozessors zu senden. Der Trend zu Distributed-Memory-MIMD-Systemen ist

ungebrochen. Realisieren lassen sich diese Computer nur noch durch massiv-parallele Systeme. Hier spielt jedoch die Netztopologie und die Ausgewogenheit zwischen Kommunikations- und Rechenleistung eine entscheidende Rolle. +