Grundlagen der Informatik(Wintersemester 2009/2010)
Jörg Roth
Jörg Roth 2
0 Motivation und Überblick
Drei große Bereiche der Vorlesung:
■ Darstellung von Zahlen in Rechnern
■ Verarbeitung von Binärdaten auf der Ebene digitaler Schaltungen
■ Programmierung auf Maschinenebene
und relativ knapp
■ Aufbau von Rechnern (Register, Arithmetische Einheit, Speicher etc.)
& >1
&
&
addi $sp,$sp,-16# Platz für 4 Register freimachensw $s0,0($sp)# Register $s0, $s1, $s2, $ra -> Stapelsw $s1,4($sp)sw $s2,8($sp)
Jörg Roth 3
Darstellung von Zahlen:
■ unser liebgewonnenes Dezimalsystem eignet sich nicht für Computer
■ wir machen uns daher Gedanken,wie man Zahlen mit nur zwei Zifferndarstellen kann
Grundidee: Verwendung der Basis 2 statt 10 für die Ziffern z.B.
123(dezimal) = 1.102 + 2.101 + 3.100 = 1.26 + 1.25 + 1.24 + 1.23 + 0.22 + 1.21 + 1.20 = 1111011(binär)
Probleme, die wir in der Vorlesung behandeln:
■ Umrechnung zwischen den Darstellungen
■ Ausführung von Berechnungen im Binärsystem
■ Darstellung von negativen und reellen Zahlen
There are only 10 types of people in
the world: Those who understand
binary, and those who don't!
Jörg Roth 4
Wir gehen in dieser Vorlesung darüber hinaus der Frage nach
Als Softwareentwickler könnten wir in einem Programm z.B. folgende Anweisung schreiben:
a = a+2*b;
Wie wird diese Anweisung letztlich ausgeführt?
Wie rechnet ein Rechner?
Jörg Roth 5
Transistoren
Gatter
Register undMikroprogramm
Assembler undMaschinenprogramm
HöhereProgrammiersprache
int a=1, b=2;a = a+2*b;
lw $t0, alw $t1, badd $t0, $t0, $t1add $t0, $t0, $t1sw $t0, a
& >1
&
&
Jörg Roth 6
Transistoren
Gatter
Register undMikroprogramm
Assembler undMaschinenprogramm
HöhereProgrammiersprache
int a=1, b=2;a = a+2*b;
lw $t0, alw $t1, badd $t0, $t0, $t1add $t0, $t0, $t1sw $t0, a
& >1
&
&
Jörg Roth 7
Was bieten uns die verschiedenen Ebenen als Ausdrucksmittel?Mit welchen "Objekten" haben wir auf den verschiedenen Ebenen zu tun?
Höhere Programmiersprache:
■ Es stehen höhere Programmiersprachenkonzeptezu Verfügung: Namenschemata, Objekte, Vererbung, ...
■ Komfortable Datentypen: String, Array, Hashtable, ...
■ Komfortable Kontrollstrukturen: while, if, switch, ...
■ Weitere Funktionen: Mathematische Bibliotheken (sin, cos etc.), Dateizugriffe, Netzwerkzugriffe, Zugriffe auf Peripherie etc.
int a=1, b=2;a = a+2*b;
Jörg Roth 8
Assembler und Maschinenprogramm:
■ Assembler-Programme liegen als Quell-Datei vor und werden durch ein Übersetzungsprogramm (dem so genannten Assembler) in Maschinencode umgewandelt. Nur Maschinencode ist direkt ausführbar.
■ Bei der Verwendung höherer Programmiersprachen entfällt der Schritt über den Assembler häufig und aus dem höheren Programm wird durch den Compiler direkt Maschinencode erzeugt.
■ Auch möglich: Übersetzen in einen Zwischencode, der von einer virtual Maschine (in Maschinencode vorliegend) interpretiert wird
lw $t0, alw $t1, badd $t0, $t0, $t1add $t0, $t0, $t1sw $t0, a
Jörg Roth 9
Eigenschaften von Assembler und Maschinenprogramm:
■ In der Assembler-Sprache stehen keine komfortablen Programmierspra-chenkonzepte zur Verfügung, bestenfalls
• symbolische Variablennamen• symbolische Sprungadressen
• Makros
■ Nur elementare Datentypen verfügbar:
• Byte (8 Bit), 2-Byte-Integer, 4-Byte-Integer• oft keine Fließkomma-Datentypen, oft keine Strings
• Addition, Subtraktion, oft keine Multiplikation, Division
• Logische Bit-Operationen
■ Wenige Kontrollstrukturen: meist nur
• Sprung, bedingter Sprung• Sprung in ein Unterprogramm
Jörg Roth 10
Register und Mikroprogramm:
■ Es gibt nur noch Register und elementare Operationen darauf
■ Typische Operationen: Addieren, Subtrahieren, Inkrementieren, Dekrementieren
■ Das Mikroprogramm steuert den Datenfluss(Welches Register wird mit welchem Operationselement verbunden?)
Gatter:
■ Es gibt nur noch Bits und Operationen auf Bits
■ Typische Operation: Bit1 AND Bit2 Bit3
& >1
&
&
Jörg Roth 11
Ebene der Transistoren:
■ Zur Darstellung von Daten werden Spannungen und Ströme verwendet
■ Elemente dieser Ebene sind im Wesentlichen Transistoren, Dioden und Widerstände
■ Definierte Signalpegel werden auf digitale Daten abgebildet(z.B. >3 Volt bedeutet Bit=1)
Jörg Roth 12
Transistoren
Gatter
Register undMikroprogramm
Assembler undMaschinenprogramm
HöhereProgrammiersprache
lw $t0, alw $t1, badd $t0, $t0, $t1add $t0, $t0, $t1sw $t0, a
& >1
&
&
GD
I
int a=1, b=2;a = a+2*b;
Jörg Roth 13
Daten und Datentypen:
■ Wir müssen auch der Frage nachgehen, wie Daten dargestellt werden.
■ Z.B. Frage: Was bedeutet die folgende Bit-Folge?
0100 0111
0100 0100
0100 1001
0000 0000
Jörg Roth 14
■ Ausweichende Antwort: Es kommt darauf an
■ Die Bedeutung von Bit-Folgen hängt vom jeweiligen Datentyp ab
Man unterscheidet
■ Elementare Datentypen: solche, die nicht weiter zerlegt werden können
■ Zusammengesetzte Datentypen: aus elementaren Datentypen aufgebaut
Elementare Datentypen:
■ Ordinale Datentypen (alles, was man "aufzählen" kann):
• Zeichen: ’a’, ’b’, ’c’,...• Ganze Zahlen mit oder ohne Vorzeichen: byte, short, int, long, word,...
• Boolesche Daten: erlauben nur zwei Werte TRUE, FALSE
• Aufzählungstyp: z.B. (ROT, GRUEN, GELB)(wird intern auf (0, 1, 2) abgebildet)
Jörg Roth 15
■ Zeiger (Pointer):
• Verweise auf Speicherstellen• Bei linear adressierbaren Speicher: eine ganze Zahl
• Sind je nach Programmiersprache explizit vorhanden (und manipulier-bar) oder versteckt
• Für Maschinensprache unerlässlich
■ Gebrochene Zahlen:
• Fließkomma-Zahlen: float, double
• Manchmal (insb. in Datenbanken): Festkomma-Datentypen (z.B.: um Euro-Beträge auszudrücken)
Jörg Roth 16
Zusammengesetzte Datentypen:
■ Feld (array): feste Anzahl gleicher Daten, z.B. 10 ganze Zahlen
■ Zeichenkette (string): z.B. "GDI"
• Strings werden je nach Programmiersprache oder Prozessortyp auch als elementarer Datentyp behandelt
• Strings können auch als Feld von Zeichen angesehen werden
■ Record (auch struct genannt): Datentyp, der aus u.U. verschiedenen Typen zusammengesetzt wird
• Beispiel: Person = String: vorname; String: name; int: alter;
• Durch die objektorientierte Programmierung sind Records durch Objekte darstellbar
Jörg Roth 17
Weitere zusammengesetzte Datentypen:
■ Menge: Jedes Element kann nur einmal aufgenommen werden
■ Hashtable: Man kann Paare von Daten ablegen, nach dem ersten Datum suchen (Schlüssel) und bekommt das zweite Datum (Wert) zurückgelie-fert
■ Vektor: Feld, das dynamisch wachsen kann
In der Regel werden diese Datentypen intern durch andere zusammenge-setzte Datentypen realisiert. Beispiele:
■ Mengen in Pascal werden durch Bit-Felder realisiert
■ Vektoren in Java werden durch Felder fester Größe realisiert, die bei Bedarf auf größere Felder umkopiert werden
Jörg Roth 18
Die "Zahlen"-Datentypen
■ ganze Zahlen mit oder ohne Vorzeichen,
■ Fließkomma-Zahlen,
■ sowie die Operationen darauf
sind Gegenstand des ersten Kapitels.
Zeichen-Datentyp:
■ Kenntnis des Zeichensatzes ist unerlässlich zur Interpretation eines Zei-chens
■ Zeichensätze legen die Zuordnung
interne Darstellung Zeichen
fest
Jörg Roth 19
■ Beispiele:
• ASCII (7 Bit)• EBCDIC (vorwiegend IBM Mainframes)
• Unicode
Der ASCII-Zeichensatz (American Standard Code for Information Inter-change):
■ 7-Bit entspricht 128 möglichen Zeichen (nummeriert 0 - 127)
■ Die Zeichen 0 - 31 und 127 sind Steuerzeichen - also nicht als Einzelzei-chen z.B. auf Bildschirm oder Drucker darstellbar.
■ Die Zeichen 32 -126 sind druckbare Zeichen.
Jörg Roth 20
Die ASCII-Steuerzeichen:
■ Viele Zeichen stammen noch aus der Zeit der Textterminals
■ Bekannte Eingabe-Zeichen: Return, Escape, Del,Backspace
■ Viele Steuerzeichen werden heute nicht mehr benutztNr. Bedeutung Nr. Bedeutung Nr. Bedeutung
0 Null character 11 Vertical Tab 22 Synchronous Idle
1 Start of Header 12 Form feed 23 End of Trans. Block
2 Start of Text 13 Carriage return 24 Cancel
3 End of Text 14 Shift Out 25 End of Medium
4 End of Transmission 15 Shift In 26 Substitute
5 Enquiry 16 Data Link Escape 27 Escape
6 Acknowledgment 17 Device Control 1 (oft XON) 28 File Separator
7 Bell 18 Device Control 2 29 Group Separator
8 Backspace 19 Device Control 3 (oft XOFF) 30 Record Separator
9 Horizontal Tab 20 Device Control 4 31 Unit Separator
10 Line feed 21 Negative Acknowledgement 127 Delete
Ein Textterminal aus den 80er-Jahren
Jörg Roth 21
Druckbare Zeichen im ASCII-Zeichensatz:
Nr. Zeichen Nr. Zeichen Nr. Zeichen Nr. Zeichen Nr. Zeichen Nr. Zeichen
32 Blank 48 0 64 @ 80 P 96 ` 112 p
33 ! 49 1 65 A 81 Q 97 a 113 q
34 " 50 2 66 B 82 R 98 b 114 r
35 # 51 3 67 C 83 S 99 c 115 s
36 $ 52 4 68 D 84 T 100 d 116 t
37 % 53 5 69 E 85 U 101 e 117 u
38 & 54 6 70 F 86 V 102 f 118 v
39 ' 55 7 71 G 87 W 103 g 119 w
40 ( 56 8 72 H 88 X 104 h 120 x
41 ) 57 9 73 I 89 Y 105 i 121 y
42 * 58 : 74 J 90 Z 106 j 122 z
43 + 59 ; 75 K 91 [ 107 k 123 {
44 , 60 < 76 L 92 \ 108 l 124 |
45 - 61 = 77 M 93 ] 109 m 125 }
46 . 62 > 78 N 94 ^ 110 n 126 ~
47 / 63 ? 79 O 95 _ 111 o
Jörg Roth 22
Nachteile des ASCII-Zeichensatzes:
■ Die 7-Bit-Kodierung stammt aus einer Zeit, als "jedes Bit zählte" – heutzutage sind 95 druckbare Zeichen zu wenig
■ Ein Problem: Darstellung der nationalen Sonderzeichen (z.B. ’ä’, ’ö’, ’ü’, ’ß’)
■ Zwischenlösung: der Bereich 128 - 255 wurde für nationale Zeichen ver-wendet.
• Die Zuordnung war aber bei verschiedenen Systemen teilweise unein-heitlich
• Die weiteren 128 Zeichen reichen auch nicht für alle möglichen nationa-len Sonderzeichen
■ Moderne Lösung: Unicode-Zeichen
Jörg Roth 23
Unicode:
■ Ursprünglich 16-Bit, damit waren 65536 mögliche Zeichen darstellbar; die Nummern der Zeichen werden Code Points genannt.
■ Mittlerweile sind 1.114.112 Code Points vorgesehen, von denen aller-dings nur ca. 100.000 mit Zeichen belegt sind, u.a.
• lateinische Zeichen• griechische Zeichen
• chinesische Zeichen
• japanische Zeichen
■ Damit häufige Zeichen weiterhin mit 8 Bit dargestellt werden können, verwendet man UTF-8:
• Zeichen 0 - 127: ASCII• Zeichen 128 - 255: 1-3 weitere Bytes
Arithmetik Jörg Roth 24
1 Arithmetik
Wir behandeln die Darstellung von ganzen und reellen Zahlen in b-adischen Zahlensystemen und geben Algorithmen für die Umrechnung von Darstel-lungen an. Mit ganzen Zahlen (mit einer festen Anzahl von Stellen) wird im Zweier- und Einerkomplement gerechnet und es werden Kriterien für Bereichsüberschreitungen entwickelt. Zur Darstellung von Gleitkommazah-len wird das IEEE-Format benutzt.
Arithmetik Jörg Roth 25
Allgemeines zur Darstellung von Zahlen:
Man unterscheidet zwei Arten der Zahlendarstellung: Additionssysteme, Stellenwertsysteme
Additionssysteme:
■ Der Wert einer Zahl wird durch die Summe der einzelnen Ziffernwerte gebildet.
■ Bekanntestes Beispiel: Römische Zahlen:I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000MMCV = 1000 + 1000 + 100 + 5 = 2105
• Die Reihenfolge ist vorgeschrieben (hier von groß nach klein)• zur Vermeidung zu langer Ziffernkombinationen gibt es einige Aus-
nahmen zu berücksichtigen (z.B. klein vor groß heißt "abziehen")
Arithmetik Jörg Roth 26
■ Ägyptische Zahlen:
= 1, = 10, = 100, = 1 000, = 10 000, = 100 000, = 1 mio
■ Hebräische Zahlen:Verschiedene Ziffern für 1, 2,..9, 10, 20, ...90, 100, 200,... 900
■ Das unäre "Bierdeckelsystem":kennt nur eine Ziffer: I = 1
(man könnte = 5 auch noch als Ziffer interpretieren)
Additionssysteme haben einige Nachteile:
■ Häufig keine Darstellung der Null, keine gebrochenen Zahlen, keine negativen Zahlen
■ Mathematische Operationen sind schwierig
MMCV x XXII = ?
Arithmetik Jörg Roth 27
Stellenwertsysteme:
■ Schon die Maya verwendeten ein Stellenwertsystem, allerdings mit 20 verschiedenen Ziffern
■ Auch Stellenwertsysteme kennen eine Reihe von Ziffern (z.B. 0, 1,... 9), der Wert einer Ziffer hängt aber von der Position innerhalb der Zahl ab
5238 = 51000 + 2100 + 310 + 81
■ Mit Stellenwertsysteme können mathematische Operationen viel einfa-cher berechnet werden als mit AdditionssystemenZ.B. schriftliches Addieren, Subtrahieren, Multiplizieren, Dividieren
■ Die Vorteile Stellenwertsysteme führen dazu, dass diese auch zur Darstel-lung von Zahlen in Rechnern verwendet werden
Arithmetik Jörg Roth 28
Wieviele Ziffern verwendet man?
Das Zweiersystem eignet sich für Computer besonders, da sich die zwei möglichen Ziffern sehr einfach durch zwei Signalpegel darstellen lassen.
Die Mayas zählten mit Händen und Füßen...
...in Europa nur mit den Händen...
...Computer rechnen nur mit zwei Fingern.
Arithmetik Jörg Roth 31
Beispiele für b-adische Entwicklungen:
Darstellungen der Dezimalzahl z = 34
■ b = 5:
z = 152+151+450 (a2 = 1, a1 = 1, a0 = 4)
■ b = 10:
z = 3101+4100 (a1 = 3, a0 = 4)
■ b = 2:
z = 125+ 024+023+022+121+020 (a5 = 1, a4 = 0, a3 = 0, a2 = 0, a1 = 1, a0 = 0)
Arithmetik Jörg Roth 33
Ausführlicherer Beweis zur Existenz und Eindeutigkeit der Division mit Rest:
Existenz:
Existenz heißt: es gibt zu jedem Zahlenpaar z, a ein Zahlenpaar q, r mit
z = qa + r
Wir zeigen die Existenz über die vollständige Induktion nach z:
■ Induktionsanfang: 0z<a: z = 0a+z ist eine Darstellung
■ Induktionsschritt: za und die Aussage sei für Zahlen z’z–a bewiesen, d.h. für z–a existiert schon eine Darstellung qa+r.
Dann existiert für z die Darstellung z = a+qa+r = (q+1)a+r.
Arithmetik Jörg Roth 34
Eindeutigkeit:
Eindeutigkeit heißt: zu jedem Zahlenpaar z, a gibt es nur ein Zahlenpaar q, r mit
z = qa + r
■ Seien z = qa+r und z = qa+r.
Dann gilt 0 = (q–q)a+(r–r) oder
(q–q)a = (r–r), d.h. (r–r) muss durch a teilbar sein.
Für die Differenz (r–r) zweier Zahlen ri mit 0ri<a gilt: 0|r–r|<a.
Die einzige durch a teilbare natürliche Zahl kleiner a ist 0: also ist (r–r) = 0 damit r = rund schließlich q = q.
Arithmetik Jörg Roth 36
Zurück zur b-adischen Entwicklung (Satz 1.1): Zu zeigen ist immer noch: eine Zahl z ist auf genau eine Weise als b-adische Entwicklung darstellbar.
Existenz der Darstellung:
z = q1b + r0
(Darstellung existiert, Überlegungen siehe oben)
q1 = q2b + r1
q2 = q3b + r2
...
qn-1 = 0b + rn-1
Damit ist
z = (((rn-1)...)b + r2)b + r1)b + r0 = rn-1bn-1 +...+ r1b
1 + r0b0 =
eine b-adische Entwicklung
ribi
i 0=
n 1–
Arithmetik Jörg Roth 37
Beispiele für die Existenz der b-adischen Darstellung.
■ b = 10, z = 345
345 = 3410+5
34 = 310+4
3 = 010+3
also: a0 = r0 = 5, a1 = r1 = 4, a2= r2 = 3
■ b = 2, z = 10
10 = 52+0
5 = 22+1
2 = 12+0
1 = 02+1
also: a0 = r0 = 0, a1 = r1 = 1, a2= r2 = 0, a3= r3 = 1
Arithmetik Jörg Roth 40
Alternativer Beweis zur Eindeutigkeit der b-adischen Darstellung
Seien z= und z= zwei Darstellungen von z.
Es gilt =(...((an-1)b+an-2)b+...a1)b+a0
und =(...((a’m-1)b+a’m-2)b+...a’1)b+a’0
Aus Satz 1.2 wissen wir, dass eine Zahl z = qb+a auf genau eine Weise durch q und a darstellbar ist, damit a0 = a’0
sowie (...((an-1)b+an-2)b+...a1 = (...((a’n-1)b+a’n-2)b+...a’1
durch wiederholte Anwendung erhält man ai = a’i
aibi
i 0=
n 1–
a'ibi
i 0=
m 1–
aibi
i 0=
n 1–
a'ibi
i 0=
m 1–
Arithmetik Jörg Roth 42
Schreibweisen zu den vorgenannten Beispielen:
■ (34)10 = (114)5
■ (34)10 =(100010)2
■ (10)10=(1010)2
Weitere Beispiele:■ (AFFE)16 = (45054)10
■ (F)16 = (15)10=(1111)2
Arithmetik Jörg Roth 44
Beispiele:
■ Der maximale Wert einer 10-adischen Zahl der Länge 3 ist
103–1 = 999
■ Der maximale Wert einer 2-adischen Zahl der Länge 8 ist
28–1 = 255 =(11111111)2
Arithmetik Jörg Roth 50
Beispiele: b = 2
Bemerkung. üi1, i = -1,...,N-1. Insbesondere eN1
Vereinfachungen für b = 2:
■ ei = 1 wenn die Anzahl der 1en in ci, di, üi-1 ungerade ist
■ üi = 1 wenn die Anzahl der 1en in ci, di, üi-1 größer oder gleich 2 ist
ci
00001111
di
00110011
üi-1
01010101
üi
00010111
ei
01101001
101101011101111
111111110
100100100
ci
di
üi-1
ei
i=0i=N
Arithmetik Jörg Roth 51
b = 3
ci
0000001111…2
di
0011220011…2
üi-1
0101010101…1
üi
0000010001…1
ei
0112201220…2
11021222
01110
12020
ci
di
üi-1
ei
i=0i=N
Arithmetik Jörg Roth 53
Beispiel. b = 2
Besonderheiten im Binärsystem:
■ Aus üi-1 = 0 folgt üi = 0. Da ü-1=0 gilt üi = 0 für alle i.
■ Da z {0, 1} vereinfacht sich cz zu cz =
101101 1001
101101000
101101
110010101
c d
c d3 b3
c d0 111
ci0011
z0101
üi-10000
üi0000
vi0001
c für z 1=
0 für z 0=
Arithmetik Jörg Roth 54
b = 3
Bemerkung. Der Übertrag üi kann auch größer als 1 sein: Z.B. bei b = 10: üi {0, 1, ... 8}. (Ohne Beweis: allgemein gilt: üi {0,... b-2} )
221 12
2210
1212
11122
c d
c d1 b1
c d0 11
ci
00**11112222
z**0011221122
üi-1
010101010101
üi
000000010111
vi
010112202012
11ü2
Arithmetik Jörg Roth 56
Exkurs: Relation, Äquivalenzrelation
Sei M eine Menge
■ heißt (zweistellige) Relation auf M
■ Eine Relation R auf M heißt Äquivalenzrelation, wenn für gilt
• (Reflexivität)
• (Symmetrie)
• und (Transitivität)
Schreibweise für
■ heißt Äquivalenzklasse von x
■ heißt Menge der Äquivalenzklassen von ~
R M M
x y z M
x x Rx y R y x R
x y R y z R x z Rx y x y R
x x y M x y := :=
M ~ x x M :=
Arithmetik Jörg Roth 58
Beispiele zu Äquivalenzklassen in Restklassenringen:
■ In /3 gilt
• 7~1 denn 7-1 ist durch 3 teilbar• Schreibweisen: 7 mod 3 = 1 mod 3
aber auch 7 = 1 mod 3oft auch 7 1 mod 3
■ In /3 gibt es 3 verschiedene Äquivalenzklassen
• [0] = {..., -9, -6, -3, 0, 3, 6, 9,...}• [1] = {..., -8, -5, -2, 1, 4, 7, 10,...}
• [2] = {..., -7, -4, -1, 2, 5, 8, 11,...}
■ In /3 gilt
• [-9] = [-6] = [-3] = [0] = [3] = [6] = [9] ...• [-8] = [-5] = [-2] = [1] = [4] = [7] = [10] ...
• [-7] = [-4] = [-1] = [2] = [5] = [8] = [11] ...
Arithmetik Jörg Roth 60
Beispiel.
123456789 123456789 mod 10 = ?
(123456789 mod 10) (123456789 mod 10) mod 10 =
9 9 mod 10 = 81 mod 10 = 1
Bemerkung:
123456789 123456789 mod 10= 15241578750190521 mod 10 = 1
lässt sich mit den meisten Taschenrechnern nicht ausrechnen
Arithmetik Jörg Roth 64
Beispiele zur Addition mod bN–1
b = 10, N = 3
4 5 56 5 5
1 1 011
1 1 1
111
9 9 99 9 9
9 9 811
9 9 9
111
9 9 80 1 1
0 0 911
0 1 0
11
1
Arithmetik Jörg Roth 66
Beispiele zur Komplementbildung:
In /3 gilt
■ K([0]) = [0]
■ K([1]) = [2]
■ K([2]) = [1]
Ausrechnen von [6]–[2] in /10:
■ [6]–[2] = [6]+K([2]) = [6]+[8] = [4]
■ Anders ausgedrückt: 6–2 mod 10 = 6+(10–2) mod 10 = 6+8 mod 10 = 4 mod 10
Arithmetik Jörg Roth 67
b- und (b-1)-Komplement-Bildung
Wir wollen für die Fälle n = bN und n = bN–1 die Komplementbildung ver-einfachen.
Sei a = Wir definieren ai = (b–1)–ai
Sei weiter a = . Dann ist a das Komplement von a bezüglich bN–1
denn a+a = = bN–1
Damit ist (a+1) das Komplement von a bezüglich bN
denn a + (a+1) = bN
■ a heißt das (b–1)-Komplement von a
■ (a+1) heißt das b-Komplement von a
aibi
i 0=
N 1–
aibi
i 0=
N 1–
b 1– bi
i 0=
N 1–
Arithmetik Jörg Roth 68
Bemerkung.
■ Das (b–1)-Komplement der 0 ist (b–1...b–1). Daher sind (0...0) und (b–1...b–1) zwei Darstellungen der 0
■ Das b-Komplement der 0 ist (0...0), d.h. hier gibt es nur eine Darstellung der 0
Beispiele.
b = 10, N = 3
a = 345
a = 654
654 ist das 9er-Komplement von 345
(654+1) = 655 ist das 10er-Komplement von 345
ai ai
0 9
1 8
2 7
3 6
4 5
5 4
6 3
7 2
8 1
9 0
Arithmetik Jörg Roth 69
b = 2, N = 4
a = 0010
a = 1101
1101 ist das 1er-Komplement von 0010
(1101+1) = 1110 ist das 2er-Komplement von 0010
ai ai
0 1
1 0
Arithmetik Jörg Roth 70
Rechenbeispiele.
b = 10, N = 3, wir rechnen mod bN–1:
■ Verwendung des 9er-Komplements
■ Addition mod bN–1, d.h. mit Einerrücklauf
654–123 = ?
Das 9er-Komplement von 123 ist 876
654
+ 876
1530
= 531 (Einerrücklauf)
Arithmetik Jörg Roth 71
b = 10, N = 3, wir rechnen mod bN:
■ Verwendung des 10er-Komplements
■ Addition mod bN, d.h. wir ignorieren eN
654–123 = ?
Das 10er-Komplement von 123 ist 877
654
+ 877
1531
= 531 (ignorieren von eN)
Arithmetik Jörg Roth 72
b = 2, N = 4, wir rechnen mod bN:
■ Verwendung des 2er-Komplements
■ Addition mod bN, d.h. wir ignorieren eN
0101–0010 = ?
Das 2er-Komplement von 0010 ist 1110
0101
+ 1110
10011
= 0011 (ignorieren von eN)
Arithmetik Jörg Roth 75
Beispiel (Darstellung mit Vorzeichen und Betrag).
b = 2, Betrag mit 2 Stellen
Bitfolge Wert
000 0
001 1
010 2
011 3
100 0
101 -1
110 -2
111 -3
Arithmetik Jörg Roth 76
Bemerkung.
Bei der Addition und Subtraktion ergeben sich für jede Kombination der Vorzeichen eigene Berechnungswege.
Berechnung von e = a + b, für z bezeichne z.VZ Vorzeichen, z.B Betrag
+ a.VZ=0 a.VZ=1
b.VZ=0 e.VZ=0e.B=a.B+b.B e.VZ=
e.B=|a.B–b.B|
b.VZ=1e.VZ=
e.B=|a.B–b.B|
e.VZ=1e.B=a.B+b.B
1 a.B b.B0 a.B b.B
1 b.B a.B0 b.B a.B
Arithmetik Jörg Roth 77
Die Multiplikation ist jedoch sehr einfach
f = a b
f.VZ=
f.B=a.B b.B
Die Berechnung des Vorzeichens lässt sich später auf die logische Operation Exklusiv-Oder zurückführen
0 für a.VZ b.VZ=
1 sonst
Arithmetik Jörg Roth 78
1.2.2 Exzessdarstellung
Wir stellen positive ganze Zahlen b-adisch dar. Um den Wert einer Darstel-lung zu erhalten, ziehen wir einen konstanten Wert (Exzess) ab.Also:
Mit
■ z: der Wert einer Zahl
■ (aN-1...a0): die b-adische Darstellung einer positiven Zahl
■ -Exzess: der kleineste (negative) Wert
Beispiele: b=2, N=3, Exzess=2:
■ a=101 hat den Wert z=5-2=3
■ a=001 hat den Wert z=1-2=-1
z aibi
Exzess–i 0=
N 1–
=
Arithmetik Jörg Roth 81
Bemerkung.
Bei der Addition von zwei Zahlen hat man Exzess zwei mal addiert.
Berechnung von e = a + b, ex bezeichne den Exzess
In der Exzess-Darstellung berechnet man
(a + ex) + (b + ex) = (a + b) +2ex = (e + ex) + ex
Um die Darstellung (e + ex) zu erhalten, müssen wir ex abziehen.
Spezialfall ex=2N-1
In der Binärdarstellung und bei der Wahl von ex = 2N-1 entspricht der Exzess dem höchstwertigsten Bit. Das Abziehen von ex mod 2N entspricht dem Umkehren des höchstwertigsten Bits 01.
Beispiele. –1 011 –3 001
(N=3) + 2 110 + 2 110
= 001 = 111
–ex = 101 (= 1) –ex = 011 (= –1)
Arithmetik Jörg Roth 82
Multiplikation von Exzess-ZahlenIn der Regel ist es aufwändig, in der Exzess-Darstellung zu multiplizieren
Spezialfall ex=2N-1
(a+ex).(b+ex) mod 2N
= ex2 + ex(a+b) + a.b mod 2N
= 0 + ex(a+b) + a.b mod 2N
D.h. man multipliziert (a+ex).(b+ex) und addiert ex, falls a+b=0 mod 2.Beispiel N=8 damit ex=128, a.b=-15.5 = ?
Wir rechnen 0111 0001 . 1000 0101 = 1011 0101 (b-adisch)
da a+b=0 mod 2 addieren wir ex (d.h. wir invertieren das vorderste Bit)
damit lautetet das Ergebnis 0011 0101 mit dem Wert -75
ex a b+ wenn a b+ 1 mod 2=
a b sonst
=
Arithmetik Jörg Roth 86
Beispiele für Zweierkomplement-Darstellungen.
Binärzahlen mit 3 Stellen:
Bitfolge Wert
000 0
001 1
010 2
011 3
100 -4
101 -3
110 -2
111 -1
Arithmetik Jörg Roth 87
Binärzahlen mit 8 Stellen:
01001001 stellt 73 dar
11001001 stellt -55 dar, denn K(11001001) = 00110110 + 1 = 55
Bitfolge Wert
0000 0000 0
0000 0001 1
0000 0010 2
... ...
0111 1111 127
1000 0000 -128
... ...
1111 1110 -2
1111 1111 -1
Arithmetik Jörg Roth 90
1.2.4 Einerkomplement-Darstellung
Arithmetik Jörg Roth 91
Bemerkung: in der Einerkomplementdarstellung ist bei der Multiplikation eine Korrektur erforderlich. Grund: die Darstellung für z<0 lautet
2N–1+z = z–1 mod 2N
Arithmetik Jörg Roth 92
Beispiele für Einerkomplement-Darstellungen.
Binärzahlen mit 3 Stellen:
Bitfolge Wert
000 0
001 1
010 2
011 3
100 -3
101 -2
110 -1
111 0
Arithmetik Jörg Roth 93
Binärzahlen mit 8 Stellen:
01001001 stellt 73 dar.
11001001 stellt -54 dar, denn K(11001001) = 00110110 = 54
Bitfolge Wert
0000 0000 0
0000 0001 1
0000 0010 2
... ...
0111 1111 127
1000 0000 -127
... ...
1111 1110 -1
1111 1111 0
Arithmetik Jörg Roth 98
Vorüberlegung zur Erkennung von Bereichsüberschreitungen
Es gilt eN = üN-1
Weiter gilt cN-1+dN-1+üN-2 = (eN eN-1)b = eN 2 + eN-1 = üN-1 2 + eN-1
cN-1 cN-2 c0...dN-1 dN-2 d0...üN-2 ü-1üN-1
eN-1 eN-2 e0...eN
Ergebnis
Vorzeichen von c, d
Vorzeichen des Ergebnisses
Erkennen der Bereichs-
überschreitung...
Arithmetik Jörg Roth 99
Beweis.
Wir unterscheiden zwei Fälle
1. Fall: cs und ds besitzen verschiedene Vorzeichen (cN-1dN-1):
Das Resultat ist dem Betrag nach kleiner oder gleich dem größten der beiden Summanden und deshalb immer darstellbar. Es gilt nämlich
|cs+ds|=max(|cs|,|ds|)–min(|cs|,|ds|), d.h. 0|cs+ds|max(|cs|,|ds|)
Bereichsüberschreitungen treten also nicht auf.
Wegen cN-1dN-1=1 gilt üN-2=1 üN-1=1 also üN-2=üN-1
1 cN-2 c0...0 dN-2 d0...
üN-2 ü-1üN-1
eN-1 eN-2 e0...eN
1000
10
...
...
...
...
üN-2=0
1011
01
...
...
...
...
üN-2=1
...
Arithmetik Jörg Roth 100
2. Fall: cs und ds besitzen gleiche Vorzeichen (cN-1dN-1):
Es gilt
(eN eN-1)b = (üN-1 eN-1)b = cN-1+dN-1+üN-2 = 2cN-1+üN-2 = (cN-1 üN-2)b
somit üN-1 = cN-1 und eN-1 = üN-2
Es findet keine Bereichsüberschreitung statt, wenn das Resultat dasselbe Vorzeichen besitzt wie die Summanden, d.h. eN-1 = cN-1
Aus üN-1 = cN-1, eN-1 = üN-2 folgt eN-1 = cN-1 üN-1 = üN-2
cN-2 c0...dN-2 d0...
üN-2 ü-1üN-1
eN-1 eN-2 e0...eN
0000
00
...
...
...
...
cN-1=0
1111
11
...
...
...
...
cN-1=1
cN-1
dN-1
...
Arithmetik Jörg Roth 104
Bemerkung.
Es gilt
=
Damit ergibt sich für zi = 0 für i>0 gerade die b-adische Darstellung natürli-cher Zahlen.
zi 1 b i
i m–=
z i– bi
i m=
–
Arithmetik Jörg Roth 105
Bemerkung.
Es gibt Eigenschaften, die unabhängig von einer gewählten Darstellung sind z.B.
■ eine Zahl ist eine Primzahl,
■ eine Zahl hat eine unendliche, nicht-periodische b-adische Entwicklung,
(z.B. hat in jeder Darstellung unendlich viele Ziffern)
■ eine Zahl ist gerade.
Andere Eigenschaften sind von der Darstellung abhängig, z.B.
■ eine Zahl hat eine periodische oder abbrechende b-adische Entwicklung,(z.B. 1/3 = (0.33333....)10 = (0.1)3 )
■ die Quersumme einer Zahl ist gerade.
Zwischen den Begriffen Zahl und Darstellung einer Zahl ist deshalb sorgfäl-tig zu unterscheiden.
2
Arithmetik Jörg Roth 112
Beispiele zur Umrechnung im Quellsystem:
Z1 = [0.2 . 2] = [0.4] = 0
z = (0.2)10 = (0.Z1Z2Z3...)2
Z2 = [0.4 . 2] = [0.8] = 0
Z3 = [0.8 . 2] = [1.6] = 1
Z4 = [0.6 . 2] = [1.2] = 1
Z5 = [0.2 . 2] = [0.4] = 0
{}
{}
{}
{}
z = (0.0011)2
Z1 = [0.85 . 3] = [2.55] = 2
z = (0.85)10 = (0.Z1Z2Z3...)3
Z2 = [0.55 . 3] = [1.65] = 1
Z3 = [0.65 . 3] = [1.95] = 1
Z4 = [0.95 . 3] = [2.85] = 2
Z5 = [0.85 . 3] = [2.55] = 2
{}
{}
{}
{}
z = (0.2112)3
Arithmetik Jörg Roth 114
Bemerkung.
Alle Brüche im 10er-System sind im Binärsystem nicht durch eine
abbrechende Entwicklung darstellbar. Z.B. (0.1)10 = (0.00011)2
Muss man aber sehr exakt mit Zehntel und Hundertstel etc. rechnen (z.B. im Bankwesen) gibt es folgende Alternativen:
■ Alternative 1: Man spendiert so viele Stellen hinter dem Komma, dass bei allen denkbaren Rechenoperationen (mit allen denkbaren Zahlen) nach dem Runden der exakte erwartete Betrag resultiert.
■ Alternative 2: Man stellt Werte im 10er-System dar und stellt Algorith-men zur Verfügung, um ziffernweise im 10er-System zu rechnen.Beispiel BCD-Darstellung (Binär-codierte Dezimalzahl):Man stellt jede Dezimalziffer einzeln binär dar:
1
10i
-------
Arithmetik Jörg Roth 115
0: 0000 1: 0001 ... 9: 1001Man stellt die 4-Bit-Kombination zu den Ziffern hintereinander dar, d.h. man erhält pro Byte 2 Ziffern: z.B.
1845 wird in BCD dargestellt als 0001 1000 0100 0101Zum Rechnen benötigen wir dann ziffernweise arbeitende Verfahren.
■ Alternative 3: Man bestimmt die kleinste darzustellende Einheit und ver-schiebt das Komma solange nach rechts, bis man wieder nur noch mit ganzen Zahlen rechnet.Beispielsweise könnte man statt in Euro auch in Cent rechnen und erhält dadurch ganze Zahlen. Die Darstellung ist damit exakt.
Arithmetik Jörg Roth 121
Bemerkung zur Verschiebung des Kommas.
Ist B=bk und wird der Exponent um 1 kleiner, verschiebt sich das Komma um k nach rechts.
Beispiele:
b = 2, B = 8, d.h. B = b3
0.000001011 83 = 0.001011 82 = 1.011 81
b = 10, B = 100, d.h. B = b2
0.002006 100-4 = 0.2006 100-5 = 20.06 100-6
Die Darstellungen in der Mitte sind jeweils normalisiert.
Arithmetik Jörg Roth 124
Bemerkung zur Wahl von B.
■ Wahl eines größeren B: Bei einer festen Stellenzahl für Exponenten wird die Spanne zwischen der größten und kleinsten positiven Zahl größer (analog auch für negative Zahlen).
■ Wahl eines kleineren B: Bei einer festen Stellenzahl für Mantissen werden die verfügbaren Stellen im Mittel besser ausgenutzt, d.h. weniger mit 0en gefüllt. Die Genauigkeit der Darstellung ist daher im Mittel größer.
Arithmetik Jörg Roth 129
IEEE-Format zur Darstellung von Gleitkommazahlen.IEEE Standard 754 1985
■ In der Norm IEEE 754 werden Grunddatenformate für binäre Gleitkom-mazahlen dargestellt und genaue Verfahren für die Durchführung mathe-matischer Operationen festgelegt.
■ Implementiert von Intel-, Motorola-, SPARC- und MIPS-Prozessoren
■ Implementiert durch das Java-Laufzeitsystem
■ Der Standard beinhaltet "single precision"- (32 Bit) und "double precis-ion"-Format (64 Bit).
Allgemeines Format:
■ z =
■ Normalisieren heißt, . Die "1." wird nicht gespeichert
■ Kleine Zahlen werden nicht-normalisiert gespeichert
1. m1m2mn 2e
1 m 2
Arithmetik Jörg Roth 131
Codierungen:
Darstellungen Bemerkung Codierung
Normalisiert e>0...0, e<1...1
Nichtnormalisiert Für kleine Zahlen, die nicht mehr normalisiert werden kön-nen
e=0...0
Null Es gibt zwei Darstellungen der Null (+0, -0)
e=0...0, m=0...0VZ beliebig
Infinite/-Infinite Z.B. Ergebnis von 1/0 oder -1/0; begrenztes Weiterrechnen möglich
e=1...1, m=0...0VZ=0: +VZ=1: -
Not a Number (NaN)
Z.B. Ergebnis von e=1...1, m0...0VZ beliebig
1–
Arithmetik Jörg Roth 134
Erklärung der darstellbaren Zahlen am Beispiel von single precision:nicht-normalisiert normalisiert
kleinste (pos)darstellbare
Zahl
m = 0.00...0001 = 2-23
e = 00..000 = -126
z = 2-23.2-126 = 2-149
m = 1.00...00 = 1e = 00..001 = -126
z = 1.2-126 = 2-126
größtedarstellbare
Zahl
m = 0.11...11 1e = 00..000 = -126
z 1.2-126 = 2-126
m = 1.11...11 2e = 11..110 = 254-127 = 127
z 2.2127 = 2128
Genauigkeit(kleinster Wert)
aufeinanderfolgende Zahlen:m1 = 0.**...***0 m2 = 0.**...***1
m2-m1 = 2-23
e1 = e2 = 00..000 = -126
z2-z1 = 2-23.2-126 = 2-149
m2-m1 = 2-23
e1 = e2 = 00..001 = -126
z2-z1 = 2-23.2-126 = 2-149
Genauigkeit(größter Wert)
m2-m1 = 2-23
e1 = e2 = 11..110 = 127
z2-z1 = 2-23.2127 = 2104
Arithmetik Jörg Roth 135
Zusammenfassung zu Kapitel 1
Was haben wir erreicht?
■ Ganze Zahlen:
• Darstellen in verschiedenen Zahlensystemen• Umrechnen zwischen verschiedenen Zahlensystemen
• Umgehen mit Vorzeichen (Exzess, Vorzeichen/Betrag, b-Komplement, b–1-Komplement)
• Realisierung der Grundrechenarten
• Wir können (im Spezialfall 2er-Komplement) einen Überlauf erkennen
■ Reelle Zahlen:
• Darstellen in verschiedenen Zahlensystemen• Umrechnen zwischen verschiedenen Zahlensystemen
• Festkomma vs. Gleitkomma, Betrachtung der Genauigkeiten
• Normalisierung einer Gleitkomma-Zahl
2 SchaltungenMotiviation
Transistoren
Gatter
Register undMikroprogramm
Assembler undMaschinenprogramm
HöhereProgrammiersprache
lw $t0, alw $t1, badd $t0, $t0, $t1add $t0, $t0, $t1sw $t0, a
& >1
&
& Kap 2
int a=1, b=2;a = a+2*b;
Schaltungen Jörg Roth 137
Ebene der Gatter:
■ Es gibt nur Bits und Operationen auf Bits
■ Typische Operation: Die AND-Verknüpfung:wenn Eingang1=1 UND Eingang2=1 dann Ausgang=1 (und nur dann)
Wichtige Themen der Gatter-Ebene:
■ Gatter bilden formal so genannte boolsche Algebren ab.
■ Boolsche Funktionen sollten mit möglichst wenigen Gattern dargestellt werden
• Platzersparnis auf Chips• Geringere Energieaufnahme und Wärmeentwicklung
• Geringer Schaltzeiten
=> das Karnaugh-Veitch-Verfahren ermöglicht die Vereinfachung von Gatter-Schaltungen
&
Schaltungen Jörg Roth 138
■ Durch Zusammenschaltung von Gattern können komplexere Funktionen realisiert werden, z.B.:
• Addition von Binärzahlen• Multiplexer (Auswahl eines Eingangs anhand einer Eingangsnummer
und Schalten auf den Ausgang)
• Decoder (Aktivieren eines Ausgangs anhand einer Ausgangsnummer)
■ Durch Rückkopplung der Ausgänge auf die Eingänge können Zustände gespeichert werden=> Flipflops
Schaltungen Jörg Roth 141
Beispiele:
1. Sei X eine Menge, P(X) := {Y | YX}) die Potenzmenge von X. (P, , ) ist eine boolsche Algebra.
Das 0-Element: {}
Das 1-Element: X
X
a
Xa
X
a b
X
a b
X
a b
Schaltungen Jörg Roth 143
3. Aussagenlogik
Sei A die Menge der Aussagen. In A enthalten sind z.B.:
■ a1: "Nürnberg ist eine Großstadt"
■ a2: "Wenn es regnet gibt es immer einen Regenbogen"
■ a3: "5 ist eine Primzahl"
Wir ordnen jeder Aussage einen Wahrheitswert wahr oder falsch zu:
■ w(a1) = wahr
■ w(a2) = falsch
■ w(a3) = wahr
Schaltungen Jörg Roth 144
Seien ai, aj zwei Aussagen. Dann können wir neue Aussagen konstruieren:
■ und-Verknüpfung: ai und aj z.B. "Nürnberg ist eine Großstadt und wenn
es regnet gibt es immer einen Regenbogen"
■ oder-Verknüpfung: ai oder aj z.B. "Nürnberg ist eine Großstadt oder wenn
es regnet gibt es immer einen Regenbogen"
Es gilt:
■ w(ai und aj ) = w(ai) w(aj)
■ w(ai oder aj ) = w(ai) w(aj)
■ Die 1 ist die immer wahre Aussage "wahr"
■ Die 0 ist die immer falsche Aussage "falsch"
(A, oder, und) ist eine boolsche Algebra.
Schaltungen Jörg Roth 150
Decodierer, Multiplexer, Demultiplexer
8 zu 1Multiplexer
i0
i7
...
c0c1c2
3 zu 8Decoder
c0c1c2
d0
d7
...
1 zu 8Demulti-plexer
c0c1c2
d0
d7
...
Schaltungen Jörg Roth 154
Darstellung als Wahrheitstabelle.
Beispiel: f2 (Inhibition)
Es gilt: f2(x, y) =
Bemerkung: bei y=1 wird die Durchschaltung von x verhindert, daher der Name "Inhibition"
x y f2(x, y)
0 0 0
0 1 0
1 0 1
1 1 0
x für y 0=
0 sonst
Schaltungen Jörg Roth 161
Beispiele für Minterme und Maxterme:
Sei n = 3.
i (i)2 Minterm mi Maxterm Mi
0 000 x1x2x3 x1x2x3
1 001 x1x2x3 x1x2x3
2 010 x1x2x3 x1x2x3
3 011 x1x2x3 x1x2x3
4 100 x1x2x3 x1x2x3
5 101 x1x2x3 x1x2x3
6 110 x1x2x3 x1x2x3
7 111 x1x2x3 x1x2x3
Schaltungen Jörg Roth 163
Beispiel.
Sei n = 3
m3: B3 B, (x1, x2, x3) x1x2x3
...
m3(0, 1, 0) = 0 (j=2)
m3(0, 1, 1) = 1 (j=3)
m3(1, 0, 0) = 0 (j=4)
...
M3: B3 B, (x1, x2, x3) x1x2x3
...
M3(0, 1, 0) = 1 (j=2)
M3(0, 1, 1) = 0 (j=3)
M3(1, 0, 0) = 1 (j=4)
...
Schaltungen Jörg Roth 165
Beispiel.
Sei n = 3
Sei f(x1, x2, x3) =
Dann ist If = {0, 7}
1 falls x1 x2 x3= =
0 sonst
Schaltungen Jörg Roth 167
Beispiel.
Sei n = 3
Sei f(x1, x2, x3) =
Dann ist
f(x1, x2, x3) = x1x2x3+x1x2x3
die disjunktive Normalform und
f(x1, x2, x3) = (x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)
die konjunktive Normalform.
1 falls x1 x2 x3= =
0 sonst
Schaltungen Jörg Roth 168
Beweis.
Existenz der DNF. Sei jBn.
f(j) = 1 jIf = = +mj(j) = 0 + 1 = 1
Eindeutigkeit der DNF.
Sei , J{0,..., 2n–1} eine weitere DNF-Darstellung von f.
Wegen kIf f(k) = 1 (k) = 1 kJ folgt J = If.
i If mi j
i If mi j
i If\ j mi j
i J mi
i J mi
Schaltungen Jörg Roth 170
Gatter (Symbole nach IEC 60617-12)
AND, NAND, OR und NOR können auch mehr als zwei Eingänge besitzen.
&&
>1>1
=1=1
Inverter (NOT-Gatter)
E01
A10
E1 E2
0 00 11 01 1
A0001
E1 E2
0 00 11 01 1
A0111
E1 E2
0 00 11 01 1
A1110
E1 E2
0 00 11 01 1
A1000
E1 E2
0 00 11 01 1
A0110
E1 E2
0 00 11 01 1
A1001
AND-Gatter
OR-Gatter
1
NAND-Gatter
NOR-Gatter
XOR-Gatter XNOR-Gatter
Schaltungen Jörg Roth 171
Realisierung logischer Funktionen als SchaltkreiseBeispiel TTL (Transistor-Transistor-Logik)
Schaltungen Jörg Roth 172
Regeln für die Darstellung von Schaltnetzen mit Gattern■ Inverter können explizit als Gatter oder nur als offenen Punkt dargestellt
werden. Im letzten Fall wird der offene Punkt an das Kästchen eines anderen Gatters gezeichnet.
■ Durchgezogene Linien verbinden Ausgänge mit Eingängen. Ein Ausgang kann mir mehreren Eingängen verbunden werden. Mehrere Ausgänge dürfen nicht zusammengeschaltet werden.
■ Verzweigt eine Linie, kann diese zur besseren Lesbarkeit mit einem geschlossenen Punkt gekennzeichnet werden (kein Inverter). Für verbun-dene Kreuzungen ist der Punkt zwingend erforderlich.
&1
&=
= =verbunden nicht verbunden verbundenverbunden
Schaltungen Jörg Roth 174
Realisierung von Gattern mit NAND- und NOR-Gattern
&
&
>11
&&>1
>1>1
&&
1
&
&&
0
>1
>1>1
>1
xxx x+x
xy
(xy)(xy)
(xy) 1
(x+y)+(x+y)
(x+y)+0
(x+x)+(y+y)
(xx)(yy)
Gatter Darstellung mit NAND Darstellung mit NOR
x+y
>1
Schaltungen Jörg Roth 176
Schaltung des Halbaddierers:
&>1
&
&
x y
s
u
Schaltungen Jörg Roth 178
Schaltung des Volladdierers:
&
>1
&
y u
s
x
&
&
>1
& &
>1
&
&
&
>1
>1 u
Schaltungen Jörg Roth 180
Schaltung des 2 zu 4 Decodierers:
&
&
&
i1 i0
a2
a0
a1
& a3
Schaltungen Jörg Roth 182
Schaltung des 4 zu 1 Multiplexers:
&
&
&
c1 c0
i2
i0
i1
&i3
>1 a
Schaltungen Jörg Roth 183
2.1.4 Vereinfachung von Schaltungen
Beispiele:
1. f(x1, x2, x3) = x1x2x3+x1x2x3 = (x1+x1)x2x3 = x2x3
2. f(x1, x2, x3, x4) = x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4
= x1x2x4+x1x2x4+x1x3x4
= x2x4+x1x3x4
Beobachtung: Wir können zusammenfassen, wenn
■ sich zwei Terme an genau einer Stelle unterscheiden: (xi+xi)(...) = (...)
■ sich vier Terme an genau zwei Stellen unterscheiden und alle Kombinati-onen der zwei Variablen vorkommen: (xixj+xixj+xixj+xixj)(...) = (...)
■ sich acht Terme an genau drei Stellen unterscheiden...
Schaltungen Jörg Roth 186
Eine andere Darstellung von KV-Diagrammen
Wir markieren solche Felder mit "1", bei denen die Funktion eine 1 liefert. Z.B. für f(x1, x2, x3) = + + +
x4
x2
x1
x3
x2
x1
x3
x2
x1x1
x1x3 x1x3 x1x2x3 x1x2x3
1
11
1
11x2
x1
x3
Schaltungen Jörg Roth 187
Für dieses Beispiel kann man nun folgende Vereinfachung durchführen:
Damit f(x1, x2, x3) = +
1
11
1
11x2
x1
x3
x1 x2
Schaltungen Jörg Roth 188
Weiteres Beispiel.
Sei
f(x1, x2, x3) =
Damit f(x1, x2, x3) = + +
1 wenn x1 x2 x3 oder x= = 1x3 oder x1 x3
0 sonst
11
11
1
1
1
x2
x1
x3
x1 x2 x3
Schaltungen Jörg Roth 189
Beispiele möglicher Minimierungen:
■ 8fach-Felder:
■ 4fach-Felder:
1
1
1
1
1 1
11x4
x2
x1
x3
1
1
1
1
1 1
11x4
x2
x1
x3
1 1 1 1
1111x4
x2
x1
x3
x1 x1 x4
11
1 1x4
x2
x1
x3
1
1
1
1x4
x2
x1
x3
1 1
11x4
x2
x1
x3
x1x2 x1x3
11
11x4
x2
x1
x3
x1x4 x1x2
Schaltungen Jörg Roth 190
■ 2fach-Felder:
Wichtig: immer möglichst große Blöcke bilden, auch wenn sich mehrfache Überlappungen ergeben:
1
1x4
x2
x1
x3
11x4
x2
x1
x3
11
x4
x2
x1
x3
x1x3x4 x2x3x4 x1x2x4
11
11
1
1
1
1 1
1111x4
x2
x1
x3
11
11
1
1
1
1 1
1111x4
x2
x1
x3
Schaltungen Jörg Roth 191
Beispiele:
1. f(x1, x2, x3, x4) =
+ + + + +
f(x1, x2, x3, x4) = + +
x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4
111
1 1 1x4
x2
x1
x3
x1x2 x2x3x4 x2x3x4
Schaltungen Jörg Roth 192
2. f(x1, x2, x3, x4) =
+ + +
+ + + +
f(x1, x2, x3, x4) = +
x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4
x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4
1
11
1
1 1
11x4
x2
x1
x3
x1x2 x1x2
Schaltungen Jörg Roth 193
Beispiel mit fünf boolschen Variablen.
f(x1, x2, x3, x4, x5) = + +
1
1
1
1
1
1
111x4
x2
x1
x3
11
1
1
1
1
111
x1
x5
x2x3 x1x4 x1x3
Schaltungen Jörg Roth 194
Weiteres Beispiel.
f(x1, x2, x3, x4, x5) = + + + + +
Bemerkung. KV-Diagramme mit mehr als fünf Variablen sind für Men-schen nur noch schwer lesbar
1
1
1
1
1
1
1 1
111x4
x2
x1
x3
11
1
1
1
1
1
1
1111
x1
x5
x3x5 x1x4 x1x2 x2x5 x3x4x5 x1x3x5
Schaltungen Jörg Roth 196
Beispiel.
Die Don’t Care-Terme seien durch "*" dargestellt
(x1, x2, x3, x4) = +
**
1
11
1 * 1 1
**x4
x2
x1
x3
f̃ x2 x1x3
Schaltungen Jörg Roth 197
Weiteres Beispiel.
(x1, x2, x3, x4) = +
*
*
1*
1
1 1
**x4
x2
x1
x3
f̃ x1x2 x2x3x4
Schaltungen Jörg Roth 205
2.2.2 Flipflops
Flipflops sind einfache rückgekoppelte Schaltungen, die jeweils ein einzel-nes Bit speichern können. Es gibt verschiedene Typen, die sich im "Kom-fort" der Ansteuerung unterscheiden.
Einfache Flipflops:
>1
>1 &
&z1
z2=z1
z1
z2=z1
e1
e2
e1
e2
Schaltungen Jörg Roth 206
Funktionsweise eines einfachen Flipflop (am Beispiel der NAND-Variante):
■ Man kann ein Bit speichern, indem man Verlauf 101 an dem jeweili-gen Eingang anlegt und den anderen Eingang auf 1 setzt
Nachteile:
■ das Speichern wird durch einen Signalverlauf 101 an einem Eingang durchgeführt, währenddessen muss der zweite Eingang auf 1 bleiben. Das ist ein kompliziertes Verfahren.
■ Durch die Eingangsbelegung (0, 0) wird das Speichern verhindert und der Ausgang auf (1, 1) gelegt (illegaler Zustand)
Wunsch:
■ Signalwechsel an einem Takteingang soll zum Speichern führen
■ Es sollen keine illegalen Zustände möglich sein
Schaltungen Jörg Roth 207
Das D-Flipflop (Daten).Schaltung:
Symbol:
&
& z1
z2&
&e
$
y1
y2
z1
z2
e
$
D Q
Q
Schaltungen Jörg Roth 208
Funktionsweise des D-Flipflops:
■ Man kann durch einen Signalverlauf 010 am Takteingang das Bit am Dateneingang speichern
D Q Q (nach Takt) Bemerkung
0 0 00-Bit speichern
0 1 0
1 0 11-Bit speichern
1 1 1
Schaltungen Jörg Roth 209
Vorteile des D-Flipflops:
■ Da nur ein Dateneingang existiert, kann man keine illegale Kombination der Dateneingänge anlegen.
■ Das Einspeichern wird durch einen Takt und nicht durch den Datenein-gang durchgeführt.
Nachteile des D-Flipflops:
■ Solange der Takt auf 1 gesetzt wird, wird der Eingangswert sofort am Ausgang sichtbar.
■ Es muss bei jedem Takt etwas gespeichert werden. Soll der alte Wert erhalten werden, muss er wieder eingespeist werden. Dies ist problema-tisch, wenn man mehrere Speicherzellen über einen zentralen Takt ansteuert.
Schaltungen Jörg Roth 210
Das (R,S)-Flipflop (reset, set).
Schaltung:
Symbol:
z1
z2&
&R
$
y1
y2
S
>1
>1
S Q
R Q
z1
z2
$
R
S
Schaltungen Jörg Roth 211
Funktionsweise des (R,S)-Flipflops:
■ Man kann durch einen Signalverlauf 010 am Takteingang ein 0-Bit oder 1-Bit speichern
■ Die Wahl wird durch zwei separate Dateneingänge durchgeführt: Set: Speichern von 1-Bit, Reset: Speichern von 0-Bit
R S Q Q (nach Takt) Bemerkung
0 0 0 0Zustand halten
0 0 1 1
0 1 0 11-Bit speichern
0 1 1 1
1 0 0 00-Bit speichern
1 0 1 0
1 1 0 zufällignicht erlaubt
1 1 1 zufällig
Schaltungen Jörg Roth 212
Vorteile des (R,S)-Flipflops:
■ Takteingang wie beim D-Flip-Flop
■ Explizites Setzen/Zurücksetzen möglich, zusätzlich durch (Set, Reset)=(0, 0) kann man den alten Zustand erhalten – beim D-Flip-Flop wurde bei jedem Takt gespeichert
Nachteile des (R,S)-Flipflops:
■ Wie beim D-Flip-Flop: bei Takt=1 werden Änderungen an Eingängen sofort an den Ausgängen sichtbar
■ Durch (Set, Reset)=(1, 1) erzeugt man einen nicht vorhersehbaren Folge-zustand
Schaltungen Jörg Roth 213
Das Master-Slave-Flipflop.
Master-Slave-Flipflops bestehen aus zwei Teilflipflops:
■ Der Master speichert den Wert am Eingang zwischen. Der Zwischenge-speicherte Wert wird nicht sofort am Ausgang sichtbar.
■ Der Slave übernimmt den Wert des Masters und gibt ihn an den Ausgang. Damit sind Eingang und Ausgang entkoppelt.
■ Master-Slave-Flipflops können aus je zwei D- oder zwei (R,S)-Flipflops aufgebaut werden.
Takt T
D Q
Q
D Q
Q
1
Master Slave
Schaltungen Jörg Roth 214
Funktionsweise des Master-Slave-Flipflop (aus D-Flipflops):
■ Durch einen Signalverlauf 01 am Takteingang wird der Wert am Daten-eingang in einen Zwischenspeicher (Master) übernommen.
■ Durch einen Signalverlauf 10 am Takteingang wird der zwischenge-speicherte Wert in den Ausgangsspeicher (Slave) übernommen.
Vorteil des Master-Slave-Flipflop:
■ Der Ausgang ist immer stabil. Zu keiner Zeit werden Änderungen des Eingangs sofort am Ausgang sichtbar.
Nachteile des Master-Slave-Flipflop:
■ Aufgebaut aus D-Flipflops: wie beim einfachen D-Flipflop muss bei jedem Takt ein Wert eingespeist werden.
■ Aufgebaut aus RS-Flipflops: wie beim einfachen (R,S)-Flipflop führt die Kombination (R, S) = (1, 1) zu unvorhersehbaren Ergebnissen.
Schaltungen Jörg Roth 215
Das (J,K)-Master-Slave-Flipflop.
Das (J,K)-Master-Slave-Flipflop besteht aus zwei (R,S)-Flipflops und hat an den Dateneingängen zwei AND-Gatter, die (R, S) = (1, 1) am Master verhin-dern.
Aufbau:
Takt T
1
Master Slave
S Q
R Q
S Q
R Q
&
&
J
K
Schaltungen Jörg Roth 216
Symbol:
Funktionsweise (J,K)-Master-Slave-Flipflops:
■ Master/Slave-Funktionsweise ist wie beim Master-Slave-Flipflop
■ Alle vier mögliche Eingaben sind erlaubt:
• (J, K) = (0, 0) erhalte das zuletzt gespeicherte Bit
• (J, K) = (1, 0) setze 1-Bit
• (J, K) = (0, 1) setze 0-Bit
• (J, K) = (1, 1) wechsle das zuletzt gespeicherte Bit (01, 10)
J Q
K Q
Schaltungen Jörg Roth 217
J K Q Q (nach Takt) Bemerkung
0 0 0 0Zustand halten
0 0 1 1
0 1 0 00-Bit speichern
0 1 1 0
1 0 0 11-Bit speichern
1 0 1 1
1 1 0 1Zustand wechseln
1 1 1 0
Schaltungen Jörg Roth 218
Bemerkung.
Es gibt auch ein einfaches (nicht Master-Slave-) (J,K)-Flipflop. Bei diesen wird der Zustand des enthaltenen Flipflops auf den Eingang zurückgeführt. Wenn die Taktphase T = 1 zu lange ist, wechselt dieses Flipflop seinen Zustand mehrfach. In Schaltungen mit diesem Flipflop wählt man daher eine sehr kurze Taktphase T = 1.
Schaltungen Jörg Roth 219
Das T-Master-Slave-Flipflop (Toggle).Das T-Master-Slave-Flipflop wechselt bei jedem Takt den Zustand.
Schaltung und Symbol:
Funktionsweise:
■ Wechsle den Zustand bei jedem Takt, wenn T = 1, sonst halte den letzten Zustand
Bemerkung:
■ Kein Flipflop zum expliziten Speichern eines Bits!
J Q
K Q
Q
QTT
Schaltungen Jörg Roth 220
T Q Q (nach Takt) Bemerkung
0 0 0Zustand halten
0 1 1
1 0 1Zustand wechseln
1 1 0
Schaltungen Jörg Roth 224
Anwendung von Schieberegistern:
■ Umwandlung paralleler Informationen in serielle Informationen und umgekehrt. Beispiele:
• Ausgabe von Bytes auf eine serielle Schnittstelle (z.B. USB)• Serielles Senden der Bits von Netzwerk-Rahmen über ein Ethernet-
Kabel.
Weitere Anwendung für Schieberegister:
■ Multiplikation einer positiven Binärzahl mit 2: links-Schieben, wobei von rechts eine 0 nachgeschoben wird
■ Ganzzahl-Division einer positiven Binärzahl durch 2: rechts-Schieben, wobei von links eine 0 nachgeschoben wird
■ Ganzzahl-Division einer 2er-Komplement-Zahl durch 2: rechts-Schieben, wobei das Vorzeichen-Bit dupliziert wird (auch Arithmetic Shift genannt).
Schaltungen Jörg Roth 237
Begründung für die Laufzeit der Addition:
&
>1
&
y u
s
x
&
>1
&
&
&
u
&>1
&
x y
s
u
HAVAu
VAu
VAu
...
1 Gatterlaufzeit für u
3 Gatterlaufzeiten für u
2 weitere Gatterlaufzeiten für s
Halbaddierer
Volladdierer
&
>1
>1
&
&
>1
&
Schaltungen Jörg Roth 238
Für die Zeit zur Berechnung der Summe gilt:
ÜbHA+(n–2)ÜbVA+AddVA
= 1G+(n–2)3G+2G
= (3n–3)G
Bemerkung: diese Art der Übertragsberechnung wird Ripple Carry genannt.
Schaltungen Jörg Roth 242
Carry-Look-Ahead für 4 Bits
>1
x0x1x2x3 uy0y1y2y3
>1
>1
>1
& & & &&
&&>1
>1
u4
>1
2 Gatterlaufzeiten&
2 Gatterlaufzeiten
4 Die Mikroprogrammebene eines Rechners
Das Abarbeiten eines Arbeitszyklus eines einzelnen Befehls besteht selbst wieder aus verschiedenen Schritten (Befehl holen, Befehl dekodieren, Ope-randen holen etc.). Diese einzelnen Schritte werden durch das Mikropro-gramm gesteuert.
Transistoren
Gatter
Register undMikroprogramm
Assembler undMaschinenprogramm
HöhereProgrammiersprache
lw $t0, alw $t1, badd $t0, $t0, $t1add $t0, $t0, $t1sw $t0, a
& >1
&
&
Kap 4
int a=1, b=2;a = a+2*b;
Die Mikroprogrammebene eines Rechners Jörg Roth 258
Es gibt zwei unterschiedliche Rechnerarchitektur-Typen:
■ CISC (Complex Instructions Set Computers): Ein Befehl auf Maschinen-ebene wird durch mehrere Befehle auf der Mikroprogrammebene darge-stellt. Dadurch stellen Maschinen-Befehle kleine "Programme" dar, die z.B. Schleifen enthalten können. Es sind komfortable Befehle möglich.
■ RISC (Reduced Instructions Set Computers): Ein Befehl auf Maschinen-ebene entspricht direkt einem Befehl der Mikroprogrammebene. Dadurch sind weniger komfortable Befehle möglich, diese werden aber sehr schnell abgearbeitet.
Die Mikroprogrammebene eines Rechners Jörg Roth 259
Typische Bestandteile einer CPU:
■ Ein Satz von Registern (typisch: ca. 4-32 Stück), die Zwischenergebnisse speichern und als Operanden verwendet werden können.
■ Meist ein einzelnes ausgezeichnetes Register, das als ein Operand und Speicher des Ergebnisses benutzt wird (genannt Akkumulator). Auch möglich: Speichern des Ergebnisses in ein beliebiges Register.
■ Eine Arithmetisch Logische Einheit (ALU) berechnet logische Operatio-nen (AND, XOR etc.) und arithmetische Operationen (Addition, Subtrak-tion, eventuell Multiplikation, Division).
Die Mikroprogrammebene eines Rechners Jörg Roth 260
Beispiel: 4-Bit-ALU 74181
(Bemerkung: 74181 ist ein eigener ALU-Baustein. Üblicherweise sind ALUs innerhalb der CPU integriert).
■ Mögliche Funktionen:
• logische (AND, OR, XOR, Invertieren etc.)• arithmetische (Addition, Subtraktion)
■ Carry-Eingang, Carry-Ausgang (Carry Look-Ahead). Mehrere 74181-ALUs können hintereinandergeschaltet werden, um größere Bitbreiten zu realisieren
■ Über 5 Eingänge (S0...S3, M) wird die Funktion selektiert
■ Nicht alle 32 möglichen Funktionen haben eine unmittelbare Bedeutung z.B. (1, 0, 1, 0, 1) bedeutet (A UND B) PLUS (A ODER B) PLUS Carry
Die Mikroprogrammebene eines Rechners Jörg Roth 261
Die wichtigsten 74181-Funktionen:
M S3 S2 S1 S0 Funktion M S3 S2 S1 S0
0 0 0 0 0 F = A 1 0 0 0 0 F = A PLUS Carry
0 0 0 0 1 F = A UND B 1 0 0 0 1
0 0 0 1 0 F = A ODER B 1 0 0 1 0
0 0 0 1 1 F = (1, 1, 1, 1) 1 0 0 1 1 F = (Carry, Carry, Carry, Carry)
0 0 1 0 0 F = A ODER B 1 0 1 0 0
0 0 1 0 1 F = B 1 0 1 0 1
0 0 1 1 0 F = (A = B) 1 0 1 1 0 F = A MINUS B MINUS Carry
0 0 1 1 1 F = A ODER B 1 0 1 1 1
0 1 0 0 0 F = A UND B 1 1 0 0 0
0 1 0 0 1 F = A XOR B 1 1 0 0 1 F = A PLUS B PLUS Carry
0 1 0 1 0 F = B 1 1 0 1 0
0 1 0 1 1 F = A ODER B 1 1 0 1 1
0 1 1 0 0 F = (0, 0, 0, 0) 1 1 1 0 0
0 1 1 0 1 F = A UND B 1 1 1 0 1
0 1 1 1 0 F = A UND B 1 1 1 1 0
0 1 1 1 1 F = A 1 1 1 1 1 F = A MINUS Carry
Die Mikroprogrammebene eines Rechners Jörg Roth 262
Typische Bestandteile einer CPU (Fortsetzung):■ Eine Schiebeeinheit (Shifter) führt rechts-, links-Schieben, arithmetisches
Schieben und Rotieren durch. Die Schiebefunktionen werden oft auch der ALU zugerechnet und nicht durch eine eigene Komponente realisiert.
■ Ein Satz von Flags gibt über den Status einer Berechnung Auskunft:
• Carry: es ist ein Übertrag entstanden• Overflow: es ist ein Überlauf entstanden
• Zero: es ist eine 0 entstanden (bzw. Gleichheit beim Vergleich)
• Negativ: es ist eine negative Zahl entstanden (bzw. kleiner-Bedingung beim Vergleich)
Die Mikroprogrammebene eines Rechners Jörg Roth 263
Zusammenspiel zwischen ALU, Registern und Flags:
ALU& Shifter
Akku
Reg2
Reg3
Regn
...
...
Auswahl Funktion
Auswahl 2.Operand
C O Z N
Die Mikroprogrammebene eines Rechners Jörg Roth 264
Typische Bestandteile einer CPU (Fortsetzung):■ Ein Register, das auf den nächsten Maschinen-Befehl im Speicher zeigt
(Instruction Pointer, IP).
■ Ein Register, das (z.B. für Unterprogrammaufrufe) auf die oberste Adresse eines Stapels zeigt (Stack Pointer, SP).
■ Ein Satz von Registern, ist für die Kommunikation mit dem Hauptspei-cher notwendig:
• ein Register hält die Speicheradresse (Memory Address Register, MAR),• ein weiteres Register speichert den Inhalt zum Schreiben und Lesen
(Memory Buffer Register, MBR).
■ Ein Steuerwerk wertet die Maschinen-Befehle aus und steuert die Daten-flüsse zwischen den einzelnen Komponenten in der geforderten Weise.
Die Mikroprogrammebene eines Rechners Jörg Roth 265
Weitere Komponenten einer CPU:
■ Interrupt-Logik: Die CPU muss asynchron auf auftretende Ereignisse reagieren können (z.B. Netzwerkkarte meldet, dass ein Netzwerkpaket eingetroffen ist). Diese Ereignisse werden über spezielle Eingänge gemel-det und unterbrechen die aktuelle Programmabarbeitung.
■ Cache-Speicher: Zum Beschleunigen der Speicherzugriffe werden Daten auf dem Prozessor-Chip zwischengespeichert. Liegen die Daten bei einem erneuten Zugriff noch vor, so ist der Zugriff wesentlich schneller.
■ Fließkomma-Einheit: Traditionell sind Fließkomma-Einheiten nicht Bestandteil der CPU. Früher gab es dazu einen mathematischen Copro-zessor (Floating Point Unit, FPU), der typische Fließkomma-Befehle bereitstellte. Heutzutage kann die FPU auf dem CPU-Chip integriert wer-den. Es gibt aber auch CPUs ohne jegliche Fließkomma-Funktionen. In diesem Fall muss die Fließkomma-Arithmetik über Software realisiert werden.
Die Mikroprogrammebene eines Rechners Jörg Roth 266
Schematischer Aufbau einer CPU:
ALU& Shifter
Akku
Reg2
Reg3
Regn
...
...
Auswahl Funktion
Auswahl 2.Operand
C O Z N
IP
SP
MAR
MBR
Haupt-speicher-Adresse
Auswahl Register für Speicherzugriff
Auswahl Schreiben oder Lesen
Auswahl welches Register speichern/
laden
Haupt-speicher-
Daten
Auswahl Adresse/Daten
Die Mikroprogrammebene eines Rechners Jörg Roth 267
Schematischer Aufbau einer CPU inklusive Steuerwerk:
ALU& Shifter
Akku
Reg2
Reg3
Regn
...
...
Auswahl Funktion
Auswahl 2.Operand
C O Z N
IP
SP
MAR
MBR
Haupt-speicher-Adresse
Auswahl Register für Speicherzugriff
Auswahl Schreiben oder Lesen
Auswahl welches Register speichern/
laden
Haupt-speicher-
Daten
Auswahl Adresse/Daten
Steuerwerk
Auswahl ...
Auswahl ...
Auswahl ...
Auswahl ...
Befehl
Die Mikroprogrammebene eines Rechners Jörg Roth 268
Funktionsweise des Steuerwerks:
■ Anhand des geladenen Befehls wird an eine bestimmte Stelle des Mikro-programm-Speichers verzweigt.
■ Ein Mikroprogramm-Befehl besteht aus einem Bitvektor (Auswahl1,
Auswahl2,....). Dadurch werden die Multiplexer/Demultiplexer ("Aus-
wahl...") so angesteuert, wie es der Befehl erfordert.
■ Üblicherweise erfordert ein Befehl mehrere Schritte im Mikroprogramm. Deshalb enthält ein Mikroprogramm-Befehl auch Anteile, die das Mikro-programm selbst steuern (z.B. Mikroprogramm-Zähler um 1 weiterschal-ten).
Die Mikroprogrammebene eines Rechners Jörg Roth 269
Durch Berücksichtigen der Flags kann das Mikroprogramm unterschiedlich reagieren.
Beispiel:
■ Maschinenbefehl des Z80-Prozessors: JP Z,<adresse> // (Jump If Zero) Bedeutung: Springe zu einer Programmadresse, wenn die letzte Opera-tion den Wert 0 ergab
■ Pseudo-Code des zugehörigen Mikroprogramms:
Werte das Zero-Flag ausIst das Zero-Flag gesetzt, dann setze IP:=<adr>Ist das Zero-Flag nicht gesetzt, dann setze IP:=IP+1
Die Mikroprogrammebene eines Rechners Jörg Roth 270
Bemerkung:
■ In der Regel ist das Mikroprogramm einer CPU fest. Es gibt einige wenige CPUs, deren Mikroprogramm neu geladen werden kann.
■ Warum programmiert man nicht direkt auf Mikroprogramm-Ebene?
• Mikroprogramm-Befehle sind in der Regel sehr "breit"• Mikroprogramm-Befehle erfordern viel Wissen über den internen Auf-
bau der CPU
5 Die Maschinenprogrammebene eines Rechners
Transistoren
Gatter
Register undMikroprogramm
Assembler undMaschinenprogramm
HöhereProgrammiersprache
lw $t0, alw $t1, badd $t0, $t0, $t1add $t0, $t0, $t1sw $t0, a
& >1
&
&
Kap 5
int a=1, b=2;a = a+2*b;
Die Maschinenprogrammebene eines Rechners Jörg Roth 272
Wir betrachten die Ebene der Maschinenprogramme am Beispiel des MIPS R2000 Prozessors.
Wir behandeln:
■ die Architektur des MIPS-Prozessors, Register, Adressierungsarten;
■ die Befehle des MIPS-Prozessors;
■ Assembler vs. Maschinensprache, Kodierung von Befehlen;
■ die MARS-Simulationsumgebung für den MIPS-Prozessor;
■ weitere Eigenschaften der Befehle und Programmbeispiele.
Die Maschinenprogrammebene eines Rechners Jörg Roth 273
5.ADie Komponenten des MIPS R2000
Speicher
ALU& Shifter
$zero
$1
$2
$31
...
...
Auswahl Funktion (funct)
Auswahl 2.Operand (rt)
O Z N
Auswahl Ziel (rd) Auswahl 1.Operand (rs)
...
lesen
Adresse
schreiben
Auswahl Quelle
Offset
addieren
Befehls-register
Direkter Operand (immediate)
Anzahl Shifting-Schritte (shamt)
Adress-Offset
Adresse (address)
Auswahl Adress-Quelle
shamt
functrd
rt
rs
Hi LoErgebnisse MULT, DIV
Auswahl Auswahl ...
Die Maschinenprogrammebene eines Rechners Jörg Roth 274
Register des MIPS
Es gibt 32 interne Register. Zwei Arten der Bezeichnung:
■ Durchnumeriert: $0,... $31
■ Anhand der Eigenschaft: $zero, $s0,... $s7, $t0,... $t7
■ Es gibt eine 1-1-Zuordnung zwischen beiden Bezeichnungen, z.B. $0=$zero, $16=$s0, $17=$s1
Die Register haben verschiedene Bedeutungen. Einige davon:
■ $zero: gibt immer die 0 zurück, kann nicht geschrieben werden
■ $s0,... $s7: generelle Register für Zwischenrechungen
Zwei weitere Register mit speziellen Funktionen: Hi, Lo
■ Resultate für Multiplikation: (Hi, Lo) = op1 op2
■ Resultat für die Division: Hi = op1 mod op2, Lo = op1/op2
Die Maschinenprogrammebene eines Rechners Jörg Roth 275
Übersicht der Register:
Register Symbolisch Bedeutung
$0 $zero immer 0
$1 $at verwendet Assembler bei Pseudobefehlen
$2 – $3 $v0 – $v1 Rückgabewerte von Unterprogrammen
$4 – $7 $a0 – $a3 Parameter für Unterprogr. (Unterprogr. darf verändern)
$8 – $15 $t0 – $t7 Register, die ein Unterprogramm nicht sichern muss
$16 – $23 $s0 – $s7 Register, die ein Unterprogramm sichern muss
$24 – $25 $t8 – $t9 Register, die ein Unterprogramm nicht sichern muss
$26 – $27 $k0 – $k1 reserviert für das Betriebssystem (Interrupts)
$28 $gp Zeiger auf globalen Speicherbereich
$29 $sp Stackpointer (zum Retten von Registern in Unterprog.)
$30 $s8/$fp Framepointer ($sp beim Start eines Unterprogramms)
$31 $ra Rücksprungadresse für Unterprogramme
Die Maschinenprogrammebene eines Rechners Jörg Roth 276
Bemerkungen zu den Registern:
■ Die Bedeutung der Register außer $zero und $ra ist nur eine Konvention.
■ Logische und arithmetische Operationen sowie Shift-Funktionen werden nur auf den Registern durchgeführt, nicht auf Speicheradressen. Beispiel: add $s1, $s2, $s3
bedeutet $s1 := $s2 + $s3
■ Um Operationen auf Speicherinhalten durchzuführen, müssen zuerst die Inhalte in Register geladen werden und am Ende das Resultat gespeichert werden:
lw $s2,1000 # Lade Inhalt von Adresse 1000 in $s2 lw $s3,2000 # Lade Inhalt von Adresse 2000 in $s3 add $s1, $s2, $s3 # Addiere sw $s1, 3000 # Speichere Resultat in Adresse 3000
Die Maschinenprogrammebene eines Rechners Jörg Roth 277
5.BMaschinensprache und Assembler
■ Die vom Prozessor ausführbaren Befehle liegen im Binärformat vor. Nur solche Befehle sind direkt ausführbar. So steht das Wort
(02538820)16
für den symbolischen Befehl
add $17, $18, $19 bzw. add $s1, $s2, $s3
■ Während der Befehl (02538820)16 für den Prozessor leicht "verständlich"
ist, ist er für Menschen schwer lesbar. Für Menschen ist dagegen die Text-zeile "add $s1, $s2, $s3" verständlicher.
• Das "add" im Befehl wird Mnemonic genannt. • Die Registerbenennung kann in der gewünschten Form erfolgen.
• Zusätzlich gibt es syntaktische Kennzeichnungen für verschiedene Adressierungsarten (siehe unten).
Die Maschinenprogrammebene eines Rechners Jörg Roth 278
Zur Lösung dieses Problems verwendet man zur Programmierung auf Maschinenebene einen so genannten Assembler:
■ Assembler lesen Texte zeilenweise und wandeln in der Regel jede Text-zeile in einen Maschinenbefehl um.
■ Ein typischer Befehl besteht aus einem Mnemonic (z.B. addi) und Ope-randen (z.B. $s1), letztere durch Kommata oder Blanks getrennt.
■ Die Übersetzung von Assembler-Texten in Maschinenbefehle ähnelt der Compilierung bei höheren Programmiersprachen – der Prozess wird Assemblierung genannt. Nicht korrekt geformte Texte können Syntaxfeh-ler enthalten, so dass kein Maschinenprogramm generiert werden kann.
■ Es gibt eine 1-1-Übersetzung von Assembler-Befehlen zu Maschinen-Befehlen – man verfügt also bei weitem nicht über die Möglichkeiten einer höheren Programmiersprache.
Die Maschinenprogrammebene eines Rechners Jörg Roth 279
Weitere Funktionen eines Assemblers:
■ Hantieren mit symbolischen Adressen: Der Entwickler kann bestimmten Speicheradressen Namen (Label) zuordnen. Der Assembler erkennt diese Namen und fügt bei der Übersetzung die Originaladressen ein.
■ Hantieren mit symbolischen Sprungzielen: Sprungbefehle führen den Pro-grammablauf an einer anderen Stelle des Programms fort. Diese Stellen können symbolisch benannt werden. Bei relativen Sprüngen (z.B. "springe 100 Bytes nach vorne") berechnet der Assembler die Sprungdif-ferenz anhand des symbolischen Namens automatisch.
■ Komfortables Einfügen statischer Daten: Neben den Maschinenbefehlen enthält ein Programm auch statische Bereiche, z.B. feste Zeichenketten oder numerische Konstanten. Über Assembler-Befehle können solche Datenbereiche komfortabel erstellt werden.
■ Angabe von numerischen Konstanten in verschiedenen Zahlensystemen, z.B. "100" (dezimal) "0xFF" (hexadezimal).
Die Maschinenprogrammebene eines Rechners Jörg Roth 280
■ Pseudobefehle: häufig benutzte Befehle können durch eigene Befehlskür-zel abgekürzt werden. So existiert in MIPS der Pseudobefehl li (load immediate), z.B. in
li $s1, 100 # Lade die Zahl 100 in das Register $s1
der allerdings bei der Assemblierung in den Befehl ori $s1, $zero, 100 # $s1 := 0 OR 100 übersetzt wird.
Der zweite Befehl ist inhaltsgleich aber für Menschen schwerer lesbar.
■ Makros sind mehrzeilige Befehlssequenzen, die bei der Assemblierung textuell eingefügt werden. Das kann die Lesbarkeit erhöhen. Markos kön-nen auch parametrisiert werden, dürfen aber nicht mit Unterprogrammen verwechselt werden, da sie zur Assemblierzeit textuell eingefügt werden und keine Verwaltung zur Laufzeit erfordern.
Die Maschinenprogrammebene eines Rechners Jörg Roth 281
Ein MIPS-Beispielprogramm:
.text # Schlüsselwort für den Anfang des Programmtextsmain: # Einstiegspunkt des Programms addi $s1, $zero, 20# Lade 20 in das Register $s1 ($s1 := 0 + 20) sll $s1, $s1, 3 # Schiebe $s1 um 3 Bit nach links ($s1 := $s1 * 8) addi $s2, $s1, 10 # $s2 := $s1+10
Dieses Programm berechnet 20*8+10 und legt das Ergebnis in $s2 ab.
Bemerkung: Dieses Programm soll lediglich die Wirkungsweise von Maschinenbefehlen illustrieren. In der Realität würde man das Ergebnis der Rechnung (170) direkt dem Register $s2 zuweisen.
Die Maschinenprogrammebene eines Rechners Jörg Roth 282
5.CDie MIPS-Befehle
Die MIPS-Befehle orientieren sich an folgenden vier Design-Prinzipien:
■ Simplicity favors regularity ("Einfachheit bevorzugt Regelmäßigkeit"):
• Nur eine Befehlslänge von 32 Bit• Nur drei Befehlsformate
• Innerhalb eines Befehlsformats: feste Anzahl von Operanden
■ Smaller is faster ("Kleiner ist schneller"):
• Eine kleine Anzahl von Registern begünstigt eine schnelle Befehlsabar-beitung.
Die Maschinenprogrammebene eines Rechners Jörg Roth 283
■ Good design demands compromise ("Gutes Design erfordert einen Kom-promiß"):
• Einiges ist unbequem, z.B. immer exakt drei Operanden für bestimmte Befehle zu haben.
• Einige wünschenswerte Befehle fehlen, z.B. Register-Kopien.
• Ein Teil der Unbequemlichkeit wird durch Pseudo-Befehle behoben.
■ Make the common case fast ("Mache den üblichen Fall schnell"):
• Beispiel der Angabe von Konstanten: Für 16-Bit Konstanten ("der übli-che Fall") kann MIPS dies in einem 32-Bit-Befehl ausdrücken. Für grö-ßere Konstanten ("der unübliche Fall") erfordert dies 2 Befehle.
Die Maschinenprogrammebene eines Rechners Jörg Roth 284
Bezeichnungen:
■ Rd, Rs, Rt: Register $0...$31 bzw. $v0 – $v1, $a0 – $a3, $t0 – $t7 etc.
■ I: Direktoperand (immediate): Operand wird durch 16 Bit gegeben, die auf 32 Bit erweitert werden: Beispiel :1000 stellt den direkten Wert der Zahl 1000 dar.
■ Hi, Lo: Multiplikations-, Divisionsergebnis
■ Label: Sprungziel
■ shamt: Feste Zahl von Schiebeschritten (vergleichbar mit I)
■ Address(Rs): Zugriff auf die Speicherzelle Mem[Address+Rs], Beispiel 1000($s1) für Zugriff auf Mem(1000+$s1)
Die Bedeutung der Spalte F (Format) wird weiter unten erklärt.
Die Maschinenprogrammebene eines Rechners Jörg Roth 285
Arithmetische Operationen:
Befehl Beschreibung Vorzeichen F
add Rd, Rs, Rt Rd := Rs + Rt mit R
addu Rd, Rs, Rt Rd := Rs + Rt ohne R
addi Rt, Rs, I Rt := Rs + I mit I
addiu Rt, Rs, I Rt := Rs + I ohne I
sub Rd, Rs, Rt Rd := Rs – Rt mit R
subu Rd, Rs, Rt Rd := Rs – Rt ohne R
div Rs, Rt Lo := Rs/Rt, Hi := Rs mod Rt mit R
divu Rs, Rt Lo := Rs/Rt, Hi := Rs mod Rt ohne R
mult Rs, Rt (Hi, Lo) := Rs Rt Hi = oberen 32 Bits, Lo = unteren 32 Bits
mit R
multu Rs, Rt (Hi, Lo) := Rs Rt Hi = oberen 32 Bits, Lo = unteren 32 Bits
ohne R
Die Maschinenprogrammebene eines Rechners Jörg Roth 286
Bitweise logische Verknüpfungen:
Befehl Beschreibung F
and Rd, Rs, Rt Rd := Rs Rt R
andi Rt, Rs, I Rt := Rs I I
nor Rd, Rs, Rt Rd := Rs Rt R
or Rd, Rs, Rt Rd := Rs Rt R
ori Rt, Rs, I Rt := Rs I I
xor Rd, Rs, Rt Rd := Rs Rt R
xori Rt, Rs, I Rt := Rs I I
Die Maschinenprogrammebene eines Rechners Jörg Roth 287
Schiebeoperationen:
Befehl Beschreibung F
sll Rd, Rt, shamt Rd := Rt links-geschoben um shamt Bits R
sllv Rd, Rt, Rs Rd := Rt links-geschoben um Rs Bits R
srl Rd, Rt, shamt Rd := Rt rechts-geschoben um shamt Bits R
srlv Rd, Rt, Rs Rd := Rt rechts-geschoben um Rs Bits R
sra Rd, Rt, shamt Rd := Rt rechts-geschoben um shamt Bits(arithmetisch, d.h. Erhaltung des Vorzeichens)
R
srav Rd, Rt, Rs Rd := Rt rechts-geschoben um Rs Bits(arithmetisch, d.h. Erhaltung des Vorzeichens)
R
Die Maschinenprogrammebene eines Rechners Jörg Roth 288
Vergleichen von Inhalten:
Befehl Beschreibung Vorzeichen F
slt Rd, Rs, Rt Rd := 1 wenn Rs < Rt, Rd := 0 wenn Rs Rt
mit R
sltu Rd, Rs, Rt Rd := 1 wenn Rs < Rt, Rd := 0 wenn Rs Rt
ohne R
slti Rt, Rs, I Rt := 1 wenn Rs < I, Rt := 0 wenn Rs I
mit I
sltiu Rt, Rs, I Rt := 1 wenn Rs < I, Rt := 0 wenn Rs I
ohne I
Die Maschinenprogrammebene eines Rechners Jörg Roth 289
Laden und Speichern:
Befehl Beschreibung F
mfhi Rd Rd := Hi R
mflo Rd Rd := Lo R
lui Rt, I Rt := I216
(oberste 16 Bit = I , unterste 16 Bit = 0)
I
lb Rt, Address(Rs) Rt := Byte in Mem[Address + Rs](Vorzeichen auf 32 Bit erweitert)
I
lbu Rt, Address(Rs) Rt := Byte in Mem[Address + Rs](keine Vorzeichenerweiterung)
I
sb Rt, Address(Rs) Byte in Mem[Address + Rs] := Rt I
lw Rt, Address(Rs) Rt := Word in Mem[Address + Rs] I
sw Rt, Address(Rs) Word in Mem[Address + Rs] := Rt I
Die Maschinenprogrammebene eines Rechners Jörg Roth 290
Relative Sprünge (Branch):
Befehl Beschreibung Vorzeichen F
beq Rs, Rt, Label Springe wenn Rs =Rt egal I
bne Rs, Rt, Label Springe wenn Rs Rt egal I
bgez Rs, Label Springe wenn Rs 0 mit I
bgtz Rs, Label Springe wenn Rs > 0 mit I
blez Rs, Label Springe wenn Rs 0 mit I
bltz Rs, Label Springe wenn Rs < 0 mit I
Die Maschinenprogrammebene eines Rechners Jörg Roth 291
Absolute Sprünge (Jump):
Sonstige Befehle:
Befehl Beschreibung F
j Label Springe J
jal Label Unterprogrammaufruf J
jr Rs Springe zur Adresse in Rs R
jalr Rs Unterprogrammaufruf zur Adresse in Rs R
Befehl Beschreibung F
syscall Betriebssystemaufruf R
break n Exception n aufrufen R
Die Maschinenprogrammebene eines Rechners Jörg Roth 292
Die wichtigsten Pseudobefehle:
Befehl Beschreibung
li Rd, I Rd := I
la Rd, Label Rd := Adresse des Labels(Achtung: nicht den Inhalt der Speicherzelle kopieren, sondern die Adresse der Speicherzelle)
move Rd, Rs Rd := Rs
Die Maschinenprogrammebene eines Rechners Jörg Roth 293
Adressierungsarten:
■ Durch den Befehl wird die jeweilige Adressierungsart festgelegt, also die Art, wie auf einen Operanden zugegriffen wird, z.B.
• add: Registeradressierung• addi: Direktoperand
■ Nicht bei jeder Assemblersprache ist das so. Bei einigen Assemblerspra-chen gibt es ein einziges Mnemonic für verschiedene Adressierungsarten. Der Assembler erkennt dann syntaktisch die jeweilige Variante und fügt automatisch die verschiedenen Binärbefehle ein.
Beispiel Z80-Assembler ADD A, B # Addiere A := A + B (A, B sind CPU-Register) ADD A, 100 # Addiere A := A + 100 (addiere Direktoperand 100) ADD A, (HL) # Addiere A := A + Mem(HL) (HL ist ein Zeigerregister)
Die Maschinenprogrammebene eines Rechners Jörg Roth 294
Adressierungsarten des MIPS:
■ Direktwert (immediate): eine Zahl i, die direkt im Befehl steht
■ Register: ein Register, darstellt durch eine Registernummer r, z.B. r = 17 für $s1
■ Speicher: Speicherinhalt einer Adresse a: Mem[a]
■ Register-indirekt: eine Registernummer r definiert ein Register, das als Zeiger auf eine Speicheradresse benutzt wird: Mem[$r]
■ Register-indirekt mit Versatz: eine Registernummer r definiert eine Zei-gerregister, zu dem eine Adresse a hinzuaddiert wird: Mem[a + $r]
Bemerkung: MIPS stellt die Adressierungsarten Speicher und Register-indirekt immer als Register-indirekt mit Versatz dar:■ Speicher: Mem[a + $zero]
■ Register-indirekt: Mem[0 + $r]
Die Maschinenprogrammebene eines Rechners Jörg Roth 295
5.DKodierung von MIPS-Befehlen
■ Es gibt drei Formate (siehe Spalte F in den Befehlstabellen)
■ Jeder Befehl ist 32 Bit lang
op rs rt rd shamt funct
6 Bit 5 Bit 5 Bit 5 Bit 5 Bit 6 Bit
op rs rt address/immediate
6 Bit 5 Bit 5 Bit 16 Bit
op address
6 Bit 26 Bit
R-Format
I-Format
J-Format
Die Maschinenprogrammebene eines Rechners Jörg Roth 296
■ Anhand des Feldes op wird erkannt, welches Format verwendet wird
• R-Format: op = (000000)
• I-Format: alle op außer op = (000000), op = (00001*), op = (0100**)
• J-Format: op = (00001*)
• Ein weiteres Format ist für Co-Prozessor-Befehle reserviert (hier nicht behandelt): op = (0100**)
Bedeutung der Felder:
■ op, funct: op spezifiziert den Befehl (Opcode). Bei op = 0 wird funct hin-zugenommen, um den Befehl zu identifizieren
■ rs, rt, rd: Register: rs: 1. Operand (source), rt: 2. Operand bzw. Zielregis-ter (target), rd: Zielregister (destination)
■ shamt: Zahl von Schiebeschritten
■ address/immediate: relative Sprungadresse oder 16-Bit Direktoperand
■ address: Absolute Sprungadresse
Die Maschinenprogrammebene eines Rechners Jörg Roth 297
R-Format-Befehle:
Befehl op rs rt rd shamt funct
add Rd, Rs, Rt 0 rs rt rd 0 32
addu Rd, Rs, Rt 0 rs rt rd 0 33
sub Rd, Rs, Rt 0 rs rt rd 0 34
subu Rd, Rs, Rt 0 rs rt rd 0 35
div Rs, Rt 0 rs rt 0 0 26
divu Rs, Rt 0 rs rt 0 0 27
mult Rs, Rt 0 rs rt 0 0 24
multu Rs, Rt 0 rs rt 0 0 25
and Rd, Rs, Rt 0 rs rt rd 0 36
nor Rd, Rs, Rt 0 rs rt rd 0 39
or Rd, Rs, Rt 0 rs rt rd 0 37
Die Maschinenprogrammebene eines Rechners Jörg Roth 298
xor Rd, Rs, Rt 0 rs rt rd 0 38
sll Rd, Rt, shamt 0 0 rt rd shamt 0
sllv Rd, Rt, Rs 0 rs rt rd 0 4
srl Rd, Rt, shamt 0 0 rt rd shamt 2
srlv Rd, Rt, Rs 0 rs rt rd 0 6
sra Rd, Rt, shamt 0 0 rt rd shamt 3
srav Rd, Rt, Rs 0 rs rt rd 0 7
mfhi Rd 0 0 0 rd 0 16
mflo Rd 0 0 0 rd 0 18
slt Rd, Rs, Rt 0 rs rt rd 0 42
sltu Rd, Rs, Rt 0 rs rt rd 0 43
jr Rs 0 rs 0 0 0 8
jalr Rs 0 rs 0 0 0 9
Befehl op rs rt rd shamt funct
Die Maschinenprogrammebene eines Rechners Jörg Roth 299
syscall 0 0 0 0 0 12
break n 0 0 0 0 n 13
Befehl op rs rt rd shamt funct
Die Maschinenprogrammebene eines Rechners Jörg Roth 300
I-Format-Befehle:
Befehl op rs rt address/immediate
addi Rt, Rs, I 8 rs rt immediate
addiu Rt, Rs, I 9 rs rt immediate
andi Rt, Rs, I 12 rs rt immediate
ori Rt, Rs, I 13 rs rt immediate
xori Rt, Rs, I 14 rs rt immediate
lui Rt, I 15 0 rt immediate
lb Rt, Address(Rs) 32 rs rt address
lbu Rt, Address(Rs) 36 rs rt address
sb Rt, Address(Rs) 40 rs rt address
lw Rt, Address(Rs) 35 rs rt address
sw Rt, Address(Rs) 43 rs rt address
Die Maschinenprogrammebene eines Rechners Jörg Roth 301
J-Format-Befehle:
slti Rt, Rs, I 10 rs rt immediate
sltiu Rt, Rs, I 11 rs rt immediate
beq Rs, Rt, Label 4 rs rt address
bne Rs, Rt, Label 5 rs rt address
bgez Rs, Label 1 rs 1 address
bgtz Rs, Label 7 rs 0 address
blez Rs, Label 6 rs 0 address
bltz Rs, Label 1 rs 0 address
Befehl op address
j Label 2 address
jal Label 3 address
Befehl op rs rt address/immediate
Die Maschinenprogrammebene eines Rechners Jörg Roth 302
Beispiel: Übersetzen des Beispielprogramms in Maschinensprache
Befehlszeile F op rs rt rd shamt functadr/imm
Maschinen-befehl (Hex)
addi $s1,$zero,20 I 8001000
000000
1710001
- - - 200000 00000001 0100
2011 0014
sll $s1,$s1,3 R 0000000
000000
1710001
1710001
300011
0000000
- 0011 88C0
addi $s2,$s1,10 I 8001000
1710001
1810010
- - - 100000 00000000 1010
2232 000A
Die Maschinenprogrammebene eines Rechners Jörg Roth 303
5.E Die MARS-Umgebung
■ MARS ist ein Simulationswerkzeug für MIPS-Prozessoren
■ Es enthält einen Assembler und eine Laufzeitumgebung
■ Da das Wirtsystem (z.B. Windows) auf einem anderen Prozessor basiert, werden die MIPS-Maschinenbefehle zur Laufzeit auf einem virtuellen Prozessor simuliert.
Die Maschinenprogrammebene eines Rechners Jörg Roth 304
MARS-Funktionen:
■ Anzeigen von Register- und Speicherinhalten
■ Zeigen des assemblierten Programms
■ Durchlaufen des Codes im Einzelschrittmodus
■ Setzen von Break-Points
■ Über syscall kann aus dem Maschinenprogramm heraus eine rudimentäre Konsole angesprochen werden
• Ein/Ausgabe von Zahlen• Ein/Ausgaben von Zeichenketten
Die Maschinenprogrammebene eines Rechners Jörg Roth 305
Direktiven des MARS-Assemblers an einem Beispiel:
.data # Schlüsselwort für den statischen Datenteil
label1: .word 1000 # Anlegen des 32-Bit-Wortes mit dem Wert 1000label2: .byte 10 # Anlegen des Bytes mit dem Wert 10label3: .byte ’a’ # Anlegen des Bytes mit dem ASCII-Wert für ’a’label3: .space 15 # Anlegen von 15 Bytes mit dem Wert 0label4: .asciiz "Dies ist ein Text" # Anlegen eines 0-terminierten Strings
.text # Schlüsselwort für den Programmtext
main: # Ein Programm muss diesen Einstiegspunkt haben addi ... # Ab hier stehen die Assemblerbefehle
Die Maschinenprogrammebene eines Rechners Jörg Roth 306
Die wichtigsten MARS syscalls
Nr. $v0
BeschreibungAufruf-
argumentRückgabewert
1 32-Bit-Zahl dezimal auf die Kon-sole ausgeben
$a0 = Wert der Zahl –
4 0-terminierten String auf die Kon-sole ausgeben
$a0 = Adresse des Strings –
5 32-Bit-Zahl dezimal von der Kon-sole einlesen
– $v0 = Wert der Zahl
8 String von der Konsole einlesen und 0-terminiert in Puffer ablegen
$a0 = Adresse des Stringpuffers$a1 = Länge des Stringpuffers
–
9 Dynamischen Speicher allozieren $a0 = Länge des Blocks $v0 = Adresse des Blocks
10 Programm beenden – –
Die Maschinenprogrammebene eines Rechners Jörg Roth 307
Bemerkungen zu den MARS syscalls:
■ Ein Programm terminiert automatisch nach der letzten Befehlszeile. sys-call 10 wird nur benötigt, wenn man das Programm vorher beenden möchte. Alternativ kann man hinter den letzten Befehl springen.
■ Die syscalls zur Zahlen-Ein/Ausgabe verwenden Register für die Zahlen-speicherung.
■ Die syscalls zu der String-Ein/Ausgabe legen die Zeichenketten im Spei-cher ab (nicht in den Registern). Über das Register $a0 wird die Adresse des Strings bzw. des freien Stringpuffers angegeben.
Die Maschinenprogrammebene eines Rechners Jörg Roth 308
Beispiel:
.data
prompt: .asciiz "Bitte Zahl eingeben: "text1: .asciiz "Sie haben die Zahl "text2: .asciiz " eingegeben\n"
.text
main: li $v0, 4 # String ausgeben la $a0,prompt # "Bitte Zahl eingeben: syscall
li $v0, 5 # Zahl einlesen syscall or $s0, $zero, $v0 # $s0 := Eingabe;
Die Maschinenprogrammebene eines Rechners Jörg Roth 309
li $v0, 4 # String ausgeben la $a0,text1 # "Sie haben die Zahl " syscall
li $v0, 1 # Resultat ausgeben or $a0, $zero, $s0 # in $s0 stand die Zahl syscall
li $v0, 4 # String ausgeben la $a0,text2 # " eingegeben\n" syscall
li $v0, 10 # Programm beenden syscall
Die Maschinenprogrammebene eines Rechners Jörg Roth 310
5.F Die Maschinenbefehle im Detail
5.F.a Arithmetische Operationen
Addition und Subtraktion:
Befehl Beschreibung Vorzeichen
add Rd, Rs, Rt Rd := Rs + Rt mit
addu Rd, Rs, Rt Rd := Rs + Rt ohne
addi Rt, Rs, I Rt := Rs + I mit
addiu Rt, Rs, I Rt := Rs + I ohne
sub Rd, Rs, Rt Rd := Rs – Rt mit
subu Rd, Rs, Rt Rd := Rs – Rt ohne
Die Maschinenprogrammebene eines Rechners Jörg Roth 311
Bemerkungen:
■ Zahlendarstellung: 32 Bit-Zweierkomplement
■ Es gibt kein subi und subiu. Stattdessen verwendet man addi und addiu und muss den immediate-Operanden von Hand negieren. Z.B.
addi $s0, $s0, -1
um 1 von $s0 abzuziehen
■ add und addu addieren intern identisch. add erzeugt aber eine Exception, wenn das Resultat das falsche Vorzeichen erhält (Overflow-Bedingung). addu produziert keine Exception, auch wenn ein Übertrag generiert wird.
Die Maschinenprogrammebene eines Rechners Jörg Roth 312
Beispiele:
li $s0, 2147483647 # = 2^31-1 addiu $s1, $s0, 1 # bei unsigned addition Resultat: $s1=2147483648
li $s0, 2147483647 # maximale positive Zahl addi $s1, $s0, 1 # Resultat bekommt falsches VorzeichenResultat: Arithmetic Overflow
li $s0, 4294967295 # maximale 32-Bit-Zahl addiu $s1, $s0, 1 # Übertrag wird ignoriertResultat: $s1=0 (Bemerkung: würde auch bei addi entstehen)
Die Maschinenprogrammebene eines Rechners Jörg Roth 313
Multiplikation und Division:
Bemerkungen:
■ Es gibt keine Mult-, Div-Befehle mit immediate-Operand.
■ Das Ergebnis einer 32-Bit-Multiplikation benötigt 64 Bit. Daher existie-ren zwei 32-Bit-Register Hi und Lo, die die Resultate aufnehmen. Diese Register können nicht explizit beschrieben werden.
Befehl Beschreibung Vorzeichen
div Rs, Rt Lo := Rs/Rt, Hi := Rs mod Rt mit
divu Rs, Rt Lo := Rs/Rt, Hi := Rs mod Rt ohne
mult Rs, Rt (Hi, Lo) := Rs Rt Hi = oberen 32 Bits, Lo = unteren 32 Bits
mit
multu Rs, Rt (Hi, Lo) := Rs Rt Hi = oberen 32 Bits, Lo = unteren 32 Bits
ohne
Die Maschinenprogrammebene eines Rechners Jörg Roth 314
■ multu behandelt die Operanden als vorzeichenlose Zahlen, mult als Vor-zeichenzahlen. Es kann kein Überlauf oder Übertrag produziert werden, also auch keine Exceptions.
■ Im Ggs. zu add/addu werden intern unterschiedliche Operationen durch-geführt, je nachdem ob man Vorzeichenzahlen oder vorzeichenlose Zah-len verwendet. Beispiel:
li $s0, 4294967295 # 2^32-1 entspricht -1 li $s1, 4294967295 # 2^32-1 entspricht -1 mult $s0, $s1Resultat (Hi, Lo) = 1
li $s0, 4294967295 # 2^32-1 (max. 32-Bit-Zahl) li $s1, 4294967295 # 2^32-1 (max. 32-Bit-Zahl) multu $s0, $s1Resultat (Hi, Lo) = 18446744065119617025
Die Maschinenprogrammebene eines Rechners Jörg Roth 315
5.F.bLogische Operationen
Bitweise logische Verknüpfungen
Befehl Beschreibung
and Rd, Rs, Rt Rd := Rs Rt
andi Rt, Rs, I Rt := Rs I
nor Rd, Rs, Rt Rd := Rs Rt
or Rd, Rs, Rt Rd := Rs Rt
ori Rt, Rs, I Rt := Rs I
xor Rd, Rs, Rt Rd := Rs Rt
xori Rt, Rs, I Rt := Rs I
Die Maschinenprogrammebene eines Rechners Jörg Roth 316
Illustration am Beispiel des and-Befehls:
Bemerkungen:
■ Es gibt keinen immediate Befehl für nor.
■ Es gibt keine Befehle für nand und xnor.
& & &
...
&
rs
rt
rd
...
...
Die Maschinenprogrammebene eines Rechners Jörg Roth 317
Möglichkeiten für das Komplementieren von Bits:Beispiel: $s1 := $s0
■ nor $s1, $s0, $s0
■ xori $s1, $s0, -1 # -1 = FFFF, Achtung: nur 16 Bit komplementiert
Bemerkungen:
■ Der "native" xori-Befehl verwendet (wie alle immediate-Befehle) nur 16-Bit-Immediate-Operanden. Damit werden nur die unteren 16 Bit komple-mentiert.
■ Verwendet man xori mit einem Operanden mit mehr als 16 Bit, so erkennt der Assembler das und verwendet automatisch einen Pseudobefehl:
• Laden der oberen 16 Bit in das $at-Register (Befehl lui)• Laden der unteren 16 Bit in das $at-Register (Befehl ori)
• Verwenden der xor-Operation (nicht xori) mit Register $at
Die Maschinenprogrammebene eines Rechners Jörg Roth 318
Wozu benötigt man bitweise logische Verknüpfungen?
Beispiel Mauszeiger:
Mauszeiger: alle Bits des Bildschirms müssen auf 1
gesetzt werden
Maske: alle Bits des Bildschirms müssen auf 0
gesetzt werden
Zeigerbits Maskenbits
Bildschirm Bildschirm UND MaskeBildschirm UND Maske
ODER Maus
Die Maschinenprogrammebene eines Rechners Jörg Roth 319
Das zugehörige Programm:
■ Die 64 Zeigerbits seien in $s0, $s1 gespeichert
■ Die 64 Maskenbits seien in $s2, $s3 gespeichert
■ Die 64 Bildschirmbits unter dem Zeiger seien schon aus dem Bildspei-cher in $s4, $s5 abgelegt
nor $s2, $s2, $s2 # Maskenbits invertierennor $s3, $s3, $s3and $s4, $s4, $s2 # Bildschirm UND Komplement der Maskeand $s5, $s5, $s3 # d.h. alle Bild-Bits außerhalb der Maske =0or $s4,$s4, $s0 # Resultat ODER Mauszeigeror $s5,$s5, $s1 # damit werden alle Bild-Bits des Zeigers =1
Die Maschinenprogrammebene eines Rechners Jörg Roth 320
Schiebeoperationen:
Befehl Beschreibung
sll Rd, Rt, shamt Rd := Rt links-geschoben um shamt Bits
sllv Rd, Rt, Rs Rd := Rt links-geschoben um Rs Bits
srl Rd, Rt, shamt Rd := Rt rechts-geschoben um shamt Bits
srlv Rd, Rt, Rs Rd := Rt rechts-geschoben um Rs Bits
sra Rd, Rt, shamt Rd := Rt rechts-geschoben um shamt Bits(arithmetisch, d.h. Erhaltung des Vorzeichens)
srav Rd, Rt, Rs Rd := Rt rechts-geschoben um Rs Bits(arithmetisch, d.h. Erhaltung des Vorzeichens)
Die Maschinenprogrammebene eines Rechners Jörg Roth 321
Illustration der Schiebeoperationen mit shamt=1
Verwendung der Schiebebefehle:
■ Operanden multiplizieren mit 2shamt, dividieren durch 2shamt
■ Umwandlung serielle Datenparallele und umgekehrt
■ Zugriff auf Inhalte "gepackter" Strukturen
rt
rd
...
...0
sll
rt
rd
...
...
srl
0
rt
rd
...
...
sra
Die Maschinenprogrammebene eines Rechners Jörg Roth 322
Beispiel:Pixel-Information eines High-Color-Bildes (16 Bit/Pixel):
Jeder Pixel enthält folgende Informationen:
■ 5 Bit-Wert für "rot"
■ 6 Bit-Wert für "grün"
■ 5 Bit-Wert für "blau"
(Es gibt eine Reihe weiterer Möglichkeiten, z.B. True-Color mit 32 Bit)
04515
rot grün blau
1011
Die Maschinenprogrammebene eines Rechners Jörg Roth 323
Das zugehörige Programm:
■ Der Pixelwert sei schon in $s0
■ Wir wollen rot in $t0, grün in $t1 und blau in $t2 speichern
srl $t0, $s0, 11 # oberen 5 Bits (rot) nach rechts schiebenandi $t1, $s0, 0x07e0 # mittleren 6 Bits (grün) herauskopierensrl $t1, $t1, 5 # und nach rechts schiebenandi $t2, $s0, 0x001f # unteren 5 Bits (blau) herauskopieren
Die Maschinenprogrammebene eines Rechners Jörg Roth 324
5.F.c Vergleiche
Befehl Beschreibung Vorzeichen
slt Rd, Rs, Rt Rd := 1 wenn Rs < Rt, Rd := 0 wenn Rs Rt
mit
sltu Rd, Rs, Rt Rd := 1 wenn Rs < Rt, Rd := 0 wenn Rs Rt
ohne
slti Rt, Rs, I Rt := 1 wenn Rs < I, Rt := 0 wenn Rs I
mit
sltiu Rt, Rs, I Rt := 1 wenn Rs < I, Rt := 0 wenn Rs I
ohne
Die Maschinenprogrammebene eines Rechners Jörg Roth 325
Motivation für die slt-Befehle:
■ Es gibt (siehe weiter unten) keine bedingten Sprünge, die den Größenver-gleich zweier Operanden durchführen.
■ Vergleich und Sprung führt man daher so aus:
slt $t0, $s0, $s1 # $t0 := 1 wenn $s0 <$s1bgtz $t0, Label # Springe wenn $t0 > 0 (d.h. $s0 <$s1)
Die Maschinenprogrammebene eines Rechners Jörg Roth 326
Weiteres Beispiel:
■ In den Registern $t0, $t1, $t2 sind drei Zahlen abgelegt.
■ Zähle, wie viele dieser drei Zahlen kleiner als 100 sind. Ablage in $s0
slti $s0, $t0, 100 # $s0 := 1 wenn $t0 <100slti $s1, $t1, 100 # $s1 := 1 wenn $t1 <100add $s0, $s0, $s1 # $s0 := Summe der ersten beiden Ergebnisseslti $s1, $t2, 100 # $s1 := 1 wenn $t2 <100add $s0, $s0, $s1 # $s0 := Summe alle Ergebnisse
Die Maschinenprogrammebene eines Rechners Jörg Roth 327
Weitere Funktion von sltu: Berechnen des Übertrags
In MIPS gibt es kein Carry-Bit, wie in den meisten anderen CPUs. Man erkennt daher nicht auf einfache Weise, ob ein Übertrag bei einer Addition entstanden ist.
Berechnung des Carry-Bits – in $t0, $t1 seien positive Zahlen gespeichert: addu $t2, $t0, $t1 sltu $t3, $t2, $t1 # Teste, ob die Summe kleiner ist als $t1
Danach:
■ $t2: Summe von $t0, $t1 (mod 232)
■ $t3: 1, wenn Übertrag aufgetreten ist
Die Maschinenprogrammebene eines Rechners Jörg Roth 328
5.F.d Laden und Speichern
Befehl Beschreibung
mfhi Rd Rd := Hi
mflo Rd Rd := Lo
lui Rt, I Rt := I216
(oberste 16 Bit = I , unterste 16 Bit = 0)
lb Rt, Address(Rs) Rt := Byte in Mem[Address + Rs](Vorzeichen auf 32 Bit erweitert)
lbu Rt, Address(Rs) Rt := Byte in Mem[Address + Rs](keine Vorzeichenerweiterung)
sb Rt, Address(Rs) Byte in Mem[Address + Rs] := Rt
lw Rt, Address(Rs) Rt := Word in Mem[Address + Rs]
sw Rt, Address(Rs) Word in Mem[Address + Rs] := Rt
Die Maschinenprogrammebene eines Rechners Jörg Roth 329
Bemerkungen:
■ Es gibt keinen nativen Befehl für das Laden von immediate-Operanden – li ist ein Pseudobefehl, der intern auf ori ...,$zero, ... abgebildet wird.
■ Um 32-Bit-Konstanten in Register zu kopieren, reichen die 16-Bit in einem Befehl (I-Format) nicht aus. Deshalb gibt es den Befehl lui, der die oberen 16 Bit eines Registers mit dem immediate-Operanden füllt. Die untere Hälfte kann dann mit ori ... gefüllt werden.
■ lb, lw (bzw. sb, sw) unterscheiden sich in der Bit-Breite des Zugriffs:
• lb, sb: 8 Bit, lw, sw: 32 Bit■ Da bei lb nur 8 Bit des 32-Bit-Registers belegt werden, kann man ent-
scheiden, wie die übrigen 24 Bit gesetzt werden:
• lbu: restliche 24 Bit werden auf 0 gesetzt• lb: restliche 24 Bit werden auf Bit 7 (Vorzeichenbit) gesetzt
■ Bei sb werden die Bits 8-31 des Registers beim Speichern ignoriert.
Die Maschinenprogrammebene eines Rechners Jörg Roth 330
■ Die Befehle lb, lbu, lw, sb, sw benutzen die Adressierungsart Register-indirekt mit Versatz.
■ Da der Versatz als immediate-Operator definiert wird, kann nur ein Ver-
satz von -215 bis 215–1 ausgedrückt werden. Daher kann z.B. der Befehl lb $s0, 50 000 nicht direkt übersetzt werden, da der immediate-Operand größer ist als 32767. Der Assembler erkennt dies und wertet in diesem Fall lb als Pseudobefehl aus:
lui $at, 1 # $at = 65536lb $s0, -15536($at)# $s0 := Mem[-15536+65536] = Mem[50000]
■ Jedes Wort belegt 4 Byte. Die Adressierung basiert auf Bytes. Sollen Worte adressiert werden, die direkt hintereinander im Speicher liegen, muss man die Adresse jeweils um 4 erhöhen.
Die Maschinenprogrammebene eines Rechners Jörg Roth 331
Beispiel:
.dataword1: .word 10 # Zwei Worte direkt hintereinander im Speicherword2: .word 11
.textmain:
la $s0,word1 # Lade die Adresse des ersten Worteslw $t0,0($s0) # Lade erstes Wortlw $t1,4($s0) # Lade zweites Wort
Die Maschinenprogrammebene eines Rechners Jörg Roth 332
5.F.e Sprungbefehle
Befehl Beschreibung Vorzeichen
beq Rs, Rt, Label Springe wenn Rs =Rt egal
bne Rs, Rt, Label Springe wenn Rs Rt egal
bgez Rs, Label Springe wenn Rs 0 mit
bgtz Rs, Label Springe wenn Rs > 0 mit
blez Rs, Label Springe wenn Rs 0 mit
bltz Rs, Label Springe wenn Rs < 0 mit
j Label Springe
nichtanwendbar
jal Label Unterprogrammaufruf
jr Rs Springe zur Adresse in Rs
jalr Rs Unterprogrammaufruf zur Adresse in Rs
Die Maschinenprogrammebene eines Rechners Jörg Roth 333
Bemerkungen:
■ Da jeder MIPS-Befehl 32 Bits umfasst, liegen die Befehle immer passend auf 4-Byte-Blöcken. Die Adresse des ersten Bytes eines Befehls ist damit immer durch 4 teilbar (4 byte alignment).
• Da die möglichen Sprungziele immer binär auf 00 enden, müssen diese Bits nicht angegeben werden und man definiert nur die Bits ab Bit2 auf-wärts.
■ Die branch-Befehle (b...) verwenden relative Sprungziele.
• Der immediate-Operand definiert den Abstand zur Adresse des aktuel-len Befehls. Negative Distanz: Sprung vor den aktuellen Befehl. Positive Distanz: Sprung hinter den aktuellen Befehl.
• Der Bereich für immediate-Operanden ist -215 bis 215–1. Dieser wird mit 4 multipliziert (wegen alignment) und zur aktuellen Befehlsadresse hinzugezählt. Es sind damit Sprungweiten von ca. +/-128k möglich
Die Maschinenprogrammebene eines Rechners Jörg Roth 334
Beispiele:
Sprung zurück:
loop: add $s0, $s1, $s2beq $s0,$s1,loop# Sprungweite -4 , kodiert als immediate-Op. -1
Sprung nach vorne:
beq $s0,$s1,labx # Sprungweite +8 , kodiert als immediate-Op. 2add $s0, $s1, $s2
labx: add $s0, $s1, $s2
■ Der Assembler-Entwickler gibt auch bei relativen Sprüngen ein Label als Ziel an. Der Assembler berechnet automatisch die Distanz und meldet ggfs. einen Fehler wenn der Sprung zu weit geht.
Die Maschinenprogrammebene eines Rechners Jörg Roth 335
Bemerkungen zu absoluten Sprüngen:
■ Die j...-Befehle verwenden absolute Sprungadressen.
■ Absolute Adressen in den J-Format-Befehlen haben 26 Bit. Da die letzten
2 Bits 00 lauten, sind Sprünge im Bereich 228 (0–256 MB) möglich.
• Die MIPS Architektur ermöglicht zwar einen Adressraum von 232 Bytes (4GB), die Adressen oberhalb von 256 MB können allerdings nicht mit den J-Format-Sprüngen erreicht werden.
• Die Sprungbefehle mit Registerinhalten (jr, jalr) und relative Sprünge kennen diese Grenze zwar nicht, dennoch wird nur der Bereich bis 256 MB als Text-Segment (der Code-Bereich) definiert.
■ Die Befehle jal und jalr funktionieren wie j bzw. jr. Vor dem Sprung wird aber die aktuelle Befehlsadresse + 4 in das Register $ra geschrieben. Damit sind Unterprogramme möglich, die nach der Beendigung mit jr $ra hinter den Aufrufbefehl springen.
Die Maschinenprogrammebene eines Rechners Jörg Roth 336
5.F.f Pseudobefehle
■ Pseudobefehle sind nicht nativ im MIPS-Prozessor realisiert.
■ Sie vereinfachen die Assembler-Programmierung und erhöhen die Les-barkeit von Assembler-Programmen.
■ Die Menge von Pseudo-Befehlen ist je nach Assembler unterschiedlich. Auch die Übersetzung von Pseudo-Befehlen in native Befehle ist unter-schiedlich.
■ Typische MIPS-Pseudobefehle werden in 1, 2 oder 3 native Befehle über-setzt.
Die Maschinenprogrammebene eines Rechners Jörg Roth 337
Einige Pseudobefehle:
Befehl Beschreibung Realisierung
li Rd, I Rd := I ori Rd, $zero, I # 16-Bit-Ioder
lui $at, I(31...16)
ori Rd, $at, I(15...0) # 32-Bit-I
la Rd, Label Rd := Adresse des Labels
Wie li, der Assembler verhindert aber das Auswerten von "Label" – la kann ohne Hilfe des Assemblers nicht durch andere Befehle ersetzt werden!
move Rd, Rs Rd := Rs or Rd, $zero, Rs
nop tue nichts or $zero, $zero, $zerooder
sll $zero, $zero, 0
Die Maschinenprogrammebene eines Rechners Jörg Roth 338
b Label Relativer Sprung
beq $zero, $zero, Label
addi Rt, Rs, Iandi Rt, Rs, Iori Rt, Rs, I...
...i-Befehle mit 32-Bit-I-Oper-and
lui $at, I(31...16)
ori $at, $at, I(15...0) add Rt, Rs, $at # bzw. and, or...
lb Rt, Addr(Rs)lbu Rt, Addr(Rs)lw Rt, Addr(Rs)sb Rt, Addr(Rs)sw Rt, Addr(Rs)
wie lb etc., nur dass Addr mit mehr als 16 Bit
lui $at, Hi-Addrlb $s0, Lo-Addr($at) # bzw. lbu, lw, sb, sw
Befehl Beschreibung Realisierung
Die Maschinenprogrammebene eines Rechners Jörg Roth 339
5.F.g Speicherorganisation
Aufteilung des verfügbaren Adressraums:
Reserviert
Text Segment
Statische Daten
Dynamische Daten
Stapel
0x0000 0000
0x0040 0000
0x1000 0000
0x1001 0000
0x1000 8000$gp =
0x7FFF FFFF
$sp
252 MB
0x8000 0000
0xFFFF FFFF
Reserviert
64 kB
ca. 1,8 GB
2 GB
4 MB
Die Maschinenprogrammebene eines Rechners Jörg Roth 340
Bemerkungen:
■ Die Bereiche vor 0x0040 0000 und ab 0x8000 0000 sind reserviert.
■ Der verbleibende Bereich bis 0x1000 0000 ist das Text Segment, in dem sich der Programmcode befindet. Sprungbefehle nach dem J-Format kön-nen keine größeren Adressen anspringen.
■ Im Bereich statischer Daten verweist $gp auf die Mitte. Damit können Speicherzugriffe ohne Pseudobefehle mit nur einem Befehl formuliert werden. Z.B.
lw $s0, -0x8000($gp) # Zugriff auf Adresse 0x1000 0000
Da der Bereich statischer Daten 64k umfasst, kann man mit einem 16-Bit-Offset den gesamten Bereich adressieren. Ohne $gp würde dieser Zugriff zwei Befehle erfordern:
lui $at, 4096 # entspricht 0x1000 0000lw $s0,0($at)
Die Maschinenprogrammebene eines Rechners Jörg Roth 341
■ Der Stapel und der Bereich dynamischer Daten wachsen in entgegenge-setzer Richtung. Damit steht bei ungleicher Benutzung beiden Bereiche immer der maximale Rest zur Verfügung.
■ Der Bereich dynamischer Daten wird vom Betriebssystem verwaltet. Es gibt keine Register im MIPS, die diese Verwaltung unterstützen.
■ Der Stapel wächst per Konvention in die Richtung niedriger Adressen. $sp zeigt auf das zuletzt gefüllte Stapel-Element.
■ Der Stapel muss nicht unbedingt bei 0x7FFF FFFF beginnen. Stehen weniger als 2GB Speicher zur Verfügung kann der Stapel auch bei einer kleineren Adressen beginnen.
Die Maschinenprogrammebene eines Rechners Jörg Roth 342
5.GTypische Anwendungsfälle
Wir betrachten im Folgenden typische Fälle aus dem Bereich imperativer Programmiersprachen und beschreiben, wie diese in MIPS-Assembler reali-siert werden. Compiler, die höhere Programmiersprachen in Maschinenspra-che übersetzen, müssen über ein Regelwerk verfügen, die Programmstruktu-ren in Maschinensprache-Sequenzen zu übersetzen.
Die Maschinenprogrammebene eines Rechners Jörg Roth 343
5.G.aif-then-else
Höhere Programmiersprache:if (<Bedingung>) then <Anweisungen1> else <Anweisungen2>
Assembler:... # Code um die Bedingung zu berechnenb... else # Bedingung, um in den Else-Zweig zu springen... # Code der Anweisungen1j exit
else: ... # Code für Anweisungen2exit:
Bemerkung: Das in imperativen Sprachen verpönte "goto" ist die einzige Möglichkeit in Maschinensprache Kontrollstrukturen abzubilden.
Die Maschinenprogrammebene eines Rechners Jörg Roth 344
Weitere Bemerkung: Labels müssen global eindeutig sein. Verwendet man mehrere der dargestellten Strukturen, müssen die Labels "else" und "exit" z.B. durch Nummern ("else1" etc.) eindeutig gemacht werden.
Konkretes Beispiel:if ($s1<$s2) then $s3:=$s3+1; else $s4:=2*$s4;
Assembler:slt $t0, $s1, $s2 # $t0=1 wenn $s1<$s2beq $t0, $zero, else # wenn $t0=0: else-Zweigaddi $s3,$s3,1 # then-Zweigj exit # an das Ende springen
else: add $s4, $s4, $s4 # else-Zweigexit:
Die Maschinenprogrammebene eines Rechners Jörg Roth 345
5.G.bswitch-case
Höhere Programmiersprache:switch (<int-variable>) case 0:<Anweisungen0> case 1:<Anweisungen1> ... case n:<Anweisungenn>
Idee: Wir legen alle möglichen Sprungziele case 0, case 1, ... case n in einem Feld ab. Wir laden anhand der Variablen das richtige Sprungziel und sprin-gen mit jr.
Die Maschinenprogrammebene eines Rechners Jörg Roth 346
Assembler:sll $t0, $t0, 2 # $t0*4 ($t0 sei der switch-Wert)la $t1, jumpTableadd $t0, $t0, $t1 # Berechne switch-Wert*4+Adr(jumpTable)lw $t0, 0($t0) # Lade jumpTable[<switch-Wert>]jr $t0 # Springe gemäß Registerinhalt
case0: ... # Code der Anweisungen0j exit
case1: ... # Code der Anweisungen1j exit
...casen: ... # Code der Anweisungennexit:
Die Maschinenprogrammebene eines Rechners Jörg Roth 347
Konkretes Beispiel:switch ($t0) case 0: $s3:=$s3+1; case 1: $s4:=2*$s4; case 2: $s5:=0;
Assembler:sll $t0, $t0, 2 # $t0*4 ($t0 sei der switch-Wert)la $t1, jumpTableadd $t0, $t0, $t1 # Berechne switch-Wert*4+Adr(jumpTable)lw $t0, 0($t0) # Lade jumpTable[<switch-Wert>]jr $t0 # Springe gemäß Registerinhalt
case0: addi $s3,$s3,1 # Code für case 0j exit
Die Maschinenprogrammebene eines Rechners Jörg Roth 348
case1: add $s4, $s4, $s4# Code für case 1j exit
case2: li $s5,0 # Code für case 2exit:
Bemerkungen:
■ Es wird keine Überprüfung durchgeführt, ob der switch-Wert innerhalb der erwarteten Grenzen liegt. In der aktuellen Fassung sind die Ergeb-nisse bei einer Bereichsverletzung nicht vorhersehbar (und in der Regel katastrophal).
■ Die Sprungtabelle muss vor der ersten Benutzung initialisiert werden:
Die Maschinenprogrammebene eines Rechners Jörg Roth 349
.datajumpTable:.space 12 # Platz für 3 Adressen
.textmain: la $s0, jumpTable # Adresse der Sprungtabelle in $s0
la $t1, case0sw $t1,0($s0) # Zieladresse in jumpTable[0] ablegenla $t1, case1sw $t1,4($s0) # Zieladresse in jumpTable[1] ablegenla $t1, case2sw $t1,8($s0) # Zieladresse in jumpTable[2] ablegen...
Die Maschinenprogrammebene eines Rechners Jörg Roth 350
Bemerkung: Diese Initialisierung muss nicht zur Laufzeit erfolgen. Viel effizienter ist, die Sprungadressen schon zur Laufzeit durch den Assembler eintragen zu lassen. Die resultierende Code-Variante:
.datajumpTable: .word case0
.word case1
.word case2
.textmain:
... # Code vor switch
Die Maschinenprogrammebene eines Rechners Jörg Roth 351
sll $t0, $t0, 2 # $t0*4 ($t0 sei der switch-Wert)la $t1, jumpTableadd $t0, $t0, $t1 # Berechne switch-Wert*4+Adr(jumpTable)lw $t0, 0($t0) # Lade jumpTable[<switch-Wert>]jr $t0 # Springe gemäß Registerinhalt
case0: addi $s3,$s3,1 # Code für case 0j exit
case1: add $s4, $s4, $s4# Code für case 1j exit
case2: li $s5,0 # Code für case 2exit:
... # Code nach switch
Die Maschinenprogrammebene eines Rechners Jörg Roth 352
5.G.c while- und for-Schleifen
Höhere Programmiersprache:while (<Bedingung>) <Anweisungen>
Assembler:loop: ... # Code um die Bedingung zu berechnen
b... exit # Bedingung, um in die Schleife zu verlassen... # Code der Anweisungenj loop # Schleife wiederholen
exit:
Die Maschinenprogrammebene eines Rechners Jörg Roth 353
Konkretes Beispiel:while ($s1<$s2) $s1:=$s1+1; $s3:=$s3+1;
Assembler:loop: slt $t0, $s1, $s2 # $t0=1 wenn $s1<$s2
beq $t0, $zero, exit # wenn $t0=0: Schleife verlassenaddi $s1,$s1,1 # Code der Anweisungenaddi $s3,$s3,1j loop # Schleife wiederholen
exit:
Die Maschinenprogrammebene eines Rechners Jörg Roth 354
Höhere Programmiersprache:for i:=<startwert> to <endwert> do <Anweisungen>
Assembler:li $t0,<startwert> # Zähler initialisieren, $t0 sei die Zählvariableli $t1,<endwert+1># $t1 sei <endwert+1>
loop: beq $t0,$t1,exit # Endwert schon abgearbeitet... # Code der Anweisungenaddi $t0,$t0,1 # Zähler inkrementieren
j loop # Schleife wiederholenexit:
Bemerkung: diese Konstruktion überprüft nicht, ob der Endwert erreicht werden kann. Gibt man einen endwert<startwert an, rechnet die Schleife bis $t0 nach einem Überlauf den endwert erreicht.
Die Maschinenprogrammebene eines Rechners Jörg Roth 355
Konkretes Beispiel:for $t0:=1 to 10 do $t2:=$t2*2;
Assembler:li $t0,1 # Zähler initialisieren, $t0 sei die Zählvariableli $t1,11 # $t1 sei <endwert+1>
loop: beq $t0,$t1,exit # Endwert schon abgearbeitetadd $t2,$t2,$t2 # Code der Anweisungenaddi $t0,$t0,1 # Zähler inkrementieren
j loop # Schleife wiederholenexit:
Die Maschinenprogrammebene eines Rechners Jörg Roth 356
5.G.dZugriff auf Arrays, Strings
Höhere Programmiersprache:
Schreiben eines Array-Elements:array[index] := wert
Lesen eines Array-Elements:variable := array[index]
Bemerkung: Für die Entwicklung in Maschinensprache muss der Entwick-ler wissen, wie viele Bytes der zugrunde liegende Datentyp beansprucht, um auf ein bestimmtes Element zugreifen zu können. In höheren Programmier-sprachen wird diese Information beim Array-Zugriff verborgen.
Die Maschinenprogrammebene eines Rechners Jörg Roth 357
Konkretes Beispiel:
Variablen: wordarray: ARRAY [0..2] OF WORD = {1, 2, 3};
bytearray: ARRAY[0..2] OF BYTE = {7, 8, 9};
$s0 := wordarray[$t0];
$s1 := bytearray[$t1]:
Assembler:.data
wordarray: .word 1.word 2.word 3
bytearray: .byte 7.byte 8.byte 9
Die Maschinenprogrammebene eines Rechners Jörg Roth 358
.textmain: ...
la $t2, wordarraysll $t0, $t0, 2 # $t0*4 ($t0 sei der Index für wordarray)add $t0, $t0, $t2 # $t0 := wordarray+4*Indexlw $s0, 0($t0) # $s0 := wordarray[$t0]
la $t2, bytearrayadd $t1, $t1, $t2 # $t1 := bytearray+1*Indexlb $s1, 0($t1) # $s1 := bytearray[$t1]
Bemerkung: Es findet keine Erkennung auf Bereichsverletzungen statt. Damit kann man u.U. auf andere Daten oder sogar Code zugreifen. Pro-gramme, die keinen Bereichstest durchführen führen u.U. zu unmotivierten Abstürzen oder sind für bösartige Software angreifbar.
Die Maschinenprogrammebene eines Rechners Jörg Roth 359
Strings
■ Strings werden wie byte-Arrays flexibler Länge behandelt. Die Länge eines Strings erkennt man entweder durch ein spezielles Zeichen (in der Regel 0), wie in der Programmiersprache C oder durch eine vorange-stellte Längenangabe wie in Pascal.
■ Da man einen String häufig zeichenweise durchläuft, bietet es sich an, einen Zeiger auf das aktuelle Zeichen zu verwalten, der zeichenweise weitergeschaltet wird.
Die Maschinenprogrammebene eines Rechners Jörg Roth 360
Möglichkeiten des Zeichenzugriffs in Strings:
h a l l o 0x00Speicher
Register adr 2$t0 $t1
+
Zugriff über zwei Register
h a l l o 0x00Speicher
Register
$t0
Zugriff über einen Zeiger
adr+2
Die Maschinenprogrammebene eines Rechners Jörg Roth 361
Konkretes Beispiel:Variable text: String="halloABC";$s0=strlen(text); // Länge des Strings bestimmentext=toUpper(text); // Alle Zeichen nach "groß" konvertieren (z.B. ’a’-> ’A’)Assembler:
.datatext: .asciiz "halloABC"
.textmain: la $t0,text # Pointer auf String-Anfang setzen
li $s0,0 # Anzahl der Zeichen auf 0 setzenloop1: lb $t1,0($t0) # Lade Zeichen
beq $t1,$zero,toupper # Wenn 0: Zählen fertigaddi $s0,$s0,1 # Weiterzählenaddi $t0,$t0,1 # Pointer weiterschaltenj loop1
Die Maschinenprogrammebene eines Rechners Jörg Roth 362
toupper: la $t0,text # Pointer auf String-Anfang setzenloop2: lb $t1,0($t0) # Lade Zeichen
beq $t1,$zero,end # Wenn 0: fertigandi $t1, $t1, 223 # Nach UpperCase verwandelnsb $t1, 0($t0) # und Zeichen zurückspeichernaddi $t0,$t0,1 # Pointer weiterschaltenj loop2
end:
Die Maschinenprogrammebene eines Rechners Jörg Roth 363
5.G.e Unterprogramme
Unterprogramme können – wie in höheren Programmiersprachen – von ver-schiedenen Aufrufstellen aus aufgerufen werden. So kann man eine häufig benutzte Funktion einmal im Speicher ablegen und beliebig häufig benutzen. Im Gegensatz zu höheren Programmiersprachen muss der Entwickler aber die Organisation des Aufrufs (insb. Rücksprung, Parameterübergabe, Retten von lokalen Variablen) selbst vornehmen.
Die Maschinenprogrammebene eines Rechners Jörg Roth 364
Ablauf von Unterprogramm-Aufrufen:
■ Hinterlegen der Parameter in die vorgesehenen Register ($a0 – $a3).
■ jal Unterprogramm-Label – damit wird die Adresse des nächsten Befehls automatisch in $ra geschrieben.
■ Im Unterprogramm: Wenn notwendig, Register auf Stapel sichern (insb. $s0 – $s7 und $ra).
■ Die eigentliche Funktion berechnen. Potenzielle Rückgabewerte in $v0 – $v1 ablegen.
■ Gesicherte Register zurücklesen.
■ jr $ra – damit wird in das aufrufende Programm zurückgesprungen (genau hinter den Befehl jal...).
Die Maschinenprogrammebene eines Rechners Jörg Roth 365
Beispiel Speicherinhalte tauschen.data
word1: .word 100word2: .word 200word3: .word 400word4: .word 500
.text
main: # Einstiegspunkt des Programmsla $a0,word1 # Tausche word1la $a1,word2 # mit word2jal swap # Unterprogramm "swap" aufrufen
la $a0,word3 # Tausche word3la $a1,word4 # mit word4
Die Maschinenprogrammebene eines Rechners Jörg Roth 366
jal swap # Unterprogramm "swap" aufrufenli $v0, 10 # Programm beendensyscall
swap: # Unterprogramm zum Tauschen von Inhaltenlw $t0, 0($a0) # 1. Wort in Register ladenlw $t1, 0($a1) # 2. Wort in Register ladensw $t0, 0($a1) # umgekehrt zurückspeichernsw $t1, 0($a0)jr $ra # Rücksprung ins aufrufende Programm
Bemerkung:
Da das Unterprogramm swap keine zu sicherernden Register verwendet, ent-fallen die Punkte "Register auf Stapel sichern" und "Gesicherte Register zurücklesen".
Die Maschinenprogrammebene eines Rechners Jörg Roth 367
Verschachtelte Unterprogramme:
Ruft ein Unterprogramm ein weiteres Unterprogramm auf, so muss mindes-tens das Register $ra gesichert werden.
Haupt-programm Unter-
programmUP1jal UP1
Unter-programm
UP2
jr $ra
jal UP2jr $ra
Rücksprungadresse in $ra schreiben
Rücksprungadresse in $ra schreiben
Die Maschinenprogrammebene eines Rechners Jörg Roth 368
Beispiel: Sortieren von exakt drei Speicherinhalten:
Vorgehensweise:
■ Ein Unterprogramm sort2 tauscht zwei Inhalte, wenn sie in der falschen Reihenfolge vorliegen.
■ Ein Unterprogramm sort3 ruft dreimal sort 2 auf mit den Kombinationen (wort1, wort2), (wort2, wort3), (wort1, wort2).
■ Sind diese in der Reihenfolge paarweise sortiert worden, sind alle drei Speicherinhalte sortiert worden.
.data
word1: .word 4word2: .word 3word3: .word 2
Die Maschinenprogrammebene eines Rechners Jörg Roth 369
.text main: # Einstiegspunkt des Programms
la $a0,word1 # Sortieren von word1,la $a1,word2 # word2la $a2,word3 # und word3jal sort3 # Unterprogramm "sort3" aufrufenli $v0, 10 # Programm beendensyscall
sort2: # Sortieren von zwei Speicherinhaltenlw $t0, 0($a0) # 1. Wort in Register ladenlw $t1, 0($a1) # 2. Wort in Register ladenslt $t2,$t0, $t1 # Vergleich Inhaltebne $zero,$t2,ret # $t2=1, also $t0<$t1, dann nicht tauschensw $t0, 0($a1) # sonst umgekehrt zurückspeichernsw $t1, 0($a0)
ret: jr $ra # Rücksprung ins aufrufende Programm
Die Maschinenprogrammebene eines Rechners Jörg Roth 370
sort3: # Sortieren von drei Speicherinhaltenaddi $sp,$sp,-16 # Auf dem Stapel Platz für 4 Register freimachensw $s0,0($sp) # Register $s0, $s1, $s2, $ra auf den Stapelsw $s1,4($sp)sw $s2,8($sp)sw $ra,12($sp) # Wichtig: auch die Rücksprungadresse sichern
move $s0,$a0 # Kopiere die drei Argumente in $s0, $s1, $s2move $s1,$a1move $s2,$a2
jal sort2 # Sortiere Wort1 und Wort2
move $a0,$s1move $a1,$s2
Die Maschinenprogrammebene eines Rechners Jörg Roth 371
jal sort2 # Sortiere Wort2 und Wort3
move $a0,$s0move $a1,$s1jal sort2 # Sortiere nochmal Wort1 und Wort2
lw $s0,0($sp) # Register $s0, $s1, $s2, $ra von dem Stapellw $s1,4($sp)lw $s2,8($sp)lw $ra,12($sp)addi $sp,$sp,16 # Stapelzeiger auf Wert vor dem Aufruf setzenjr $ra # Rücksprung ins aufrufende Programm
Die Maschinenprogrammebene eines Rechners Jörg Roth 372
Bemerkung zu $fp:
■ Bei Funktionen mit vielen Parametern reichen die Register $a0 – $a3 nicht aus. Deshalb kann der Aufrufer die Parameter auch auf dem Stapel hinterlegen.
■ Damit das Unterprogramm bequem auf die Parameter auf dem Stapel zugreifen kann, kann das Register $fp eingesetzt werden. Es zeigt dann auf das Parameter-Wort mit der höchsten Adresse. Dadurch kann mit 0($fp), -4($fp), -8($fp) etc. auf die Parameter zugegriffen werden.
■ Die Verwendung von $fp ist nicht zwingend. Auch sind andere Konventi-onen denkbar, auf die Parameter auf dem Stapel zuzugreifen.
Die Maschinenprogrammebene eines Rechners Jörg Roth 373
Rekursive Unterprogrammaufrufe:
Da die lokalen Register und die Rücksprungadressen auf dem Stapel gespei-chert werden, kann ein Unterprogramm sich selbst aufrufen.
Beispiel Berechnung der Fakultät:
■ x! := x (x-1) (x-2) ... 3 2 1
■ Es gilt: x! = .
Damit kann man die Berechnung von x! rekursiv implementieren.
1 wenn x 1x x 1– ! sonst
Die Maschinenprogrammebene eines Rechners Jörg Roth 374
.textmain:
li $v0, 5 # Eingabe einlesensyscallor $a0, $zero, $v0 # $a0 := Eingabe
### Hier beginnt die Berechnung ###
jal fakultaet
### Hier endet die Berechnung ###or $a0, $zero, $v0 # in $v0 stand das Ergebnisli $v0, 1 # Resultat ausgebensyscallli $v0, 10 # Programm beendensyscall
Die Maschinenprogrammebene eines Rechners Jörg Roth 375
fakultaet:addi $sp,$sp,-12 # Auf dem Stapel Platz für 3 Register freimachensw $s0,0($sp) # Register $s0, $s1, $ra auf den Stapelsw $s1,4($sp)sw $ra,8($sp) # Wichtig: auch die Rücksprungadresse sichern
### Hier beginnt die eigentliche Arbeit des Unterprogramms fakultaet ###
or $s0,$zero,$a0 # Lade Argument in $s0li $s1,1 # Lade 1 in $s1beq $s0,$s1,result1# Ist das Argument=1 fertigaddi $a0,$a0,-1 # Ansonsten: das neue Argument-1
jal fakultaet # fakultaet rekursiv aufrufen
mult $s0,$v0 # Ergebnis mit dem Argument multiplizeren
Die Maschinenprogrammebene eines Rechners Jörg Roth 376
mflo $v0 # und als Ergebnis zurückliefernj end
result1:li $v0,1 # Im Falle Argument=1: 1 zu zurückliefern
end:
### Hier endet die eigentliche Arbeit des Unterprogramms fakultaet ###
lw $s0,0($sp) # Zurücklesen der Register $s0, $s1, $ra lw $s1,4($sp)lw $ra,8($sp)addi $sp,$sp,12 # Stapelzeiger auf Wert vor dem Aufruf setzen
jr $ra # Rücksprung zum Aufrufer