Philipps – Universität Marburg

Fachbereich Mathematik und Informatik

Implementierung eines DLX-Simulators in

der funktionalen Sprache Haskell

Informatikpraktikum im Grundstudium SS 2000

Gruppe 1.1 – „Ausführung/Pipelining“

Teilnehmer :

Martin Kaletsch, Olaf Siefart, Adam Sosnowski, Yan Sun, Nils Weskamp

Betreuer :

Steffen Priebe

Abgegeben am 10.07.2000

Grundlage dieser Arbeit ist das Buch „Computer Architechture – A quantitative approach“ von Hennessy/Patterson

Abstract

In dem Buch von [Hennessy/Patterson] wird mit DLX ein einfaches Modell einer RISC-Architektur vorgestellt. Das Ziel unseres Projektes war es, einen CPU – Simulator für DLX in der funktionalen Sprache Haskell zu erstellen. Die Verwendung des funktionalen Programmierkonzeptes ermöglichte uns die Erstellung einer „ausführbaren Spezifikation“, d.h. die Phasen für Spezifikation und Entwicklung konnten parallel durchgeführt werden.

Die Aufgabe unserer Gruppe bestand insbesondere darin, die eigentliche CPU mit Pipelining und Strategien zur Vermeidung von Hazards zu modellieren.

Inhaltsverzeichnis

1. Einführung

2. Grundlagen

3. Hauptteil

3.1 Die fünf Pipelinephasen

3.1.1 InstructionFetch

3.1.2 InstructionDecode

3.1.3 Execute

3.1.4 MemoryAccess

3.1.5 WriteBack

3.2 Pipelineverwaltung, Hazards

3.3 Stalling-Strategie

3.4 Forwarding – Strategie

3.5 Schnittstellen

4. DLXasm - Assembler

5. Schlußbemerkung und Fazit

6. Literatur

1. Einführung

Die drastischen Steigerungen in der Verarbeitungsgeschwindigkeit moderner Prozessoren sind nicht allein auf gesteigerte Taktraten zurückzuführen, sondern ließen sich nur durch erhebliche Veränderungen in der Architektur der CPUs realisieren. Früher ging es vor allem darum, einen möglichst umfangreichen Befehlssatz (CISC) zur Verfügung zu stellen [der durch die Nutzung von Microcode realisiert wurde] und die Verarbeitungsgeschwindigkeit der einzelnen Befehle so niedrig wie möglich zu halten. Bei der heute üblichen RISC – Technologie ist das Ziel ein möglichst einfacher, direkt als Hardware realisierter Befehlssatz.

Hinzu kommt meist noch die Technik des Pipelining, zu deutsch Fließbandverarbeitung. Dazu wird zunächst die Ausführung eines Befehles in mehrere Phasen aufgeteilt, die jeweils möglichst unabhängig voneinander ablaufen. Es wird damit ermöglicht, mehrere Befehle überlappend, also „versetzt parallel“, auszuführen, was zu einer weiteren, deutlichen Geschwindigkeitssteigerung, aber auch zu Problemen führt. Probleme treten immer dann auf, wenn ein Befehl auf das Ergebnis eines kurz vorhergehenden Befehls zugreift, der aufgrund des Pipelinings noch nicht vollständig verarbeitet wurde. Solche Situationen bezeichnet man auch als Hazards, deren Behandlung ein Hauptproblem bei der Entwicklung von RISC-Prozessoren und der entsprechenden Software darstellt.

Die erheblich gesteigerte Verarbeitungsgeschwindigkeit von z.B. einem Befehl pro Taktzyklus stellt jedoch ein großes Problem beim Zugriff auf externe Systeme wie etwa den Arbeitsspeicher dar. Hier ist es notwendig, den gesteigerten Anforderungen z.B. durch geeignete Cache-Strategien zu begegnen.

Die gleichen Probleme treten natürlich auch bei der Realisierung eines Simulators für eine solche CPU auf und müssen entsprechend behandelt werden. Wir haben uns entschlossen, gleich mehrere Strategien zur Vermeidung von Hazards zu realisieren, um deren unterschiedliche Effizienz besser vergleichen zu können.

Das folgende, zweite Kapitel legt kurz die Grundlagen der verwendeten funktionalen Programmiersprache Haskell und die Konsequenzen für die Realisierung unseres Projektes dar.

Im dritten Kapitel werden unsere Designentscheidungen, die Moduleinteilungen und schließlich die Realisierung genauer beschrieben.

2. Grundlagen

Bei der Entwicklung unseres DLX-Simulators wurde die funktionale Sprache Haskell eingesetzt, insbesondere wurde der Interpreter Hugs98 benutzt. Da sich die funktionale Programmierung grundsätzlich erheblich von der imperativen unterscheidet, haben wir uns entschlossen, an dieser Stelle eine kurze Einführung in Haskell einzufügen. Für weitergehende Informationen verweisen wir auf das Literaturverzeichnis.

Funktionale Sprachen sind nicht aus der Abstraktion von imperativen Maschinensprachen entstanden, sondern beruhen auf einem soliden mathematischen Fundament, welches aus dem -Kalkül entstanden ist. Aufgrund des hohen Abstraktionsniveaus ist die Entwicklung in funktionalen Sprachen sehr schnell, die Programme sind oft kürzer und verständlicher als ihre imperativen Pendants. Ein funktionales Programm besteht aus einer Reihe von Funktionen im mathematischen Sinne, welche einen oder mehrere Parameter auf einen oder mehrere Funktionswerte abbilden.

Beispiel : fibo :: Int -> Int

fibo n | n == 0 = 1

| n == 1 = 1

| otherwise = (fibo (n-1)) + (fibo (n-2))

Die Notation in Haskell lehnt sich sehr stark an die mathematische Schreibweise von Funktionsdefinitionen an.

Bei der Entwicklung von funktionalen Programmen steht im Vordergrund, was eine Funktion realisieren soll. Wie diese Berechnung dann tatsächlich umgesetzt wird, liegt nicht in der Verantwortung des Programmierers. Dies legt auch den Begriff der „ausführbaren Spezifikation“ nahe, da ein Haskell-Programm letztlich nur eine formale Spezifikation darstellt. Aufgrund dieser besonderen Eigenschaften konnte in unserem Projekt auf eine separate Spezifikations- und Designphase verzichtet werden.

In funktionalen Sprachen steht als einzige Kontrollstruktur die Rekursion zur Verfügung, die Verwendung von Schleifen ist nicht vorgesehen. Ebenso können nicht -wie in der imperativen Sprachfamilie üblich- Variablen als Bezeichnungen für Speicherzellen genutzt werden. Die Konsequenzen dieser Eigenschaften sind weitreichend. So sind die funktionalen Sprachen grundsätzlich frei von Seiteneffekten, für Ausdrücke gilt die sogenannte „referenzielle Transparenz“, d.h., das Auswertungsergebnis eines Ausdrucks hängt nicht von Ort und Zeit seiner Auswertung ab. Dies eröffnet erhebliche Möglichkeiten für die Paralellverarbeitung von funktionalen Programmen, schafft allerdings auch Probleme, wenn etwa Daten innerhalb eines Programmablaufes persistent gehalten werden sollen. Da Daten grundsätzlich nicht in Form von Variablen verwaltet werden können, sind oft sehr unübersichtliche Funktionsdefinitionen notwendig.

Darüber hinaus besitzt Haskell ein sehr mächtiges Typkonzept, das jede Form von Typfehler bereits zum Zeitpunkt der Übersetzung eines Programmes abfängt. Dies kommt natürlich einer arbeitsteiligen Entwicklung sehr entgegen, da inkompatible Funktionsdefinitionen bereits zum Zeitpunkt der Typüberprüfung bemerkt werden.

3. Hauptteil

Die grundlegenden Definitionen wurden in unserem Modul "Datentypen.hs" festgelegt :

Dokumentation zum Modul Datentypen:

In diesem Modul werden die grundlegenden Datentypen für die Befehlsverarbeitung in der Pipeline festgelegt und die einzelnen möglichen Instruktionen für den DLX festgelegt. Hierbei definierten wir zuerst folgende grundlegende Datentypen: Byte (8 Bit), Halbwort (16 Bit) und Wort (32 Bit), die jeweils durch einen Int-Wert repräsentiert werden.

Es folgen die DLX-Definitionen:

Reg (Register), Imm (Immediate (16 Bit)), Dis (Displacement (16 Bit)), Label (Sprungmarke), TrapNr (Code für Betriebssystemaufruf), die auch durch Int-Werte repräsentiert werden.

Nach der Definiton dieser dem DLX zugrundeliegenden Datentypen begannen wir unsere eigene Datenstruktur zu entwickeln.

Die einzelnen Register R₀,...,R₃₁ verwalten wir als Liste ([R₀,...,R₃₁]) von Int-Werten.

Die internen Register Program Counter, New Program Counter, Instruction Register, A-Register, B-Register, Immediate-Register, ALU-Output Register, Condition-Register, Load Memory Data Register werden ebenfalls als Liste ([PC, NPC, IR, A-Reg, B-Reg, Imm-Reg,

Alu-Out, Cond-Reg, LMD-Reg]) von Int-Werten verwaltet.

Zu jedem Befehl, der in der Pipeline steht, wird verwaltet:

(Instruktion, interne Register, Resourcen)

Hierbei steht der eigentliche Befehl in der Instruktion, danach eine Version der internen Register und anschließend die Resourcen (Register,..) die sie benötigen. Da die Pipeline aus 5 Befehlen besteht, realisierten wir sie als Liste ([(Instruktion, interne Register, Resourcen)]). So entstand unsere endgültige Datenstruktur:

CPU = (Register, [(Instruktion, interne Register, Resourcen)])

Als erstes Ziel hatten wir uns gesetzt, einen Simulator zu schreiben, der Befehle sequentiell abarbeiten kann. Hierzu beschlossen wir die einzelnen Phasen InstruktionFetch, InstruktionDecode, Execute, MemoryAccess und WriteBack in einzelne Module aufzuteilen, die dann von den einzelnen Teilnehmern programmiert werden konnten. Dabei sollten die Hauptfunktionen der einzelnen Module die folgende Signatur besitzen:

(CPU, Memory) ® (CPU, Memory)

So konnte gesichert werden, das wir später bei der Hintereinanderausführung der einzelnen Hauptfunktionen keine Probleme mit den Datentypen bekamen.

Zusätzlich entwarfen wir ein Modul, das einen gehelfsmäßigen Speicher simulierte, da zu dieser Zeit von den Gruppen 3 und 4 noch nichts zu Verfügung gestellt werden konnte (was von uns auch nicht erwartet wurde), wir die Load/Store Befehle aber schon implementieren wollten. Hierzu stellten wir den Speicher einfach als Liste von Instruktionen (Programm) dar, in der die Adresse modulo 4 der entsprechenden Listenposition entsprach, da wir später bei der Umstellung auf die Speichermodule der Gruppe 3 und 4 keine Probleme mit den Adressen bekommen wollten, zumal dort der Speicher in Bytes verwaltet wird.

Die Datenstruktur Pipeline bestand zu dieser Zeit einfach aus einem einzigen Befehl, und die internen Register hatten den gleichen Stand wie die normalen.

3.1 Die fünf Pipelinephasen

Jede der fünf Pipelinephasen wurde in einem eigenen Modul behandelt.

Dokumentation zum Modul InstructionFetch:

Im Modul InstructionFetch wird im obersten Pipelinebefehl von der Adresse, auf die der PC zeigt, die nächste Instruktion (als Int-Wert) gelesen und ins IR geschrieben. Zusätzlich wird der NPC auf PC+4 gesetzt.

Dokumentation zum Modul InstructionDecode:

Befehlsformat:

Um eine effiziente Verarbeitung der Instruktionen zu ermöglichen, besitzen die RISC CPUs Maschinenbefehle einheitlicher Länge, im Gegensatz zu herkömmlichen Architekturen, bei denen zur Dekodierung des Befehls unterschiedlich viele Speicherzugriffe nötig sind.

Bei der DLX Architektur hat jeder Maschinenbefehl eine Länge von 32 Bit und kann in einem Zugriff aus dem Speicher gelesen werden, da der Speicherbus 32 Bit breit ist,.

Um eine schnelle Dekodierung und Ausführung der Befehle zu ermöglichen, gibt es nur drei verschiedene Formate.

1. I-Format Befehle:

Dabei haben die verschiedenen Abschnitte des Befehles folgende Bedeutung:

• Bits 0...5 : Opcode, identifiziert den Befehl.

• Bits 6...10: Quellregister 1 (rs1)(in diesem Fall einziges Quellregister)

• Bits 11...15: Zielregister (rd)

• Bits 16...31: konstanter 16 Bit Wert (imm)

Alle Befehle der Art rd ¬ rs1 op Imm werden in diesem Format kodiert.

Bei bedingten Sprüngen gibt rs1 das Condition-Register an, Imm eine eine PC-relative Sprungadresse.

Bei ’jump register’ und ’jump and link register’ gibt rs1 das Zielregister an.

Bei Speicherzugriffen gibt rs1 + Imm (in diesem Zusammenhang wird Imm auch als “Displacement“ bezeichnet) die Speicheradresse an, deren Wert nach rd gelesen bzw. an die der Wert von rd geschrieben wird.

2. R-Format Befehle

Dabei haben die verschiedenen Abschnitte des Befehles folgende Bedeutung:

• Bits 0...5: Opcode = 0

• Bits 6...10: Quellregister 1 (rs1)

• Bits 11...15: Quellregister 2 (rs2)

• Bits 16...20: Zielregister (rd)

• Bits 26...31: Art der Operation (func)

Befehle der Art rd <- rs1 func rs2 werden in diesem Format kodiert.

3. J-Format Befehle

Dabei haben die verschiedenen Abschnitte des Befehles folgende Bedeutung:

• Bits 0...5: Opcode

• Bits 6...31: PC-relative 26 Bit Adresse

Die Befehle J und JAL werden in diesem Format kodiert.

Befehlsliste

Die arithmetischen Befehle der DLX CPU existieren in zwei Varianten, signed und unsigned (z.B. ADD und ADDU). Diese Varianten führen die gleichen Operationen aus; bei der signed Variante werden die Operanden als Zweierkomplementzahlen interpretiert, bei unsigned als vorzeichenlose Binärzahlen.

Folgende Befehle wurden implementiert:

I-Typ Befehle:

Opcode	Bezeichnung	Operanden	Bemerkungen
1	LB	rd, dis (rs1)	Reg[rd] <-Mem[Reg[rs1]+dis] Ein Byte (8 Bit) laden
2	LBU	rd, dis (rs1)	wie oben, jedoch mit Vorzeichenerweiterung
3	SB	dis (rs1), rd	Mem[Reg[rs1]+dis]<-Reg[rd] Ein Byte speichern
4	LH	rd, dis (rs1)	Reg[rd] <-Mem[Reg[rs1]+dis] Ein Halbwort (16 Bit) laden
5	LHU	rd, dis (rs1)	wie oben, jedoch mit Vorzeichenerweiterung
6	SH	dis (rs1), rd	Mem[Reg[rs1]+dis]<-Reg[rd] Ein Halbwort speichern
7	LW	rd, dis (rs1)	Reg[rd] <-Mem[Reg[rs1]+dis] Ein Wort (32 Bit) laden
8	SW	dis (rs1), rd	Mem[Reg[rs1]+dis]<-Reg[rd] Ein Wort speichern
9	ADDI	rd, rs1, Imm	Reg[rd] <- Reg[rs1] + Imm
10	ADDUI	rd, rs1, Imm
11	SUBI	rd, rs1, Imm	Reg[rd] <- Reg[rs1] - Imm
12	SUBUI	rd, rs1, Imm
13	ANDI	rd, rs1, Imm	Reg[rd] <- Reg[rs1] & Imm bitweises AND
14	ORI	rd, rs1, Imm	Reg[rd] <- Reg[rs1] | Imm bitweises OR
15	XORI	rd, rs1, Imm	Reg[rd] <- [rs1] XOR Imm bitweises XOR
16	SLLI	rd, rs1, Imm	Reg[rd] <- Reg[rs1] << Imm Logisher Shift Links
17	SRLI	rd, rs1, Imm	Reg[rd] <- Reg[rs1] >> Imm Logischer Shift Rechts
18	SLTI	rd, rs,1 Imm	Reg[rd] <- 1 wenn Reg[rs] < Imm Reg[rd] <- 0 sonst
19	SRAI	rd, rs1, Imm	Reg[rd] <- Reg[rs1] >>> Imm Arithmetischer Shift Rechts
20	SGTI	rd, rs1, Imm	Reg[rd] <- 1 wenn Reg[rs] > Imm Reg[rd] <- 0 sonst
21	SLE	rd, rs1, Imm	Reg[rd] <- 1 wenn Reg[rs] <= Imm Reg[rd] <- 0 sonst
22	SGEI	rd, rs1, Imm	Reg[rd] <- 1 wenn Reg[rs] >= Imm Reg[rd] <- 0 sonst
23	SEQI	rd, rs1, Imm	Reg[rd] <- 1 wenn Reg[rs] = Imm Reg[rd] <- 0 sonst
24	SNEI	rd, rs1, Imm	Reg[rd] <- 1 wenn Reg[rs] <> Imm Reg[rd] <- 0 sonst
25	BEQZ	rs1, Imm	Springe nach NPC+Imm wenn REg[rs1] = 0 Sonst setze Ausführung bei NPC fort
26	BNEZ	rs1, Imm	Springe nach NPC+Imm, wenn Reg[rs1] <> 0 Sonst setze Ausführung bei NPC fort
27	JAL	Offset	Wird verlegt!!
28	JR	rs1	Sprung an die Adresse, deren Wert in Reg[rs1] steht
29	JALR	rs1	Springe an die Adresse, deren Wert in Reg[rs1] steht, R31 <- NPC
30	LHI	rd, Imm	Lade Imm in die oberen 16 Bit von Reg[rd]

R-Typ Befehle

Sämtliche R-Typ Befehle haben den Opcode 0 (Bits 0...5), die auf den Registern auszuführende Operation wird durch den in den Bits 26...31 gespeicherten func Wert bestimmt.

func	Bezeichnung	Operanden	Bemerkungen
9	ADD	rd, rs1, rs2	Reg[Rd] <- Reg[rs1] + Reg[rs2]
10	ADDU	rd, rs1, rs2
11	SUB	rd, rs1, rs2	Reg[Rd] <- Reg[rs1] - Reg[rs2]
12	SUBU	rd, rs1, rs2
13	AND	rd, rs1, rs2	Reg[Rd] <- Reg[rs1] & Reg[rs2]
14	OR	rd, rs1, rs2	Reg[Rd] <- Reg[rs1] | Reg[rs2]
15	XOR	rd, rs1, rs2	Reg[Rd] <- Reg[rs1] XOR Reg[rs2]
16	SLL	rd, rs1, rs2	Reg[rd] <- Reg[rs1] << Reg[rs2] Logisher Shift Links
17	SRL	rd, rs1, rs2	Reg[rd] <- Reg[rs1] >> Reg[rs2] Logisher Shift Rechts
18	SLT	rd, rs1, rs2	Reg[rd] <- 1 wenn Reg[rs1] < Reg[rs2] Reg[rd] <- 0 sonst
19	SRA	rd, rs1, rs2	Reg[rd] <- Reg[rs1] >>> Reg[rs2] Arithmetischer Shift Rechts
20	SGT	rd, rs1, rs2	Reg[rd] <- 1 wenn Reg[rs1] > Reg[rs2] Reg[rd] <- 0 sonst
21	SLE	rd, rs1, rs2	Reg[rd] <- 1 wenn Reg[rs1] <= Reg[rs2] Reg[rd] <- 0 sonst
22	SGE	rd, rs1, rs2	Reg[rd] <- 1 wenn Reg[rs1] >= Reg[rs2] Reg[rd] <- 0 sonst
23	SEQ	rd, rs1, rs2	Reg[rd] <- 1 wenn Reg[rs1] = Reg[rs2] Reg[rd] <- 0 sonst
24	SNE	rd, rs1, rs2	Reg[rd] <- 1 wenn Reg[rs1] <> Reg[rs2] Reg[rd] <- 0 sonst

J-Typ Befehle

Opcode	Bezeichnung	Operanden	Bemerkungen
61	JAL	offset	Springt nach NPC + offset R31 <- NPC (wurde hierhin verlegt)
62	J	offset	Springt nach NPC + offset
63	TRAP	offset	TRAP 0 beendet das laufende Programm

Sonstige Befehle

NOP: Aus historischen Gründen wird dieser Befehl sowohl durch den Opcode 32 als auch durch opcode = func = 0 kodiert.

Dieser Befehl führt keine Operationen durch und er verwendet keine Argumente.

In unserer Version der DLX CPU wird dieser Befehl hauptsächlich intern verwendet, um Wartezyklen bei der Pipelineverarbeitung zu realisieren. Der Programmierer muß selbst keine NOP Befehle in sein Programm integrieren, da alle Formen von Hazards intern abgefangen werden.

InstructionDecode

Das Modul InstructionDecode stellt die Funktion

instructionDecode :: (CPU, Memory) -> (CPU, Memory)

zur Verfügung. Die Funktion führt auf dem übergebenen CPU Zustand die Pipelinephase InstructionDecode aus; zurückgegeben wird der dadurch geänderte CPU Zustand. Der ebenfalls übergebene Speicher wird unverändert zurückgegeben.

Dem DXL-Modell entsprechend werden folgende Funktionen durchgeführt:

• Die Inhalte der durch die Bits 6...10 und 11...15 im Befehlswort im IR bezeichneten Register werden in die internen Register A und B geschrieben.

• Die Bits 16...31 des Befehlswortes in IR werden in das Imm (Immediate) Register geschrieben, dabei findet eine Vorzeichenerweiterung statt, d.h. die obersten 16 Bit des Imm Registers werden auf den Wert von Bit 16 des Befehlswortes gesetzt.
Handelt es sich um einen J-Typ Befehl, werden die Bits 6...31 mit Vorzeichenerweiterung ins Imm eingetragen.

Zusätzlich zu den durch das DLX Modell festgelegten Operationen der Pipelinephase wandelt die Funktion noch das im Instruktionsregister der aktuellen Pipelinephase stehende 32-Bit Befehlswort in das interne Befehlsformat (Instruktion) um und speichert es im ersten Element des Drei-Tupels, das die aktuelle Pipelinephase beschreibt.

Weiterhin wird in die zur Hazardvermeidung verwendeten Ressourcenliste eingetragen, welche Register jeweils vom dekodierten Befehl gelesen bzw. geschrieben werden. In das erste Element der Liste wird die Nummer des Zielregisters, in das zweite und dritte die Nummern der beiden Quellregister eingetragen. Wird eine der drei Resoucen vom dekodierten Befehl nicht genutzt, so wird der entsprechende Eintrag auf -1 gesetzt. Die weiteren Elemente der Resourcenliste bleiben unverändert.

Dokumentation zum Modul Execute:

Das Modul "Execute" implementiert die dritte Phase der Pipeline - die Execution-Phase. In dieser Phase werden die Instruktionen, die in den beiden Phasen davor aus dem Speicher geholt und dekodiert wurden, ausgeführt bzw. zur Ausführung vorbereitet.

Es wird dazu auf die dekodierten Operanden zugegriffen, die vom vorausgehenden Modul "InstructionDecode" in den internen Registern "A", "B" und "Imm" bereitgestellt werden. Je nach Instruktionstyp werden die internen Register "ALU-Output" und "Cond" gesetzt.

Es gibt vier grundlegende Instruktionstypen: Speicherzugriff, Register-Register ALU-Operation, Register-Immediate ALU-Operation und (bedingter) Sprung. Alle Befehle können eindeutig einem dieser Typen zugeordnet werden. Der Befehl selbst wird aus der Datenstruktur "CPU" entnommen. Dort steht er in dekodierter Form als Instruktion vom Typ "Instruktion".

Das Modul "Execute" besteht im Grunde aus der folgenden Funktion:

execute :: (CPU,Memory) -> (CPU,Memory)

Wie zu sehen ist, erhält die Funktion - wie alle anderen Pipeline-Phasen auch - einen CPU-Zustand als Eingabe, verändert diesen und gibt den neuen CPU-Zustand an die nächste Phase weiter. Die nachfolgende Codezeile aus dem Modul "Execute" zeigt anhand des einfachsten Befehls, wie dies konkret aussieht:

execute ((x,[a,b,(NOP,iRegs,y),c,d]),mem) =

x,[a,b,(NOP,iRegs,y),c,d]),mem)

In diesem speziellen Fall ist die Eingabe gleich der Ausgabe, da der Befehl "NOP" nichts macht. Weiter unten sind einige andere Befehle aufgeführt, die zeigen, wie der CPU-Zustand verändert wird. An dem ersten Beispiel ist aber bereits zu sehen, welche Komponenten der Datenstruktur "CPU" für die Funktion "execute" von Bedeutung sind.

"x" kennzeichnet die Liste der 32 Allzweckregister und "mem" den Arbeitsspeicher. Da in der Execute-Phase sowohl Allzweck-Register als auch der Speicher nicht verändert wird - dies geschieht erst später in den Phasen "MemoryAccess" und "WriteBack" - sind diese Komponenten für die Funktion unerheblich. Das gleiche gilt für die Bezeichner "a", "b","c","d", welche für die anderen vier Phasen von Bedeutung sind.

Analog zur Pipelinestufe wird in diesem Modul nur auf das dritte Element der Liste

[(Instruktion,IntRegisters,Resource)]

zugegriffen. Hierbei sind auch nur die ersten beiden Komponenten des 3-Tupels von Bedeutung. Die letzte Komponente wird in der vorhergehenden Phase verändert. In der ersten Komponente steht die dekodierte Instruktion, in der zweiten die internen Register ("Latch").

Die Funktion "execute" wird mittels Pattern-Matching aufgerufen, d.h. je nachdem, welcher Befehl in der ersten Komponente steht, wird die richtige Version der Funktion "execute" aufgerufen und ausgeführt.

Wie vorhin erwähnt, kann man alle (in dieser DLX-CPU implementierten) Befehlen in vier Gattungen aufteilen. Im folgenden wird auf diese vier Instruktionstypen eingegangen und gezeigt, in welcher Weise sie die internen Register "ALU-Output" und "Cond" verändern.

1. Speicherzugriffe

Bei Instruktionen vom Typ Speicherzugriff (auch "Load/Store"-Befehle) wird die Speicheradresse, in die geschrieben bzw. aus der gelesen werden soll, berechnet und in ALU-Output abgelegt. Erst in einer der nachfolgenden Pipeline-Phasen erfolgt dann der eigentliche Zugriff auf diese Adresse.

Die Adresse setzt sich aus einem Offset und dem Inhalt eines Registers zusammen. Betrachten wir beispielsweise folgenden Befehl: "LB R1, 80(R2)"

Hier wird ein Byte aus der Speicherzelle, die durch das Displacement 80(R2) adressiert wird, gelesen und im Register R1 abgelegt. Bei allen Speicherzugriffsbefehlen wird mit dem Displacement adressiert. Die Zahl 80 ist im obigen Beispiel der Offset. Er wird in der Phase "InstructionDecode" im internen Register "Imm" abgelegt. Der Inhalt des Registers R2 liegt im internen Register "A" bereit. In der Execution-Phase werden nun die beiden Werte addiert und im internen Register "ALU-Output" gespeichert.

Diagramm: ALU-Output ¬ A + Imm

Der zugehörige Funktionsaufruf ist:

execute ((x,[a,b,(LB op1 op2,iRegs,y),c,d]),mem) =

((x,[a,b,(LB op1 op2,ueberschreibe aluOutPos

((nth iRegs aPos) + (nth iRegs immPos)) iRegs,y),c,d]),mem)

Zuerst werden mit "nth iRegs aPos" und "nth iRegs immPos" die internen Register "A" und "Imm" aus der Liste "iRegs" der internen Register ausgelesen und dann addiert. Danach wird in der gleichen Liste mit der Hilfsfunktion "ueberschreibe" das Ergebnis der Addition in das interne Register "ALU-Output" (Position "aluOutPos") geschrieben, und der neue CPU-Zustand wird zurückgegeben.

Das ist im Prinzip die Vorgehensweise der Funktion "execute" bei allen Befehlen. Demzufolge kann bei den nachfolgenden Beispielen auf eine nochmalige Erklärung der Code-Zeilen verzichtet werden.

2. Register-Register ALU-Operationen

Befehle diese Instruktionstyps gehören zu den Befehlen, die in der Execute-Phase wirklich ausgeführt werden, d.h., es wird nicht wie bei den "Load/Store"-Befehlen bzw. den Sprüngen in der Execute-Phase nur etwas vorbereitet, was erst später tatsächlich eintrifft (wie der Speicherzugriff bzw. die Verzweigung). Zu den Reg.-Reg. ALU-Operationen gehören die arithmetischen, die logischen, die Shift- und die Set-Befehle. Je nach Art des Befehls wird im ALU-Output das Ergebnis der Operation abgelegt.

Diagramm: ALU-Output ¬ A op B

Beispiele:

Arithmetischer Befehl "ADD R1, R2, R3", schreibt in R1 die Summe aus R2 und R3. Der Wert des ersten Quelloperanden (R2) liegt im internen Register "A", der des zweiten (R3) in "B". Zugehörige Funktion:

execute ((x,[a,b,(ADD op1 op2 op3,iRegs,y),c,d]),mem)

= ((x,[a,b,(ADD op1 op2 op3,ueberschreibe aluOutPos ((nth iRegs aPos) + (nth iRegs bPos)) iRegs,y),c,d]),mem)

Logischer Befehl "AND R1, R2, R3", schreibt in R1 mit Hilfe der Funktion "bAND" das Ergebnis aus der bitweisen AND-Verknüpfung von R2 und R3.

Zugehörige Funktion:

execute ((x,[a,b,(AND op1 op2 op3,iRegs,y),c,d]),mem)

= ((x,[a,b,(AND op1 op2 op3,ueberschreibe aluOutPos

(bAND (nth iRegs aPos) (nth iRegs bPos)) iRegs,y),c,d]),mem)

3. Register-Immediate ALU-Operationen

Zu jedem Befehl vom Typ Register-Register ALU-Operation gehört ein Pendant vom Typ Register-Immediate ALU-Operation. Im Unterschied zum ersten Typ kommt bei diesen Befehlen eine Zahl, ein sogenanntes Immediate, als Operand vor.

Diagramm: ALU-Output ¬ A op Imm

Beispiele:

Shift-Befehl "SLLI R10, R20, #2", schreibt mit Hilfe der Funktion "<<" den um 2 Stellen nach links geshifteten Wert aus R20 in R10 (äquivalent zur Multiplikation mit 4). Zugehörige Funktion:

-- ShiftLeftLogicalImmediate

execute ((x,[a,b,(SLLI op1 op2 imm,iRegs,y),c,d]),mem)

= ((x,[a,b,(SLLI op1 op2 imm,ueberschreibe aluOutPos ((nth iRegs

aPos) << (nth iRegs immPos)) iRegs,y),c,d]),mem)

Set-Befehl "SLTI R11, R12, #100", schreibt in R11 eine 1, wenn der Wert von R12 kleiner ist als 100, ansonsten eine 0. Zugehörige Funktion:

execute ((x,[a,b,(SLTI op1 op2 imm,iRegs,y),c,d]),mem)

= ((x,[a,b,(SLTI op1 op2 imm,ueberschreibe aluOutPos ergebnis

iRegs,y),c,d]),mem) where ergebnis = if (nth iRegs aPos)

< (nth iRegs immPos) then 1 else 0

4. Sprünge

Bei allen Sprüngen außer "JR Reg" und "JALR Reg" wird der Sprung-Offset relativ zum internen Register "NPC" ("NewProgrammCounter") berechnet. Bei den Befehlen "JR Reg" und "JALR Reg" wird direkt zu der Adresse im Register "Reg" verzweigt. In beiden Fällen wird die endgültige Sprung-Adresse in "ALU-Output" geschrieben. Die eigentliche Verzweigung erfolgt in einer anderen Pipeline-Phase.

Die Verzweigung erfolgt aber nur, wenn im internen Register "Cond" eine 1 steht. Bei den unbedingten Sprüngen "J Name", "JR Reg", "JAL Name" und "JALR Reg" wird dagegen das "Cond"-Register in jedem Fall mit einer 1 beschrieben. Bei den beiden bedingten Sprüngen "BEQZ Reg,Name" und "BNEZ Reg,Name" wird zuerst eine Bedingung überprüft und dann "Cond" je nach Ergebnis mit einer 1 oder einer 0 beschrieben.

Diagramm: ALU-Output ¬ NPC + Imm ; Cond ¬ A op 0

Beispiele:

Bedingter Sprung "BEQZ R21,Loop", verzweigt zu Adresse "Loop", wenn in R21 eine 0 steht. Der Operand "Loop" ist ein 16-Bit-Offset, der in "Imm" bereitliegt. Er wird zu dem Wert in "NPC" addiert und anschließend in "ALU-Output" gespeichert. In "A" liegt der Wert vom ersten Operanden (R21). Er wird mit 0 verglichen und entsprechend wird dann "Cond" gesetzt. Zugehörige Funktion:

execute ((x,[a,b,(BEQZ op name,iRegs,y),c,d]),mem)

= ((x,[a,b,(BEQZ op name,ueberschreibe condPos ergebnis

(ueberschreibe aluOutPos ((nth iRegs npcPos) + (nth iRegs immPos))

iRegs),y),c,d]),mem)

where ergebnis = if ((nth iRegs aPos)==0) then 1 else 0

Unbedingter Sprung "JR R17", hier wird direkt zur Adresse im Register R17 verzweigt. Dazu muß in das "Cond"-Register eine 1 geschrieben werden. In "ALU-Output" wird der Wert des Operanden (R17) geschrieben. Dieser wurde nach "A" dekodiert. Zugehörige Funktion:

execute ((x,[a,b,(JR op,iRegs,y),c,d]),mem)

= ((x,[a,b,(JR op,ueberschreibe condPos 1

(ueberschreibe aluOutPos (nth iRegs aPos) iRegs),y),c,d]),mem)

Bei den Sprüngen "JAL Reg" "JALR Reg" wird die Rücksprungadresse nicht in R31geschieben, weil...

Dokumentation zum Modul MemoryAccess:

Im Modul MemoryAccess werden die Speicherzugriffe realisiert. Wenn im Programm ein Load- oder Storebefehl auftaucht, wird entweder der Inhalt der entsprechenden Speicherzelle in das interne LMD-Register des jeweiligen Latches geschrieben oder der Inhalt aus dem internen B-Register in den Speicher geschrieben. Dabei werden gegebenfalls auftretende Verzögerungen (etwa durch einen Cache-Miss) berücksichtigt.

Dokumentation zum Modul WriteBack:

Im Modul WriteBack wird zunächst zwischen 4 Instruktionstypen unterschieden:

a) Register-Register ALU Operationen (z.B. ADD, SUB, etc.)

b) Register-Immediate ALU Operationen (z.B. ADDI, SUBI, etc.)

c) Load-Befehle (z.B. LB, LW, etc.)

d) Sprungbefehle JAL und JALR

e) Sonstige Instruktionen

In den Fällen a) und b) wird der Inhalt vom ALU-Output Register und im Fall c) der Inhalt vom LMD-Register in die Zielregister geschrieben. Im Fall d) wird der Inhalt vom ALU-Output-Register in das Register R31 geschrieben. In sonstigen Fällen bleibt der CPU-Zustand unverändert.

Nachdem jeder sein Modul fertiggestellt hatte, schalteten wir sie hintereinander und erhielten ein Programm, welches in der Lage war, einen Befehl sequentiell abzuarbeiten. Der nächste Schritt war nun die Entwicklung einer Pipelinestruktur, die es uns ermöglichen sollte, mehrere Befehle gleichzeitig, aber jeweils um einen Takt versetzt, abzuarbeiten. Hier entschieden wir, daß jedes unserer Module immer nur auf einen Befehl zugreifen sollte, der an einer bestimmten Stelle der Pipeline steht, so daß die 5 Module "gleichzeitig" auf den 5 verschieden Befehlen in der Pipeline ausgeführt werden sollten und die Befehle dann anschließend um eine Position weiterverschoben wurden. Diese Pipelineverwaltung wurde dann wieder in einem Modul gekapselt.

3.2 Pipelineverwaltung, Hazards

Die parallele Verarbeitung der Instruktionen in der Pipeline ist eine der wichtigsten Gründe für den Geschwindigkeitsgewinn der RISC Architektur gegenüber herkömmlichen Prozessoren. Durch die Pipeline kann theoretische pro Taktzyklus ein Befehl ausgeführt werden.

Bei der praktischen Realisierung ist dies allerdings nur der Idealfall. Unter verschiedenen Bedingungen können die Befehle nicht wie gewünscht abgearbeitet werden. Diese Situationen nennt man Hazards.

Es werden drei Arten von Hazards unterschieden:

• 1. Strukturhazards treten auf, wenn zwei Instruktionen gleichzeitig auf dieselbe Hardware zugreifen, z.B., wenn ein Befehl in der InstructionDecode Phase ein Register liest, während ein anderer in der WriteBack Phase in dieses Register schreibt.

• 2. Datenhazards treten auf, wenn ein Befehl auf Daten zugreift, die das Ergebnis eines vorhergehenden Befehls sind, aber durch die Pipelineverarbeitung noch nicht zur Verfügung stehen, z.B. wenn ein Befehl im InstructionDecode ein Register liest, das aber Zielregister eines vorhergehenden Befehls ist, der in diesem Takt noch vor der WriteBack Phase steht.

• 3. Kontrollhazards treten auf, wenn bei der Verarbeitung von bedingten Sprungbefehlen erst dann entschieden werden kann, ob ein Sprung genommen wird oder nicht, wenn bereits weitere Befehle in die Pipeline geladen wurden, so daß die Pipelineverarbeitung unter Umständen für mehrere Takten verzögert wird.

Es gibt verschiedene Methoden, bei dem Entwurf einer CPU mit Hazards umzugehen, deren Effizienz variiert. Es besteht natürlich auch die Möglichkeit, es dem Assemblerprogrammierer oder Compiler zu überlassen, das Entstehen von Hazards durch geschickte Anordnung der Befehle selbst zu verhindern,. Dies vereinfacht den Entwurf der CPU natürlich deutlich und kann, wenn es vernünftig durchgeführt wird, eine sehr effiziente Lösung sein.

Beim Entwurf unseres Modells haben wir uns dafür entschieden, sämtliche Formen von Hazards abzufangen so, daß der Programmierer sich darum nicht kümmern muß.

Wir haben verschiedene Methoden der Hazardvermeidung implementiert, die der Benutzer auswählen kann, um die Effizienz der verschiedenen Strategien bei der Abarbeitung von Programmen selbst zu überprüfen.

3.3 Stalling - Strategie

Dokumentation zum Modul Pipeline:

Im Modul Pipeline findet die eigentliche Pipelineverwaltung und Hazardbehandlung statt.

Hierbei wird in einer Pipelinephase immer ein InstruktionFetch aud dem ersten, InstruktionDecode auf dem zweiten, Execute auf dem dritten, MemoryAccess auf dem vierten und Writeback auf dem fünften Befehl auf der Pipeline gleichzeitig ausgeführt (Pseudoparallel sozusagen, da echte Parallelität in Haskell nicht realisierbar ist)[1].

Grundlegende Funktion in diesem Modul ist die Einschub-Funktion

einschub :: Int ® (CPU,Memory) ® (CPU,Memory)

Mit ihrer Hilfe wird ein einer beliebigen Stelle i (0 £ i £ 4) in der Pipeline ein Nop eingeschoben, daß dann später von dem neuen Befehl überschrieben wird und gleichzeitig wird der fünfte Befehl entfernt, die Pipeline wird somit ganz oder zumindestens partiell weitergeschoben. Das partielle Weiterschieben dient der Hazard-Behandlung, so kann der Befehl, der durch einen Hazard aufgehalten wird, an der entsprechenden Stelle in der Pipeline gehalten werden, während die unteren Befehle weiter abgearbeitet werden.

Auf dieser Funktion baut dann die eigentlich Pipeline-Funktion

pipeline :: (CPU,Memory) ® (CPU,Memory)

auf. Diese entscheidet nach Auswertung eines Hazard-Prädikates, wie sie die Pipeline weiterschieben muß, ob ganz oder partiell. Hierbei wird durch die hierarchische Struktur gesichert, das Hazards, die weiter unten in der Pipeline auftreten zuerst abgehandelt werden.

Die Pipeline wurde auf diesen Grundlagen erstmal implementiert und funktionierte auch, obwohl sie relativ ineffektiv war. Aus diesem Grund wurden folgende Oprtimierungen

programmiert und eingebaut :

1. Die Ausführung der absoluten Sprünge schon in der InstruktionFetch-Phase

2. Die Ausführung der bedingten Sprünge in die InstruktionDecode-Phase

3. Data-Forwarding

Die Behandlung bedingter und unbedingter Sprünge in der Pipeline

In einer Pipeline stellt die Verarbeitung von bedingten und unbedingten Sprüngen ein erhebliches Problem dar, da ein Sprung eben die gesamte Pipeline verändert. Grundsätzlich ist es zwar möglich, Sprünge genau wie alle anderen Befehle zu verarbeiten, dies erfordert jedoch, daß bei jedem Sprung ein Teil der Pipeline gelöscht wird. Damit entstünde nach jedem Sprung eine „Lücke“ von mehreren Phasen in der Pipeline, die sich natürlich auf die Ausführungsgeschwindigkeit auswirkt. Um nun dieses Problem zu lösen, haben wir uns entschieden, die bedingten und unbedingten Sprünge gesondert zu behandeln.

Die Verarbeitung der unbedingten Sprünge wurde in die Phase „Instruction Fetch“ verlagert. Nachdem ein Befehl aus dem Arbeitsspeicher gelesen wurde, wird nun zusätzlich der Opcode extrahiert und festgestellt, ob dieser einen absoluten Sprung[2] anzeigt. Wenn dies der Fall ist, so wird bereits an dieser Stelle der Sprung ausgeführt, der nächste Befehl kann ohne Unterbrechung in die Pipeline eingefügt werden.

Bei den bedingten Sprüngen ergaben sich zusätzliche Probleme. Ob ein solcher Sprung tatsächlich ausgeführt wird, hängt von den Inhalten einzelner Register ab, diese könnten jedoch von vorhergehenden Befehlen verändert werden. Um derartige Datenhazards abfangen zu können, werden die bedingten Sprünge in unserer Implementierung in der Phase „Instruktion Decode“ verarbeitet, dort werden auch die Datenhazards der übrigen arithmetisch-logischen Kommandos beseitigt. Wenn ein bedingter Sprung auf ein Register zugreift, welches von einem anderen, in der Pipeline befindlichen Befehl verändert wird, dann wird die Ausführung dieses Sprunges verzögert, bis es zu keinen Komplikationen mehr kommen kann. Nachteil dieser Lösung ist, daß aufgrund der Verlagerung in die 2. Pipelinephase bei bedingten Sprüngen eine „Lücke“ von einem Zyklus in der Pipeline auftritt. Dies ist jedoch gegenüber der ursprünglichen Lücke von 3 (!) Befehlen eine erhebliche Ersparnis.

Zu 1 : Die Verlagerung der absoluten Sprünge in die InstructionFetch-Phase wird durch die Funktionen

isJump :: Int ® Bool

handleJumps :: (CPU, Memory) ® (CPU, Memory)

realisiert. Grund für die Verlagerung war die Tatsache, das vorher ein absoluter Sprung immer erst in der Execute-Phase ausgeführt wurde. Daraus folgte, das die beiden Befehle über ihm nochmal neu geladen werden mußten und zusätzlich zwei Pipelinephasen verschwendet wurden. Durch die Verlagerung konnte dieses Manko behoben werden. Die Funktion isJump ist dabei als Prädikat zu sehen, das feststellt, ob ein absoluter Sprung vorliegt. Sie wird von der Funktion handleJumps benutzt, die dann je nach Aussage des Prädikats entscheidet, ob sie einen Sprung ausführen muß oder nicht, nachdem im InstruktionFetch der Befehl aus dem Speicher geladen worden ist.

Zu 2 : Die Verlagerung der bedingten Sprünge in die InstructionDecode-Phase wird durch die Funktionen

isCondJump :: Instruktion ® Bool

handleCondJumps :: (CPU, Memory) ® (CPU, Memory)

Zu 3.

Im allgemeinen können mit Hilfe des Data-Forwarding Datenhazards vermieden werden, außer wenn die Datenabhängigkeit zwischen zwei nachbarten Befehlen liegt, wobei der vordere ein Loadbefehl ist, da die benötigte Daten erst nach der Phase “MemoryAccess” im LMD vorhanden sein werden. (vgl. Kapitel 3.4.)

In unserer CPU beachten wir aber zwei Sonderheiten:

1) Wir simulieren keine echte gleichzeitige Durchführung der 5 Pipeline-Phasen in einem Takt. In der Simulation laufen die 5 Phasen in der Folge WriteBack -> MemoryAccess -> Execute -> InstruktionDecode -> InstruktionFetch ab. Das bedeutet z.B., daß bei der Durchführung der Phase Execute” die Phase “MemoryAccess” schon fertig ist, also im Zustand, der eigentlich erst im nächsten Takt auftritt. Diesen “Simulationscharakter” haben wir so ausgenutzt, daß wir hier eine Behandlung der eigentlich nicht vom Data-Forwarding vermeidbare Datenhazard sparen können.

2) Um eine effizientere Behandlung der bedingten Sprünge zu erhalten, haben wir sie an die Stelle direkt nach der “InstruktionDecode” vorgeschoben. Daher brauchen wir eine zusätzliche Forwarding-Behandlung vor dieser Sprung-Behandlung vor dem “Execute”. Im Fall, daß die Quellregister des Sprungsbefehls und das Zielregister des nächsten Befehls identisch sind, tritt ein Datenhazards auf, der nicht vom “Data-Forwarding” vermieden werden kann. In diesem Fall müssen wir einen 1-Takt-Stall bezahlen, also ein NOP einfügen. Im Programm werden solche Fälle durch das Prädikat “isHazard” abgefangen und die Funktion “einschube 2” (???) implementiert das Einfügen der NOP.

3.4 “Forwarding”-Strategie

“Data-Forwarding” ist eine Hardware-Technik, die den Datenfluß zwischen den Latches der verschiedener Phasen ermöglicht. Somit werden Datenhazards vermieden und damit ein effizienteres Pipelineverhalten erzielt. Die Kernidee ist, im Fall eines Datenhazards die Daten direkt aus einem internen Register (LMD bei Load-Befehlen, ALU-Output bei anderen) zu holen, anstatt zu warten, bis die benötigten Daten in Allzweck-Registern vorliegen.

Im Modul “Dataforward” haben wir das Forwarding folgendermaßen implementiert:

· Vor der Durchführung von “Execute”, “MemoryAccess” und “WriteBack” wird jeweils geprüft, ob eine Datenabhängigkeit vorhanden ist (ein Quellregister der durchzuführenden Instruktion ist ein Zielregister einer vorherigen Instruktion).

· Liegt eine Datenabhängigkeit vor, so wird zunächst unterschieden, ob die benötigte Daten von einem Loadbefehl erzeugt werden. Ist dies der Fall, so werden die Daten aus dem LMD-Register, ansonsten aus dem ALU-Output-Register jeweils an die erwünschte Stelle (Register A bzw. B) geschrieben. Im Programm dient die Funktion “forward” für diesen Datentransport.

· Im Fall einer mehrfachen Datenabhängigkeit (ein Quellregister der durchzuführenden Instruktion gleicht dem Zielregister mehrerer vorhergehenden Instruktionen) werden die aktuellsten Daten “geforwardet”.

Leider müssen wir bemerken, daß das “Data-Forwarding” nicht alle Datahazards vermeiden kann. So kann zum Beispiel der Fall auftreten, daß die Datenabhängigkeit zwischen zwei direkt aufeinanderfolgenden Befehlen liegt, wobei der erste ein Loadbefehl ist. Da der Speicherzugriff immer in der Phase “MemoryAccess” stattfindet, stehen die zu holenden Daten erst nach der 4. Pipeline-Phase im LMD zur Verfügung. Also sind die Daten erst nach “MemoryAccess” “forward”-bereit. Wenn diese Daten von dem nächsten Befehl (in der Phase “Execute”) benötigt werden, so muß dieser nächste Befehl einen Takt warten. lücklicherweise können wir bei der Simulation die tatsächlich sequentielle Durchführung der verschiedener Phasen ausnutzen und uns damit von der Behandlung solcher Fälle befreien.

3.5 Schnittstellen

3.5.1 Arbeitsspeicher

Der ursprünglich für interne Zwecke entwickelte, vorläufige Speicher wurde, sobald dieser fertiggestellt war, durch die Arbeitsspeichermodule der Gruppe 4 ersetzt.Wir verweisen auf deren Dokumentation für weitere Informationen.

3.5.2 Benutzeroberfläche

Für die Gruppen, die für die Benutzeroberfläche zuständig sind, stellen wir im wesentlichen die folgende Funktion zur Verfügung :

pipelinezyklus :: Int -> Int -> (CPU,Memory, Int) -> (CPU,Memory, Int)

Diese Funktion simuliert einen, auf Wunsch auch mehrere, Prozessortakt(e) einer DLX-CPU. Der erste Parameter legt fest, welche Strategie zur Hazard-Vermeidug angewandt werden soll. Hier sind Werte zwischen 0 und 3 zulässig, ein Wechsel der Strategie im laufenden Betrieb ist nicht empfohlen. Der zweite Parameter gibt an, wie viele Taktzyklen auf einmal ausgeführt werden sollen. Besonders bei umfangreichen Programmen kann sich dies überaus positiv auf die Verarbeitungsgeschwindigkeit auswirken. Um eine korrekte Beendigung des Programmes zu ermögliche, stellen wir zusätzlich ein Prädikat

isEnd :: (CPU,Memory, Int) -> Bool

zur Verfügung. Dieses stellt fest, ob der aktuelle Befehl im zweiten Latch ein TRAP 0, und in diesem Fall kann das Programm beendet werden.

Die Funktion

initpipeline :: [(Instruktion,IntRegisters,Resource)]

stellt eine "leere" Pipeline zur Verfügung und dient dazu, die Programmausführung überhaupt zu starten.

4. DLXasm – Assembler

Wir zitieren hier an dieser Stelle die README-Datei zum DLX-Assembler von Adam Sosnowski, dem für die Entwicklung an dieser Stelle herzlich gedankt sei :

Der DLX-Assembler DLXasm

DLXasm ist ein einfacher DLX-Assembler. Er sollte uns ursprünglich bei der Erstellung von Testprogrammen für unsere DLX-CPU behilflich sein. Aus dem kleinen Tool ist mittlerweile ein 3-Pass-Assembler geworden, der ein relativ komfortables Schreiben von DLX-Programmen ermöglicht.

DLXasm liest Quellcode in Mnemonic-Schreibweise ein und übersetzt diesen in für den DLX-Simulator lesbare Instruktionen. Diese Instruktionen werden in Form von 32-Bit Integerwerten in einer Haskell-Liste gespeichert. Ausgegeben wird also eine hs-Datei, die im DLX-Simulator direkt als Speicherinhalt eingelesen und weiterverarbeitet werden kann. Dazu wird es im fertigen DLX-Simulator eine Eingabemöglichkeit geben, mit der man ein mit DLXasm assembliertes Programm einlesen und auszuführen kann.

Nachfolgendes Beispiel zeigt eine Ausgabe von DLXasm. Es ist die assemblierte Version des Beispiel-Programms "bubble.as". Der Quelltext dazu befindet sich weiter unten.

 
program = [  5787655,
 6051847,
 605290496,
 264905,
 264267,
 1343574080,
 3671385,
 3409178,
 106505,
 (-257399),
 266377,
 1209337984,
 (-2357927),
 6279,
 270471,
 1343561920,
 (-1833639),
 8328,
 268424,
 605290496,
 (-2754),
 63,
 96,
 128,
 34,
 2344,
 0,
 333,
 (-34),
 1,
 444,
 10,
 1 ] :: Memory

Syntax:

Die Syntax der Mnemonic-Schreibweise ist die gleiche, wie sie im Hennessy-Patterson vorgestellt wird. Also der Form:

 
 ADDI R1, R2, #123 
 LHI R4, #-1000
 LB R30, 48(R0) 
 SW -80(R20), R21
 NOP
 JAL -1234 
 BNEZ R15, 20

Immediates werden mit einer vorausgehenden Raute # gekennzeichnet und Register mit einem R. Displacements erfordern die bekannte Klammerung.
Zusätzlich zu den DLX-Befehlen im Mnemonic-Format kann DLXasm noch mit einigen Assembleranweisungen umgehen:

• Kommentare werden mit einem Semikolon ";" eingeleitet und erstrecken sich dann bis zum Ende der Zeile.

· Es dürfen Sprungmarken definiert werden. Sie müssen als erstes Wort in der Zeile stehen und mit einem Doppelpunkt ":" enden. Das erste Zeichen muß ein Buchstabe sein, danach dürfen auch Ziffern vorkommen, also z.B. "Loop2Begin:". Soll ein Sprungmarkenname ('Label') als Operand innerhalb eine Sprungbefehls vorkommen, dann muß der Doppelpunkt weggelassen werden.
Labels können maximal 20 Zeichen lang sein und es können maximal 100 Sprungmarken angelegt werden. Ich habe dies der Einfachheit halber so festgelegt, da mir diese Grenzen im Hinblick auf die geringe zu erwartete Komplexität der Programme für den DLX-Simulator für sinnvoll erschienen. Sollten irgendwann mal größere Wert benötigt werden, kann dies leicht in der Datei "DLXasm.y" geändert werden (siehe dazu die Preprozessor-Konstante 'MAXLABEL').

· Es können - wie aus x86-Assemblern bekannt - mit der Assembleranweisung "dw" (DefineWord) Speicherzellen mit 32-Bit-Integerwerten vordefiniert werden.

DLXasm ist case-insensitive, d.h. es wird nicht zwischen Groß- und Kleinschreibung unterschieden. Dies gilt allerdings nicht für Sprungmarken! So sind z.B. "loop" und "Loop" zwei verschiedene Labels.
Desweiteren sind jegliche Abstände zwischen Befehlen, Kommata, Klammern und Operanden völlig egal.

Es folgt das Beispiel-Programm "bubble.as". Es veranschaulicht gut, welchen Quellcode der Assembler verarbeiten kann.

 
; Bubble Sort (mit gezielten Abbruch), sortiert das Int-Array von Adresse lo bis hi
; (C) Adam Sosnowski 2000
 
; Die Adresse des Arrayanfangs(=lo) steht an Adresse 88, die des Arrayendes(=hi) an Adresse 92
; Dort können die Arraygrenzen verändert werden, wenn andere Arrays sortiert werden sollen
 
; Persönliche Konvention:
; Im Programm werden Register 1-9 für Indizes und sonstige Variablen, Register 10-19 für Konstanten 
; und Register 20-29 für Flags/Boolvariablen bei Vergleichs- und Branchbefehlen verwendet
 
 lw r10, 88(r0) ; Anfangsadresse des Arrays in R10 
 lw r11, 92(r0) ; Endadresse des Arrays in R11 
 
 add r20, r0, r0 ; R20=0(=False) : Flag zum gezielten Abbruch auf False setzen
 
 ;äußere Schleife "for (R1=hi; R1>lo; --R1)"
 addi r1, r11, #4 ; R1=hi+4 : äußerer Index, zeigt auf das kleinste Element der geordneten 
 ;   Teilliste, hier kontrollstrukturbedingte Korrektur um +1
AUSSEN: subi r1, r1, #4 ; R1=R1-4 : äußeren Index runterzählen 
 sgt r21, r1, r10 ; if (R1>lo) R21=1 else R21=0
 beqz r21, ENDE ; if (R21==0) goto ENDE else mache weiter : wenn R1=lo, dann Array sortiert
 bnez r20, ENDE ; if (R20!=0) goto ENDE : wenn R20==True, dann vorzeitiger Abbruch
 addi r20, r0, #1 ; R20=1(=True) : wenn R20 in der inneren Schleife True bleibt, 
 ;   dann Array schon sortiert
 
 ;innere Schleife "for (R2=lo; R2<R1; ++R2)"
 addi r2, r10, #-4 ; R2=lo-4 : innerer Index, fängt immer vom ersten Listenelement an zu zählen
 ;  auch hier kontrollstrukturbedingte Korrektur um -1 
INNEN: addi r2, r2, #4 ; R2=R2+4
 slt r21, r2, r1 ; if (R2<R1) R21=1 else R21=0
 beqz r21, AUSSEN ; if (R21==0) goto AUSSEN
 
 ;jetzt kommt das Vertauschen der Zellen
 lw r3, 0 (r2) ; R3=Array[R2]
 lw r4, 4 (r2) ; R4=Array[R2+1]
 sgt r21, r3, r4 ; if (R3>R4) R21=1 else R21=0
 beqz r21, INNEN ; if (R21==0) goto INNEN else vertausche Zellen und setze Flag:
 sw 0 (r2), r4
 sw 4 (r2), r3
 add r20, r0, r0 ; R20=0(=False) : kein vorzeitiger Abbruch
 j INNEN ; goto INNEN : innere Schleife wiederholen 
 
ENDE: trap  0  ; ciao
 
; Datenbereich:
 dw 96,128 ; defineWord: Arrayanfang, Arrayende
 dw 34,2344,0,333,-34,1,444,10,1 ; und nun die zu sortierenden Zahlen

DLXasm kann nicht mit Bezeichnern für Variablen umgehen. D.h. man kann nicht Befehle der Art "SW X, R2" schreiben, wobei "X" eine Variable sein soll. Daher muß bei Speicherzugriffen mit Displacements gearbeitet werden. Da der DLX-Simulator sowieso Lehrzwecken dienen soll, ist dies kein Nachteil.
Bei der Verwendung von Displacements ist zu beachten, daß die Zahlen Vielfache von vier sein müssen. Es wird PC-relativ zugegriffen. Beispiel:

 
 LW R1, 8(R0) ;lade Word aus der Speicherzelle hinter dem nächsten Befehl
 NOP
 DW 4711 ;auf diese Speicherzelle wird zugegriffen

Last not least verfügt DLXasm über eine umfassende Fehlerbehandlung. Je nach Fehlerart wird eine Meldung mit Zeilennummer ausgegeben.


Kodierung und Befehlsformat:

Ich habe mich strikt an die R, I und J-type Befehlsformate aus Hennessy-Patterson gehalten. Einzige Ausnahme sind die Befehle mit den speziellen Opcodes. Dort wird func nicht in den höchstwertigen 11 Bit kodiert sondern in den höchstwertigen 6 Bit. Dies ist eine der Festlegungen, die am Anfang des Praktikums in Übereinstimmung mit der Gruppe 2 gemacht wurden. Desweiteren werden die Opcodes wie abgesprochen durchnummeriert (siehe dazu die Liste der DLX-Befehle).

Der Befehl TRAP wird auch kodiert, ist aber (zumindest bei unserer DLX-CPU) nicht im Befehlssatz enthalten. Er wird von uns als "Programmende"-Befehl verwendet bzw. für eine kontrollierte Ausführung benutzt.


Aufruf und Compilierung:

DLXasm wird folgendermaßen aufgerufen:

 
  DLXasm [-o ziel.hs] quell.as

Bei Aufruf ohne Parameter wird diese Meldung ausgegen. Wird keine Ausgabedatei angegeben, erzeugt DLXasm standardmäßig als Ausgabe eine Datei "out.hs", in der dann der assemblierte Code liegt. Ein Aufruf der Art

 
  DLXasm datei.as

würde dies bewirken. Es kann aber auch explizit eine Ausgabedatei angegeben werden:

 
 DLXasm -o datei.hs datei.as

Nach dem Assemblieren liegt das Programm in für den DLX-Simulator verständlicher Form im Verzeichnis. Außerdem wird eine Datei "DLXasmPass2.as" erzeugt. In dieser Datei befindet sich der ursprüngliche Quellcode, so wie er nach der zweiten Assemblierungsphase aussieht. D.h. sämtliche Labels wurden durch Sprung-Offsets ersetzt. Diese Datei dient ausschließlich zur Fehlersuche.

Wer den Assembler selbst unter Linux compilieren möchte, muß folgendes eingeben:

 
 flex -i DLXasm.l
 yacc DLXasm.y (oder: bison -y DLXasm.y)
 gcc -o DLXasm y.tab.c -lfl

Diese Arbeit auch automatisch von dem Bash-Script "Make" ausgeführt werden. (Nicht vergessen, das Execute-Bit für Make zu setzen.)
Falls jemand eine GCC (GNU Compiler Collection) unter MS-Windows installiert hat, kann den Assembler auch unter Windows compilieren und dazu das Batch-Script "Make.bat" verwenden. Ich persönlich empfehle hierfür "mingw32", Download unter "http://agnes.dida.physik.uni-essen.de/~janjaap/mingw32/". Die Datei "DLXasm.exe" sollte aber unter allen MS-Windows 9x Versionen laufen (NT habe ich nicht getestet), so daß eine Neucompilierung ohnehin nicht notwendig ist.

WICHTIG: Sollte unter Linux das Compilieren des Assemblers nicht klappen oder wenn der Assembler unerklärliche Ausgaben bzw. Fehlermeldungen erzeugt, ist zu überprüfen, ob nicht vielleicht eine Quelldatei im DOS-Format (also mit CR/LF) vorliegt bzw. im UNIX-Format (nur CR ?), falls unter MS-Windows compiliert wird.


Zu den Dateien in diesem Verzeichnis:

 
- DLXasm : Ich habe diese Version unter Suse 6.5 compiliert, sollte
    somit auch unter Suse 6.5 laufen
- DLXasm.exe : Version für MS-Windows
- DLXasm.l : flex-Quelldatei
- DLXasm.y : yacc-Quelldatei
- Make : Bash-Script zur automatischen Compilierung von DLXasm unter Linux
- Make.bat : Batch-Script - " - unter MS-Windows
- DLX-Befehle : Eine Auflistung der Formate und Opcodes der DLX-Befehle, quasi die "Spezifikation"
- bubble.as : Beispiel-Programm: BubbleSort mit gezieltem Abbruch
- bubble.hs : assemblierte Version
- fibo.as : Beispiel-Programm: Berechnet Fibonacci-Zahl
- fibo.hs : assemblierte Version

Über alle Änderungen/persönlichen Anpassungen am Quellcode - sofern sie erfolgen - bitte ich, mich zu benachrichtigen.

Fragen, Kommentare sowie Tips bitte an Adam Sosnowski

5. Schlußbemerkung und Fazit

Die Verwendung der funktionalen Sprache Haskell in einem Software-Projekt größeren Umfanges hat die besonderen Eigenschaften dieser Programmiersprache und die damit verbundenen Arbeitsweisen deutlich hervortreten lassen. Das Schlagwort "Ausführbare Spezifikation" macht deutlich, daß es und möglich war, ohne größere Vorarbeiten direkt mit Design und Entwicklung des CPU-Simulators zu beginnen. Damit konnte gegenüber einer Entwicklung in einer imperativen Programmiersprache ein erheblicher Zeitgewinn verzeichnet werden. Gleichzeitig erfordert aber die Nutzung des funktionalen Programmierkonzeptes eine erhebliche Umstellung im Aufbau der Programme.

6. Literatur

[Hennessy/Patterson] Hennessy/Patterson : Computer Architecture – A quantitative

approach, 2^nd ed., Morgan-Kauffman, 1998

[Info IIIa] Seeger : Skript zur Vorlesung Informatik IIIa

WS 1999/2000, Philipps - Universität Marburg

[Info IIIb] Loogen : Skript zur Vorlesung Informatik IIIb

WS 1999/2000, Philipps – Universität Marburg

[Thompson] Thompson : Haskell – The Craft of Functional Programming

Addison-Wesley, 1995

[Hudak/Peterson/Fasel] Hudak/Peterson/Fasel : A Gentle Introduction to Haskell

1999

---

[1] Selbstverständlich würde die Benutzung der parallelen funktionalen Sprache EDEN eine echte Parallelverarbeitung ermöglichen.

[2] Die Einteilung in bedingte und unbedingte Sprünge wurde von uns anders vorgenommen, als die evtl. intuitiv zu erwarten wäre : Nur J und JAL sind absolute Sprünge. Da die Befehl JR und JALR auf Register zugreifen, kann es bei deren Abarbeitung zu Datenhazards kommen. Um dieses Problem zu umgehen, wurden diese Instruktionen zu bedingten Sprüngen erklärt und ihre Behandlung in die nachfolgende Phase verlagert.