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 in Teil 1 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).
| |
Teil 1 | Einführung in Reconfigurable Computing |
|---|---|
Teil 2 | >S<puter |
Teil 3 | Reconfigurable RISC |
Teil 4 | UCB/UCM;-Konzept |
Teil 5 | XPP-Architektur und Xputer |
Diesen Artikel und eine ganze Reihe weiterer Grundlagenthemen zu Prozessoren finden Sie auch in unserem tecCHANNEL-Compact "Prozessor-Technologie". Die Ausgabe können Sie in unserem Online-Shop versandkostenfrei bestellen. Ausführliche Infos zum Inhalt des tecCHANNEL-Compact "Prozessor-Technologie" finden Sie hier.
Einführung in 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 aus Artikel "Grundlagen der RISC-Architektur") 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 in diesem Beispiel (Bild 3) 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.
Optimale Hardware-Lösung für PLDs
Die gleiche Problemstellung lässt sich auch in Hardware lösen und führt zur Implementierung eines NOR-Gatters.
Das Ergebnis in Bild 4 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).
Zusammenhang von 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 mit Hilfe 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 (siehe Bild 5) Sequential Computing und Configurable Computing vor.
Charakteristische Zeiten für programmierbare Einheiten
Zugleich mit dieser Darstellung 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. Diese Darstellung erklärt schon vieles, aber sie grenzt noch nicht scharf ab. Hierzu zeigt Tabelle 1 die charakteristischen Zeiten für PLD und Mikroprozessoren (µP).
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?
Tabelle 1 gibt auch hierzu Auskunft [1]. 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.
Bereich des Reconfigurable Computing
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 in Bild 5 als dritte Darstellungsdimension noch die Komplexität der Operation hinzu, so erhält man die komplette Klassifizierung der verschiedenen Rechnerplattformen in Bild 6. Hier wird bei den Operationen zwischen logisch (bitweise) und arithmetisch (Wort-weise) 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. Das sind zum Beispiel irreguläre Steueralgorithmen, kompakte Speicherung von Zustandskodierungen et cetera. Die UCBStrukturen eignen sich besser für arithmetisch basierte Algorithmen, etwa aus der digitalen Signalverarbeitung.
Ausblick
Gegenstand des nächsten Artikelteils ist der >S<puter, der aus der Variation des Instruction Scheduling der superskalaren Prozessoren stammt und aus dem schließlich auch die UCBs weiterentwickelt wurden.
| |
Teil 1 | Einführung in Reconfigurable Computing |
|---|---|
Teil 2 | >S<puter |
Teil 3 | Reconfigurable RISC |
Teil 4 | UCB/UCM;-Konzept |
Teil 5 | XPP-Architektur und Xputer |
Diesen Artikel und eine ganze Reihe weiterer Grundlagenthemen zu Prozessoren finden Sie auch in unserem tecCHANNEL-Compact "Prozessor-Technologie". Die Ausgabe können Sie in unserem Online-Shop versandkostenfrei bestellen. Ausführliche Infos zum Inhalt des tecCHANNEL-Compact "Prozessor-Technologie" finden Sie hier. (mec)
Literatur
[1] Andre Dehon, John Wawrzynek: "Reconfigurable Computing: What, Why and Implications for Design Automation". Design Automation Conference DAC99, San Francisco, 1999