Grundlagen der Rechnerarchitektur
[CS3100.010]
Wintersemester 2014/15
Heiko Falk
Institut für Eingebettete Systeme/Echtzeitsysteme Ingenieurwissenschaften und Informatik
Universität Ulm
Kapitel 5
Rechnerarithmetik
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 3/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Inhalte der Vorlesung
1. Einführung 2. Kombinatorische Logik 3. Sequentielle Logik 4. Technologische Grundlagen 5. Rechnerarithmetik 6. Grundlagen der Rechnerarchitektur 7. Speicher-Hardware 8. Ein-/Ausgabe
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 4/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Inhalte des Kapitels (1)
5. Rechnerarithmetik – Einleitung – Binäre Addition
– Ripple Carry Addierer – Serielles Addierwerk – Carry-Look-Ahead-Addierer – Carry-Select-Addierer – Carry-Save-Addierer
– Binäre Subtraktion – Zweierkomplement-Darstellung – Subtraktion im Zweierkomplement
– ...
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 5/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Inhalte des Kapitels (2)
5. Rechnerarithmetik – … – Binäre Multiplikation
– Vorzeichenlose Multiplikation – Serielles Schaltwerk – Array-Multiplizierer
– Vorzeichenbehaftete Multiplikation – Booth-Algorithmus – Implementierung in VHDL
– Binäre Division – Restoring-Division – Non-Restoring-Division
– BCD-Arithmetik
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 6/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Einordnung
Vorlesung „Grundlagen der Betriebssysteme“ – Repräsentation von Zahlen in der Computer-Hardware ist bekannt
– Natürliche Zahlen: Darstellung zu einer Basis b – Ganze Zahlen: Zweierkomplementdarstellung – Reelle Zahlen: Festkomma- und Gleitkommadarstellung, IEEE 754
– Algorithmischer Ablauf der Grundrechenarten auf den verschiedenen Zahlendarstellungen ist ebenfalls bekannt
Unklar – Wie können die Algorithmen für die Grundrechenarten effizient in
Hardware umgesetzt werden? Wie sind Rechenwerke (arithmetical logical units, ALUs) intern
aufgebaut?
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 7/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Erinnerung: Halbaddierer
Addition in erster (rechter) Spalte – Zwei Eingänge: erstes Bit von jeder Zahl – Zwei Ausgänge: erstes Bit des Ergebnisses, Carry-Bit – Wahrheitstabelle Blockschaltbild
– Gatterschaltung c = a * b s = a * b + a * b = a ⊕ b (XOR)
a b s c 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 8/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Erinnerung: Volladdierer (1)
Addition in anderen Spalte – Drei Eingänge: je ein Bit der Summanden, und Carry von voriger Stelle – Zwei Ausgänge: Summen-Bit des Ergebnisses, Carry-Bit – Wahrheitstabelle Blockschaltbild
a b cin s cout
0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 9/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Erinnerung: Volladdierer (2)
Schaltung – Aufbau mit Halbaddierern
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 10/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Paralleles Addierwerk
Schaltnetz zur Addition n-Bit langer Summanden
– Lange Gatterlaufzeit, bis Endergebnis stabil anliegt
– Gatterlaufzeit: t = 2n * ∆t – Ripple Carry Adder (RCA)
0
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 11/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Serielles Addierwerk
Synchrones Schaltwerk zur Addition n-Bit langer Summanden
– Schieberegister für jeden Summanden und für das Ergebnis – Pro Takt wird genau eine Stelle der Summanden addiert – Additionsergebnis liegt nach n Takten vor – Carry-Flip-Flop muss zu Beginn mit 0 initialisiert werden!
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 12/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Carry-Look-Ahead-Addierer (1)
Beschleunigung der Addition – Vermeidung des sequentiellen Durchlaufs der Überträge – Idee: parallele Berechnung aller Überträge für jede Stelle i
Es gilt für Stelle i – ci+1 = ai * bi + (ai + bi) * ci – = Gi + Pi * ci mit
– Gi = ai * bi gibt an, ob Stelle i Carry generiert (Generate) – Pi = ai + bi gibt an, ob Stelle i Carry weitergeben muss (Propagate),
falls vorherige Stelle Carry generiert oder weitergibt – Schaltfunktionen für Überträge
c1 = G0 + P0 * c0 c2 = G1 + P1 * c1 = G1 + P1 * G0 + P1 * P0 * c0 c3 = G2 + P2 * c2 = G2 + P2 * G1 + P2 * P1 * G0 + P2 * P1 * P0 * c0 …
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 13/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Carry-Look-Ahead-Addierer (2)
Berechnung der Überträge mit maximal 2 Gatterlaufzeiten möglich – Max. Anzahl der Gattereingänge hängt von der Breite des Addierers ab
– Kaskadierung möglich – Pro CLA-Addierer nur 4∆t Verzögerung
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 14/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Carry-Select-Addierer
Beschleunigung der Addition – Idee: nicht auf das Carry des niederwertigen Blocks warten, sondern
beide Ergebnisse berechnen und später selektieren
– Multiplexer selektiert Endergebnis
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 15/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Carry-Save-Addierer
Mehr als zwei Summanden – Überträge aus erster Addition werden in der nächsten Addition
berücksichtigt (keine Weitergabe der Überträge in der laufenden Addition)
– Beispiel: 4-Bit CSA für vier Summanden a, b, c, d
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 16/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Zweierkomplement-Darstellung
Berechnung des Zweierkomplements einer Zahl N bei n Ziffern – C = 2n – N bei n Ziffern/Bits – Komplement C entspricht dem Wert -N
Darstellung positiver ganzer Zahlen – Höchstwertiges Bit zn-1 = 0 – Andere Bits unbeschränkt
– Wert: (zn-1, ..., z1, z0)2 = Σ zi * 2i
Darstellung negativer ganzer Zahlen – Höchstwertiges Bit zn-1 = 1 – Andere Bits unbeschränkt
– Wert: (zn-1, ..., z1, z0)2 = -2n + Σ zi * 2i
i
i
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 17/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Binäre Subtraktion
Subtrahierer kann ähnlich wie Addierer entwickelt werden – Verwendung von Addierern zur Subtraktion
– Idee: a – b = a + (-b)
Addition – Einsatz von Standardaddierern für Zahlen im Zweierkomplement
Subtraktion – Vorherige Komplementbildung eines Summanden erfordert
– Invertierung der Ziffern – Addition von 1
kann durch gesetzten Carry-Eingang erzielt werden
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 18/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Subtraktion im Zweierkomplement
Addier- und Subtrahierwerk
– Beim Subtrahieren
– Invertieren der b-Eingänge durch XOR-Gatter – Addieren von 1 durch gesetztes Carry-in
– Überlauferkennung: cout ≠ cin
– Bei Subtraktion ist gesetztes Carry-out der Normalfall
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 19/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Binäre Multiplikation
Schriftliche Multiplikation / „Schulmethode“ auf positiven Binärzahlen – 0011 * 1010 – 0011 1 – 0000 0 – 0011 1 – 0000 0 – = 0011110
Übertragung auf einen Computer – Realisierung der Multiplikation durch Verschiebe-Operationen
(Schieberegister) und einen Addierer
+
Kontrolle: 3 * 10 = 30 30 = 111102
Ver- schieben
Addieren
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 20/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Vorzeichenlose Multiplikation (1)
Alternative A: Serielles Schaltwerk zur Multiplikation
– Lösche p (clear p) – n-mal:
– Ermittle b0 (shift right b) – Addiere a auf (p2n-1, …, pn+1, pn)2 oder nicht, je nach b0 (add) – Verschiebe p einschließlich cout der vorherigen Addition (shift right p)
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 21/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Vorzeichenlose Multiplikation (2)
Alternative B: Array-Multiplizierer – Schaltwerk für das schriftliche Multiplikationsschema – Beispiel: n = 4
– Einsatz von Carry-Save-Addierern für die einzelnen Zeilen
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 22/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Vorzeichenlose Multiplikation (3)
Alternative B: Array-Multiplizierer – Schaltwerk für n = 4
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 23/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Vorzeichenlose Multiplikation (4)
Alternative C: Alternative B und baumförmige Addierer-Anordnung – Baumförmige statt sequentielle Anordnung der Carry-Save-Addierer – Beispiel: n = 8
– Vorteil: geringere Gatterlaufzeit
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 24/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Alternative D: Zweistufiges Schaltnetz für Multiplizierer – Z.B. als PROM/ROM Siehe Kapitel 2, Folien 74ff.
– Schnellste Variante, aber extrem aufwändig 22n * 2n Bits in der Wertetabelle notwendig
Vorzeichenlose Multiplikation (5)
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 25/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Vorzeichenbehaftete Multiplikation: Booth-Algorithmus (1)
Wiederholung: Verfahren nach Booth – Beispiel: -2 * 3 = -6 (für n = 4) – A * B: 1110 * 0011 – 2n+1 Bits breite Hilfsvariable R: 0000 0011 0
Bits R4, ..., R1 mit B initialisiert, Rest 0 1. Fenster „10“: Subtrahiere A: -1110 – 0010 0011 0 – Vorzeichenbehaftetes Schieben: 0001 0001 1 2. Fenster „11“: nur Schieben: 0000 1000 1 3. Fenster „01“: Addiere A: +1110
1110 1000 1 – Vorzeichenbehaftetes Schieben: 1111 0100 0 4. Fenster „00“: nur Schieben: 1111 1010 0
Fenster
Ergebnis: 111110102 = -6
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 26/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Booth-Algorithmus in Hardware-Beschreibungssprache VHDL FUNCTION Booth(A, B : IN bit_vector) RETURN bit_vector IS CONSTANT n : natural := A’LENGTH; VARIABLE P : bit_vector(n-1 DOWNTO 0) := (OTHERS=>’0’); VARIABLE Q : bit_vector(n DOWNTO 0) := (OTHERS=>’0’); BEGIN Q(n DOWNTO 1) := B; FOR i IN 0 TO n-1 LOOP CASE Q(1 DOWNTO 0) IS WHEN "10" => P := P – A; WHEN "01" => P := P + A; WHEN OTHERS => -- keine Aktion END CASE; P & Q := sra(P & Q); -- arithm. Rechts-Schieben END LOOP; RETURN P(n-1 DOWNTO 0) & Q(n DOWNTO 1); END Booth;
Vorzeichenbehaftete Multiplikation: Booth-Algorithmus (2)
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 27/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Erklärungen zum VHDL-Code – Eingabe sind Bit-Vektoren A und B im Zweierkomplement, Ausgabe ist
wiederum ein Bit-Vektor. – Voraussetzung: Eingaben A und B enthalten gleich viele Bits – Die 2n+1 Bits breite Hilfsvariable R von Folie 25 wird im VHDL-Code
repräsentiert durch zwei Hilfsvariablen P und Q. P stellt die höherwertigsten n Bits von R dar, Q die niederwertigsten n+1. Hilfsvariable R ergibt sich aus P konkateniert mit Q (P & Q).
– Das typische Booth-Fenster wird im VHDL-Code repräsentiert durch Bits 0 und 1 der Hilfsvariable Q: Q(1 DOWNTO 0).
– Abhängig vom Fensterinhalt wird in den höherwertigsten Bits von R (d.h. auf P im VHDL-Code) subtrahiert oder addiert.
– In jeder Iteration wird R (d.h. P & Q in VHDL) arithmetisch um ein Bit nach rechts geschoben
Vorzeichenbehaftete Multiplikation: Booth-Algorithmus (2)
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 28/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Vorzeichenbehaftete Multiplikation: Booth-Algorithmus (3)
Serielles Schaltwerk zur Multiplikation
– Lösche P und Q (clear P&Q) – n-mal:
– Addiere bzw. subtrahiere A auf P oder nicht, je nach Q1 und Q0 (add/sub)
– Verschiebe P und Q (sra P&Q)
An-1 … A1 A0 Bn-1 … B1 B0
n-Bit Addierer/ Subtrahierer
n
n Pn-1 … P1 P0 Qn-1 … Q1 Q0 Qn &
n Steuer-
werk
n add/sub
clear P&Q sra P&Q
2
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 29/36
-
-
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Binäre Division
Schriftliche Division / „Schulmethode“ – Beispiel: 103 / 9 = ? – 01100111 / 1001 =
– Verfahren wird auch Restoring-Division genannt, da durch Korrektur ursprünglicher Dividend wiederhergestellt wird
0000 0
0110 0
1
1001 0011 1
0
- 0000 01111
1
- 1001 01101
1
- 1001 0100
Divisor Quotient
Rest
Dividend
Kontrolle: 103 / 9 = 11 Rest 4
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 30/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Restoring-Division (1)
Einsatz von Addition/Subtraktion und Schiebeoperationen – In jedem Schritt testweise Subtraktion des skalierten Divisors b vom
Dividenden a – qi = 1 falls a – b ≥ 0 – qi = 0 und Korrektur falls a – b < 0
– Nachholen signifikanter Ziffern zum Zwischenergebnis durch Schiebeoperation
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 31/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Restoring-Division (2)
Serielles Dividierwerk für vorzeichenlose Zahlen
– Lade q: obere Hälfte = 0, untere Hälfte = a (load q) – n-mal:
– Schiebe q nach links (shift left q) – Subtrahiere b von oberer Hälfte von q (sub):
negativ: q0 = 0 und addiere b zurück (add) / positiv: q0 = 1 – Ergebnis: obere Hälfte q = Rest, untere Hälfte q = Quotient
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 32/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Restoring-Division (3)
Vorzeichenbehaftete Division mit Zweierkomplement-Darstellung – Verfahren im Prinzip identisch – Jedoch:
– Unterschiedliche Erkennung von Unterläufen – Propagierung des Vorzeichens in oberer Hälfte von q beim Laden
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 33/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Non-Restoring-Division
Restoring-Division – Divisor wird subtrahiert – Falls Unterlauf (Ergebnis negativ): Divisor wird wieder addiert – Im nächsten Durchlauf wird die Hälfte des Divisors wieder subtrahiert
(wegen Links-Shift des Dividenden vor der Subtraktion)
Idee der Non-Restoring-Division – Bei Unterlauf wird stattdessen nur die Hälfte des Divisors addiert Ersparnis einer Addition bzw. Subtraktion
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 34/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
BCD-Arithmetik (1)
BCD-Code (Binary Coded Decimals) – 4-Bit Darstellung von Dezimalzahlen im Rechner
– Zahlendarstellung mit mehreren 4-Bit breiten Ziffern, z.B. (0001 0011 1001)BCD entspricht der Dezimalzahl 13910
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 35/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
BCD-Arithmetik (2)
Vorteil – Leichtes Umwandeln von Dezimalzahlen in BCD-codierte Zahlen Rechnen mit BCD-codierten Zahlen – Spezielle Rechenwerke – Unterstützung in gängigen Prozessoren
– Zumindest für Addition und Subtraktion
Nachteil – Oft nicht alle Rechenoperationen in Hardware unterstützt – Rechenoperation in Software ineffizient – Verschwendung von Speicherplatz
Grundlagen der Rechnerarchitektur (GdRA) WS 2014/15 Folie 36/36
© H. Falk | 01.10.2014 5 - Rechnerarithmetik
Zusammenfassung
Binäre Grundrechenarten – Addition und Subtraktion auf Grundlage von Volladdierern leicht
realisierbar – Addier-/Subtrahierwerke haben je nach Aufbau unterschiedlich lange
Gatterlaufzeiten – Multiplikation und Division sind im Vergleich zu Addition/Subtraktion
komplexer: benötigen mehr Aufwand in Hardware und/oder Rechenzeit – Multiplizierer/Dividierer sind in der Regel als serielle Rechenwerke auf
Grundlage von Schieberegistern und Addierern realisiert