View
216
Download
0
Category
Preview:
Citation preview
Frank SlomkaOldenburg, Sommersemester 2003
2Vorlesung Eingebettete Systeme II
Aufbau des Kapitels
• Einführung
• Motivierendes Beispiel
• Grundlagen
• Rechenwerk
• Algorithmen zur Ablaufplanung
• Algorithmen zur Bindung
• Steuerwerk
• Ermittlung der Entwurfsparameter
Frank SlomkaOldenburg, Sommersemester 2003
3Vorlesung Eingebettete Systeme II
Aufbau des Kapitels
• Einführung
• Motivierendes Beispiel
• Grundlagen
• Rechenwerk
• Algorithmen zur Ablaufplanung
• Bestimmung des Taktes
• Algorithmen zur Bindung
• Steuerwerk
• Ermittlung der Entwurfsparameter
Frank SlomkaOldenburg, Sommersemester 2003
4Vorlesung Eingebettete Systeme II
Verhaltenssynthese
Verhalten Struktur
Zelllayout
Maskenlayout
Schaltkreis
Logik
RTL
Alu’s, Mux’s
Transistoren
GatterBoolscheFunktionen
RTL-Beschreibung
Differential-gleichungen
Floorplan physikalischeDarstellung
Algorithmik
Algorithmus
Frank SlomkaOldenburg, Sommersemester 2003
5Vorlesung Eingebettete Systeme II
Grundaufgaben der Synthese
• Allokation
Auswahl einer Komponente• Verhaltenssynthese: ALU, Multiplizierer einer Operation auswählen
• RTL-Synthese: Für eine Verzweigung einen MUX auswählen
• Logiksynthese: Operation UND durch mehrere NANDs realisieren
• Bindung
Eine Operation konkret einer Komponente zuordnen• Verhaltenssynthese: Multiplikation 5 der ALU1 zuweisen.
• RTL-Synthese: Verzweigung3 dem MUX7 zuweisen
• Ablaufplanung
Bei konkurierenden Bindungen die Reihenfolge desZugriffs festlegen
Frank SlomkaOldenburg, Sommersemester 2003
6Vorlesung Eingebettete Systeme II
Literatur
• Daniel D. Gajski et al.. Specification and Design ofEmbedded Systems. Prentice Hall, New Jersey, 1994
• Giovanni De Micheli. Synthesis and Optimization ofDigital Circuits. MacGraw Hill,New Jersey, 1994
• Daniel D. Gajski. Principles of Logic Design. PrenticeHall. New Jersey, 1997
• Jürgen Teich. Digitale Hardware/Software Systeme.Springer Verlag, Berlin, 1997
Frank SlomkaOldenburg, Sommersemester 2003
7Vorlesung Eingebettete Systeme II
Entwurfsmodell
Zu
stan
dsr
egis
ter
Ein
gan
gsl
og
ik
Au
sgan
gsl
og
ik
Steuerwerk Rechenwerk
ALU *
BankRegister-
Register
Register
Frank SlomkaOldenburg, Sommersemester 2003
8Vorlesung Eingebettete Systeme II
Motivierendes Beispiel
• Einführung
• Motivierendes Beispiel
• Grundlagen
• Rechenwerk
• Bestimmung des Taktes
• Algorithmen zur Ablaufplanung
• Algorithmen zur Bindung
• Steuerwerk
• Ermittlung der Entwurfsparameter
Frank SlomkaOldenburg, Sommersemester 2003
9Vorlesung Eingebettete Systeme II
Beispiel
entity square_root isport ( a, b :in Integer;
START :in Bit;RESULT:out Integer;DONE:out Bit);
end square_root;
architecture behavior of square_root isbegin -- square_root(a^2 + b^2);
process(START)begin
if START =1 thenRESULT := max((0.875*max(a,b) + 0.5 *min(a,b), max(a,b));DONE <= 1;
end if;end;
end square_root;
Frank SlomkaOldenburg, Sommersemester 2003
10Vorlesung Eingebettete Systeme II
Beispiel
entity square_root isport ( a, b :in Integer;
START :in Bit;RESULT:out Integer;DONE:out Bit);
end square_root;
architecture behavior of square_root isbegin
process(START)begin
if START =1 thenRESULT := max((0.875*a + 0.5 *b), a); -- square_root(a^2 + b^2);DONE <= 1;
end if;end;
end square_root;
t1 = |a|t2 = |b|x = max (t1,t2)y = min (t1,t2)t3 = x >> 3t4 = y >> 1t5 = x - t3t6 = t4 + t5t7 = max(t6,x)DONE = 1
Frank SlomkaOldenburg, Sommersemester 2003
11Vorlesung Eingebettete Systeme II
Kontroll-/Datenflußgraph (CDFG)
|a| |b|
min max
>>1 >>3
+
-
max
IF
1
y x
t3x
t4
t6
t5
t7
t1 t2
t1 = |a|t2 = |b|x = max (t1,t2)y = min (t1,t2)t3 = x >> 3t4 = y >> 1t5 = x - t3t6 = t4 + t5t7 = max(t6,x)DONE = 1
Frank SlomkaOldenburg, Sommersemester 2003
12Vorlesung Eingebettete Systeme II
|a| |b|
min max
>>1 >>3
+
-
max
IF
1
Taktung
• Welche Taktzykluszeit benötigt man?
• Wievile Takt- oder Kontrollschrittewerden benötigt?
• In welchem Kontrollschritt wird wel-che Operation ausgeführt (Ablaufpla-nung)?
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2
Frank SlomkaOldenburg, Sommersemester 2003
13Vorlesung Eingebettete Systeme II
Bauteile-Bibliothek
Subtrahierer
Multiplexer
Addierer
Subtrahierer
Multiplexer
Betrag
Min
Subtrahierer
Multiplexer
Max
Subtrahierer
Frank SlomkaOldenburg, Sommersemester 2003
14Vorlesung Eingebettete Systeme II
Variablenbelegung
y x t1 t2 t3 t4 t5 t6 t7
|a| |b|
min max
>>1 >>3
+
-
max
IF
1
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2
a b
Frank SlomkaOldenburg, Sommersemester 2003
15Vorlesung Eingebettete Systeme II
Operationsbelegung
absmin max >> - +
2
1 1
2
1
1
1
2
2
2
1
1
1
2 21 1 1 1
|a| |b|
min max
>>1 >>3
+
-
max
IF
1
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2
Frank SlomkaOldenburg, Sommersemester 2003
16Vorlesung Eingebettete Systeme II
Verbindungen
abs1 abs2min max >>1 >>3 - +
abt1t2xyt3t4t5t6t7
IO
III
I
I
I
I
I|a| |b|
min max
>>1 >>3
+
-
max
IF
1
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2
I
I
O
O
O
O
O
O
O
O
O
O
Frank SlomkaOldenburg, Sommersemester 2003
17Vorlesung Eingebettete Systeme II
Sortierte Variablenbelegung
y x t1 t2 t4 t3 t5 t6 t7
|a| |b|
min max
>>1 >>3
+
-
max
IF
1
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2
a b
Frank SlomkaOldenburg, Sommersemester 2003
18Vorlesung Eingebettete Systeme II
Zuordnung der Register
y x t1 t2 t4 t3 t5 t6 t7
|a| |b|
min max
>>1 >>3
+
-
max
IF
1
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2
a b
R1 = [a, y, t1,t4,t6,t7]R2 = [b, x, t2]R3 = [t3, t5]
Frank SlomkaOldenburg, Sommersemester 2003
19Vorlesung Eingebettete Systeme II
Rechenwerk (Datenpfad)
abs abs
MUX
R2
MUX
R1
MUX
R3
- >>1>>3max min +
R1 = [a, y, t1,t4,t6,t7]R2 = [b, x, t2]R3 = [t3, t5]
Frank SlomkaOldenburg, Sommersemester 2003
20Vorlesung Eingebettete Systeme II
Zusammenlegen von Variablen
+
MUX
MUX MUX
a b c d
MUX
x y
MUX
MUX
a,c b,d
MUX
x,y
+
Register-SharingRessource-Sharing
Frank SlomkaOldenburg, Sommersemester 2003
21Vorlesung Eingebettete Systeme II
Algorithmische Bestimmung der Registeranzahl
y x t1 t2 t3 t4 t5 t6 t7a ba
b y
t1
t2
x
Frank SlomkaOldenburg, Sommersemester 2003
22Vorlesung Eingebettete Systeme II
Aufstellen eines Kompatibilitätsgraphen
y x t1 t2 t3 t4 t5 t6 t7a ba
b y
t1
t2
x
Frank SlomkaOldenburg, Sommersemester 2003
23Vorlesung Eingebettete Systeme II
Aufstellen eines Kompatibilitätsgraphen
a
b x
t1
t2
y
y x t1 t2 t3 t4 t5 t6 t7a b
Frank SlomkaOldenburg, Sommersemester 2003
24Vorlesung Eingebettete Systeme II
Aufstellen eines Kompatibilitätsgraphen
a
b
t1 y
t7
t3 t5
t4 y x t1 t2 t3 t4 t5 t6 t7a b
t6
xt2
Frank SlomkaOldenburg, Sommersemester 2003
25Vorlesung Eingebettete Systeme II
Bestimmung der Registerzuordnung durch Graphfärbung
R1 = [a, t1,y, t3, t5, t6, t7]
a
b
t1 y
t7
t3 t5
t4
t6
xt2
Frank SlomkaOldenburg, Sommersemester 2003
26Vorlesung Eingebettete Systeme II
Bestimmung der Registerzuordnung durch Graphfärbung
a
b x
t1
t2
y
t7
t3 t6t5
t4
R1 = [a, t1,y, t3, t5, t6, t7]
R2 = [b, t2, t4, t5, t5, t6]
Frank SlomkaOldenburg, Sommersemester 2003
27Vorlesung Eingebettete Systeme II
Bestimmung der Registerzuordnung durch Graphfärbung
a
b x
t1
t2
y
t7
t3 t6t5
t4
R1 = [a, t1,y, t3, t5, t6, t7]
R2 = [b, t2, t4, t5, t5, t6]
R3 = [x]
Frank SlomkaOldenburg, Sommersemester 2003
28Vorlesung Eingebettete Systeme II
Nutzung gemeinsamer Ressourcen
+
a b c d
-
x y
keine gemeinsame Nutzung
+/-
MUX
a b c d
MUX
x y
gemeinsame Nutzung
Frank SlomkaOldenburg, Sommersemester 2003
29Vorlesung Eingebettete Systeme II
Aufstellen eines Kompatibilitätsgraphen
|a| |b|
min max
>>1 >>3
+
-
max
IF
1
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2
|a| |b|
maxmin
+ -
Frank SlomkaOldenburg, Sommersemester 2003
30Vorlesung Eingebettete Systeme II
Partitionierung 1
|a| |b|
min max
>>1 >>3
+
-
max
1
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2
IF
|a|
+ -
maxmin
|b|
Frank SlomkaOldenburg, Sommersemester 2003
31Vorlesung Eingebettete Systeme II
Partitionierung 2
|a| |b|
min max
>>1 >>3
+
-
max
IF
1
S1
S2
S3
S4
S5
S6
S7
y x
t3x
t4
t6
t5
t7
t1 t2 |a| |b|
maxmin
+ -
Frank SlomkaOldenburg, Sommersemester 2003
32Vorlesung Eingebettete Systeme II
Rechenwerk (Datenpfad)
R1 R2 R3
MUX MUX MUX
>>3>>1abs/min abs/max/+/-
MUX
|a| |b|
min
+ -
max
Frank SlomkaOldenburg, Sommersemester 2003
33Vorlesung Eingebettete Systeme II
Rechenwerk (Datenpfad)
R3
>>3>>1abs/min abs/max/+/-
MUX
MUXMUX
R2R1
MUX
Frank SlomkaOldenburg, Sommersemester 2003
34Vorlesung Eingebettete Systeme II
R1 R3
MUX MUX
>>3>>1abs/min abs/min/+/-
MUX
Zusammenlegen von Verbindungen: Busse
AB C
D E
F G
H
I JK L
R2
MUX
M N
Frank SlomkaOldenburg, Sommersemester 2003
35Vorlesung Eingebettete Systeme II
Zusammenlegen von Verbindungen: Busse
S0 S1 S2 S3 S4 S5 S6 S7
A X
B X X
C X X X
D X X
E X
F X X X X
G X
H X
I X X X
J X X X X
K X
L X
Frank SlomkaOldenburg, Sommersemester 2003
36Vorlesung Eingebettete Systeme II
Zusammenlegen von Verbindungen: Busse
B
F
D E
C
A
HG
N
M
I
J
K
L
Frank SlomkaOldenburg, Sommersemester 2003
37Vorlesung Eingebettete Systeme II
Zusammenlegen von Verbindungen: Busse
B
F
D E
C
A
HG
I K
L
Ausgangsleitungen (Register) Eingangsleitungen (Register)
Bus1
Bus2
Bus3
Bus4N
M
J
Frank SlomkaOldenburg, Sommersemester 2003
38Vorlesung Eingebettete Systeme II
Rechenwerk (Datenpfad)
R1 R2 R3
>>3>>1abs/min abs/min/+/-
Frank SlomkaOldenburg, Sommersemester 2003
39Vorlesung Eingebettete Systeme II
Zusammenlegen von Registern
S0 S1 S2 S3 S4 S5 S6 S7
R1
R2
R3
Frank SlomkaOldenburg, Sommersemester 2003
40Vorlesung Eingebettete Systeme II
Zusammenlegen von Registern
S0 S1 S2 S3 S4 S5 S6 S7
R1
R2
R3
R3
R1 R2
Frank SlomkaOldenburg, Sommersemester 2003
41Vorlesung Eingebettete Systeme II
Rechenwerk (Datenpfad)
R3
R1R2
>>3>>1abs/min abs/min/+/-
Frank SlomkaOldenburg, Sommersemester 2003
42Vorlesung Eingebettete Systeme II
Grundlagen
• Einführung
• Motivierendes Beispiel
• Grundlagen
• Rechenwerk
• Algorithmen zur Ablaufplanung
• Bestimmung des Taktes
• Algorithmen zur Bindung
• Steuerwerk
• Ermittlung der Entwurfsparameter
• Optimierung
Frank SlomkaOldenburg, Sommersemester 2003
43Vorlesung Eingebettete Systeme II
Algorithmen und Komplexität
• Bei der Verhaltenssynthese handelt es sich um Ent-scheidungs und Optimierungsprobleme.
Definition : Ein Algorithmus ist eine Berechnungsvor-schrift, die aus einer Menge von Eingaben, Ausgaben undeiner endlichen Anzahl von Bearbeitungsschrittenbesteht und in einer endlichen Anzahl von Bearbeitungs-schritten terminiert.
oder ein Algorithmus ist :
Ein Rezept für ein Programm
Frank SlomkaOldenburg, Sommersemester 2003
44Vorlesung Eingebettete Systeme II
Klassifikation von Algorithmen
• Qualität der Lösung
• exakt
• approximativ (heuristisch)
• Berechnungsaufwand (Zeit- und Speicherbedarf)
• worst case
• avarage case
• Komplexitätsanalyse
• Maß der Zeitkomplexität an elementaren Operationen als Funktion derProblemgröße n.
Definition : Die Zeitkomlexität eines Algorithmus derProblemgröße n von der Ordnung f(n), geschriebenO(f(n)), wenn es eine Konstante c gibt, so daß c f(n) eineobere Schranke für die Anzahl von Operationen darstellt.
Frank SlomkaOldenburg, Sommersemester 2003
45Vorlesung Eingebettete Systeme II
Effizienz
• Effizient: Polynomielle Algorithmen, bei denen f(n) einPolynom in n ist:
f(n) = n3 + 1/2 n
• Ineffizient: Algorithmen mit exponentieller Laufzeit:
f(n) = 2n
f(n) =nn/2
Frank SlomkaOldenburg, Sommersemester 2003
46Vorlesung Eingebettete Systeme II
Optimalität
Definition : Optimalität - Ein Algorithmus heißt opti-mal, wenn seine Komplexität gleich der dem Probleminhärenten Komplexität ist.
• Beispiel: Bestimmung des Maximums von n ganzenZahlen. Untere Schranke: n Operationen. Jeder Algo-rithmus der Komplexität O(n) ist optimal.
Frank SlomkaOldenburg, Sommersemester 2003
47Vorlesung Eingebettete Systeme II
Klassifikation von Problemen
P
NP-Vollständig
NP
NP-hart
Frank SlomkaOldenburg, Sommersemester 2003
48Vorlesung Eingebettete Systeme II
NP-Vollständig
NP-Vollständig(Erfüllbarkeitsproblem)
SAT
Cooksche TransformationTransformation mit polyno-mieller Komplexität
TSP
G3C
1) Raten einer Lösung
2) Überprüfen (in polynomieller Zeit!), ob Lösung gültig.
Frank SlomkaOldenburg, Sommersemester 2003
49Vorlesung Eingebettete Systeme II
Datenstrukturen
• Kontrollflußgraph
• Datenflußgraph
• Kontrolldatenfluß- bzw. Sequenzgraph
• Ressourcengraph
• Algebraische Spezifikation von Allokation und Bindung
Frank SlomkaOldenburg, Sommersemester 2003
50Vorlesung Eingebettete Systeme II
Kontrollflußgraph
BasisblockBasisblock
Steuerblock
Steuerblock
B2
S1
S2
• Modellierung des Kontrollflusses einer gegebenen algo-rithmischen Beschreibung (z.B. C-Programm)
• Aufteilung der algorithmischen Beschreibung in Steuer-und Basisblöcke.
C-Programm:
do {
if (a > 0) {
c = a + b + f;
d = e - c;
} else {
a++;
d = a + d;
}
} while (d > 0)
Kontrollflußgraph:
B1
B2
S2
B1
S1
B1
Frank SlomkaOldenburg, Sommersemester 2003
51Vorlesung Eingebettete Systeme II
Datenflußgraph
• Modellierung des Datenflußes von Datenoperationeneiner algorithmischen Beschreibung
C-Programm:
do {
if (a > 0) {
c = a + b + f;
d = e - c;
} else {
a++;
d = a + d;
}
} while (d > 0)
B1
B2
B1 ++
a b
d
e +
-c
1a
+
d
f
B1 B2
Datenflußgraphen:
Frank SlomkaOldenburg, Sommersemester 2003
52Vorlesung Eingebettete Systeme II
Datenflußgraph
x1 = x +dxu1 = u - (3*x*u*dx) - (3*y*dx)y1 =y + u*dxc = x1 < A
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
Frank SlomkaOldenburg, Sommersemester 2003
53Vorlesung Eingebettete Systeme II
Kontrolldatenflußgraph
BasisblockBasisblock
Steuerblock
SteuerblockS1
S2
+
1a
+
dB2
+
a b
d
e +
-c
f
B1
• Modellierung der kompletten algorithmischen Beschrei-bung durch Kombination von CFG und DFG.
• Aus den DFGs können sowohl die Kosten als auch dasZeitverhalten der einzelnen Steuerblöcke als auch derBasisblöcke abgeleitet werden.
Frank SlomkaOldenburg, Sommersemester 2003
54Vorlesung Eingebettete Systeme II
Sequenzgraph (Funktionen)
*
+
N
N
+
C
N
N
+ *
Call
Frank SlomkaOldenburg, Sommersemester 2003
55Vorlesung Eingebettete Systeme II
Sequenzgraph (Verzweigungen)
*
+
N
N
+
BR
N
N
+ *
N
N
-
Branch
B1 B2
Frank SlomkaOldenburg, Sommersemester 2003
56Vorlesung Eingebettete Systeme II
Ressourcegraph
r1
*
*
*
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
1
2
3
*
*
*
6
7
8
MUL
α(r1) = 2
2
22
2
2
2
Frank SlomkaOldenburg, Sommersemester 2003
57Vorlesung Eingebettete Systeme II
Ressourcegraph
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
r2
-
-
+
4
5
9
+
<
10
11
ALU
α(r2) = 1
1
11
1
1
Frank SlomkaOldenburg, Sommersemester 2003
58Vorlesung Eingebettete Systeme II
Ressourcegraph
GR(VR,ER) besteht aus KnotenVR = VS ∪ VT mit:
VS ∈ GS Knoten des Sequenzgra-phen.
VT Knoten, die den jeweiligen Res-sourcentyp spezifizieren.
Kanten (vs,vt), die die Verfügbar-keit einer Instanz vom Ressource-typ vt für eine Operation vsbeschreiben.
r1
*
*
*
1
2
3
*
*
*
6
7
8
MUL
α(r1) = 2
2
22
2
2
2
r2
-
-
+
4
5
9
+
<
10
11
ALU
α(r2) = 1
1
11
1
1
Frank SlomkaOldenburg, Sommersemester 2003
59Vorlesung Eingebettete Systeme II
Allokation, Bindung, Ablaufplan
Definition : Eine Allokation ist eine Funktion α: VT ->Z+ die jedem Ressourcetyp vt ∈ VT die Anzahl α(vt) verfüg-barer Instanzen zuweist.
Definition : Die Bindung eines Sequenzgraphen sindFunktionen β: Vs -> VT und γ: Vs -> Z+, wobei β(vs) = vt undγ(vs) = r bedeutet, daß die r-te Instanz des Ressourcetypsvt implementiert wird. Eine gültige Bedingung erfüllt dieBedingungen: β(vs) = vt und γ(vs) < α(vt) .
Definition : Ein Ablaufplan (Schedule) eines Sequenz-graphen GS = (VS,ES) ist eine Funktion τ: Vs -> N, die dieBedingungen τ(vj) - τ(vi) > wi ∀ (vi,vj) ∈ ES erfüllt. Dabeibeschreibt die Funktion wi: Vs -> N, die jeweilige Ausfüh-rungszeit von vi auf vt.
Frank SlomkaOldenburg, Sommersemester 2003
60Vorlesung Eingebettete Systeme II
Beispiel
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
r2
-
-
*
4
5
9
*
*
10
11
ALU
α(r2) = 1
1
11
1
1
Frank SlomkaOldenburg, Sommersemester 2003
61Vorlesung Eingebettete Systeme II
Beispiel
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
β(v4) = r2 γ(v4) = 1β(v5) = r2 γ(v5) = 1β(v6) = r1 γ(v6) = 1β(v7) = r1 γ(v7) = 1β(v8) = r1 γ(v8) = 1β(v9) = r2 γ(v9) = 1β(v10) = r2 γ(v10) = 1β(v11) = r2 γ(v11) = 1
Frank SlomkaOldenburg, Sommersemester 2003
62Vorlesung Eingebettete Systeme II
Beispiel
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
r2
-
-
*
4
5
9
*
*
10
11
ALU
α(r2) = 2
1
11
1
1
1
2
Frank SlomkaOldenburg, Sommersemester 2003
63Vorlesung Eingebettete Systeme II
Beispiel
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
1
2
β(v4) = γ(v4) =β(v5) = γ(v5) =β(v6) = γ(v6) =β(v7) = γ(v7) =β(v8) = γ(v8) =β(v9) = γ(v9) =β(v10) = γ(v10) =β(v11) = γ(v11) =
Frank SlomkaOldenburg, Sommersemester 2003
64Vorlesung Eingebettete Systeme II
Beispiel
β(v4) = r2 γ(v4) = 1β(v5) = r2 γ(v5) = 1β(v6) = r1 γ(v6) = 1β(v7) = r1 γ(v7) = 1β(v8) = r1 γ(v8) = 1β(v9) = r2 γ(v9) = 1β(v10) = r2 γ(v10) = 2β(v11) = r2 γ(v11) = 2
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
1
2
Frank SlomkaOldenburg, Sommersemester 2003
65Vorlesung Eingebettete Systeme II
Latenz
Definition : Die Latenz L eines Ablauf-plans τ eines Sequenzgraphen GS = VS,ES)ist definiert als L = max (τ(vi) + wi) - min (vj)
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
Frank SlomkaOldenburg, Sommersemester 2003
66Vorlesung Eingebettete Systeme II
Beispiel
Definition : Die Latenz L eines Ablauf-plans τ eines Sequenzgraphen GS = VS,ES)ist definiert als L = max (τ(vi) + wi) - min (vj)
* ** * +
* * <+
-
-
3 x u dx 3 y u dx x dx
aydx
u
x1
y1
u1
1 2
3
4
5
6
7
8
9
10
11
w1
τ1
w3
τ3
w4τ4
w5
τ2
max(τ(vi) + wi)
min(τ(vj))
Frank SlomkaOldenburg, Sommersemester 2003
67Vorlesung Eingebettete Systeme II
Übersicht
• Einführung
• Motivierendes Beispiel
• Grundlagen
• Rechenwerk
• Algorithmen zur Ablaufplanung
• Algorithmen zur Bindung
• Steuerwerk
• Ermittlung der Entwurfsparameter
• Optimierung
Frank SlomkaOldenburg, Sommersemester 2003
68Vorlesung Eingebettete Systeme II
Ablaufplanung
Einteilung
• Unbeschränkte Ressourcen: Keine Vorgaben
• Beschränkte Ressourcen: Vorgaben von Ressourcenbe-schränkungen (Anzahl, Typen), die den Lösungsraumgeeigneter Ablaufpläne einschränken.
• Transformatorische Algorithmen
• Iterativ konstruktive Algorithmen
Frank SlomkaOldenburg, Sommersemester 2003
69Vorlesung Eingebettete Systeme II
Ablaufplanung
Ablaufplanung ohne Ressourcenbeschränkungen
• Bestimmung unterere Schranken
• Bindung mit dedizierten Ressourcen
• Lösung der Ablaufplanung nach der Bindung, d.h. dieKosten der späteren Implementierung sind unabhängigvon der Ablaufplanung.
Frank SlomkaOldenburg, Sommersemester 2003
70Vorlesung Eingebettete Systeme II
Ablaufplanung
Definition : Gegeben ein Sequenz- und eine Res-sourcegraph, mit einer Gewichtungsfunktion, die jederKante in GR die Ausführungszeit ws = w(vs,vt) zuordnet.Unter Latenzminimierung ohne Ressourcenbeschränkungversteht man das Problem
min {L | τ(vi) - τ(vj ) > wi, ∀ (vi,vj) ∈ ES}
Frank SlomkaOldenburg, Sommersemester 2003
71Vorlesung Eingebettete Systeme II
ASAP/ALAP
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
Frank SlomkaOldenburg, Sommersemester 2003
72Vorlesung Eingebettete Systeme II
ASAP/ALAP
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Soon as Possible (ASAP):
1. Plane alle Startknoten
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
+*
+ +12
6 8
Frank SlomkaOldenburg, Sommersemester 2003
73Vorlesung Eingebettete Systeme II
ASAP/ALAP
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Soon as Possible (ASAP):
1. Plane alle Startknoten2. Plane alle Knoten deren Vor-
gänger bereits eingeplantsind
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
+*
+ +<
**
12
3
6
7
89
Frank SlomkaOldenburg, Sommersemester 2003
74Vorlesung Eingebettete Systeme II
ASAP/ALAP
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Soon as Possible (ASAP):
1. Plane alle Startknoten2. Plane alle Knoten deren Vor-
gänger bereits eingeplantsind
3. Führe Schritt 2 solange ausbis alle Knoten geplant sind
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
+*
+ +<
**
+
12
3
4
6
7
89
Frank SlomkaOldenburg, Sommersemester 2003
75Vorlesung Eingebettete Systeme II
ASAP/ALAP
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Soon as Possible (ASAP):
1. Plane alle Startknoten2. Plane alle Knoten deren Vor-
gänger bereits eingeplantsind
3. Führe Schritt 2 solange ausbis alle Knoten geplant sind
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
+*
+ +<
**
+
*
12
3
4
5
6
7
89
Frank SlomkaOldenburg, Sommersemester 2003
76Vorlesung Eingebettete Systeme II
ASAP/ALAP
+*
+ +<
**
+
*
12
3
4
5
6
7
89
Lat
enz
= 7
Z.E
.
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Soon as Possible (ASAP):
1. Plane alle Startknoten2. Plane alle Knoten deren Vor-
gänger bereits eingeplantsind
3. Führe Schritt 2 solange ausbis alle Knoten geplant sind
Frank SlomkaOldenburg, Sommersemester 2003
77Vorlesung Eingebettete Systeme II
ASAP/ALAP
<*59
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Late as Possible (ALAP):
1. Plane alle Endknoten
Frank SlomkaOldenburg, Sommersemester 2003
78Vorlesung Eingebettete Systeme II
ASAP/ALAP
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Late as Possible (ALAP):
1. Plane alle Endknoten2. Plane alle Knoten deren
Nachfolger bereits einge-plant sind
3. Führe Schritt 2 solange ausbis alle Knoten geplant sind
+<
**
+
*
3
4
5
7
89
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
Frank SlomkaOldenburg, Sommersemester 2003
79Vorlesung Eingebettete Systeme II
ASAP/ALAP
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Late as Possible (ALAP):
1. Plane alle Endknoten2. Plane alle Knoten deren
Nachfolger bereits einge-plant sind
3. Führe Schritt 2 solange ausbis alle Knoten geplant sind
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
+
+<
**
+
*
3
4
5
6
7
89
Frank SlomkaOldenburg, Sommersemester 2003
80Vorlesung Eingebettete Systeme II
ASAP/ALAP
• Polynomielle Algorithmen
• Keine Ressourcenbeschrän-kung!
• Ablaufplan ist latenzoptimal
• As Late as Possible (ALAP):
1. Plane alle Endknoten2. Plane alle Knoten deren
Nachfolger bereits einge-plant sind
3. Führe Schritt 2 solange ausbis alle Knoten geplant sind
+ *
+
+<
**
+
*
12
3
4
5
6
7
89
Lat
enz
= 7
Z.E
.
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
Frank SlomkaOldenburg, Sommersemester 2003
81Vorlesung Eingebettete Systeme II
ASAP/ALAP
+
+
*
+ +
*
*
*
<
1 2
3
4
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
1 ALU1 MUL
Ressourcen:5
• Linearer Algorithmus
• Ressourcenbeschränkungwird berücksichtigt
• Ablaufplan ist suboptimal
+ *
+
+<
**
+
*
12
3
4
5
6
7
89
Lat
enz
= 7
Z.E
.
Frank SlomkaOldenburg, Sommersemester 2003
82Vorlesung Eingebettete Systeme II
Listscheduling
• Linearer Algorithmus
• Ressourcenbeschränkungwird berücksichtigt
• Ablaufplan ist suboptimal
• Listscheduling:
1. Berechne für jeden Knoteneine Priorität (z.B. Mobilitätnach ASAP/ALAP), t = 0
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
1 ALU1 MUL
Ressourcen:
+ *
+
+<
**
+
*
12
3
4
5
6
7
89
ASAP
Mobilität
ALAP
Frank SlomkaOldenburg, Sommersemester 2003
83Vorlesung Eingebettete Systeme II
Listscheduling
• Linearer Algorithmus
• Ressourcenbeschränkungwird berücksichtigt
• Ablaufplan ist suboptimal
• Listscheduling:
1. Berechne für jeden Knoteneine Priorität (z.B. Mobilitätnach ASAP/ALAP), t = 0
2. Sortiere alle nicht geplantenKnoten deren Vorgänger zurZeit t ausgeführt sind nachihrer Priorität
3. Plane alle Knoten gemäß dersortierten Reihenfolgesoweit die jeweils benötigtenRessourcen zur Zeit t freisind.
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
+*
12
Frank SlomkaOldenburg, Sommersemester 2003
84Vorlesung Eingebettete Systeme II
Listscheduling
• Linearer Algorithmus
• Ressourcenbeschränkungwird berücksichtigt
• Ablaufplan ist suboptimal
• Listscheduling:
1. Berechne für jeden Knoteneine Priorität (z.B. Mobilitätnach ASAP/ALAP), t = 0
2. Sortiere alle nicht geplantenKnoten deren Vorgänger zurZeit t ausgeführt sind nachihrer Priorität
3. Plane alle Knoten gemäß dersortierten Reihenfolgesoweit die jeweils benötigtenRessourcen zur Zeit t freisind.
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
+* +
12
6
Frank SlomkaOldenburg, Sommersemester 2003
85Vorlesung Eingebettete Systeme II
Listscheduling
+* +
+*
12
3
68
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
• Linearer Algorithmus
• Ressourcenbeschränkungwird berücksichtigt
• Ablaufplan ist suboptimal
• Listscheduling:
1. Berechne für jeden Knoteneine Priorität (z.B. Mobilitätnach ASAP/ALAP), t = 0
2. Sortiere alle nicht geplantenKnoten deren Vorgänger zurZeit t ausgeführt sind nachihrer Priorität
3. Plane alle Knoten gemäß dersortierten Reihenfolgesoweit die jeweils benötigtenRessourcen zur Zeit t freisind.
Frank SlomkaOldenburg, Sommersemester 2003
86Vorlesung Eingebettete Systeme II
Listscheduling
• Linearer Algorithmus
• Ressourcenbeschränkungwird berücksichtigt
• Ablaufplan ist suboptimal
• Listscheduling:
1. Berechne für jeden Knoteneine Priorität (z.B. Mobilitätnach ASAP/ALAP), t = 0
2. Sortiere alle nicht geplantenKnoten deren Vorgänger zurZeit t ausgeführt sind nachihrer Priorität
3. Plane alle Knoten gemäß dersortierten Reihenfolgesoweit die jeweils benötigtenRessourcen zur Zeit t freisind.
+* +
+<*
12
3
689
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
Frank SlomkaOldenburg, Sommersemester 2003
87Vorlesung Eingebettete Systeme II
Listscheduling
• Linearer Algorithmus
• Ressourcenbeschränkungwird berücksichtigt
• Ablaufplan ist suboptimal
• Listscheduling:
1. Berechne für jeden Knoteneine Priorität (z.B. Mobilitätnach ASAP/ALAP), t = 0
2. Sortiere alle nicht geplantenKnoten deren Vorgänger zurZeit t ausgeführt sind nachihrer Priorität
3. Plane alle Knoten gemäß dersortierten Reihenfolgesoweit die jeweils benötigtenRessourcen zur Zeit t freisind.
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
+* +
+<
*
*
+
*
12
3
4
5
6
7
89
Lat
enz
= 8
Z.E
.
Frank SlomkaOldenburg, Sommersemester 2003
88Vorlesung Eingebettete Systeme II
Force-Directed Scheduling
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
+ *
+
+<
**
+
*
12
3
4
5
6
7
89
ASAP
Mobilität
ALAP
• Linearer Algorithmus
• Ressourcenbeschränkungwird berücksichtigt
• Ablaufplan ist suboptimal
• Force-Directed Scheduling:
1. Berechne für jeden Knoteneine Priorität (z.B. Mobilitätnach ASAP/ALAP), t = 0
2. Bestimme das Mobilitätsinter-vall der Knoten für jede Res-source getrennt.
Frank SlomkaOldenburg, Sommersemester 2003
89Vorlesung Eingebettete Systeme II
Force-Directed Scheduling
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
3. Berechne für jeden Knotenseine Ausführungswahr-scheinlichkeit im Mobiltitätsin-tervall t = [τs(vi), τl(vi)]:
pi t, µ vi( ) +----------------------=
1
1
4
8
16
9
11/61/2 1/3ALU
Frank SlomkaOldenburg, Sommersemester 2003
90Vorlesung Eingebettete Systeme II
Force-Directed Scheduling
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
4
8
16
9
17/62/31/34/31/31/6
11/61/2 1/3ALU qk,t = Σ
3. Berechne für jeden Knotenseine Ausführungswahr-scheinlichkeit im Mobiltitätsin-tervall t = [τs(vi), τl(vi)]:
4. Bestimme für jeden Zeit-schritt die Belegung der Res-source.
pi t, µ vi( ) +----------------------=
1
1
Frank SlomkaOldenburg, Sommersemester 2003
91Vorlesung Eingebettete Systeme II
Force-Directed Scheduling
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
2
7
14/34/34/31/311
1 1/3MUL qk,t = Σ
3
5
3. Berechne für jeden Knotenseine Ausführungswahr-scheinlichkeit im Mobiltitätsin-tervall t = [τs(vi), τl(vi)]:
4. Bestimme für jeden Zeit-schritt die Belegung der Res-source.
pi t, µ vi( ) +----------------------=
1
1
Frank SlomkaOldenburg, Sommersemester 2003
92Vorlesung Eingebettete Systeme II
Force-Directed Scheduling
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
3. Berechne für jeden Knotenseine Ausführungswahr-scheinlichkeit im Mobiltitätsin-tervall t = [τs(vi), τl(vi)]:
4. Bestimme für jeden Zeit-schritt die Belegung der Res-source.
5. Aus der Liste der ungeplan-ten Aufgaben, plane die Auf-gabe mit der geringsten Kraft.Dabei wird die Kraft für jedenZeitschritt unter derAnnahme berechnet, daß dieOperation jeweils in diesemSchritt geplant wird:
pi t, µ vi( ) +----------------------=
1
1
Fk t, qk t, pk t,sched pi t,–( )⋅
t∑=
2
7
14/34/34/31/311
1 0,33MUL
3
5
qk,t = Σ
-1/3-7/9-8/9-8/9
-28/9-28/9-28/9-47/9
00
Frank SlomkaOldenburg, Sommersemester 2003
93Vorlesung Eingebettete Systeme II
Force-Directed Scheduling
3. Berechne für jeden Knotenseine Ausführungswahr-scheinlichkeit im Mobiltitätsin-tervall t = [τs(vi), τl(vi)]:
4. Bestimme für jeden Zeit-schritt die Belegung der Res-source.
5. Aus der Liste der ungeplan-ten Aufgaben, plane die Auf-gabe mit der geringsten Kraft.Dabei wird die Kraft für jedenZeitschritt unter derAnnahme berechnet, daß dieOperation jeweils in diesemSchritt geplant wird:
pi t, µ vi( ) +----------------------=
1
1
Fk t, qk t, pk t,sched pi t,–( )⋅
t∑=
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
4
8
16
9
17/62/31/34/31/31/6
11/61/2 1/3ALU qk,t = Σ
-1/12-13/12
0
Frank SlomkaOldenburg, Sommersemester 2003
94Vorlesung Eingebettete Systeme II
Force-Directed Scheduling
+* +
+<
*
*
+
*
12
3
4
5
6
7
89
Lat
enz
= 8
Z.E
.
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
0 2 51Mobilität:
Priorität
1 ALU1 MUL
Ressourcen:
3. Berechne für jeden Knotenseine Ausführungswahr-scheinlichkeit im Mobiltitätsin-tervall t = [τs(vi), τl(vi)]:
4. Bestimme für jeden Zeit-schritt die Belegung der Res-source.
5. Aus der Liste der ungeplan-ten Aufgaben, plane die Auf-gabe mit der geringsten Kraft.
6. Addiere zur Selbstkraft jedeseinzelnen Knoten die Kräftealler seiner Vorgänger undNachfolger.
pi t, µ vi( ) +----------------------=
1
1
Frank SlomkaOldenburg, Sommersemester 2003
95Vorlesung Eingebettete Systeme II
Pfadscheduling
• Pfadbasiertes Verfahren:
- As Fast as Possible (AFAP)(Camposano 1991)
• Globales Verfahren auf Kon-trollflußgraphen (CFG)
• Vorteil: Ablaufplanung überdie Grenzen von Basisblöckenist möglich
• Nachteil: Pfadexplosion beikomplexen Algorithmen
• Voraussetzung: Allokation istfestgelegt
do {
if (a > 0) {
c = a + b + f;
d = e - c;
} else {
a++;
d = a + d;
}
} while (d > 0)
B1
B2
S2
B1
S1
>
>a>0 a>0
d>0
C-ProgrammCFG
+ +
+ +
= =
-
=
Frank SlomkaOldenburg, Sommersemester 2003
96Vorlesung Eingebettete Systeme II
Pfadschduling
• Algorithmus:
1. Schleifeneleminierung
vf
vl
Store:1,5,d>0
>
>a>0 a>0
d>0
+ +
+ +
= =
-
=
1
2
3
4
5
6
7
8
>
>a>0 a>0
+ +
+ +
= =
-
=
9
10
Frank SlomkaOldenburg, Sommersemester 2003
97Vorlesung Eingebettete Systeme II
Pfadschduling
• Algorithmus:
1. Schleifeneleminierung2. Auftrennen des CFG in Teil-
graphen, die durch Verzwei-gungen oder den Beginn vonSchleifen definiert sind
vf
vl
Store:1,5,d>0
>
>a>0 a>0
d>0
+ +
+ +
= =
-
=
1
2
3
4
5
6
7
8
>
>a>0 a>0
+ +
+ +
= =
-
=
9
10
Pfad
1 2
Frank SlomkaOldenburg, Sommersemester 2003
98Vorlesung Eingebettete Systeme II
Pfadschduling
• Algorithmus:
1. Schleifeneleminierung2. Auftrennen des CFG in Teil-
graphen, die durch Verzwei-gungen oder den Beginn vonSchleifen definiert sind
3. Aufstellen von Randbedin-gungen für jeden Teilgraphen(Intervalle) wenn:• Zwei Knoten die gleiche
Ressource benötigen• Die Summe von Knoten-
ausführungen kleiner alsein gegebener Zyklus Tist
7
1
2
3
4
5
6
ALU2
REG
ALU2
ALU1
ALU1
REG
ALU1
a
d
vf
vl
Store:1,5,d>0
>
>a>0 a>0
d>0
+ +
+ +
= =
-
=
1
2
3
4
5
6
7
8
>
>a>0 a>0
+ +
+ +
= =
-
=
9
10
Pfad
1 2
Frank SlomkaOldenburg, Sommersemester 2003
99Vorlesung Eingebettete Systeme II
Pfadschduling
vf
vl
Store:1,5,d>0
>
>a>0 a>0
d>0
+ +
+ +
= =
-
=
1
2
3
4
5
6
7
8
>
>a>0 a>0
+ +
+ +
= =
-
=
9
10
Pfad
1 2
• Algorithmus:
1. Schleifeneleminierung2. Auftrennen des CFG in Teil-
graphen, die durch Verzwei-gungen oder den Beginn vonSchleifen definiert sind
3. Aufstellen von Randbedin-gungen für jeden Teilgraphen(Intervalle) wenn:• Zwei Knoten die gleiche
Ressource benötigen• Die Summe von Knoten-
ausführungen kleiner alsein gegebener Zyklus Tist
7
1
2
3
4
5
6
ALU2
REG
ALU2
ALU1
ALU1
REG
ALU1
a
b
cd
Frank SlomkaOldenburg, Sommersemester 2003
100Vorlesung Eingebettete Systeme II
Pfadscheduling
• Algorithmus:
1. Schleifeneleminierung2. Auftrennen des CFG in Teil-
graphen, die durch Verzwei-gungen oder den Beginn vonSchleifen definiert sind
3. Aufstellen von Randbedin-gungen für jeden Teilgraphen(Intervalle) wenn:• Zwei Knoten die gleiche
Ressource benötigen• Die Summe von Knoten-
ausführungen kleiner alsein gegebener Zyklus Tist
4. Ermitteln der minimal benö-tigten Steuerschritte (cut)
a
c d
b a
c d
b
clique 2
clique 1
cut1
cut0
7
1
2
3
4
5
6
ALU2
REG
ALU2
ALU1
ALU1
REG
ALU1
a
b
cd
cut2
vf
vl
Store:1,5,d>0
>
>a>0 a>0
d>0
+ +
+ +
= =
-
=
1
2
3
4
5
6
7
8
>
>a>0 a>0
+ +
+ +
= =
-
=
9
10
Pfad
1 2
Frank SlomkaOldenburg, Sommersemester 2003
101Vorlesung Eingebettete Systeme II
Pfadschduling
• Algorithmus:
1. Schleifeneleminierung2. Auftrennen des CFG in Teil-
graphen, die durch Verzwei-gungen oder den Beginn vonSchleifen definiert sind
3. Aufstellen von Randbedin-gungen für jeden Teilgraphen(Intervalle) wenn:• Zwei Knoten die gleiche
Ressource benötigen• Die Summe von Knoten-
ausführungen kleiner alsein gegebener Zyklus Tist
4. Ermitteln der minimal benö-tigten Steuerschritte (cut)
5. überlagern der Steuer-schritte aller Pfade
2
3
4
5
6
7
8
>
>a>0 a>0
+ +
+ +
= =
-
=
9
10
cut20
cut21
Takt 4
Takt 3
Takt 1
Takt 2
Pfad 1 Pfad 2
cut11
cut10
cut12Takt 5
10 20
11 21clique 2
clique 1
11
10 20
11 21
12clique 3
clique 4
Frank SlomkaOldenburg, Sommersemester 2003
102Vorlesung Eingebettete Systeme II
Pfadscheduling: Beispiel
entity prefetch isport ( branchpc, ibus : in bit32;
branch, ire : in bit;ppc, popc, abus: out bit32);
end prefetch;
architecture behavior of prefetch isbegin
processvariable pc, oldpc: bit32 := 0;begin
ppc <= pc; -- 1popc <= oldpc; -- 2abus <= ibus + 4; -- 3if (branch = ’1’) then -- 4
pc := branchpc; -- 5end if; -- 6wait until (ire = ’1’); -- 7oldpc := pc; -- 8pc := pc + 4; -- 9, 10
end process;end behavior;
1
2
5
4
6
7
0
3
ire
branch
branch
8
9
ire
Frank SlomkaOldenburg, Sommersemester 2003
103Vorlesung Eingebettete Systeme II
Pfadscheduling: Beispiel
1
2
5
4
6
7
0
3
ire
branch
branch
8
9
ire
entity prefetch isport ( branchpc, ibus : in bit32;
branch, ire : in bit;ppc, popc, abus: out bit32);
end prefetch;
architecture behavior of prefetch isbegin
processvariable pc, oldpc: bit32 := 0;begin
ppc <= pc; -- 1popc <= oldpc; -- 2abus <= ibus + 4; -- 3if (branch = ’1’) then -- 4
pc := branchpc; -- 5end if; -- 6wait until (ire = ’1’); -- 7oldpc := pc; -- 8pc := pc + 4; -- 9, 10
end process;end behavior;
Frank SlomkaOldenburg, Sommersemester 2003
104Vorlesung Eingebettete Systeme II
Entfernen der Schleifen
1
2
5
4
6
7
0
3
branch
branch
8
9
Store7, 7, ire1, 10, 1
entity prefetch isport ( branchpc, ibus : in bit32;
branch, ire : in bit;ppc, popc, abus: out bit32);
end prefetch;
architecture behavior of prefetch isbegin
processvariable pc, oldpc: bit32 := 0;begin
ppc <= pc; -- 1popc <= oldpc; -- 2abus <= ibus + 4; -- 3if (branch = ’1’) then -- 4
pc := branchpc; -- 5end if; -- 6wait until (ire = ’1’); -- 7oldpc := pc; -- 8pc := pc + 4; -- 9, 10
end process;end behavior;
Frank SlomkaOldenburg, Sommersemester 2003
105Vorlesung Eingebettete Systeme II
Bedingungen
1
2
5
4
6
7
0
3
8
9
Store7, 7, ire1, 10, 1
• In einem Kontrollschrittkann nur eine Variablezugewiesen werden.
• Eine Ressource kann ineinem Kontrollschrittnur einmal verwendetwerden.
• I/O Ports können ineinem Kontrollschrittnur einmal geschriebenbzw. gelesen werden.
• Die maximale Zykluszeitbegrenzt die Länge einesKontrollschrittes.
Frank SlomkaOldenburg, Sommersemester 2003
106Vorlesung Eingebettete Systeme II
Bedingungen
1
2
5
4
6
7
0
3
8
9
Store7, 7, ire1, 10, 1
architecture behavior of prefetch isbegin
processvariable pc, oldpc: bit32 := 0;begin
ppc <= pc; -- 1popc <= oldpc; -- 2abus <= ibus + 4; -- 3if (branch = ’1’) then -- 4
pc := branchpc; -- 5end if; -- 6wait until (ire = ’1’); -- 7oldpc := pc; -- 8pc := pc + 4; -- 9, 10
end process;end behavior;
Frank SlomkaOldenburg, Sommersemester 2003
107Vorlesung Eingebettete Systeme II
Intervallgraph
1
2
5
4
6
7
0
3
8
9
Store7, 7, ire1, 10, 1
1
2
cut 0
cut 112
clique 1
Frank SlomkaOldenburg, Sommersemester 2003
108Vorlesung Eingebettete Systeme II
Bedingungen
1
2
4
6
7
0
3
8
9
Store7, 7, ire1, 10, 1
architecture behavior of prefetch isbegin
processvariable pc, oldpc: bit32 := 0;begin
ppc <= pc; -- 1popc <= oldpc; -- 2abus <= ibus + 4; -- 3if (branch = ’1’) then -- 4
pc := branchpc; -- 5end if; -- 6wait until (ire = ’1’); -- 7oldpc := pc; -- 8pc := pc + 4; -- 9, 10
end process;end behavior;
1
23
4
5
Frank SlomkaOldenburg, Sommersemester 2003
109Vorlesung Eingebettete Systeme II
Intervallgraph
1
2
4
6
7
0
3
8
9
Store7, 7, ire1, 10, 1
1
23
4
5
cut 0
cut 1
cut 2
3
2
1
4 5
clique 1
clique 2
Frank SlomkaOldenburg, Sommersemester 2003
110Vorlesung Eingebettete Systeme II
Überlappen der Pfade: Suchen der maximalen Überdeckung
1
2
5
4
6
7
0
3
8
9
cut 10
cut 11
1
2
4
6
7
0
3
8
9
cut 20
cut 21
7
0
8
9
cut 30
Vorgegeben durchFlächenbeschränkung
Frank SlomkaOldenburg, Sommersemester 2003
111Vorlesung Eingebettete Systeme II
ILP-Modell zur Ablaufplanung
xi t, 0 1,{ }∈ vi V t:li t hi≤ ≤∀,∈∀
xi t,t li=
hi
∑ 1= vi V∈∀
t x⋅ i t,t li=
hi
∑ τ vi )( )= vi V∈∀
τ vi( ) τ vj( )– di≥ vi vj,( ) V∈∀
xi t p–, α rk( )≤p max 0 t hi–,{ }=
max di 1– t li–,{ }
∑i: vi vj,( ) ER∈∀
∑
rk∀ VT min li{ } t max hi( )≤ ≤∀,∈
• Algorithmus:
1. Aufstellen des Gleichungssy-stems
2. Finden einer Variablenbele-gung x, die das gleichungsy-stem mit minimaler Latenzerfüllt. Lösung mit z.B.Branch and Bound
Frank SlomkaOldenburg, Sommersemester 2003
112Vorlesung Eingebettete Systeme II
ILP-Modell zur Ablaufplanung
Jede Operation darfnur einmal geplant werden
xi t, 0 1,{ }∈ vi V t:li t hi≤ ≤∀,∈∀
xi t,t li=
hi
∑ 1= vi V∈∀
Frank SlomkaOldenburg, Sommersemester 2003
113Vorlesung Eingebettete Systeme II
ILP-Modell zur Ablaufplanung
Berechnung derStartzeitpunkte
xi t, 0 1,{ }∈ vi V t:li t hi≤ ≤∀,∈∀
xi t,t li=
hi
∑ 1= vi V∈∀
t x⋅ i t,t li=
hi
∑ τ vi )( )= vi V∈∀
Jede Operation darfnur einmal geplant werden
Frank SlomkaOldenburg, Sommersemester 2003
114Vorlesung Eingebettete Systeme II
ILP-Modell zur Ablaufplanung
Berücksichigung vonDatenabhängigkeiten
xi t, 0 1,{ }∈ vi V t:li t hi≤ ≤∀,∈∀
xi t,t li=
hi
∑ 1= vi V∈∀
t x⋅ i t,t li=
hi
∑ τ vi )( )= vi V∈∀
τ vi( ) τ vj( )– di≥ vi vj,( ) V∈∀
Berechnung derStartzeitpunkte
Jede Operation darfnur einmal geplant werden
Frank SlomkaOldenburg, Sommersemester 2003
115Vorlesung Eingebettete Systeme II
ILP-Modell zur Ablaufplanung
Berücksichtigung derRessourcenbe-schränkungen
xi t, 0 1,{ }∈ vi V t:li t hi≤ ≤∀,∈∀
xi t,t li=
hi
∑ 1= vi V∈∀
t x⋅ i t,t li=
hi
∑ τ vi )( )= vi V∈∀
τ vi( ) τ vj( )– di≥ vi vj,( ) V∈∀
xi t p–, α rk( )≤p max 0 t hi–,{ }=
max di 1– t li–,{ }
∑i: vi vj,( ) ER∈∀
∑
rk∀ VT min li{ } t max hi( )≤ ≤∀,∈
Berücksichigung vonDatenabhängigkeiten
Berechnung derStartzeitpunkte
Jede Operation darfnur einmal geplant werden
Frank SlomkaOldenburg, Sommersemester 2003
116Vorlesung Eingebettete Systeme II
Übersicht
• Einführung
• Motivierendes Beispiel
• Grundlagen
• Rechenwerk
• Algorithmen zur Ablaufplanung
• Algorithmen zur Bindung
• Steuerwerk
• Ermittlung der Entwurfsparameter
Frank SlomkaOldenburg, Sommersemester 2003
117Vorlesung Eingebettete Systeme II
Verträglichkeit
Definition : Zwei Knoten eines Sequenz-, Kontroll-oder Datenflußgraphen sind schwachverträglich falls gilt,
Definition :Zwei Knoten eines Sequenz-, Kontroll- oderDatenflußgraphen sind ablaufplanverträglich, wenn sieschwachverträglich sind und für die Startzeit τ(vi) gilt τ(vi)> τ(vj) + dj
Definition : Zwei Knoten eines Sequenz-, Kontroll-oder Datenflußgraphen sind stark verträglich, falls sieschwachverträglich sind und falls ein gerichteter Pfadvon Knoten vi nach vj existiert
rk∃ VT∈ vi rk,( ) ER∈ vj rk,( ) ER∈∧=
Frank SlomkaOldenburg, Sommersemester 2003
118Vorlesung Eingebettete Systeme II
Bindung
• Eien Menge gegenseitig verträglicher Operationen ent-spricht einer Clique in GV. Eine Clique ist ein vollständi-ger Teilgraph.
• Eine maximale Verträglichkeitsmenge entspricht einermaximale Clique in GV (Eine Clique heißt maximal, wennsie in keiner anderen Clique enthalten ist).
• Kostenoptimale Bindung: Partitionierung von GV mitminimaler Anzahl von Cliquen.
Frank SlomkaOldenburg, Sommersemester 2003
119Vorlesung Eingebettete Systeme II
Beispiel
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
Frank SlomkaOldenburg, Sommersemester 2003
120Vorlesung Eingebettete Systeme II
Schwache Verträglichkeit
+ +
+ +
<
* *
* *
2 3
75
6
8
9
4
1
Definition : Zwei Knoteneines Sequenz-, Kontroll- oderDatenflußgraphen sindschwachverträglich falls gilt,
rk∃ VT∈ vi rk,( ) ER∈ vj rk,( ) ER∈∧=
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
Frank SlomkaOldenburg, Sommersemester 2003
121Vorlesung Eingebettete Systeme II
Ablaufplan Verträglichkeit
+ +
+ +
<
* *
* *
2 3
75
6
8
9
4
1
+* +
+<
*
*
+
*
12
3
4
5
6
7
89
Lat
enz
= 8
Z.E
. Definition :Zwei Knoteneines Sequenz-, Kontroll- oderDatenflußgraphen sind ablauf-planverträglich, wenn sieschwachverträglich sind undfür die Startzeit τ(vi) gilt τ(vi) >τ(vj) + dj
Frank SlomkaOldenburg, Sommersemester 2003
122Vorlesung Eingebettete Systeme II
Starke Verträglichkeit
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
+ +
+ +
<
* *
* *
2 3
75
6
8
9
4
1
Definition : Zwei Kno-ten eines Sequenz-, Kon-troll- oder Datenflußgra-phen sind stark verträg-lich, falls sie schwach-verträglich sind und fallsein gerichteter Pfad vonKnoten vi nach vj exi-stiert
Frank SlomkaOldenburg, Sommersemester 2003
123Vorlesung Eingebettete Systeme II
Konfliktgraph
Definition :Zwei Ope-rationen sind im Konflikt,genau dann, wenn sienicht verträglich sind.
+ +
+ +
<
* *
* *
2 3
75
6
8
9
4
1 + +
+ +
<
* *
* *
2 3
75
6
8
9
4
1
+ +
+ +
<
* *
* *
2 3
75
6
8
9
4
1
Frank SlomkaOldenburg, Sommersemester 2003
124Vorlesung Eingebettete Systeme II
Starker Konflikt
+ +
+ +
<
* *
* *
2 3
75
6
8
9
4
1
+ +
+ +
<
* *
* *
2 3
75
6
8
9
4
1
Definition : Zwei Ope-rationen sind im Konflikt,genau dann, wenn sienicht verträglich sind.
Frank SlomkaOldenburg, Sommersemester 2003
125Vorlesung Eingebettete Systeme II
Beobachtungen
• Konfliktgraph und Verträglichkeitsgraph sind komple-mentär.
• Eine Menge gegenseitig verträglicher Knoten VV ent-spricht einer unabhängigen Menge in GK. Eine unab-hängige Menge eines Graphen bezeichnet eineTeilmenge von Knoten, von denen keiner mit irgendei-nemanderen Knoten dieser Menge adjazent ist.
• Kostenoptimale Bindung: Die Färbung von GK mit einerminimalen Anzahl von Farben, so daß adjazente Knotenunterschiedliche Farben erhalten.
Frank SlomkaOldenburg, Sommersemester 2003
126Vorlesung Eingebettete Systeme II
Erweiterungen
• Bindung hierarchischer Graphen durch Auflösung derHierarchie; resultierende Graphen sind i.a. nicht mehrchordal.
• Bindung vor der Ablaufplanung (polynomiel):
• schwache Verträglichkeit: Sequentialisierung
• starke Verträglichkeit
Frank SlomkaOldenburg, Sommersemester 2003
127Vorlesung Eingebettete Systeme II
Algorithmen und Komplexität
Für allgemeine Graphen gilt:
• Cliquepartitionierung: NP-vollständig
• Graphfärbung: NP-vollständig
Die Berechnung der Graphfärbung erfolgt daher mit Heuri-stiken.
Frank SlomkaOldenburg, Sommersemester 2003
128Vorlesung Eingebettete Systeme II
Vertexcolor
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj zu Knoten V gibt:4. Farbe c = c + 15. Färbe Knoten vi mit C
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
Frank SlomkaOldenburg, Sommersemester 2003
129Vorlesung Eingebettete Systeme II
Vertexcolor
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
Frank SlomkaOldenburg, Sommersemester 2003
130Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
131Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
132Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
133Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
134Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
135Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
136Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
137Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
138Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
139Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
140Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
141Vorlesung Eingebettete Systeme II
Vertexcolor
< -
+ -
* *
* *
* *
+1
2
3
4
5
6
7 11
10
9
8
• Exakt für chordale Graphen
• Komplexität O(|V||N|)
1. Für alle Knoten vi:2. Farbe c = 13. Solange es einen adjazenten
Knoten vj mit Farbe c zu Kno-ten vi gibt:
4. Farbe c = c + 15. Färbe Knoten vi mit C
Frank SlomkaOldenburg, Sommersemester 2003
142Vorlesung Eingebettete Systeme II
Left-Edge
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle 1
2
3
4
5
2 4
1 5
3
Frank SlomkaOldenburg, Sommersemester 2003
143Vorlesung Eingebettete Systeme II
Left-Edge
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle
2. Lege Schranke auf erstesIntervall
3. Färbe Intervall4. Lege Schranke ans Ende des
gefärbten Intervalls.
1
32
5
4
2 4
1 5
3
Frank SlomkaOldenburg, Sommersemester 2003
144Vorlesung Eingebettete Systeme II
Left-Edge
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle
2. Lege Schranke auf erstesIntervall
3. Färbe Intervall4. Lege Schranke ans Ende des
gefärbten Intervalls.5. Gehe solange zu 2 bis Ende
des letzten Intervalls.6. Erhöhe Farbe und setze
Schranke an den linkenRand.
1
32
5
4
2 4
1 5
3
Frank SlomkaOldenburg, Sommersemester 2003
145Vorlesung Eingebettete Systeme II
Left-Edge
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle
2. Lege Schranke auf erstesIntervall
3. Färbe Intervall4. Lege Schranke ans Ende des
gefärbten Intervalls.5. Gehe solange zu 2 bis Ende
des letzten Intervalls.6. Erhöhe Farbe und setze
Schranke an den linkenRand.
1
32
5
2 4
1 5
3
Frank SlomkaOldenburg, Sommersemester 2003
146Vorlesung Eingebettete Systeme II
Left-Edge
1
32
5
2 4
1 5
3
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle
2. Lege Schranke auf erstesIntervall
3. Färbe Intervall4. Lege Schranke ans Ende des
gefärbten Intervalls.5. Gehe solange zu 2 bis Ende
des letzten Intervalls.6. Erhöhe Farbe und setze
Schranke an den linkenRand.
Frank SlomkaOldenburg, Sommersemester 2003
147Vorlesung Eingebettete Systeme II
Left-Edge
1
32
5
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle
2. Lege Schranke auf erstesIntervall
3. Färbe Intervall4. Lege Schranke ans Ende des
gefärbten Intervalls.5. Gehe solange zu 2 bis Ende
des letzten Intervalls.6. Erhöhe Farbe und setze
Schranke an den linkenRand.
2 4
1 5
3
Frank SlomkaOldenburg, Sommersemester 2003
148Vorlesung Eingebettete Systeme II
Left-Edge
1
32
5
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle
2. Lege Schranke auf erstesIntervall
3. Färbe Intervall4. Lege Schranke ans Ende des
gefärbten Intervalls.5. Gehe solange zu 2 bis Ende
des letzten Intervalls.6. Erhöhe Farbe und setze
Schranke an den linkenRand.
2 4
1 5
3
Frank SlomkaOldenburg, Sommersemester 2003
149Vorlesung Eingebettete Systeme II
2 4
1 5
3
Left-Edge
1
32
5
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle
2. Lege Schranke auf erstesIntervall
3. Färbe Intervall4. Lege Schranke ans Ende des
gefärbten Intervalls.5. Gehe solange zu 2 bis Ende
des letzten Intervalls.6. Erhöhe Farbe und setze
Schranke an den linkenRand.
Frank SlomkaOldenburg, Sommersemester 2003
150Vorlesung Eingebettete Systeme II
Left-Edge
1
32
5
2 4
1 5
3
• Komplexität O(|V| log |V|)
1. Sortiere die gegebenen Inter-valle
2. Lege Schranke auf erstesIntervall
3. Färbe Intervall4. Lege Schranke ans Ende des
gefärbten Intervalls.5. Gehe solange zu 2 bis Ende
des letzten Intervalls.6. Erhöhe Farbe und setze
Schranke an den linkenRand.
Frank SlomkaOldenburg, Sommersemester 2003
151Vorlesung Eingebettete Systeme II
Strukturelle Bindung
+ = -
*
X C
a Xb y y
wait on clkx := a + b;if (a = b)
c :=(x-y)*z
Frank SlomkaOldenburg, Sommersemester 2003
152Vorlesung Eingebettete Systeme II
Strukturelle Bindung
Cin(vi,vj) = Gemeinsame Eingänge zwischen Knoten
Cout(vi,vj) = Gemeinsame Ausgänge
W(vi,vj) = Verbindungen zwischen zwei Knoten
Smax = Maximal erlaubte Kosten
S(vi) = Kosten des Knotens (#Transistoren)
Cl vi vj,( )Con
Cmax-------------
Smax
min S vi( ) S vj( ),( )--------------------------------------------
Smax
S vi( ) S vj( )+---------------------------------
⋅ ⋅=
Con Cin vi vj,( ) Cout vi vj,( ) W vi vj,( )⋅ ⋅=
+ = -
*
X C
a Xb y y
120140140
160
180
Frank SlomkaOldenburg, Sommersemester 2003
153Vorlesung Eingebettete Systeme II
Strukturelle Bindung
*
+
=
-
+ = -
*
X C
a Xb y y
2.9 0
0.80
Cl v1 v2,( ) 8 0+8
------------ 300
120---------
300120 140+------------------------
⋅ ⋅ 2 9,= =
Cl v4 v3,( ) 0 4+8
------------ 300
160---------
300160 180+------------------------
⋅ ⋅ 0 8,= =
1
2
1
3
1
4
4 Bits
120140
160
180
Frank SlomkaOldenburg, Sommersemester 2003
154Vorlesung Eingebettete Systeme II
*
+
=
-
+ = -
*
X C
a Xb y y
2.9 0
0.80
Cl v1 v2,( ) 8 0+8
------------ 300
120---------
300120 140+------------------------
⋅ ⋅ 2 9,= =
Cl v4 v3,( ) 0 4+8
------------ 300
160---------
300160 180+------------------------
⋅ ⋅ 0 8,= =
1
2
1
3
1
4
4 Bits
120140
160
180
*
+
=
-
g1
g2
Frank SlomkaOldenburg, Sommersemester 2003
155Vorlesung Eingebettete Systeme II
Übersicht
• Einführung
• Motivierendes Beispiel
• Grundlagen
• Rechenwerk
• Algorithmen zur Ablaufplanung
• Algorithmen zur Bindung
• Steuerwerk
• Ermittlung der Entwurfsparameter
• Optimierung
Frank SlomkaOldenburg, Sommersemester 2003
156Vorlesung Eingebettete Systeme II
Zustandsautomat
+
*
*
+
*
*
+ +
<
1 2
3
4
5
6
7
8
9
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
+* +
+<
*
*
+
*
12
3
4
5
6
7
89
x0x1x2x3x4x5x6x7
x4
x0
x6
x2
x1
x3
x5
x7
1,2
6
3,8
9
4,7
5
RESET
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
Frank SlomkaOldenburg, Sommersemester 2003
157Vorlesung Eingebettete Systeme II
Moore-Automat
x4
x0
x6
x2
x1
x3
x5
x7
1,2
6
3,8
9
4,7
5
RESET
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
Ausgangs-
logik
Zustandsüber-
gangslogik
Frank SlomkaOldenburg, Sommersemester 2003
158Vorlesung Eingebettete Systeme II
Mealy-Automat
x4
x0
x6
x2
x1
x3
x5
x7
RESET
RESET & CLK (1,2)
RESET & CLK (6)
RESET & CLK (3,8)
RESET & CLK (9)
RESET & CLK
RESET & CLK (5)
RESET & CLK (4,7)
Eingangs-
logik
Zustandsüber-
gangslogik
Frank SlomkaOldenburg, Sommersemester 2003
159Vorlesung Eingebettete Systeme II
Mikroprogrammiertes Steuerwerk
x4
x0
x6
x2
x1
x3
x5
x7
1,2
6
3,8
9
4,7
5
RESET
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
RESET & CLK
Zustandsüber-
gangslogik
1,263,894,7
5
Frank SlomkaOldenburg, Sommersemester 2003
160Vorlesung Eingebettete Systeme II
Übersicht
• Einführung
• Motivierendes Beispiel
• Grundlagen
• Rechenwerk
• Algorithmen zur Ablaufplanung
• Algorithmen zur Bindung
• Steuerwerk
• Ermittlung der Entwurfsparameter
Frank SlomkaOldenburg, Sommersemester 2003
161Vorlesung Eingebettete Systeme II
Schätzmodell
Zu
stan
dsr
egis
ter
Ein
gan
gsl
og
ik
Au
sgan
gsl
og
ik
Steuerwerk Rechenwerk
ALU *
BankRegister-
Register
Register
Frank SlomkaOldenburg, Sommersemester 2003
162Vorlesung Eingebettete Systeme II
Schätzmodelle
DesignmodellZusätzlicheAufgaben
Genauigkeit Exaktheit Geschwindigkeit
Speicher Allokation niedrig niedrig niedrig
Speicher + Funktionale Einheiten Allokation
Speicher + Funktionale Einheiten +Register
Lebenszeit-analyse
Speicher + Funktionale Einheiten +Register + Multiplexer
Bindung
Speicher + Funktionale Einheiten +Register + Multiplexer + Leitungen
Floorplaning hoch hoch hoch
Frank SlomkaOldenburg, Sommersemester 2003
163Vorlesung Eingebettete Systeme II
Berechnung der Taktperiode
*
*
+
+
++
150 ns80 ns
80 ns80 ns
80 ns150 ns
1
2
3
4
56
T = 380 nsL = 1Tex = 380 nsRessourcen: 2 *, 4 +
Frank SlomkaOldenburg, Sommersemester 2003
164Vorlesung Eingebettete Systeme II
Berechnung der Taktperiode
*
*
+
+
++
80 ns
80 ns80 ns
80 ns
1
2
3
4
56
*
*
+
+
++
150 ns80 ns
80 ns80 ns
80 ns150 ns
1
2
3
4
56
T = 380 ns
150 ns
150 ns
150 ns
150 ns
L = 1Tex = 380 ns
T = 150 nsL = 3Tex = 450 nsRessourcen: *,+,+Ressourcen: 2 *, 4 +
Frank SlomkaOldenburg, Sommersemester 2003
165Vorlesung Eingebettete Systeme II
Berechnung der Taktperiode
*
*
+
+
++
80 ns
80 ns80 ns
80 ns
1
2
3
4
56
*+
+
+
+
80 ns
80 ns
80 ns
80 ns
1
2
3
4
56
*
*
+
+
++
150 ns80 ns
80 ns80 ns
80 ns150 ns
1
2
3
4
56 *
T = 380 ns
150 ns
150 ns
150 ns
150 ns
L = 1Tex = 380 ns
T = 150 nsL = 3Tex = 450 ns
T = 80 nsL = 5Tex = 400 nsRessourcen: *,+Ressourcen: *,+,+Ressourcen: 2 *, 4 +
Frank SlomkaOldenburg, Sommersemester 2003
166Vorlesung Eingebettete Systeme II
Berechnung der Taktperiode
• Maximale Verzögerungszeit
• Taktschlupf
T max z rk( )( )=
s T rk,( ) z rk( )T
----------- T z rk( )–⋅=
50 150100
Mul
Add
Sub
Schlupf Mul = 163 ns
Add = 49 ns
Sub = 56 ns
T = 163 ns
t/ns
Frank SlomkaOldenburg, Sommersemester 2003
167Vorlesung Eingebettete Systeme II
Berechnung der Taktperiode
• Mittlerer Taktschlupf
• Mittlere Ressourcenauslastung
ms T( )h rk( ) s T rk,( )⋅
k 1=
VT
∑
h rk( )k 1=
VT
∑
-----------------------------------------=
ma T( ) 1 ms T( )T
----------------– 100⋅=
50 150100
Mul
Add
Sub
Mittlerer Taktschlupf (T = 65 ns)T T T
t/ns
+ +Mul AddSub
6*32
2*9 2*17
6 22+ += 24.4 ns
Frank SlomkaOldenburg, Sommersemester 2003
168Vorlesung Eingebettete Systeme II
Registerabschätzung
+
*
*
+
*
*
+ +
<
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
ab c d ef gh i
jt1 t2
t3
t4t5
t6
x1
x2
t7
1. Ablaufplanung
+* +
+<
*
*
+
*
Frank SlomkaOldenburg, Sommersemester 2003
169Vorlesung Eingebettete Systeme II
Registerabschätzung
a b c d e f g h i j t1 t2 t3 t4 t5 t6 t7 x1 x2
1. Ablaufplanung2. Aufstellen der Lebenszeitinter-
valle +
*
*
+
*
*
+ +
<
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
ab c d ef gh i
jt1 t2
t3
t4t5
t6
x1
x2
t7
+* +
+<
*
*
+
*
Frank SlomkaOldenburg, Sommersemester 2003
170Vorlesung Eingebettete Systeme II
Registerabschätzung
+
*
*
+
*
*
+ +
<
DFG:
*
+ = 1 Z.E.
= 2 Z.E.
ab c d ef gh i
jt1 t2
t3
t4t5
t6
x1
x2
t7
+* +
+<
*
*
+
*
1. Ablaufplanung2. Aufstellen der Lebenszeitinter-
valle3. Färbung der Intervalle4. #Register = #Farben
a b c d e f g h i j t1 t2 t3 t4 t5 t6 t7 x1 x2
Recommended