Die CPU der HaDes XP ist
komplett im FPGA realisiert. Es handelt
sich um eine RISC-CPU mit folgenden Features:
- Volle Integer-Arithmetik
(add, sub, mul, div), Logikoperationen
und Shifts mit 32 bit Wortbreite
- 3-Adress-Code mit 16
General-Purpose und einigen Special-Purpose Registern
- Spezielle
Unterstützung für 16.16 bit Fixed-Point
Arithmetik
- Adressraum: bis zu 4 GB
für Daten, 128 kB für Programme
(gemeinsam genutzter Hauptspeicher)
- Schneller On-Chip Bus
für integrierte Peripherie (Zugriff durch I/O-Befehle mit bis
zu 100 MB/s)
- 25 MIPS Peak Performance
- 256 Worte Instruction-Cache
+ 256 Worte Datencache (Write-Back)
- 16-Level Interruptsystem
- ...
Eine grobe Übersicht
über den Aufbau der Hades XP CPU bietet folgendes
Datenfluss-Schaubild:

Dabei ist zu beachten, dass für einfache Arithmetikoperationen
nur zwei Takte benötigt werden:
- Instruction Fetch,
Vorverarbeitung, Instruction Decode, Register Read
- Execute, Write Back
Im Folgenden einige Anmerkungen
zu den einzelnen Komponenten der CPU.
Instruction Cache (icache)
Der Instruction Cache ist ein Cache von 256 Worten zu je 32 bit, dies
entspricht jeweils genau einer Instruktion.
Es handelt sich um einen einfachen, direkt gemappten Cache, aus dem nur
gelesen werden kann. Da angenommen wird, dass das Programm sich nicht
während der Laufzeit modifiziert, werden stets nur Daten aus
dem Hauptspeicher in den Cache gelesen und bei Bedarf an die CPU
abgegeben. Der icache
hat jedoch einen flush-Eingang,
durch den der komplette Inhalt als ungültig markiert wird.
(Diese Operation nimmt 256 Takte in Anspruch.) Dieser sollte nach dem
Laden eines neuen Programms mit Hilfe der start-Instruktion aktiviert
werden, um die Konsistenz des Caches sicherzustellen.
Instruction Fetch Unit (ifetch)
Die Instruction Fetch Unit hat
zwei wichtige Funktionen:
- Multiplexen zwischen dem
Ausgang des icache
und der bootmemory.
Bei der in die ifetch-Unit
integrierte bootmemory
handelt es sich um einen FPGA-internen ROM (aus 256 Worten), der das
Bootloader-Programm enthält. Nach dem Reset der CPU wird die bootmemory
ausgewählt, durch einen start-Befehl
wird zum icache
umgeschaltet.
- Interpretation der
CISC-Befehle. Der HaDes XP Befehlssatz (siehe weiter unten)
enthält zwei CISC-Befehle (lregs
und sregs),
durch die mehrere General-Purpose-Register auf einmal in den Speicher
gesichert bzw. aus diesem geladen werden können. (Durch diese
Befehle wird der Code-Overhead für Funktionen stark
reduziert.) Diese Befehle werden durch die ifetch-Unit
zu einer Folge von load-
bzw. store-Anweisungen
expandiert, die dann vom Rest des Prozessors ausgeführt
werden.
Instruction Decoder (indec)
Die sehr kleine Komponente
indec zerlegt das vom ifetch ausgegebene Befehlswort in Befehlstyp,
Registeradresse(n) und ggf. den Immediate-Operanden. Die HaDes XP
benutzt nur folgende zwei Instruktionsformate:
R-Format
(3 Register) |
IClass |
ICode |
Immed? |
Reg1 |
Reg2 |
Reg3 |
(leer) |
31 30 |
29 .. 25 |
24 |
23 .. 20 |
19 .. 16 |
15 .. 12 |
11 .. 0 |
|
|
hier 0 |
|
|
|
|
I-Format
(2 Register + Immediate-Operand) |
IClass |
ICode |
Immed? |
Reg1 |
Reg2 |
Immediate-Operand |
31
30 |
29 .. 25 |
24 |
23 .. 20 |
19 .. 16 |
15
.. 0 |
|
|
hier 1 |
|
|
|
|
Die folgende Tabelle zeigt die
Kodierung des HaDes-Befehlssatzes:
Befehl |
IClass |
ICode |
Immed |
Reg1 |
Reg2 |
Reg3 |
Imop |
Bemerkung |
Slice |
Detail |
Arithmetics
Class |
ADD |
00 |
00000 |
X |
WReg |
AReg |
BReg |
Imop |
2 Opcodes
reserviert wegen Load/Store |
ISL_ADDSUB |
b0 |
|
00 |
00010 |
X |
|
|
|
|
b4..b2 = 000 |
|
SUB |
00 |
00001 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
|
00 |
00011 |
X |
|
|
|
|
|
|
SHL |
00 |
00100 |
X |
WReg |
AReg |
BReg |
Imop |
|
ISL_SHIFT |
b1 = right |
CSHL |
00 |
00101 |
X |
WReg |
AReg |
BReg |
Imop |
|
b4..b2 = 001 |
b0 = cyclic |
SHR |
00 |
00110 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
|
CSHR |
00 |
00111 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
|
SHAR |
00 |
01110 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
b3 = arithm. |
SLT |
00 |
01100 |
X |
WReg |
AReg |
BReg |
Imop |
|
ISL_SXX |
b2 = less |
SGT |
00 |
01010 |
X |
WReg |
AReg |
BReg |
Imop |
|
b4..b3 = 01 |
b1 = greater |
SEQ |
00 |
01001 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
b0 = equal |
SLE |
00 |
01101 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
|
SGE |
00 |
01011 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
|
SNE |
00 |
01000 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
|
AND |
00 |
10000 |
X |
WReg |
AReg |
BReg |
Imop |
Spezialimplementierung
durch
Handoptimierte LUTs. |
ISL_LOGIC |
b1..b0 |
OR |
00 |
10001 |
X |
WReg |
AReg |
BReg |
Imop |
b4..b2 = 100 |
|
XOR |
00 |
10010 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
XNOR |
00 |
10011 |
X |
WReg |
AReg |
BReg |
Imop |
|
|
MUL |
00 |
10100 |
X |
WReg |
AReg |
BReg |
Imop |
gibt nur die 32 unteren Bits |
ISL_MUL |
|
PROD |
00 |
10101 |
0 |
WReg |
0 |
0 |
0 |
obere Bits der letzten
Multiplikation |
ISL_PROD |
|
DIV |
00 |
10110 |
X |
WReg |
AReg |
BReg |
Imop |
gibt nur den Quotient |
ISL_DIV |
b3 =
fixpoint |
DIVFP |
00 |
11010 |
X |
WReg |
AReg |
BReg |
Imop |
Fixpunkt (16,16) Division |
|
|
MOD |
00 |
10111 |
0 |
WReg |
0 |
0 |
0 |
Rest der letzten Division |
ISL_MOD |
|
DIV64P |
00 |
11000 |
0 |
0 |
AReg |
0 |
0 |
Obere Bits für die
nächste Division |
ISL_DIVPREP |
|
MULFP |
00 |
11001 |
X |
WReg |
AReg |
BReg |
Imop |
Fixpunkt (16,16) Multiplikation |
ISL_MULFP |
|
|
|
|
|
|
|
|
|
|
|
|
Jumps & I/O class |
LOAD |
01 |
00000 |
X |
Dest |
Base |
RegOff |
ImOff |
|
siehe ADD |
|
STORE |
01 |
00010 |
1 |
Val |
Base |
0 |
ImOff |
|
|
|
IN |
01 |
00100 |
X |
Dest |
0 |
RegAddr |
ImAddr |
|
|
|
OUT |
01 |
00101 |
X |
0 |
Val |
RegAddr |
ImAddr |
|
|
|
BNEZ |
01 |
01000 |
1 |
0 |
Val |
0 |
ImDest |
|
|
b3 = Sprung |
BEQZ |
01 |
01001 |
1 |
0 |
Val |
0 |
ImDest |
|
|
b0 = equal |
RET, JMPR |
01 |
01001 |
0 |
0 |
0 |
RegDest |
0 |
Achtung! Ziel ist jetzt BREG |
|
b1 = cflush |
START |
01 |
01011 |
X |
0 |
0 |
RegDest |
ImDest |
Achtung! Ziel ist jetzt BREG |
|
|
JAL |
01 |
01100 |
X |
DestPcNext |
0 |
RegDest |
ImDest |
|
|
|
RETI |
01 |
01101 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Specials Class |
ENI |
10 |
00000 |
0 |
0 |
0 |
0 |
0 |
|
|
|
DEI |
10 |
00001 |
0 |
0 |
0 |
0 |
0 |
|
|
|
SISA |
10 |
00010 |
X |
0 |
RegIntr |
RegIsa |
ImIsa |
Achtung! Interruptlevel ist
jetzt im
AREG. Ziel ist jetzt im BREG. |
|
|
LLEA |
10 |
00100 |
0 |
Dest |
0 |
0 |
0 |
|
|
|
LIRA |
10 |
00101 |
0 |
Dest |
0 |
0 |
0 |
|
|
|
SMP |
10 |
00110 |
X |
0 |
0 |
RegSmp |
ImSmp |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
LFLAGS |
10 |
01000 |
0 |
Dest |
0 |
0 |
0 |
signed, unsigned OV |
|
|
SFLAGS |
10 |
01001 |
X |
0 |
0 |
RegFlags |
ImFlags |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
CISC Class |
LREGS |
11 |
00000 |
1 |
RegUpTo |
RegBase |
0 |
ImOff |
|
|
|
SREGS |
11 |
00010 |
1 |
RegUpTo |
RegBase |
0 |
ImOff |
|
|
|
Arithmetic Logic Unit (alu)
Die ALU (Arithmetic Logic Unit) gehört zu den Kernkomponenten
eines jeden Prozessors, denn hier wird die eigentliche Berechnung
durchgeführt. Die ALU der HaDes XP nimmt eine zentrale
Rolle bei der
Abarbeitung der arithmetischen und logischen Befehle ein, welche
wiederum einen Großteil des gesamten Befehlssatzes
ausmachen. Die ALU wandelt die Eingabewerte (A-
bzw. B-Operand) in ein korrektes Ergebnis um und stellt dieses den
weiterverarbeitenden CPU-Komponenten zur Verfügung. Nicht alle
Operationen sind jedoch gleich aufwändig. Es gibt einfache
Operationen wie z.B. die Addition, die in einem Takt ausgeführt
werden können. Andere benötigen über 32 Takte (Division)
oder sogar eine von den Eingangsdaten abhängige Anzahl von Takten.
Daher muss die ALU dem Rest der CPU signalisieren, wann die Berechnung
durchgeführt ist und das korrekte Ergebnis am Ausgang anliegt.
Intern wird die ALU in Subkomponenten unterteilt, welche für die
Abarbeitung einzelner Befehle oder ganzer Befehlsgruppen zuständig
sind.
- Addierer bzw. Subtrahierer:
Die AddSub-Komponente besteht aus nur einem Addierer. Bei einer
Subtraktion werden die Bits des Subtrahenden invertiert, bevor sie an
den Adder-Baustein angelegt werden. Gleichzeitig wird das Carry-in
Signal gesetzt. Dies bewirkt eine Negation des Subtrahenden, die
anschließende Addition liefert somit das korrekte Ergebnis. FPGAs
werden u.a. auf schnelle Addition optimiert; daher gehören
Addition und Subtraktion zu den schnellsten Operationen der HaDes XP
und können in einem Takt ausgeführt werden.
- Vergleicher:
Für den Vergleich zweier Integer-Zahlen in
Zweierkomplement-Darstellung benötigt man im Prinzip einen
Subtrahierer und einen Baustein, der die Gleichheit von zwei Zahlen
prüft. Denn mit den Ergebnissen (Wahrheitswerten) von a>=b und a=b kann durch
einfache logische Verknüpfungen das Ergebnis aller anderen
Vergleichsoperationen berechnet werden. Z.B. gilt a>b, wenn a>=b and not a=b.
Der Test "größer oder gleich" wird mit dem
Subtrahierer durchgeführt, a>=b
ist nämlich äquivalent zu (a-b)>=0. Ob eine Zahl
negativ ist, lässt sich ganz leicht anhand des Vorzeichenbits
feststellen. Allerdings muss man bei der obigen Rechnung potentielle
Überläufe berücksichtigen. Ein Überlauf bei der
Subtraktion ist denkbar, wenn a
ziemlich groß und b
sehr klein (negativ) ist. Dann erhält man eine negative Differenz
und das berechnete Ergebnis ist falsch. Daher wurde bei der HaDes XP
folgende Formel verwendet: a>=b
<=> (a>=0 and b<0) or (sign(a)=sign(b) and (a-b)>=0).
Mit sign sei
dabei das Vorzeichenbit in der Zweierkomplement-Darstellung
bezeichnet. Für die Subtraktion verwendet die HaDes XP den
ALU-Adder, so dass im Wesentlichen nur durch den Gleichheitstest
zusätzliche
Kosten entstehen.
- Logische Einheit:
Die Logische Einheit ist die primitivste Subkomponente der ALU. Sie
führt die logischen Verknüpfungen and, or, xor und xnor durch. Dabei werden
die beiden Operanden als Bitstrings aufgefasst. Jeweils zwei Bits der
gleichen Ordnung (mit dem gleichen Index) werden zu einem Ergebnisbit
verknüpft. Jedes Ergebnisbit ist also ausschließlich von
seinen beiden Operandenbits abhängig. Das macht diese Operationen
besonders schnell. Doch nicht nur die Laufzeit, sondern auch der
Platzverbrauch ist minimal. Pro Ergebnisbit wird nur eine Look-Up Table
(LUT) des Spartan-II FPGAs benötigt. Jede LUT besitzt vier
Eingänge und einen Ausgang. Zwei Eingänge werden von den
Operanden belegt, an die beiden anderen wird der Operationscode
angelegt. Da es genau vier Operationen gibt, werden die LUTs optimal
ausgenutzt.
- Shifter:
Der Shifter war anfangs eine kombinatorische Schaltung wie der
Addierer und der Vergleicher auch. Doch mit der Zeit stellte sich diese
als kritisch bezüglich der Laufzeit heraus. Ein anderes Problem
war der Platz, den diese Schaltung auf dem FPGA beanspruchte. Deshalb
wurde nach Alternativen gesucht, und in der finalen Version der HaDes
XP
kam schließlich ein Multizyklus-Shifter zum Einsatz (deswegen
auch slowshifter genannt). Dieser besitzt im Prinzip ein 32-Bit
Ring-Register, in dem der Operand und die Zwischenergebnisse
abgelegt werden, und einen Zähler, welcher mit der Anzahl zu
schiebender Stellen
initialisiert wird. In jedem Schritt (Takt) wird der Operand entweder
um eine oder vier Stellen nach rechts oder links geschoben. Ob nach
rechts oder nach links geschoben wird, legt allein der Befehl (Rechts-
oder Linksshift) fest. Bei einem zyklischen Shift wird also nicht etwa
überprüft, ob ein Shift in die andere Richtung schneller
wäre. Der Counter wird nach jedem Takt entsprechend dekrementiert.
Geshiftet wird immer um die maximale Anzahl an Stellen; bei einem
Zählerstand von mindestens vier wird also auch um vier Stellen
geschoben. Erreicht der Counter den Wert 0, ist die Operation beendet.
Wie oben bereits angedeutet, ist das Register ringförmig
organisiert. Die zyklischen Shifts machen dies erforderlich.
Um auch logische bzw. arithmetische Shifts zu unterstützen,
werden bestimmte Reset-Signale generiert, welche die betroffenen Bits
im Falle eines Übertrags von der anderen Seite wieder
zurücksetzen.
- Multiplizierer:
Der Multiplizierer war die erste große Neuerung im Vergleich zur
HaDes III, denn die hatte keinen. Stattdessen musste die Multiplikation
in Software implementiert werden. Für unsere Spiele und
insbesondere die 3D-Engine war das aber zu ineffizient. Also wurde ein
Hardware-Baustein entwickelt, der eine Multiplikation von
Zweierkomplement-Zahlen (also signed) durchführt.
Da auch der
Multiplizierer nicht unnötig Ressourcen verschwenden sollte, wurde
das kompakte Shift'n'Add (Radix 4) Verfahren implementiert. Radix 4
bedeutet, dass pro Takt immer um zwei Stellen geschoben wird. Dies
erfordert zwar einen zusätzlichen Multiplexer, macht die
Multiplikation aber doppelt so schnell (16 statt 32 Takte). Die
Hardware besteht im Wesentlichen aus zwei aneinander gehängten
32-Bit Registern (zusammen PA-Register genannt), einem Zähler und
einem Addierer/Subtrahierer. Übrigens besitzt der
Multiplizierer einen eigenen Adder und verwendet nicht den
der ALU, denn die dafür nötigen Multiplexer
würden sowohl die Laufzeit als auch den Ressourcenverbrauch in die
Höhe treiben. Das Shift'n'Add (Radix 4) Verfahren funktioniert nun
wie folgt: Zu Beginn wird das P-Register gelöscht (auf 0
zurückgesetzt). Der A-Operand wird in das A-Register und der
B-Operand in ein konstantes B-Register geschrieben. Letzteres befindet
sich bei der HaDes XP außerhalb des Multiplizierers. In
jedem Schritt wird die Summe aus einem Vielfachen des B-Operanden und
dem aktuellen Wert im P-Register gebildet. Das Ergebnis wird
(gedanklich) wieder zurück ins P-Register geschrieben. Danach wird
das PA-Register um zwei Stellen nach rechts geschoben. Das alles
geschieht innerhalb eines Taktes; tatsächlich wird die
Summe also erst nach dem Shift ins P-Register
zurückgeschrieben. Nach 16 Takten kann das korrekte Produkt direkt
aus dem PA-Register abgelesen werden. Das erwähnte Vielfache des
B-Operanden wird aus den beiden niedrigstwertigen Bits des A-Registers
und einem Übertrag aus dem letzten Schritt bestimmt. Als
mögliche Faktoren ergeben sich -2, 1, 0, 1 und 2. Diese Vielfachen
lassen sich ganz leicht durch Shift und/oder Subtraktion statt Addition
berechnen. Wie oben bereits angedeutet, braucht man zur Auswahl des
geshifteten oder nicht geshifteten B-Operanden einen Multiplexer.
Die Multiplikation wird jedoch nicht wie oben beschrieben
durchgeführt,
wenn mindestens einer der beiden Operanden den Wert 0 besitzt. Dann
signalisiert der Multiplizierer sofort das Ende der Multiplikation und
spart damit 16 Takte ein. Da die 3D-Engine oft dünn besetzte
Matrizen multipliziert (viele Einträge 0), ist dieser
Zusatzaufwand (zwei Vergleicher) durchaus gerechtfertigt.
Der Multiplizierer kann problemlos auch für Fixpunktzahlen
verwendet werden,
man muss beim Ergebnis (PA-Register) lediglich das Komma verschieben.
- Dividierer:
Der Dividierer ist zweifelsohne eine der kompliziertesten Komponenten
der HaDes XP Hardware. Er ist für die Abarbeitung von vier
Prozessorbefehlen zuständig: DIV, MOD, DIV64P, DIVFP. Da die
anderen Komponenten der ALU ihre Operanden standardmäßig mit
Vorzeichen interpretieren, wurde auch beim Dividierer ein
aufwändiger signed-Algorithmus implementiert, der hier aber nicht
im
Detail beschrieben werden soll. Im Wesentlichen handelt es sich hierbei
um ein nichtrestaurierendes Shift'n'Subtract Verfahren mit zwei
zusätzlichen Korrekturschritten für die signed-Division.
Insgesamt werden also 34 Takte benötigt.
Bei der Standard-Division (DIV Befehl) sind sowohl der Dividend A als
auch der Divisor B vorzeichenbehaftete 32-Bit Zahlen. In Hinblick auf
die Division von Fixpunktzahlen sollten jedoch allgemeine 64-Bit
Dividenden unterstützt werden. Gewisse Beschränkungen des
Instruktionsformates und der Registerbank machten hierfür die
Einführung eines neuen Befehles erforderlich. DIV64P
("Preparation") lädt die 32 höchstwertigen Bits des
Dividenden; bei einem anschließenden DIV werden diese dann mit
dem dort angegebenen A-Operanden zu einer 64-Bit Zahl verknüpft.
DIV64P sollte im Programmcode also immer direkt vor einem DIV stehen.
Die Interruptlogik der HaDes XP garantiert in diesem Fall (und nur in
diesem Fall), dass die Ausführung dazwischen nicht unterbrochen
wird. Gleiches gilt übrigens für DIV und MOD. Mit Hilfe
der DIV64P Instruktion könnte man nun die Fixpunktdivision in
Software implementieren. Da uns das aber nicht gut genug war, wurde der
Dividierer am Ende noch um die DIVFP Funktionalität erweitert.
|