Verhaltenssynthese - Uni Ulm Aktuelles - Universität Ulm · Alu’s, Mux’s Transistoren Boolsche Gatter Funktionen RTL-Beschreibung Differential- ... DXX EX FXX XX GX HX IXX X

Frank SlomkaOldenburg, Sommersemester 2003

1Vorlesung Eingebettete Systeme II

Verhaltenssynthese



Aufbau des Kapitels

• Einführung

• Motivierendes Beispiel

• Grundlagen

• Rechenwerk

• Algorithmen zur Ablaufplanung

• Algorithmen zur Bindung

• Steuerwerk

• Ermittlung der Entwurfsparameter



Aufbau des Kapitels

• Einführung


• Grundlagen

• Rechenwerk


• Bestimmung des Taktes


• Steuerwerk




Verhaltenssynthese

Verhalten Struktur

Zelllayout

Maskenlayout

Schaltkreis

Logik

RTL

Alu’s, Mux’s

Transistoren

GatterBoolscheFunktionen

RTL-Beschreibung

Differential-gleichungen

Floorplan physikalischeDarstellung

Algorithmik

Algorithmus



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



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



Entwurfsmodell

Zu

stan

dsr

egis

ter

Ein

gan

gsl

og

ik

Au

sgan

gsl

og

ik

Steuerwerk Rechenwerk

ALU *

BankRegister-

Register

Register



Motivierendes Beispiel

• Einführung


• Grundlagen

• Rechenwerk




• Steuerwerk




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;



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



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



|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



Bauteile-Bibliothek

Subtrahierer

Multiplexer

Addierer

Subtrahierer

Multiplexer

Betrag

Min

Subtrahierer

Multiplexer

Max

Subtrahierer



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



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



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



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



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]



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]



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



Algorithmische Bestimmung der Registeranzahl

y x t1 t2 t3 t4 t5 t6 t7a ba

b y

t1

t2

x



Aufstellen eines Kompatibilitätsgraphen

y x t1 t2 t3 t4 t5 t6 t7a ba

b y

t1

t2

x




a

b x

t1

t2

y

y x t1 t2 t3 t4 t5 t6 t7a b




a

b

t1 y

t7

t3 t5

t4 y x t1 t2 t3 t4 t5 t6 t7a b

t6

xt2



Bestimmung der Registerzuordnung durch Graphfärbung

R1 = [a, t1,y, t3, t5, t6, t7]

a

b

t1 y

t7

t3 t5

t4

t6

xt2




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]




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]



Nutzung gemeinsamer Ressourcen

+

a b c d

-

x y

keine gemeinsame Nutzung

+/-

MUX

a b c d

MUX

x y

gemeinsame Nutzung




|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

+ -



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|



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

+ -




R1 R2 R3

MUX MUX MUX

>>3>>1abs/min abs/max/+/-

MUX

|a| |b|

min

+ -

max




R3

>>3>>1abs/min abs/max/+/-

MUX

MUXMUX

R2R1

MUX



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




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




B

F

D E

C

A

HG

N

M

I

J

K

L




B

F

D E

C

A

HG

I K

L

Ausgangsleitungen (Register) Eingangsleitungen (Register)

Bus1

Bus2

Bus3

Bus4N

M

J




R1 R2 R3




Zusammenlegen von Registern

S0 S1 S2 S3 S4 S5 S6 S7

R1

R2

R3



Zusammenlegen von Registern

S0 S1 S2 S3 S4 S5 S6 S7

R1

R2

R3

R3

R1 R2




R3

R1R2




Grundlagen

• Einführung


• Grundlagen

• Rechenwerk




• Steuerwerk


• Optimierung



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



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.



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



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.



Klassifikation von Problemen

P

NP-Vollständig

NP

NP-hart



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.



Datenstrukturen

• Kontrollflußgraph

• Datenflußgraph

• Kontrolldatenfluß- bzw. Sequenzgraph

• Ressourcengraph

• Algebraische Spezifikation von Allokation und Bindung



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



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:



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



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.



Sequenzgraph (Funktionen)

*

+

N

N

+

C

N

N

+ *

Call



Sequenzgraph (Verzweigungen)

*

+

N

N

+

BR

N

N

+ *

N

N

-

Branch

B1 B2



Ressourcegraph

r1

*

*

*

* ** * +

* * <+

-

-


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



Ressourcegraph

* ** * +

* * <+

-

-


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



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



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.



Beispiel

* ** * +

* * <+

-

-


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



Beispiel

* ** * +

* * <+

-

-


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



Beispiel

* ** * +

* * <+

-

-


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



Beispiel

* ** * +

* * <+

-

-


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) =



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

* ** * +

* * <+

-

-


aydx

u

x1

y1

u1

1 2

3

4

5

6

7

8

9

10

11

1

2



Latenz

Definition : Die Latenz L eines Ablauf-plans τ eines Sequenzgraphen GS = VS,ES)ist definiert als L = max (τ(vi) + wi) - min (vj)

* ** * +

* * <+

-

-


aydx

u

x1

y1

u1

1 2

3

4

5

6

7

8

9

10

11



Beispiel

Definition : Die Latenz L eines Ablauf-plans τ eines Sequenzgraphen GS = VS,ES)ist definiert als L = max (τ(vi) + wi) - min (vj)

* ** * +

* * <+

-

-


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))



Übersicht

• Einführung


• Grundlagen

• Rechenwerk



• Steuerwerk


• Optimierung



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



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.



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}



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.



ASAP/ALAP




• 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



ASAP/ALAP





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



ASAP/ALAP







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



ASAP/ALAP








+

*

*

+

*

*

+ +

<

1 2

3

4

5

6

7

8

9

DFG:

*

+ = 1 Z.E.

= 2 Z.E.

+*

+ +<

**

+

*

12

3

4

5

6

7

89



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.










ASAP/ALAP

<*59

+

*

*

+

*

*

+ +

<

1 2

3

4

5

6

7

8

9

DFG:

*

+ = 1 Z.E.

= 2 Z.E.




• As Late as Possible (ALAP):

1. Plane alle Endknoten



ASAP/ALAP





1. Plane alle Endknoten2. Plane alle Knoten deren

Nachfolger bereits einge-plant sind


+<

**

+

*

3

4

5

7

89

+

*

*

+

*

*

+ +

<

1 2

3

4

5

6

7

8

9

DFG:

*

+ = 1 Z.E.

= 2 Z.E.



ASAP/ALAP








+

*

*

+

*

*

+ +

<

1 2

3

4

5

6

7

8

9

DFG:

*

+ = 1 Z.E.

= 2 Z.E.

+

+<

**

+

*

3

4

5

6

7

89



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.



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

.



Listscheduling




• 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



Listscheduling




• Listscheduling:


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



Listscheduling




• Listscheduling:




+

*

*

+

*

*

+ +

<

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



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:




• Listscheduling:






Listscheduling




• Listscheduling:




+* +

+<*

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:



Listscheduling




• Listscheduling:




+

*

*

+

*

*

+ +

<

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

.



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




• Force-Directed Scheduling:


2. Bestimme das Mobilitätsinter-vall der Knoten für jede Res-source getrennt.




+

*

*

+

*

*

+ +

<

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




+

*

*

+

*

*

+ +

<

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 = Σ


4. Bestimme für jeden Zeit-schritt die Belegung der Res-source.

pi t, µ vi( ) +----------------------=

1

1




+

*

*

+

*

*

+ +

<

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



pi t, µ vi( ) +----------------------=

1

1




+

*

*

+

*

*

+ +

<

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:



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






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




+* +

+<

*

*

+

*

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:



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



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

+ +

+ +

= =

-

=



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



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



Pfadschduling

• Algorithmus:



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



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:






7

1

2

3

4

5

6

ALU2

REG

ALU2

ALU1

ALU1

REG

ALU1

a

b

cd



Pfadscheduling

• Algorithmus:






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



Pfadschduling

• Algorithmus:






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



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



Pfadscheduling: Beispiel

1

2

5

4

6

7

0

3

ire

branch

branch

8

9

ire



end prefetch;








Entfernen der Schleifen

1

2

5

4

6

7

0

3

branch

branch

8

9

Store7, 7, ire1, 10, 1



end prefetch;








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.



Bedingungen

1

2

5

4

6

7

0

3

8

9

Store7, 7, ire1, 10, 1








Intervallgraph

1

2

5

4

6

7

0

3

8

9

Store7, 7, ire1, 10, 1

1

2

cut 0

cut 112

clique 1



Bedingungen

1

2

4

6

7

0

3

8

9

Store7, 7, ire1, 10, 1






1

23

4

5



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



Ü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



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




Jede Operation darfnur einmal geplant werden

xi t, 0 1,{ }∈ vi V t:li t hi≤ ≤∀,∈∀

xi t,t li=

hi

∑ 1= vi V∈∀




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∈∀





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∈∀






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





Übersicht

• Einführung


• Grundlagen

• Rechenwerk



• Steuerwerk




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∈∧=



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.



Beispiel

+

*

*

+

*

*

+ +

<

1 2

3

4

5

6

7

8

9

DFG:

*

+ = 1 Z.E.

= 2 Z.E.



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.



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



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



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



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.



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.



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



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.



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



Vertexcolor




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



Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Vertexcolor

< -

+ -

* *

* *

* *

+1

2

3

4

5

6

7 11

10

9

8








Left-Edge

• Komplexität O(|V| log |V|)

1. Sortiere die gegebenen Inter-valle 1

2

3

4

5

2 4

1 5

3



Left-Edge


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



Left-Edge





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



Left-Edge








1

32

5

2 4

1 5

3



Left-Edge

1

32

5

2 4

1 5

3










Left-Edge

1

32

5








2 4

1 5

3



Left-Edge

1

32

5








2 4

1 5

3



2 4

1 5

3

Left-Edge

1

32

5










Left-Edge

1

32

5

2 4

1 5

3










Strukturelle Bindung

+ = -

*

X C

a Xb y y

wait on clkx := a + b;if (a = b)

c :=(x-y)*z




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




*

+

=

-

+ = -

*

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



*

+

=

-

+ = -

*

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



Übersicht

• Einführung


• Grundlagen

• Rechenwerk



• Steuerwerk


• Optimierung



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



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



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



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



Übersicht

• Einführung


• Grundlagen

• Rechenwerk



• Steuerwerk




Schätzmodell

Zu

stan

dsr

egis

ter

Ein

gan

gsl

og

ik

Au

sgan

gsl

og

ik

Steuerwerk Rechenwerk

ALU *

BankRegister-

Register

Register



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



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 +




*

*

+

+

++

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 +




*

*

+

+

++

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 +




• 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




• 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



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

+* +

+<

*

*

+

*




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

+* +

+<

*

*

+

*




+

*

*

+

*

*

+ +

<

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

Documents

Verhaltenssynthese - Uni Ulm Aktuelles - Universität Ulm · Alu’s, Mux’s Transistoren Boolsche Gatter Funktionen RTL-Beschreibung Differential- ... DXX EX FXX XX GX HX IXX X