Von Prof. Dr. Christian Siemers, tecChannel.de
In der Diskussion sind eine Vielzahl von Modellen als Alternativen zu der Von-Neumann-Rechnerarchitektur. Ziel dieser gesamten Bemühungen ist es, Nachteile der Von-Neumann-Architektur (vor allem der Verarbeitungsgeschwindigkeit oder der Reaktionsfähigkeit) zu vermeiden.
Um dies systematisch zu behandeln, geben wir hier zunächst eine kurze Einführung in das Gebiet des Reconfigurable Computing. Hierbei steht das Ausführungsprinzip, sprich die Art der Steuerung des Programms im Vordergrund.
Im Anschluss daran besprechen wir diverse Architekturen: Das UCB/UCM-Konzept (TU Clausthal) mit dem Vorläufer >S<puter und der einfachsten Implementierung in Form der rRISC-Maschine (reconfigurable RISC), den Xputer (Universität Kaiserslautern) und die XPP-Architektur der Firma PACT (München).
Reconfigurable Computing
Bekannte Formen von programmierbaren Rechnern sind der Von-Neumann-Rechner und die Programmable Logic Devices (PLD). Das folgende Beispiel verdeutlicht, worin der wesentliche Unterschied dieser Architekturen in Bezug auf die Programmausführung besteht.
Das Problem besteht in einer NOR-Funktion (Verneinung des logischen ODER) von binärwertigen Signalen an einem Eingang mit 8-Bit-Breite. Bild 1 zeigt dies als Endlosprogramm, formuliert in der Sprache C. Die NOR-Funktion der acht Eingänge (es wird vorausgesetzt, dass unsigned char einer Datenbreite von 8 Bit entspricht) wird am Ausgangsport (Adresse 0x2000), Bit 0 dargestellt.
Die Übersetzung in eine fiktive Assembler-Sprache (für eine typische RISC-Architektur, etwa MPM3) in Bild 2 ergibt natürlich eine Endlosschleife.
Sie zeigt aber insbesondere, dass dieses Programm, so klein es ist, sehr zergliedert wird. Das würde für eine superskalare Ausführung große Probleme bereiten, auf einen entsprechenden Instruction Level Parallelism zu kommen.
Abgesehen von der starken Zergliederung der Assembler-Übersetzung nimmt das Durchlaufen einer Programmschleife einige Takte in Anspruch: Für eine RISC-Architektur mit theoretisch einer Instruktion/Takt benötigt die Programmschleife (also ohne Block L0) sechs (ELSE-Zweig) beziehungsweise sieben (IF-Zweig) Takte im Minimum. Eine Eingangsänderung wird erst nach fünf Takten minimal, nach zwölf Takten maximal am Ausgang sichtbar, bei 100 MHz Taktfrequenz also im Mittel nach 85 plus minus 35 ns. Die Kontrollflussverzweigungen und die Datenabhängigkeiten verhindern übrigens in diesem Fall eine Beschleunigung durch superskalare Ausführung.
Die gleiche Problemstellung lässt sich auch in Hardware lösen und führt zur Implementierung eines NOR-Gatters.
Das Ergebnis entspricht dabei der üblichen Vorgehensweise: Die PAL-Struktur, die in zahlreichen Bausteinen mit programmierbarer Logik vorhanden ist, weist programmierbare UND-Eingänge mit dahinter liegenden, fest verdrahteten ODER-Gattern auf. Dies entspricht der disjunktiven Normalform DNF, und so lautet die optimale Lösung für PLDs (in Booleschem Assembler):
OUTPORT0 = /INPORT7 * /INPORT6 * /INPORT5 * /INPORT4 * /INPORT3 * /INPORT2 * /INPORT1 * /INPORT0;
Eine Eingangsänderung ist in diesem Fall nach einer Gatterlaufzeit am Ausgang sichtbar, also zum Beispiel nach 5 ns. Diese Zeit ist konstant für alle Änderungen, wesentliche Abweichungen von diesem Wert existieren nicht (abgesehen von Laufzeitschwankungen durch Temperaturänderungen et cetera).
Configurable und Sequential Computing
Damit sollte deutlich sein, dass beide Lösungen die gleiche logische Funktion beschreiben, dies allerdings auf vollkommen unterschiedlichem Weg. Die mikroprozessorbasierte Lösung bedient sich der vordefinierten Mikroprozessorbefehle, im Wesentlichen aus Datenoperationen und Kontrollflussinstruktionen bestehend. Diese Instruktionen werden hintereinander ausgeführt, und das Programm wird in einer zeitlichen Sequenz durchlaufen.
Die PLD-basierte Lösung besteht darin, ebenfalls vordefinierte Basisoperationen (meist NOT (Invertierung), AND sowie OR, oft noch mit abschließendem XOR) zu nutzen. Diese werden jedoch mithilfe der Programmierung verdrahtet, also strukturiert.
Man spricht im Allgemeinen von der Ausführungsdimension. Die Sequenzen in Mikroprozessoren bedeuten, dass jedes dort ausgeführte Programm in einer bestimmten Zeit abläuft. Erhöht man die Komplexität eines Algorithmus, benötigt der Prozessor mehr Zeit zur Ausführung. Dies wird als Computing in Time bezeichnet, im Gegensatz zu Computing in Space, bei dem die Komplexität beziehungsweise die Berechnung in der (Silizium-)Fläche steckt.
Man kann diese beiden Ausführungsdimensionen und ihre derzeitigen Realisierungsformen (Mikroprozessor und PLD) auch als Extrempunkte auffassen: Auf der einen Seite liegt eine Sequenz fest gefügter Instruktionen vor, auf der anderen Seite eine einzige Instruktion. Letztere ist aber durch die strukturale Programmierung aus kleinen Einheiten zusammengefügt und enthält den kompletten Algorithmus. Man findet auf dieser Skala Sequential Computing und Configurable Computing vor.
Charakteristische Zeiten
Zugleich stellt sich die Frage nach Übergangsformen, vielleicht sogar skalierbaren Varianten, die je nach Bedarf auf die eine oder andere Form abgebildet werden können. Genau dies bietet das Reconfigurable Computing, bei dem ein Algorithmus - ganz allgemein gesprochen - auf die Sequenz von Konfigurationen abgebildet wird.
Während man bei PLDs auch heute noch fast ausschließlich davon ausgeht, eine einzige Konfiguration (= Instruktion) in den Speicher zu laden und damit einen guten Ersatz für ASICs zu haben, geht der Ansatz des Reconfigurable Computing einen deutlichen Schritt weiter. Hier ist es grundsätzlich möglich, die aktuell laufende Konfiguration zumindest partiell durch eine andere zu ersetzen. Eine Hardware-Plattform, die das ermöglicht, kann natürlich auf eine einzige Konfi guration skaliert werden. Worin besteht jedoch der Unterschied zum Sequential Computing eines Mikroprozessors?
Man könnte es so auffassen, dass ein Mikroprozessor eine Konfiguration (genannt Instruktion) aufnimmt, interpretiert und ausführt. Das Gleiche macht eine rekonfigurierbare Hardware, von der angenommen wird, dass das Laden der Konfiguration auch in einem (schnellen) Takt erfolgen kann. Der wesentliche Unterschied zwischen diesen beiden Formen ist derjenige, dass der Mikroprozessor die Instruktion nach Ausführung maschinendefiniert verwirft, während dies bei rekonfigurierbarer Hardware applikations- oder User-definiert erfolgen kann.
Zusammenfassend ergeben die verschiedenen Ausführungsformen eines Rechenprogramms folgende Möglichkeiten:
Alle drei Formen der programmierbaren Hardware ermöglichen es dem Systementwickler, ein berechenbares Problem zu lösen. Sie besitzen nach entsprechender Programmierung alle die gleiche (logische oder arithmetische) makroskopische Funktionalität. Hardware für Sequential Computing (Mikroprozessoren) optimiert dabei auf die Fläche zu Ungunsten der Ausführungszeit, Hardware für Configurable Computing (PLD) auf die Zeit zu Ungunsten der Fläche. Bei Hardware für Reconfigurable Computing kann man zwischen beiden Optimierungsformen variieren: Größere Konfigurationen bedeuten mehr Fläche, mehr Konfigurationen hingegen mehr Ausführungszeit ( Space-Time-Mapping).
Nimmt man zu der Darstellung der Anzahl und Variabilität der Instruktionen als dritte Darstellungsdimension noch die Komplexität der Operation hinzu, so erhält man die komplette Klassifizierung der verschiedenen Rechnerplattformen. Hier wird bei den Operationen zwischen logisch (bitweise) und arithmetisch (wortweise) unterschieden. Gemäß dieser Darstellung existieren zwei Klassen von Hardware-Plattformen für Reconfigurable Computing: Multicontext-PLDs und die UCB-Klasse.
Die beiden Komplexitätsstufen lassen sich auch definieren und dabei auf die Abhängigkeit eines Ausgangsbits von den Eingangsbits zurückführen: Bei logischen Funktionen besteht nur die Abhängigkeit von einem Eingangsbit pro Eingangsvektor (zum Beispiel beim logischen AND oder einem Shift-Befehl). Bei arithmetischen Funktionen hängt das Ausgangsbit von mehreren Eingangsbits pro Eingangsvektor (beispielsweise bei der Addition) ab.
Diese Komplexität beinhaltet die Anpassbarkeit an verschiedene Algorithmenklassen: Die Multicontext-PLDs mit ihren logischen Operationen sind für Bit-Level-Algorithmen sehr gut geeignet. Die UCB-Strukturen eignen sich besser für arithmetisch basierte Algorithmen.
Die Fortsetzung dieses Artikels lesen Sie kommende Woche in der ComputerPartner-Ausgabe 13/05.