Embed Size (px)
Citation preview
Hardware/Software-Codesign
Kapitel 5: Hardwaresynthese
M. Schölzel
Zur Erinnerung…
Hardwaresynthese − High-Level-Synthese: Überführt Verhaltensbeschreibung auf
Architekturebene in Strukturbeschreibung auf Architekturebene − Logiksynthese: Überführt Verhaltensbeschreibung auf Logikebene in
Strukturbeschreibung
Bloc
k
Mod
ul Sy
stem
Arch
itekt
ur
Logi
k
Software Hardware
Abstraktionen / Ebenen nach J. Teich
Prozessoren, ASICs, ASIPs, Busse, Speicher,…
Programmiersprachen, Hardwarebeschreibungssprachen,
DAGs, …
ALUs, Register, Multiplexer,…
Boolesche Funktionen, Zustandsautomaten,…
Gatter, Flip-Flops, …
Hardware/Software-Codesign
High-Level-Synthese
Ziel der High-Level-Synthese
Eingabe: Spezifikation einer Funktion durch verhaltensorientierte
Beschreibung Zeitbeschränkung
Ausgabe: Datenpfad und Steuerpfad, zur Berechnung der spezifizierten
Funktion − bei Einhaltung der Zeitbeschränkung − mit minimalen Ressourcen
Erzeugte Architektur
Strukturelle Beschreibung einer Architektur besteht aus: Datenpfad
− Funktionale Ressourcen (Addierer, ALUs, …) − Kommunikationsressourcen (Leitungen, Busse) − Speicherressourcen (Register, FIFOs, RAM, …)
Kontrollpfad Klassifikation Datenpfad: Multiplexer-basiert Bus-basiert Klassifikation Kontrollpfad: Direktimplementierung Mikroprogrammiert
Multiplexer-basierte Architektur
Steuerwerk (Automat)
Datenpfad
F. U. F. U.
Reg.
Reg.
Reg.
Mux Mux
Mux
in
out
Bus-basierte Architektur
R1 R2 R3 R4 R5
Multiplizierer A L U
Ergebnisbus
Operandenbus
Ablauf High-Level-Synthese
Eingabe: − Spezifikation der Funktion (z.B. als VHDL-Programm, Hardware-C, C-Code, …)
Übersetzung der Eingabe in Zwischencode + Optimierungen (Eliminierung toten Codes, redundanter Berechnungen, …)
Erstellung einer internen Beschreibung (z. B. Steuerflussgraph, DAG)
High-Level-Synthese: − Datenpfadsynthese
• Scheduling (Erstellen eines Ablaufplans) • Allocation (Auswahl der Ressourcen) • Binding (Zuordnung der Operationen zu Ressourcen)
− Kontrollpfadsynthese
Datenpfad-Synthese
Scheduling und Allocation sind eng verknüpft Bei Optimierung der Ablaufzeit: In der Regel viele Ressourcen erforderlich Bei Optimierung der Ressourcen: Hohe Ablaufzeiten
1
2
3
4
5
DAG Zeitoptimiert Ressourcenoptimiert
1 3 5
2 4
1
2
3
4
5
Problem-Graph
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2 6 8 10
3 7 9 11
4
5
Ein Problemgraph ist ein gerichteter azyklischer Graph (DAG) mit Knotenmenge V und Kantenmenge E Í V´V. Knoten sind Aufgaben, Kanten beschreiben Abhängigkeiten zwischen den Aufgaben.
Ressource-Graph
1
3
7
2
6
8
1
1
1
1
1
1
α (r 1) = 1
Multiplizierer
r 1
4
9
11
5
10
1
1
1
1
1
α (r 2) = 1r 2
ALU
Ein Ressourcengraph ist ein bibartiter Graph (VR,K), wobei VR = V È VT und K Í V´ VT. VT ist die Menge der Ressourcentypen. Eine Kante (m,n) repräsentiert die Ausführbarkeit der Aufgabe m auf dem Ressourcentyp n.
Weiterhin ist gegeben: • Kostenfunktion c: VT ® , die jedem
Ressourcentyp Kosten zuordnet. • Gewichtsfunktion w: K ® , die jeder
Kante (m,n) die Berechnungszeit der Aufgabe m auf Ressource n zuordnet.
Ein Synthesemodell ist ein Paar aus Problemgraph und Ressourcengraph: ((V,E), (VR,K)).
Zu lösende Syntheseprobleme: • Scheduling (Finden eines Ablaufplans s
zum Problemgraphen) • Allokation • Bindung
Allokation und Bindung
Zu gegebenem Synthesemodell ((V,E), (VR,K)) legt eine Allokation a : VT ® die Anzahl der vorhandenen Instanzen eines jeden Ressourcentyps fest.
Zu gegebenem Synthesemodell ((V,E), (VR,K)) ist eine Bindung gegeben durch: − b: V ® VT mit (v, b(v)) K ist (Zuordnung zu einem Ressourcentyp) − g: V ® mit g(v) < a(b(v)) (Zuordnung zu einer Instanz eines
Ressourcentyps)
Implementierung
Synthesemodell ((V,E), (VR,K)) ist gegeben.
Eine obere Zeitschranke S
Eine Implementierung ist eine Ablaufplanung, Allokation und Bindung (s,b,g,a) mit folgenden Eigenschaften: − Zeitschranke wird eingehalten:
• Für alle v V: s(v) + w(v, b(v)) S
− In jedem Zeitschritt i werden die vorhandenen Ressourcenbeschränkungen eingehalten:
• "i"r VT:|{v | s(v) i < s(v) + w(v, b(v)) und b(v)=r}| a(r)
Ablaufplan und Bindung des Problemgraphen
Ablaufplan des Problemgraphen bei beschränkten Ressourcen
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1
2
6
8
10
3
7
9
11
4
5
Takt 5
Takt 6
Takt 7
Ablaufplan des Problemgraphen bei beschränkten Ressourcen mit Bindung
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1
2
6
8
10
3
7
9
11
4
5
Takt 5
Takt 6
Takt 7
Datenpfad aus der Implementierung ableiten Operationen mit gleicher Bindung werden
durch dieselbe Ressource implementiert
Kanten werden Register
Überlappende Kanten müssen auf verschiedene Register abgebildet werden.
Register, die von unterschiedlichen Ressourcen beschrieben werden, erhalten Multiplexer am Eingang
Ressourcen, die Werte von verschiedenen Registern nutzen, erhalten Multiplexer am Eingang
Beispiel
MUL Add, Cmp Sub
R1 R2
Mux
Mux Mux Mux Mux
Ext Ext
Ablaufplanung (Scheduling)
Zeitpunkt der Ablaufplanung: statisch (zur Übersetzungszeit) dynamisch (zur Abarbeitungszeit der Aufgabe) Zeitpunkt der Unterbrechnung Aufgabe darf unterbrochen werden (präemptive Ablaufplanung) Aufgabe darf nicht unterbrochen werden (nicht-präemptive Ablaufplanung) Art der Beschränkung ressourcenbeschränkt zeitbeschränkt Periodizität periodisch (Planung für iterative Ausführung) aperiodisch
Zeitbeschränkte Planung - As Soon As Possible (ASAP)
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2 6 8 10
3 7 9 11
4
5
0, falls keinen Vorgänger hat( )
max{ ( ) ( ) | ist Vorgänger von } 1, sonstasapasap
vv
u delay u u v
Zeitbeschränkte Planung – As Late As Possible (ALAP)
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2
6
8 10
3
7
9 11
4
5
( ), falls keine Nachfolger hat( , )
min{ ( , ) | ist Nachfolger von } ( ), sonstalapalap
L delay v vL v
L u u v delay v
ALAP-Ablaufplan für L = 5
ASAP-Scheduling mit bedingter Verschiebung (ressourcenbeschränkt)
Ausgangspunkt ist ASAP-Ablaufplan ohne Ressourcenbeschränkung Werden in einem Zeitschritt mehr Ressourcen benötigt, also vorhanden, dann verschieben der nicht ausführbaren Operationen auf späteren Zeitpunkt.
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2 6 8 10
3 7 9 11
4
5
ASAP-Ablaufplan ASAP-Ablaufplan mit bedingter Verschiebung
Ressourcenbeschränkung: a(MUL) = 2, a(ALU) = 2
Ressourcenbeschränkte Ablaufplanung (List-Scheduling)
Bekannt
Zeitbeschränkte Ablaufplanung (Force-Directed-Scheduling)
Ähnlich dem List-Scheduling Priorität einer Operation wird dynamisch bestimmt anhand von: Mobilitätsintervall: (v) = [sasap(v), salap(v)] Ausführungswahrscheinlichkeit p(v,t):
Belegung einer Ressource r:
1, falls ( ) ( )
( , ) ( ) 10, sonst
asap alapv t v
p v t v
V und v ist Operation, dieauf Ressource ausgeführtwerden kann
( , ) ( , )v
r
q r t p v t
Beispiel Belegung einer Ressource
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2
6
8 10
3
7
9 11
4
5
1
1
0 0
0
0
0
2
2
2
2
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2
6
8 10
3
7
9 11
4
5
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2 6 8 10
3 7 9 11
4
5
Belegung des Multiplizierers in Zeitschritt 0:
q(MUL,0) = p(1,0) + p(2,0) + p(6,0) + p(8,0) = 1 + 1 + 1/2 + 1/3 = 17/6 = 2,8333…
Belegungsgraph für das Beispiel mit Multiplizierer und ALU
0
1
2
3
1
2
3
qk,t Multiplizierer
q k,t ALU0 1 2 3
0 1 2 3
t
t
Selbstkraft
Takt 0
Takt 1
Takt 2
Takt 3
q(MUL,0)
qm(MUL,v)
q(MUL,1)
q(MUL,2)
q(MUL,3)
Beispiel für Multiplikation
Mobilität der Operation v qm(MUL,v)
qm(MUL,v)
( )
( )
1( , ) ( , )
( ) 1
alap
asap
v
mt v
q r v q r tv
Mittlere Auslastung der Ressource r im Mobilitätsintervall der Operation v:
Selbstkraft der Operation v zum Zeitpunkt t, v benötigt Ressource r:
,( , ) ( , )S
v t mF q r t q r v
Vorgänger-/Nachfolgerkräfte
Takt 0
Takt 1
Takt 2
Takt 3
q(MUL,0)
qm(MUL,u)
q(MUL,1)
q(MUL,2)
q(MUL,3)
Beispiel für Multiplikation
Alte Mobilität der Operation u
qm(MUL,u)
qm(MUL,u)
( )
( )
1( , ) ( , )
( ) 1
alap
asap
u
nt u
q r u q r tu
Planung einer Operation v ändert Mobilität der Vor-/Nachfolgeroperation u Geänderte Mobilität: (u) Geänderte ASAP/ALAP-Zeit: alap(u), asap(u)
Vor/Nachfolgekraftkraft der Operation u zum Zeitpunkt t, u benötigt Ressource r:
,( , ) ( , )N
u t n mF q r u q r u
Neue Mobilität der Operation u
qn(MUL,u)
qn(MUL,u)
Mittlere Auslastung der Ressource r im neuen Mobilitätsintervall der Operation u:
Gesamtkraft
, , , ,( ) ( )
S N Nv t v t u t u t
u Succ v u Pred v
F F F F
Eingabe: Problemgraph (V, E), Ressourcegraph, Zeitschranke L Ausgabe: Ablaufplan s while noch nicht alle Knoten aus V geplant do Bestimme Mobilitätsintervalle aller nicht geplanten Operationen Bestimme Belegungen der Ressourcen und Ausführungswahrscheinlichkeiten Bestimme Gesamtkräfte aller Operationen Plane Operation v in Zeitpunkt t für die Fv,t minimal ist od
Bindung und Allokation
Ausgangspunkt ist eine Spezifikation bestehend aus Problem- und Ressourcengraphen: ((V,E), (VR,K)) und Eventuell eine Ablaufplanung s Lösung durch Betrachtung von Verträglichkeiten/Konflikten: Verträgliche Aufgaben können auf derselben Ressource ausgeführt werden Aufgaben mit Konflikt müssen auf verschiedenen Ressourcen ausgeführt werden.
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2 6 8 10
3 7 9 11
4
5
Problemgraph mit Ablaufplanung
Verträglichkeitsgraph
7 3
6 1
2 8
7 3
6 1
2 8
7 3
6 1
2 8
11 5
9 10 4
11 5
9 10 4
11 5
9 10 4
Schwache Verträglichkeit (Best Case)
Ablaufplan-Verträglichkeit Starke Verträglichkeit (Worst-Case)
ALU
Multi- plizierer
u ~w v, gdw. u und v können auf derselben Ressource
ausgeführt werden.
u ~a v, gdw. u ~w v und u wird im Ablaufplan erst gestartet,
nachdem die Ausführung von v beendet wurde.
u ~s v, gdw. u ~w v und im Problemgraphen ex. ein
gerichteter Pfad von u nach v.
Berechnung einer Bindung und Allokation
Berechnung durch Finden maximaler Cliquen im Ablaufplanverträglichkeitsgraphen Im Bsp.: {4,5,10,9}, {11}, {2,7},{3,8},{1},{6} Es werden damit 2 ALUs und 4 Multiplizierer benötigt.
Ablaufplan-Verträglichkeit
7 3
6 1
2 8
11 5
9 10 4
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2 6 8 10
3 7 9 11
4
5
Konflikt-Graph Berechnung der Bindung und Allokation durch Färbung des Konfliktgraphen (analog der Färbung des Interferenzgraphen) Im Bsp: {4,5,10,11},{9}, {7,6}{3,1},{2},{8} Damit wieder 2 ALUs und vier Multiplizierer Konfliktgraph nach der Ablaufplanung ist ein Intervallgraph Finden der optimalen Lösung mit Left-Edge-Algorithmus in polynomieller Zeit möglich.
Konfliktgraph nach Ablaufplanung (komplementär zum Verträglichkeitsgraphen)
7 3
6 1
2 8
11 5
9 10 4
u ~k v, gdw. u sind nicht schwach verträglich und werden im Ablaufplan
zur selben Zeit verarbeitet.
Takt 0
Takt 1
Takt 2
Takt 3
Takt 4
1 2 6 8 10
3 7 9 11
4
5
Intervall-Graph
t 2 4 6 8 10 12 14 16 18
1
3
2 4
5
1
2
3
4
5
0
Ein ungerichteter Graph (V, E) heißt Intervallgraph, falls man jedem Knoten v V einen Intervall [av,ev) mit av, ev und av ev zuordnen kann, so dass eine Kannte (u,v) E genau dann existiert, falls sich die Intervalle [au, eu) und [av,ev) überlappen.
Sortierung der Intervalle und Färbung
Left-Edge-Algorithmus bearbeitet die Knoten in aufsteigender Reihenfolge der linken Intervallgrenzen au und weist jedem Knoten die kleinste Farbe zu, mit der noch kein Knoten gefärbt ist, dessen Intervall mit dem Intervall des aktuellen Knotens überlappt.
Kontrollpfadsynthese
Erzeugen eines Moore-Schaltwerkes (direktimplementiert) Gegeben ist eine Implementierung mit einer Latenz L Konstruktion eines Zustandsdiagramms mit L vielen Zuständen z0,…zL-1. Zustand zi repräsentiert Zeitschritt i Eingangssignal reset Startzustand x0 Zustandsübergangsfunktion:
0
1
, falls ( , )
, sonstii
x e resetf z e
z
MUL1 MUL2 ALU1 ALU2
1
r1 r2
r3
2 3 r1
r1
r1
r2
r2
r2
r3
r3
4 5 6
Kon
trollp
fad
Steu
ersig
nale
Kontrollpfadsynthese - Mikroprogrammgesteuert
Instr. 1: *, *, + Instr. 2: *, *, < Instr. 3: -, *, * Instr. 4: -, +
ROM
Kontrollwort
Adresse
Zustand
Nächste Adresse
Reset
Takt
Steuerwerk
Optimierung der Taktperiode
t(rk) ist die Verzögerungszeit, der Ressource rk
Maximale Operatorverzögerung: Schlupf:
max ( ) |k k T
T t r r V
( )( , ) ( )k
k k
t rs T r T t r
T
Minimierung des mittleren Schlupfes bei gegebener Implementierung
h(rk) sei die Anzahl der Operationen, die an die Ressource rk gebunden sind. Mittlerer Taktschlupf: Minimierung von ms(T) durch Berechnen aller möglichen mittleren Taktschlupfe für Perioden im Intervall [Tmin,…,Tmax] Tmin bzw. Tmax sind minimale/maximale Perioden der Ressourcen Mit optimalem Topt kann dann die Ausführungszeit berechnet werden: Tex = L * Topt
| |
1| |
1
( ) ( , )( )
( )
T
T
V
k kk
V
kk
h r s T rms T
h r
Entwurfsraumexploration von anwendungsspezifischen Befehlssatz-
Prozessoren (ASIPs)
Basiselemente in LISA
Alle Operationen zusammen beschreiben den Befehlssatz des Prozessors Coding: Binärcodierung Syntax: Syntax des Assemblerbefehls Behaviour: Verhalten des Befehls
Beschreibt Architektur der Speicherelemente im Prozessor: Arbeitsspeicher Register Pipeline Alle vereinbarten Ressourcen sind global in der LISA-Beschreibung gültig
RESOURCE { }
OPERATION { CODING { … } SYNTAX { … } BEHAVIOR { … } }
Beispiel für Ressourcendeklaration
Mehrere RESOURCE-Abschnitte erlaubt Verfügbare Ressourcen in LISA: REGISTER PROGRAM_COUNTER RAM
− Size: Anzahl der Elemente im Speicher
− BLOCKSIZE: Bits in einem Element
− FLAGS: R=Lesbar, W=Schreibbar, X=Ausführbar
MEMORY_MAP − RANGE: prog_mem wird auf
Bereich 0x0 … 0xfff abgebildet PIN: Pins des Prozessors Globale Variablen
RESOURCE { PROGRAM_COUNTER uint32 PC; REGISTER uint32 IR; REGISTER uint32 GPR[0..31]; RAM uint32 prog_mem { SIZE(0x1000) BLOCKSIZE(32) FLAGS(R|X) }; MEMORY_MAP { RANGE(0x0000, 0x0FFF) -> prog_mem[(31..0)]; } PIN bit[1] IRQ, NMI }
RESOURCE { uint16 forwarded_address; }
Simple Form der Kodierung einer Operation
ADD r0, r1, r2
OPERATION add { SYNTAX { „ADD“ „r0“, „r1“, „r2“ } CODING {0b0[6] 0b00001 0b00010 0b00000 0b0[5] 0b100000 } BEHAVIOR {GPR[0] = GPR[1] + GPR[2]; } }
Immer 0 Opcode
Problem: So müsste für jeden Befehl und jede Registerkombination eine separate OPERATION-Deklaration angegeben erden. Lösung: Deklaration von Gruppen.
Hierarchie von Operationen
instruction behavior: GPR[0] = GPR[1] + GPR[2] instruction syntax : "ADD r0, r1, r2" instruction coding : 000000 00001 00010 00000 00000 100000
instruction behavior: GPR[0] = GPR[1] - GPR[2] instruction syntax : "SUB r0, r1, r2" instruction coding : 000000 00001 00010 00000 00000 100010
Add-Operation: Sub-Operation:
OPERATION alu { DECLARE { GROUP opcode = {add || sub} } SYNTAX { opcode ~ „r0“, „r1“, „r2“ } CODING {0b0[6] 0b00001 0b00010 0b00000 0b0[5] opcode} BEHAVIOR { operand1 = GPR[1]; operand2 = GPR[2]; opcode(); GPR[0] = result; } }
OPERATION add { SYNTAX { „ADD“ } CODING {0b100000} BEHAVIOR { result = operand1 + operand2 } }
OPERATION sub { SYNTAX { „SUB“ } CODING {0b100010} BEHAVIOR { result = operand1 - operand2 } }
• Ein Bezeichner für mehrere Gruppen
• Obergruppe enthält gemeinsames Verhalten.
• Untergruppen modellieren alternatives Verhalten.
• Gruppenname wird als Platzhalter für korrespondierende Sektion in der Unter-gruppe verwendet
alu
add sub
Operationsgraph
behaviour call
Kodierung/Dekodierung der Operationen
Assembler: Vergleicht die eingegebenen Assembleranweisung mit allen
möglichen Assembleranweisungen, die sich durch den Operationsbaum ergeben.
Die passende Folge der Knoten wird aktiviert Die aktivierten Knoten werden zur Kodierung verwendet. Simulator: Vergleicht Bitmuster der zu simulierenden Operationen mit
allen möglichen Bitmustern, die sich im Operationsbaum bilden lassen
Die passende Folge der Knoten wird aktiviert Behaviour-Sektion der aktivierten Knoten wird zur
Ausführung der Anweisung verwendet. Disassembler: Passende Knoten werden wie im Simulator aktiviert. Syntax-Sektion dieser Knoten wird genutzt, um den
Assemblerbefehl zu erzeugen. HDL Code Generator: Nutzt alle Coding-Sektionen, um daraus den HDL-Code für die
Dekodierlogik der Befehle zu erzeugen.
alu
add sub
opcode r0,r1,r2
opcode = add opcode = sub
alu
add sub
000000 00001 00010 00000 00000 opcode
opcode = 100000 opcode = 100010
Generische Operanden
Verhalten: GPR[dest] = GPR[src1] + GPR[src2] Syntax: "ADD r<dest>, r<src1>, r<src2>" Codierung: 000000 <src1> <src2> <dest> 00000100000
Verhalten: GPR[dest] = GPR[src1] - GPR[src2] Syntax: "SUB r<dest>, r<src1>, r<src2>" Codierung: 000000 <src1> <src2> <dest> 00000100010
Add-Operation: Sub-Operation:
OPERATION alu { DECLARE { GROUP opcode = {add || sub} GROUP dest, src1, src2, = {reg} } SYNTAX { opcode ~ dest „,“ src1 „,“ src2 } CODING {0b0[6] src1 src2 dest 0b0[5] opcode} BEHAVIOR { operand1 = GPR[src1]; operand2 = GPR[src2]; opcode(); GPR[dest] = result; } }
OPERATION add { SYNTAX { „ADD“ } CODING {0b100000} BEHAVIOR { result = operand1 + operand2 } }
OPERATION sub { SYNTAX { „SUB“ } CODING {0b100010} BEHAVIOR { result = operand1 - operand2 } }
OPERATION reg { DECLARE { LABEL idx; } SYNTAX { „r“~idx=#U} CODING {idx=0bx[5]} EXPRESSION { idx } }
Label ist ein lokaler Bezeichner innerhalb einer Operation mit: • textueller Repräsentation
in Syntax-Sektion • Binärrepräsentation in
Coding-Sektion • Wert in Behavior-Sektion
• Mehrere Bezeichner für eine Gruppe.
• Obergruppe modelliert gemeinsames Verhalten.
• Untergruppe modelliert gleiches Verhalten an verschiedenen Stellen in der Obergruppe.
Anpassung durch Assembler
ADD r4, r5, r1
OPERATION alu { … SYNTAX { opcode ~ dest „,“ src1 „,“ src2 } … }
OPERATION add { SYNTAX { „ADD“ } … }
OPERATION sub { SYNTAX { „SUB“ } … }
OPERATION reg { … SYNTAX { „r“~idx=#U} … }
idx=4 idx=5 idx=1
Eingabe:
Codierung durch Assembler
OPERATION alu { … SYNTAX { opcode ~ dest „,“ src1 „,“ src2 } CODING {0b0[6] src1 src2 dest 0b0[5] opcode} … }
OPERATION add { SYNTAX { „ADD“ } CODING {0b100000} … }
OPERATION reg { … SYNTAX { „r“~idx=#U} CODING {idx=0bx[5]} … }
idx=4 idx=1 idx=5
000000 00101 00001 00100 00000 100000 Ausgabe:
Matching im Simulator
OPERATION alu { … CODING {0b0[6] src1 src2 dest 0b0[5] opcode} … }
OPERATION add { … CODING {0b100000} … }
OPERATION reg { … CODING {idx=0bx[5]} … }
idx=4
idx=1 idx=5
000000 00101 00001 00100 00000 100000 Eingabe:
OPERATION sub { … CODING {0b100010} … }
OPERATION reg { … CODING {idx=0bx[5]} … }
OPERATION reg { … CODING {idx=0bx[5]} … }
Evaluierung durch Simulator
OPERATION alu { … CODING {0b0[6] src1 src2 dest 0b0[5] opcode} BEHAVIOUR { operand1 = GPR[src1]; operand2 = GPR[src2]; opcode(); GPR[dest] = result; } }
OPERATION reg { … CODING {idx=0bx[5]} EXPRESSION { idx } }
idx=4 idx=1 idx=5
OPERATION reg { … CODING {idx=0bx[5]} EXPRESSION { idx } }
OPERATION add { … CODING {0b100000} BEHAVIOR { result = operand1 + operand2 } }
OPERATION reg { … CODING {idx=0bx[5]} EXPRESSION { idx } }
Modellierung gemeinsamen Verhaltens in verschiedenen Operationen
Zurückschreiben wird in beiden Operationen genutzt.
OPERATION alu { DECLARE { GROUP opcode = {add || sub} GROUP dest, src1, src2, = {reg} } SYNTAX { opcode ~ dest „,“ src1 „,“ src2 } CODING {0b0[6] src1 src2 dest 0b0[5] opcode} BEHAVIOR { operand1 = GPR[src1]; operand2 = GPR[src2]; opcode(); GPR[dest] = result; } }
OPERATION load { DECLARE { GROUP dest = {reg} LABEL addr } SYNTAX { „LOAD“ ~ “ „ dest „,“ „@“~ addr=#X} CODING {0b1[5] dest addr=0bx[16] 0b111011 } BEHAVIOR { result = data_mem[addr]; GPR[dest] = result; } }
Instanzen zur Nutzung gemeinsamer Funktionalität
OPERATION alu { DECLARE { GROUP opcode = {add || sub} GROUP dest, src1, src2, = {reg} } SYNTAX { opcode ~ dest „,“ src1 „,“ src2 } CODING {0b0[6] src1 src2 dest 0b0[5] opcode} BEHAVIOR { operand1 = GPR[src1]; operand2 = GPR[src2]; opcode(); writeback(); } }
OPERATION load { DECLARE { GROUP dest = {reg} LABEL addr } SYNTAX { „LOAD“ ~ “ „ dest „,“ „@“~ addr=#X} CODING {0b1[5] dest addr=0bx[16] 0b111011 } BEHAVIOR { result = data_mem[addr]; writeback(); } }
OPERATION writeback{ BEHAVIOR { GPR[dest] = result; } }
Problem: dest ist nur lokal in den Operationen alu und load gültig.
Lösung des Problems: Referenzen
OPERATION alu { DECLARE { GROUP opcode = {add || sub} GROUP dest, src1, src2, = {reg} } SYNTAX { opcode ~ dest „,“ src1 „,“ src2 } CODING {0b0[6] src1 src2 dest 0b0[5] opcode} BEHAVIOR { operand1 = GPR[src1]; operand2 = GPR[src2]; opcode(); writeback(); } }
OPERATION load { DECLARE { GROUP dest = {reg} LABEL addr } SYNTAX { „LOAD“ ~ “ „ dest „,“ „@“~ addr=#X} CODING {0b1[5] dest addr=0bx[16] 0b111011 } BEHAVIOR { result = data_mem[addr]; writeback(); } }
OPERATION writeback{ DECLARE { REFERENCE dest; } BEHAVIOR { GPR[dest] = result; } }
Eine Referenz ist ein lokaler Bezeichner, der sich auf eine Gruppe in einer übergeordneten Operation bezieht.
Zusammenfassen aller Befehle
OPERATION decode{ DECLARE { GROUP instruction = { nop || alu || load }; } CODING AT (PC) { IR == instruction } SYNTAX { instruction } BEHAVIOR { instruction(); } }
load alu nop
add sub
decode
Mechanismus Befehlsausführung
OPERATION fetch{ DECLARE { INSTANCE decode; } BEHAVIOR { IR = prog_mem[PC]; PC = PC + 1; decode(); } }
OPERATION main { DECLARE { INSTANCE fetch; } BEHAVIOR { fetch(); } }
OPERATION reset { BEHAVIOR { int i; for(i=0; i < 32; i++) { GPR[i] = 0; } IR = 0 ; PC = LISA_PROGRAM_COUNTER operand1 = 0; operand2 = 0; result = 0; } }
load alu nop
add sub
decode
fetch
main
Schnittstelle zum Befehlssatz
Architekturunabhängig: Keine Kodierung, keine
Syntax
OPERATION decode{ DECLARE { GROUP instruction = { nop || alu || load }; } CODING AT (PC) { IR == instruction } SYNTAX { instruction } BEHAVIOR { instruction(); } }
Compiler Generierung
Erweiterung der LISA-Schlüsselworte um: REGISTER, IMMEDIATE, INSTRUCTION Dadurch Kennzeichnung von Operationen, die eine Instruktion im Befehlssatz des Prozessors repräsentieren ein Register / einen Registersatz repräsentieren eine Konstante repräsentieren Einhaltung verschiedener Guidelines erforderlich, insbesondere zur automatischen Extraktion von Abhängigkeiten zwischen LISA-Operationen Bereitstellung weiterer Informationen: Abbildung aller C Datentypen und Operationen auf Assembleranweisungen Stackaufbau/Abbau bei Funktionsaufrufen Unterstützung für spezielle Operationen, die besonders effizient durch den
Prozessor verarbeitet werden können (z.B. MAC)
Ablauf im Compilerbackend in LISA
Code Selection: benötigt Spezifikation aller Muster
Register Allocation: benötigt Spezifikation aller nutzbaren Register (wird teilweise schon automatisch aus der LISA-Beschreibung extrahiert).
Scheduling: benötigt Informationen über Latenz der einzelnen Instruktionen und Abhängigkeiten (Ziel, Quelloperanden werden aus LISA-Beschreibung extrahiert).
Frontend
Register Allocation
Scheduling
Code Selection
IR-Code
Assembler-code
Matcher
Quelle: LISA-Tutorial
Spezifikation eines Musters in LISA
Quelle: LISA-Tutorial
Architekturgetriebene Entwurfsraumexploration mit LISA
LISA-Beschreibung Zielarchitektur
Zielarchitektur
Compiler
Linker
Assembler
Simulator
Profiling (Ausführungszeit)
Anwen-dung
Netzliste
VHDL-Code des Prozessors
Synthesecompiler
Profiling (Taktfrequenz, Fläche,
Stromverbrauch)
Design by Compilation
Compiler übersetzt Anwendung ohne die Zielarchitektur zu kennen
Überblick
Scheduling
Ziel: Minimierung der verwendeten Ressourcen bei gegebener Ablaufplanlänge l: Minimierung der Slots:
Minimierung der Operatoren: Verwendung von zeitbeschränkten Ablaufplanungsverfahren Ablaufplanung beachtet folgende Ressourcenallokationsphase
Ressourcenallokation
Selection: Slot Optimierung
Selection: Typoptimierung
Abschließende Allokation
