Musterlo ̈sung
U ̈bung2 RAWiSe18/19
Aufgabe 1 (Instruktionssatzarchitekturen)
In dieser Aufgabe sollen verschiedene Rechnerarchitekturen bezu ̈glich der Parameter Co- deeffizienz und Speicherbandbreite verglichen werden. Die Codeeffizienz ist umgekehrt proportional zu dem Speicherbedarf fu ̈r die Instruktionen eines gegebenen Programms. Beno ̈tigt Rechnerarchitektur A weniger Instruktionsspeicher als Rechnerarchitektur B, ist die Codeeffizienz von A ho ̈her. Speziell in eingebetteten Systemen ist die Codeeffizienz ein wichtiger Parameter, da mehr Instruktionsspeicher auch mehr Kosten bedeutet. Die Speicherbandbreite ist in diesem Zusammenhang definiert als die Summe aller zwischen Prozessor und Speicher transferierten Bytes, d. h. Instruktionen und Daten. Je ho ̈her die Speicherbandbreite, umso gro ̈ßer sind die Anforderungen an das Speichersystem.
In diesem Beispiel werden nur Datentransferinstruktionen und die Arithmetikinstruktio- nen add und sub betrachtet. Fu ̈r alle Rechnerarchitekturen soll gelten:
• Der opcode einer Instruktion ist ein Byte lang. • Speicheradressen sind 2 Byte lang.
• Registeradressen sind 4 Bit lang.
• Operanden im Speicher sind 4 Byte lang.
• Die Instruktionsla ̈nge muss ein Vielfaches von einem Byte sein. Zu untersuchen sind folgende Rechnerarchitekturen:
• Akkumulator-Architektur: Es gibt nur ein Register, den Akkumulator. Alle anderen Operanden befinden sich im Speicher. Die zur Verfu ̈gung stehenden Assemblerin- struktionen sind: load, store, add, sub.
• Speicher-Speicher-Architektur : Es gibt keine Register. Alle Instruktionen verwenden ausschließlich Speicheroperanden. Die zur Verfu ̈gung stehenden Assemblerinstruk- tionen sind: add, sub.
• Stack-Architektur: Es gibt keine frei adressierbaren Register, sondern einen Stack. Die zur Verfu ̈gung stehenden Assemblerinstruktionen sind: push, pop, add, sub.
• Register-Register-Architektur: Es gibt eine Reihe frei addressierbarer, interner Regi- ster. Die arithmetischen Instruktionen verwenden ausschließlich Registeroperanden. Die zur Verfu ̈gung stehenden Assemblerinstruktionen sind: load, store, add, sub.
(1) Bestimmen Sie fu ̈r die Codesequenz
a = b + c;
b = a + c;
d = a – b;
Seite 1 / 8
Musterlo ̈sung
U ̈bung2 RAWiSe18/19
fu ̈r jede der Architekturen die entsprechende Assemblercodesequenz. Beachten Sie, dass fu ̈r einen fairen Vergleich der Architekturen alle drei neu berechneten Variablen a, b und d wieder in den Speicher geschrieben werden mu ̈ssen. Stellen Sie fest, wie groß jeweils der Speicherbedarf fu ̈r die Instruktionen ist. Welche Architektur hat die gro ̈ßte Codeeffizienz?
(2) Bestimmen Sie fu ̈r die Assemblercodesequenz in (1) die beno ̈tigte Speicherbandbrei- te fu ̈r jede der Architekturen. Welche Architektur weist die geringste Speicherband- breite auf?
(1) Akkumulator-Architektur:
Assemblercodesequenz:
1:load Adresse_b#a=b+c 2: add Adresse_c
3: store Adresse_a
4: add Adresse_c # b = a + c
5: store Adresse_b
6:load Adresse_a#d=a-b 7: sub Adresse_b
8: store Adresse_d
Speicherbedarf je Instruktion:
Gesamtspeicherbedarf: 8 ∗ 3 Byte = 24 Byte Speicher-Speicher-Architektur:
Assemblercodesequenz:
1: add Adresse_a Adresse_b Adresse_c # a = b + c
2: add Adresse_b Adresse_a Adresse_c # b = a + c
3: sub Adresse_d Adresse_a Adresse_b # d = a – b
Gesamtspeicherbedarf: 3 ∗ 7 Byte = 21 Byte
Musterlo ̈sung
load
1 Byte (opcode) + 2 Byte (Speich.addr.)
3 Byte
store
1 Byte (opcode) + 2 Byte (Speich.addr.)
3 Byte
add
1 Byte (opcode) + 2 Byte (Speich.addr.)
3 Byte
sub
1 Byte (opcode) + 2 Byte (Speich.addr.)
3 Byte
add
1 Byte (opcode) + 3 * 2 Byte (Speich.addr.)
7 Byte
sub
1 Byte (opcode) + 3 * 2 Byte (Speich.addr.)
7 Byte
Seite 2 / 8
Musterlo ̈sung
U ̈bung2 RAWiSe18/19
Stack-Architektur:
Assemblercodesequenz:
1: push Adresse_c # a = b + c
2: push Adresse_b
3: add
4: pop Adresse_a
5: push Adresse_c # b = a + c
6: push Adresse_a
7: add
8: pop Adresse_b
9: push Adresse_b # c = a – b
10: push Adresse_a
11: sub
12: pop Adresse_d
Gesamtspeicherbedarf: 9 ∗ 3 Byte +3 ∗ 1 Byte = 30 Byte Register-Register-Architektur:
Assemblercodesequenz:
1:load Reg1Adresse_b#a=b+c 2: load Reg2 Adresse_c
3: add Reg0 Reg1 Reg2
4: store Reg0 Adresse_a
push
1 Byte (opcode) + 2 Byte (Speich.addr.)
3 Byte
pop
1 Byte (opcode) + 2 Byte (Speich.addr.)
3 Byte
add
1 Byte (opcode)
1 Byte
sub
1 Byte (opcode)
1 Byte
5: add Reg1 Reg0 Reg2
6: store Reg1 Adresse_b
7: sub Reg3 Reg0 Reg1
8: store Reg3 Adresse_d
#b=a+c
#d=a-b
load
1 Byte (opcode) + 4 Bit (Reg.adr.) + 2 Byte (Speich.adr.)
4 Byte
store
1 Byte (opcode) + 4 Bit (Reg.adr.) + 2 Byte (Speich.adr.)
4 Byte
add
1 Byte (opcode) + 3 * 4 Bit (Reg.adr.)
3 Byte
sub
1 Byte (opcode) + 3 * 4 Bit (Reg.adr.)
3 Byte
Gesamtspeicherbedarf: 5 ∗ 4 Byte +3 ∗ 3 Byte = 29 Byte
⇒ Die Speicher-Speicher-Architektur hat den kleinsten Speicherbedarf fu ̈r Instruk- tionen und daher die ho ̈chste Codeeffizienz.
Seite 3 / 8
Musterlo ̈sung
U ̈bung2 RAWiSe18/19
(2) Akkumulator-Architektur
1: load Adresse_b # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
2: add Adresse_c # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
3: store Adresse_a # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
4: add Adresse_c # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
5: store Adresse_b # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
6: load Adresse_a # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
7: sub Adresse_b # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
8: store Adresse_d # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
Speicherbandbreite: 8 ∗ 7 Byte = 56 Byte Speicher-Speicher-Architektur
1: add Adresse_a Adresse_b Adresse_c
# 7 Byte (Inst.) + 3 * 4 Byte (Dat.) = 19 Byte
2: add Adresse_b Adresse_a Adresse_c
# 7 Byte (Inst.) + 3 * 4 Byte (Dat.) = 19 Byte
3: sub Adresse_d Adresse_a Adresse_b
# 7 Byte (Inst.) + 3 * 4 Byte (Dat.) = 19 Byte
Speicherbandbreite: 3 ∗ 7 Byte +3 ∗ 12 Byte = 57 Byte Stack-Architektur
1: push Adresse_c # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte 2: push Adresse_b # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte 3: add # 1 Byte (Inst.) =1Byte 4: pop Adresse_a # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte 5: push Adresse_c # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte 6: push Adresse_a # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte 7: add # 1 Byte (Inst.) =1Byte 8: pop Adresse_b # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte 9: push Adresse_b # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
10: push Adresse_a # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte 11: sub # 1 Byte (Inst.) =1Byte 12: pop Adresse_d # 3 Byte (Inst.) + 4 Byte (Dat.) = 7 Byte
Speicherbandbreite: 9 ∗ 7 Byte +3 ∗ 1 Byte = 66 Byte
Seite 4 / 8
Musterlo ̈sung
U ̈bung2 RAWiSe18/19
Register-Register-Architektur
1: load Reg1 Adresse_b # 4 Byte (Inst.) + 4 Byte (Dat.) = 8 Byte 2: load Reg2 Adresse_c # 4 Byte (Inst.) + 4 Byte (Dat.) = 8 Byte 3: add Reg0 Reg1 Reg2 # 3 Byte (Inst.) =3Byte 4: store Reg0 Adresse_a # 4 Byte (Inst.) + 4 Byte (Dat.) = 8 Byte 5: add Reg1 Reg0 Reg2 # 4 Byte (Inst.) =3Byte 6: store Reg1 Adresse_b # 4 Byte (Inst.) + 4 Byte (Dat.) = 8 Byte 7: sub Reg3 Reg0 Reg1 # 3 Byte (Inst.) =3Byte 8: store Reg3 Adresse_d # 4 Byte (Inst.) + 4 Byte (Dat.) = 8 Byte
Speicherbandbreite: 5 ∗ 8 Byte +3 ∗ 3 Byte = 49 Byte
⇒ Die Architektur mit der geringsten Speicherbandbreite ist die Register-Register-
Architektur.
Aufgabe 2 (Maschinenstruktur)
Auf einer Register-Register-Maschine soll folgende Berechnungen ausgefu ̈hrt werden: 1. c = a – b
2. e = c + d
3. f = d + a
4. g = b + e
Gegeben seien folgende Zugriffszeiten:
• Das Lesen aus einer Speicheradresse beno ̈tige 3 Zeiteinheiten
• Das Schreiben an eine Speicheradresse beno ̈tige 4 Zeiteinheiten • Der Datentransfer zwischen 2 Registern beno ̈tige 1 Zeiteinheit
Die Variablen a, b, d seien zu Beginn im Speicher abgelegt. Die Variablen c, e, f, g sollen nach Beendigung der Rechnung im Speicher stehen.
(1) Bestimmen sie zuna ̈chst die optimale Ausfu ̈hrungsdauer der angegebenen Berech- nung auf einer Register-Register-Maschine mit 4 Registern.
(2) Bestimmen Sie die optimale Ausfu ̈hrungsdauer der angegebenen Berechnung auf einer Register-Register-Maschine mit nur 2 Registern.
Musterlo ̈sung
Seite 5 / 8
Musterlo ̈sung
U ̈bung2 RAWiSe18/19
(1) Register-Registermaschine mit 4 Registern:
Nach Umstellen der Zeilen 2 und 3 la ̈sst sich folgende Tabelle aufstellen:
Reg. 0
Reg. 1
Reg. 2
Reg.3
ZE
LOAD a
a
3
LOAD b
b
3
SUB c,a,b
c
1
LOAD d
d
3
ADD f,d,a
f
1
ADD e,c,d
e
1
ADD g,b,e
g
1
STORE c
4
STORE e
4
STORE f
4
STORE g
4
29
(2) Register-Registermaschine mit 2 Registern:
Wiederum nach Umstellen der Zeilen 2 und 3 la ̈sst sich folgende Tabelle aufstellen:
Reg. 0
Reg. 1
ZE
LOAD a
a
3
LOAD b
b
3
SUB c,a,b
c
1
STORE c
4
LOAD d
d
3
ADD f,d,a
f
1
STORE f
4
LOAD c
c
3
ADD e,c,d
e
1
LOAD b
b
3
STORE e
4
ADD g,b,e
g
1
STORE g
4
35
Seite 6 / 8
Musterlo ̈sung
U ̈bung2 RAWiSe18/19
Aufgabe 3 (U ̈bersetzung von Rekursionen)
Gegeben sei das rekursive C-Programm
int ack(int n, int m)
if (n == 0)
return m + 1;
else
if (m == 0)
return ack(n – 1, 1);
else
return ack(n – 1, ack(n, m – 1));
}
(1) U ̈bersetzen Sie das Beispiel in eine rekursive MIPS-Prozedur. Beachten Sie hierbei folgende Hinweise:
• Treffen Sie sinnvolle Annahmen u ̈ber die notwendigen Register fu ̈r die Argumente und das Resultat.
• Sichern Sie Register vor ihrer Verwendung und stellen Sie die Register anschließend wieder her.
• Verwenden Sie aussagekra ̈ftige Sprungmarken. Musterlo ̈sung
1
Annahme:
• Argument n ist in $a0.
• Argument m ist in $a1.
• Resultat wird in $v0 gespeichert.
Wir unterscheiden die Berechnung in drei Fa ̈lle:
/ m + 1 ack(n,m)={ ack(n-1,1)
wenn n = 0,
Fall A FallB FallC
wennn>0andm=0, \ack(n-1,ack(n,m-1)) wennn>0andm>0.
MIPS Code mit Kommentaren.
1Basiert auf https://gist.github.com/datagrok/760f324bcef80552cbf6
Seite 7 / 8
Musterlo ̈sung
U ̈bung2 RAWiSe18/19
ack:
# Sichern von Registern, die verwendet werden: $ra zur Rekursion. $s0 als Hilfsvariable.
subi $sp, $sp, 8
sw $s0, 4($sp)
sw $ra, 0($sp)
# Stackpointer wird erniedrigt, um Platz zu schaffen.
# $s0 wird an $sp+4 abgelegt.
# $ra wird an $sp+0 abgelegt.
# Ackermann Logik
bgtz $a0, ack_Fall_B # Wenn n > 0, Fall B oder Fall C. Anderenfalls Fall A.
# Fall A: ack(n, m) = m + 1, wenn n = 0.
ack_Fall_A:
addi $v0, $a1, 1 # – Resultat ist $v0 = m + 1
j ack_Ende # – Sprung zum Ende. Resultat ist in $v0.
# Fall B: ack(n, m) = ack(n – 1, 1), wenn n > 0 and m = 0
ack_Fall_B:
bgtz $a1, ack_Fall_C # Wenn m > 0, Fall C. Anderenfalls Fall B.
# Bereite rekursiven Aufruf von ack(n-1, 1) vor.
subi $a0,
li $a1, 1
jal ack
j ack_Ende
$a0, 1
#-Argumentn=n-1in$a0. #-Argumentm=1in$a1.
# – Rekursiver Aufruf von ack(n-1, 1).
# – Sprung zum Ende. Resultat ist in $v0.
#FallC:ack(n,m)=ack(n-1,ack(n,m- 1)),wennn>0andm>0. ack_Fall_C:
# Bereite zwei rekursive Aufrufe vor: ack(n-1, ack(n, m-1))
# – $a0 beinhaltet bereits n. Wir verwenden $s0 als Hilfsvariable/Kopie.
move $s0, $a0 # – Kopiere n nach $s0
# F ̈uhre inneren Aufruf durch: ack(n,m-1)
# – Argument n bereits in $a0.
subi $a1, $a1, 1 # – Argument m = m – 1 in $a1.
jal ack # – Rekursiver Aufruf von ack(n, m-1). Resultat ist in $v0. # F ̈uhre ̈außeren Aufruf durch: ack(n-1, ack(n, m-1)) bzw. ack(n-1, $v0)
subi $a0, $s0, 1
move $a1, $v0
jal ack
# – Argument n = n-1 in $a0 (aus $s0 wiederhergestellt). # – Argument m = ack(n, m-1) in $a1.
# – Rekursiver Aufruf von ack(n-1, ack(n, m-1))
# – Sprung zum Ende nicht notwendig. Da n ̈achster Block.
# Wiederherstellen von Registern, die verwendet wurden: $ra und $s0.
ack_Ende:
lw $s0, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 8
jr $ra
# $s0 wird wiederhergestellt
# $ra wird wiederhergestellt #Stackpointerwirderh ̈oht,umPlatzzuverringern. # Prozedur wird beendet.
Seite 8 / 8