RW-Systemarchitektur Kap 1

(Zweistufige) Logiksynthese

1.4 PLAs und zweistufige Logiksynthese

RW-Systemarchitektur Kap 1

Programmierbare Logische Felder (PLA)Zweistufige Darstellung zur Realisierung von Booleschen Polynomen

fi = mi1+mi2+ ... +mik mit miq aus {m1,...,ms}

Fläche: ~ (m+2n)x(Anzahl_der_benötigten_Monome)

Enthält Monom mj k Lite-rale, so werden k Transis-toren in der entsprechen-den Zeile des AND-Feldes benötigt.

Besteht die Beschreibung von Funktion ft aus p Mo-nomen, so benötigt man p Transistoren in der ent-sprechenden Spalte des OR-Feldes.

Enthält Monom mj k Lite-rale, so werden k Transis-toren in der entsprechen-den Zeile des AND-Feldes benötigt.

Besteht die Beschreibung von Funktion ft aus p Mo-nomen, so benötigt man p Transistoren in der ent-sprechenden Spalte des OR-Feldes.

AND-Feld

OR-Feld

m1

mj

ms

m2

x1 x2 xn fmf1 f2

R1

R1

R1

R1

R1

R1

R1

R1

1

R

1

R

1

R

1

R

1

R

1

R

RW-Systemarchitektur Kap 1

Kurzer Exkurs: MOS-Transistoren

Einen Transistor kann man vereinfacht als spannungsgesteuerten Schalter sehen: Leitung g (gate) regelt Leitfähigkeit zwischen Quelle und Senke.

n-Kanal-Transistor: Leitet, wenn am Gate eine 1 anliegt “sperrt”, wenn am Gate eine 0 anliegt

p-Kanal-Transistor: Leitet, wenn am Gate eine 0 anliegt “sperrt”, wenn am Gate eine 1 anliegt

0

1

1

0

RW-Systemarchitektur Kap 1

Programmierbare Logische Felder (PLA)

R1

1

verwenden n-Kanal-Transistoren als Schalter:liegt eine 1 am Gate, so wird die an der Quelle anliegende 1 auf 0 heruntergezogen.Um ein Konjunktion zu 0 auszuwerten muss auf der korrespondierendenLeitung mindestens ein Schalter geschaltet werden.

x1 f1

1

R

x1’

Wir nutzen die Gleicheit (a b) = ( a b) ausund realisieren wieder Konjunktionenund negieren das Ergebnis.

RW-Systemarchitektur Kap 1 5

Programmierbare logische Felder

Beispiel Beispiel f1 = x1'x2'+x2'x3+x1x2

f2 = x2'x3

1

1

1

1 1

x1 x1' x2 x2' x3 x3' f1 f2

x1' x1'x2'

x2' x2'x3

x1x1x2

RW-Systemarchitektur Kap 1 6

Programmierbare Logische Felder ff

BeispielBeispiel f1 = x1'x2'+x2'x3+x1x2

f2 = x2'x3

Bei Belegung von x1=1, x2=1, x3=1 liegt folgende Situation vor.

1

1

1

1 1

x1 x1' x2 x2' x3 x3' f1 f2

RW-Systemarchitektur Kap 1

1

1

1

1 1

x1 x1' x2 x2' x3 x3' f1 f2

RW-Systemarchitektur Kap 1 8

Kosten von Monomen

Sei q = q1·...·qr ein Monom, dann sind die

KostenKosten |q| von qgleich der Anzahl der zur Realisierung von q benötigten Transistoren im PLA, also

|q| := r

RW-Systemarchitektur Kap 1 9

Kosten von PolynomenSeien p1,...,pm Polynome, dann bezeichne M(p1,....,pm)

die Menge der in diesen Polynomen verwendeten Monome.

Die primären Kostenprimären Kosten cost1(p1,...,pm) einer Menge {p1,...,pm} von

Polynomen sind gleich der Anzahl der benötigten Zeilen im PLA, um p1,...,pm

zu realisieren, also

cost1(p1,...,pm) = |M(p1,...,pm)|.

Die sekundären Kostensekundären Kosten cost2(p1,...,pm) einer Menge {p1,...,pm} von

Polynomen sind gleich der Anzahl der benötigten Transistoren im PLA, also

cost2(p1,...,pm) = qM(p1

,...,pm

) |q| + i=1,...,m |M(pi )|

Sei im folgenden cost = (cost1 , cost2) die Kostenfunktion mit der

Eigenschaft, dass für zwei Polynommengen {p1, …, pm} und {p1´, …, pm´}

die Ungleichung cost(p1, …, pm) · cost(p1´, …, pm´) gilt, wenn entweder

cost1(p1, …, pm) < cost1(p1´, …, pm´) oder

cost1(p1, …, pm) = cost1(p1´, …, pm´) und

cost2(p1, …, pm) · cost2(p1´, …, pm´)

RW-Systemarchitektur Kap 1

1.5 Modellierung durch Schaltkreise

Idee: „gerichteter Graph mit einigen zusätzlichen Eigenschaften“

RW-Systemarchitektur Kap 1

Modellierung durch Schaltkreise (1)

Eine Zellenbibliothek BIB [ n 2 N Bn enthält Basisoperationen, die den Grundgattern entsprechen.

),,,,( mn YINtypGXSK Ein 5-Tupel heißt Schaltkreis mit n

Eingängen und m Ausgängen über der Zellenbibliothek BIB gdw.),,( 1 nn xxX ist eine endliche Folge von Eingängen.

}),,{}1,0({\ 1 nxxVI Die Menge heißt Menge der Gatter. Die Abbildung typ : I ! BIB ordnet jedem Gatter v 2 I einen Zellentyp typ(v) 2 BIB zu.

Für jedes Gatter v 2 I mit typ(v) 2 Bk gilt indeg(v) = k.

},,{}1,0{ 1 nxxv indeg(v) = 0 für…

),( EVG .),,(}1,0{ 1 Vxx n

ist ein azyklischer, gerichteter Graph mit

RW-Systemarchitektur Kap 1

Modellierung durch Schaltkreise (2)

Die Abbildung legt für jedes Gatter v 2 I eine Reihenfolge der eingehenden Kanten fest, d.h. falls indeg(v) = k, dann ist mit

Die Folge zeichnet Knoten yi 2 V als Ausgänge aus.

*: EIIN

),,()( 1 keevIN .1)( kiveZ i

),,( 1 mm yyY

RW-Systemarchitektur Kap 1

Beispiel

X1 X2 X3 X4 X5 X6 X7 X8

RW-Systemarchitektur Kap 1

Semantik von Schaltkreisen (1) Sei ein Schaltkreis über einer

Zellenbibliothek BIB.

Sei für = (1, …, n) 2 {0, 1}n eine Eingangsbelegunggegeben durch in,(xi) = i 8 1 i n.

Eine Belegung SK, : V ! {0, 1} für alle Knoten v 2 V ist dann gegeben durch die folgenden Definitionen: SK,(xi) = in,(xi) = i 8 1 i n.

SK,(0) = 0, SK,(1) = 1

falls v 2 I mit typ(v) = g 2 Bk, IN(v) = (e1, …, ek), dann ist SK,(v) = g(SK,(Q(e1)), …, SK,(Q(ek))).

Warum ist das wohldefiniert?Weil G azyklisch!

),,,,( mn YINtypGXSK

RW-Systemarchitektur Kap 1

Semantik von Schaltkreisen (2)

(SK,(y1), …, SK,(ym)) ist dann die unter

Eingangsbelegung = (1, …, n) berechnete

Ausgangsbelegung des Schaltkreises SK.

Die Berechnung von SK, bei Eingangsbelegung

heißt auch Simulation von SK für Belegung .

RW-Systemarchitektur Kap 1

Beispiel: Semantik von Schaltkreisen

1 0 0 0 0 0 0 0

0 0 0

0

000

1

RW-Systemarchitektur Kap 1

Semantik von Schaltkreisen (ff)

Die an einem Knoten v berechnete Boolesche Funktion (v) : Bn ! B

ist definiert durchvSKv

für ein beliebiges Bn .

Die durch den Schaltkreis berechnete Funktion ist

fSK y1ym

RW-Systemarchitektur Kap 1

Symbolische Simulation

Symbolische Simulation benutzt zur Simulation eines Schaltkreises keine festen Booleschen Werte an den Inputs, sondern Boolesche Variablen.

Es wird dann zu jedem Knoten die Boolesche Funktion bestimmt, die der Knoten berechnet, z.B. in Form eines Booleschen Ausdrucks.

RW-Systemarchitektur Kap 1

Beispiel: Semantik von Schaltkreisen

x1 x2 x3 x4 x5 x6 x7 x8

x2©x3 x4¢x5x6+x7

(x2©x3©x4¢x5 )+x1

x2©x3©x4¢x5

x8(x6+x7)x8¢x4¢x5

x8¢x4¢x5+x8(x6+x7)

RW-Systemarchitektur Kap 1

Kosten eines Schaltkreises

Unter den (Hardware-)Kosten C(SK) eines Schaltkreises SK versteht man die Anzahl seiner Gatter

Unter der Tiefe depth(SK) eines Schaltkreises SK versteht man die maximale Anzahl von Gattern auf einem Pfad von einem beliebigen Eingang xi zu einem beliebigen Ausgang yj von SK.

depth(SK) ist ein Maß für die Geschwindigkeit des Schaltkreises.

Bemerkung: Schaltkreise sind definiert auf Grundlage einer Zellenbibliothek BIB.

) Kosten hängen von der Wahl der Bibliothek ab. Tiefe ist nur dann ein sinnvolles Maß für die Geschwindigkeit des

Schaltnetzes, wenn die Schaltgeschwindigkeit der einzelnen Gatter aus BIB nicht sehr verschieden ist.

Wenn nichts anderes vereinbart, verwenden wir im folgenden die Standardbibliothek

.|}),,{}1,0({\| 1 nxxV

},,,,,{: NORNANDEXORORANDNOTSTD

RW-Systemarchitektur Kap 1

Beispiel: Kosten und Tiefe von Schaltkreisen

x1 x2 x3 x4 x5 x6 x7 x8

Kosten: 8

Tiefe: 3

RW-Systemarchitektur Kap 1

Teilschaltkreise, hierarchischer Entwurf

Illustration eines Teilschaltkreises:

x1

x2

x3

RW-Systemarchitektur Kap 1

Hierarchische Schaltkreise

In hierarchischen Schaltkreisen sind Teilschaltkreise durch Symbole ersetzt.

Den zugehörigen („flachen“) Schaltkreis erhält man,

indem man die Symbole durch Einsetzen derTeilschaltkreise wieder entfernt.

RW-Systemarchitektur Kap 1

Illustration eines hierarchischen Schaltkreises

EXOR

EXOR

x1

x2

x3

RW-Systemarchitektur Kap 1

Satz

Sei f Bn,m.

Dann gibt es einen Schaltkreis, der f berechnet.

Beweis folgt.

RW-Systemarchitektur Kap 1

Zu jedem Booleschen Ausdruck eBE(Xn) gibt es einen

Schaltkreis

so dass .

Lemma

SKfe

Beweis:

Induktion über die Struktur des BE.

),,,,( mn YINtypGXSK

RW-Systemarchitektur Kap 1

Beweis zum Satz:

1.Fall: f Bn. e BE(Xn), der f berechnet.

aus vorigem Lemma folgt der Satz2.Fall: f Bn,m , m 2.

Fasse f : Bn Bm als Folge von Funktionen

(f1, ..., fm) mit fi : Bn B auf.

Konstruiere für jedes fi einen SK, der fi berechnet.

Setze zusammen.

(siehe folgende Abb.)

RW-Systemarchitektur Kap 1

Abbildung

....

x1 x2 ... xn

... ...

f1 fnf2 ...

RW-Systemarchitektur Kap 1

Beispiel: Schaltkreise

2mod)(),,(16

116116

i

ixxxexor

0

1 falls Anzahl der xi mit xi = 1 ungeradesonst

Gesucht: Schaltkreisrealisierung für exor16

Annahme: Wir haben exor2 in unserer Zellenbibliothek.

Beobachtungen: Man kann exor16 als Komposition von © := exor2 darstellen. © ist eine assoziative Operation!

Gegeben:Funktion exor16 2 B16 mit

RW-Systemarchitektur Kap 1

Beispiel: Schaltkreise Realisierung für exor16:

Man sieht: 15 exor2-Gatter genügen zur Realisierung von exor16.

x1x2 x3 x4 x5x6 x7x8 x9x10 x11x12 x13x14 x15x16

RW-Systemarchitektur Kap 1

Beispiel: Schaltkreise

Frage:

Wie groß ist das kleinste Boolesche Polynom für exor16?

RW-Systemarchitektur Kap 1

Schaltkreise mit geringer TiefeAufgabe:

Realisiere die Funktion

unter Verwendung von -Gattern mit 2 Eingängen mit

möglichst geringer Tiefe.

nxx ...1

Lösung:

Benutze Assoziativität von

Balancierte Bäume

RW-Systemarchitektur Kap 1

Beispiel zur Assoziativität

x1 x4x3x2

4321 xxxx

x2x1 x4x3

4321 xxxx

RW-Systemarchitektur Kap 1

LemmaDie Funktion kann

unter Verwendung von -Gattern mit 2 Eingängen

durch einen Schaltkreis der Tiefe log2 (n)

realisiert werden.

n1 x...x

RW-Systemarchitektur Kap 1

Fazit: BEs, Schaltkreise

Definiert man die Kosten eines BEs durch die Zahl der Operationen, so folgt aus dem Beweis des Satzes, dass es zu jedem BE einen Schaltkreis gibt,dessen Kosten höchstens gleich groß sind.Durch Wiederverwendung von Teilschaltkreisen können die Kosten reduziert werden.

Die Kosten einer Schaltkreisrealisierung für beliebiges f kann mit dem Satz durch n2n - 1, die Tiefe durch n+ log2 (n) abgeschätzt werden.

RW-Systemarchitektur Kap 1

Zusammenfassung, Ausblick

Schaltkreise stellen Boolesche Funktionen dar. Optimale Boolesche Polynome können sehr viel

größer sein als entsprechende Schaltkreise (exponentielle Unterschiede möglich!).

Rechtfertigung des Einsatzes von Schaltkreisen statt PLAs

Es gibt auch Algorithmen zur Berechnung optimaler (mehrstufiger) Schaltkreise Anspruchsvoller als Optimierung von Booleschen Polynomen Meist heuristisch (Näherungsverfahren)

RW-Systemarchitektur Kap 1

Zusammenfassung, Ausblick

Schaltkreise stellen Boolesche Funktionen dar. Optimale Boolesche Polynome können sehr viel

größer sein als entsprechende Schaltkreise (exponentielle Unterschiede möglich!).

Rechtfertigung des Einsatzes von Schaltkreisen statt PLAs

Es gibt auch Algorithmen zur Berechnung optimaler (mehrstufiger) Schaltkreise Anspruchsvoller als Optimierung von Booleschen Polynomen Meist heuristisch (Näherungsverfahren)

Ausfaktorisieren Boolescher Polynome Dekomposition

Nicht Gegenstand dieser Vorlesung Hier: Schaltkreise für spezielle Funktionen, insbesondere

Arithmetik