View
216
Download
0
Category
Preview:
Citation preview
Minimierung nach Quine ‐Mc Cluskey
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 43
# A B C D OK
m9 + m11 1 0 ‐ 1 P1
m7 + m15 ‐ 1 1 1 P2
m11 + m15 1 ‐ 1 1 P3
m0 + m1 + m4 + m5 0 ‐ 0 ‐ P4
m0 + m1 + m8 + m9 ‐ 0 0 ‐ P5
m4 + m5 + m6 + m7 0 1 ‐ ‐ P6
Ermitteln der Primtermtabelle
m0 m1 m4 m5 m6 m7 m8 m9 m11 m15
P1
P2
P3
P4
P5
P6
Minimierung nach Quine ‐Mc Cluskey
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 44
Finden einer minimalen Überdeckung durch wiederholte Spalten und Zeilendominanzprüfung
m0 m1 m4 m5 m6 m7 m8 m9 m11 m15
P1 X X
P2 X X
P3 X X
P4 X X X X
P5 X X X X
P6 X X X X
Minimierung nach Quine ‐Mc Cluskey
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 45
Finden einer minimalen Überdeckung durch wiederholte Spalten und Zeilendominanzprüfung
m6 m8 m11 m15
P1 X
P2 X
P3 X X
P4
P5 X
P6 X
Minimierung nach Quine ‐Mc Cluskey
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 46
Finden einer minimalen Überdeckung durch wiederholte Spalten und Zeilendominanzprüfung
m6 m8 m11 m15
P3 X X
P5 X
P6 X
Minimierung nach Quine ‐Mc Cluskey
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 47
Finden einer minimalen Überdeckung durch wiederholte Spalten und Zeilendominanzprüfung
m6 m8 m11
P3 X
P5 X
P6 X
Addition eines einzigen BitsEingang Ausgang
a b CarryIn CarryOut Sum
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 49
+a
b
CarryIn
CarryOut
Sum
Ripple‐Carry‐Adder
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 50
+a0
b0
CarryIn
CarryOut
Sum
+a1
b1
CarryIn
CarryOut
Sum
+a2
b2
CarryIn
CarryOut
Sum
Problem: Berechnung benötigt O(n) Gatterlaufzeit.
Carry‐Lookahead‐Adder
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 51
Beobachtung 1: wenn zwei Binärzahlen a(0)...a(n‐1) und b(0)...b(n‐1) addiert werden, dann findet ein Übertrag an der Stelle i statt, wenn
Also können wir als „Carry‐Generierer“ g(i) definieren:
Beobachtung 2: ein Übertrag von der Stelle i‐1 wird von der Stelle i an die nächste Stelle i+1 weiter geleitet, wenn
Also können wir als „Carry‐Propagierer“ p(i) definieren:
Carry‐Lookahead‐Adder
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 52
Mittels der Generate‐ und Propagate‐Ausdrücke lässt ich dann für jede Stelle i der Carry (Übertrag) für die Stelle i+1 definieren:
Für einen 4‐Stelligen Addierer ergibt sich damit:
Wie hilft uns das jetzt weiter?
Carry‐Lookahead‐Adder
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 53
Wie hilft uns das jetzt weiter?
Expandieren durch Substitution:
Laufzeit: O(1), aber die hohe Anzahl der benötigten Gatter limitiert die Größe eines solchen Bausteins. (Lösung: zusammenfassen mehrerer CLA zu einer Gruppe)
∙∙∙∙
∙
Logische BausteineSequentielle Schaltungen
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 54
Sequentielle Schaltungen
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 55
Kombinatorische Schaltungen Sequentielle Schaltungen……
n Eingänge m Ausgänge
Ausgänge hängen nur von den Eingängen ab. Wie schon gezeigt, ist dies durch eine Wahrheitstabelle beschreibbar.
Zustand ……
n Eingänge m Ausgänge
Ausgänge hängen von den Eingängen und dem aktuellen Zustand des Bausteins ab. Wie kann man dieses Verhalten beschreiben?
Zustandsautomat
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 56
Zustand 00
Zustand 01
Zustand 10
Eingabe 00 / Ausgabe 11Eingabe 10 / Ausgabe 01Eingabe 11 / Ausgabe 10
Eingabe 11 / Ausgabe 00
Eingabe 01 / Ausgabe 00
2‐Bit E
ingabe
2‐Bit AusgabeEin Beispiel:
Speichern von Zuständen
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 57Bildquelle: David A. Patterson und John L. Hennessy, „Computer Organization and Design“, Fourth Edition, 2012
R S altes Q neues Q0 0 00 0 10 1 00 1 11 0 01 0 1
Speichern eines Bits am Beispiel R‐S‐Latch (S=Set, R=Reset)
Beobachtung: das Speichern von Zustand erfordert Rückkopplungen (d.h. Ausgang ist wieder Eingang) in der Schaltung.
Speichern von Zuständen
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 58
Erweiterung eines R‐S‐Latch zu einem D‐Latch (D=Data, C=Clock)
C D altes Q neues Q0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1
R S altes Q neues Q
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
R
S
Beispiel
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 59
Ergebnisist ein Bit
Eingang n Bit
…Kombinatorische Schaltung
…
Zeit
Wir wollen das Ergebnis einer kombinatorischen Schaltung in einem D‐Latch speichern. Q soll wohldefiniert entweder den Inhalt vor oder nach der „Berechnung“ speichern.
D‐Latch
D (Daten)
Q
NOT(Q)
C (Clock)
Problem: Wann liegt das Ergebnis‐Bit stabil an D an? Bildquelle: Symbole kopiert aus David A. Patterson und John L. Hennessy, „Computer Organization and Design“, Fourth Edition, 2012
Lösung: Taktung
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 60
Ergebnisist ein Bit
Eingang n Bit
…Kombinatorische Schaltung
…
Zeit
Wir wollen das Ergebnis einer kombinatorischen Schaltung in einem D‐Latch speichern. Q soll wohldefiniert entweder den Inhalt vor oder nach der „Berechnung“ speichern.
D‐Latch
D (Daten)
Q
NOT(Q)
C (Clock)
LetztesClock‐Signal
NächstesClock‐Signal
Takt‐ZyklusBildquelle: Symbole kopiert aus David A. Patterson und John L. Hennessy, „Computer Organization and Design“, Fourth Edition, 2012
D‐Latches sind Transparent bzgl. Taktsignal
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 61
R
S
D
C
Q
D‐Flip‐Flop (ist nicht transparent)
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 62
Ausgang ändert sich nur bei einer fallenden Taktflanke.
DLatch
D
C
Q DLatch
D
C
QD
C
!Q
D
C
Q
Bausteine als Black‐Box
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 64
Wir haben jetzt einige Basisbausteine kennen gelernt.
In dieser Vorlesung sind wir mit Blockschaltbildern in der Regel eine Abstraktionsebene höher.
Die betrachteten Bausteine sind „Kästen“ mit Eingangsleitungen und Ausgangsleitungen. Die Leitungen können entweder Daten (Datenleitungen) oder Steuersignale (Steuerleitungen) transportieren.
Wie die Bausteine der Blockschaltbilder intern mit Grundbausteinen aufgebaut sind und wie die Taktung der einzelnen Bausteine genau abläuft betrachten wir in dieser Vorlesung nicht weiter.
Bemerkung: In Blockschaltbildern wird das für sequentielle Bausteine erforderliche Clock‐Signal häufig der Übersicht halber weg gelassen.
Baustein
Ausgangsleitungen
Eingangsleitungen
Beispiel eines abstrakten Bausteins
Verschaltung von Bausteinen
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 65
n Bits
Einzelne Leitung
Bus (lassen häufig dieMarkierung n‐Bits weg)
Verbinden von Bauelementen DatenflussrichtungEingabeeineslogischenBausteins
AusgabeeineslogischenBausteins
Kreuzungen und Verbindungen Beispiel
Leitungen kreuzensich, sind aber nichtverbunden
Verbindungenaußerhalb derLeitungsendpunktesind durch einenPunkt gekennzeichnet.
Baustein A
Baustein B
Baustein C
Arithmetische, logische Einheit (ALU)
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 66
ALUZero (1)Result (n)Overflow (1)
ALU Operation (k)
CarryOut (1)
A (n)
B (n)
Angabe in Klammern ist die Anzahl Bits.
Beispiel‐Funktionen
AND
OR
NOT
Addition
Subtraktion
VergleichGgf. ist die ALU auf eine Operation festgelegt. Dann Entfällt der Eingang und ALU wird mit dem Namen der Operation ersetzt.
Kombinatorisch?Sequentiell?
Register und Shift‐Register
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 67
Speichert n Bits
Eingang (n)
Ausgang (n)
Shift (1)Load (1)Reset (1)
Kombinatorisch?Sequentiell?
Control
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 68
Kombinatorisch?Sequentiell?
Control
Ein Baustein der das Zusammenarbeiten von anderen Bausteinen koordiniert.In Abhängigkeit der Eingänge werden die passenden Steuerleitungen geschaltet.
Ausgänge sindSteuerleitungen in andere Bausteine
Eingänge sind Datenleitungen aus anderen Bausteinen
Control Beispiel
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 69
4‐Bit‐Register R1Store R1 4‐Bit‐Register R2
R2 Bit 0
Control
Zero
Store R2
SUB
Control soll folgenden Algorithmus implementieren:wenn R2 gerade und R1-R2=0, dann
R1 = 0wenn R2 ungerade und R1-R2!=0, dann
R2 = R1-R2sonst
R1 = R1-R2
R2Bit 0
Zero StoreR1
StoreR2
0 0
0 1
1 0
1 1
Control wird als kombinatorische Schaltung realisiert.Hierzu die Wahrheitstabelle:
Anhand der Wahrheitstabelle wird dann die Schaltung gebaut.
Rückgekoppelte Register haben immer einen wohldefinierten Zustand, da Register nur zur Clock‐Flanke aktualisiert werden.
Eingabe Ausgabe
Pseudo‐Code‐Darstellungen
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 71
Elementaranweisungen
Variablenzuweisungen, z.B.:x = 42
Arithmetik, z.B.:y = 10x = (42 + y) * 20
Das Symbol „=“ beinhaltet implizit eine zeitliche Abfolge, damit ist z.B. sinnvoll:x = x + 1Abkürzende Schreibweise für voriges Konstrukt: x++
Allgemein: als Elementaranweisung betrachten wir jede Anweisung, die auf der betrachteten Abstraktionsebene nicht weiter sinnvoll in eine Folge von einfacheren Anweisungen unterteilbar ist.
Felder
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 72
Felder für den Zugriff auf den Speicher, z.B.: A[]
Zugriff auf ite Speicherstelle: A[i]
Beispiel:
0x0f00 : 14 A[0] 0x0f01 : 15 A[1] 0x0f02 : 42 A[2] 0x0f03 : 43 A[3] ......0x0f0f : 255 A[15]
Sequenz von Elementaranweisungen
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 73
Setze i auf i+1Setze j auf 2*i
usw.
Jedes Programm beginnt an einer Stelle und terminiert (hoffentlich) irgendwann.
Im Flussdiagramm ist Beginn und Ende des Programms mit den ovalen Symbolen dargestellt.
Im Beispiel also „Start“ und „Ende“.
Das einfachste Programm arbeitet einfach eine Sequenz von elementaren Anweisungen ab.
Im Flussdiagramm wird so eine Sequenz durch ein Rechteck dargestellt.
Die Abarbeitungsrichtung des Programms wird durch die Pfeile gekennzeichnet.
Start
Ende
If‐then‐else
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 74
if‐then‐else am Beispiel:
if(i<10) then<Code-Block 1>
else<Code-Block 2>
Ist i<10?
Code‐Block 1 Code‐Block 2
ja
nein
Switch‐Statement
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 75
Switch‐Statement am Beispiel:
switch(i)case 1:
<Code-Block 1>case 2:
<Code-Block 2>...defaut:
<Code-Block n>
i=1?
Code‐Block 2
Code‐Block 1ja
Code‐Block n
i=2?
nein
ja
nein
...
For‐Schleife
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 76
For‐Schleife am Beispiel:for(i=0; i<10; i++) {
<das innere der Schleife>}
Bedeutet:• Initialisiere i mit 0• Führe das innere der Schleife aus• Erhöhe i um eins• Wiederhole wenn immer noch i<10
Ist i<10?
Ende
Start
Innere der Schleife
Setze i auf 0
Erhöhe i um 1
ja
nein
While‐Schleife
Grundlagen der Rechnerarchitektur ‐ Logik und Arithmetik 77
While‐Schleife an Beispiel:
i=0while(i<10) {
<das innereder Schleife>i++
}Bedeutet:• Initialisiere i mit 0• Führe das innere der Schleife aus• Erhöhe i um eins• Wiederhole wenn immer noch i<10
Ist i<10?
Ende
Start
Innere der Schleife
Setze i auf 0
Erhöhe i um 1
ja
nein
Recommended