HaDesWWW logo
Startseite

Downloads
Geschichte(n)
 
Hardware
FPGA-Board
Prozessor
  Instruktionssatz
Peripherie
  XBus-Referenz
PS/2-Board
Soundboard
USB-MMC-Board
 
PC-Software
HaCom
HoAsm, HLink
Emulator
Connectivity
 
Embedded Software
HAL
Dateimanager
Tetris
PacMan
3D-Engine
Pong
PacMan 3D
 
Kontakt

HaDes XP - Der Prozessor

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:

Datenfluss in der HaDes XP CPU

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:

  1. 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. 
  2. 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.
 
rrobek.de Hauptseite
 
Valid HTML 4.01!