Vraag 1 (4 punten) Gegeven het getal -132 Wat is de voorstelling van dit getal 1. in teken/grootte (16 bit) 2. in 2’s complementvoorstelling (16 bit) 3. als 2’s complementvoorstelling (8 bit) a. saturerend b. modulo 8 bit Antwoord (alle antwoorden in hexadecimaal)
1 2 3a 3b
Vraag 2 (4 punten) Gegeven het getal 251 Hoe kan je dit getal voortellen als 1. 2. 3. 4.
Binair getal (16 bits) 2’s complement getal (16 bits) packed BCD-getal floating point getal (1|5|10), vergelijkbaar met ANSI/IEEE 754
Antwoord (in hexadecimale notatie aub)
1 2 3 4
Vraag 3 (4 punten) Gegeven het bitpatroon 11011010 Wat is de waarde als 1. binair getal 2. 2’s complementgetal 3. verschoven getal (bias = 40) 4. vlottende-kommagetal (1|2|3), vergelijkbaar met het IEEE formaat. Antwoord
1 2 3 4
Vraag 4 (4 punten) Bereken het resultaat en de toestandsbits voor de volgende twee 8-bit optellingen: Opgave
Resultaat C-vlag S-vlag O-vlag
10001100 + 11101011
10000000 + 10000000
Vraag 5 (4 punten)
A
Gegeven de volgende combinatorische schakeling
B C Stel de waarheidstabel van deze schakeling op (2 punten)
Schrijf deze functie als een som van producten (mintermen) (1 punt)
D= Vereenvoudig deze uitdrukking zo ver mogelijk (minimalisatie) (1 punt)
D=
D
Vraag 6 (4 punten) Beschouw het volgende programma: #include <stdio.h> int g; int faculteit(int n) { if (n<2) return 1; else return n*faculteit(n-1); } int main() { g = faculteit(3); return 0; } :0040125C :0040125D :0040125F :00401260 :00401263 :00401266 :00401268 :0040126A :0040126B :0040126D :0040126F :00401270 :00401271 :00401276 :00401277 :00401278 :00401279 :0040127C :0040127D :0040127E :0040127F :00401280 :00401282 :00401287 :00401288 :0040128D :0040128F
55 89E5 57 8B7D08 83FF02 7D05 31C0 40 EB10 89F8 48 50 E8E6FFFFFF 59 57 97 0FAFC7 5F 5F 5D C3 6A03 E8D5FFFFFF 59 A304204000 31C0 C3
push mov push mov cmp jnl xor inc jmp mov dec push call pop push xchg imul pop pop pop ret push call pop mov xor ret
ebp ebp,esp edi edi,[ebp+08] edi,2 0040126D eax,eax eax 0040127D eax,edi eax eax 0040125C ecx edi edi,eax edi edi edi ebp 3 0040125C ecx [00402004],eax eax,eax
Vragen: 1. Op welk adres bevindt zich de veranderlijke g? (1 punt)
2. Hoeveel instructies worden er door dit programma uitgevoerd? (1 punt)
3. Teken de stapel op het ogenblik dat de instructie op adres 0040126A net achter de rug is (leg uit wat de verschillende cellen precies betekenen) (2 punten).
Vraag 7 (4 punten) Gegeven het volgende stukje escape-code.
doel_3 doel_2 doel_1
| | | | | | | | | | | | |
ADDI BRZ BRZ BRZ ADDI ADDI HALT ADDI HALT ADDI HALT ADDI HALT
R0, R0, R0, R0, R0, R0,
0x0000, R1 doel_1 doel_2 doel_3 0x0005, R1 0x0004, R1
R0, 0x0003, R1 R0, 0x0002, R1 R0, 0x0001, R1
De uitvoering van het programma begint bovenaan het codefragment. De instructie BRZ R0, doel_x is een onvoorwaardelijke sprong naar doel_x (maar wel met 2 delay slots). De instructie addi R0,n,R1 schrijft de constante n in het register R1. Teken het pijplijnactiviteitendiagramma voor de uitvoering van dit stukje programma: Tijd
Fetch
Decode
Execute
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Wat zal de uiteindelijke waarde van R1 zijn?
Mem
Write back
Vraag 4 (4 punten)
Gegeven het volgende stukje escape-code. 0000: 0004: 0008: 000C: 0010: 0014: 0018: 001C: 0020: 0024: 0028: 002C: 0030:
44020004 4401000C 0C230000 1C611800 24431800 18230040 20220800 0C230000 18230040 20220800 7C01FFDC 00000000 00000000
| | | loop1 | | | | | | | | | |
| | | | | | | | | | | | |
ADDI ADDI LDW ADD MUL STW SUB LDW STW SUB BRGE NOP NOP
R0, R0, R3, R3, R2, R3, R1, R3, R3, R1, R1,
0x0004, R2 0x000C, R1 0x0000(R1) R1, R3 R3, R3 0x0040(R1) R2, R1 0x0000(R1) 0x0040(R1) R2, R1 loop1
1. Ga uit van de situatie waarbij er geen forwarding is, het aantal cycli voor een geheugenoperatie 1 is, en er geen delay slots zijn. Schrijf voor elke instructie (net voor het verticale lijntje) hoeveel cycli ze vertraagd zal worden door het niet gebruiken van forwarding (u hoeft geen rekening te houden met het herbetreden van de lus). Indien de instructie niet vertraagd wordt, hoeft U geen 0 te schrijven. De aantallen die U schrijft corresponderen met het aantal NOP-instructies die U vóór de instructie zou moeten plaatsen om een blokkering te vermijden (2 punten). 2. Indien forwarding wel aan staat, en indien er 2 delay slots zouden zijn, op welke manier zou U het programma transformeren om er gebruik van te maken. U mag bijkomende registers aanwenden indien U dit nodig acht. Schrijf de code hieronder neer (2 punten).
Vraag 8 (4 punten) Gegeven het volgende stuk assemblercode. vijfvoud: cmp jg xor ret positief: mov imul ret programma: mov call mov
eax,0 positief eax, eax ebx, 5 ebx
eax, 6 vijfvoud g, eax
Stel dat de Pentium 1 delayslot zou toelaten. Op welke manier zou dit stukje programma kunnen versneld worden door optimaal gebruik te maken van de delayslots?
Vraag 9 (4 punten) Gegeven een datacache van 4 lijnen van 8 bytes lang. Een programma genereert een lijst van leesopdrachten van 1 byte op de volgende (decimale) adressen (kolom Adres). ¾ Vul in de kolom Blok het bloknummer van het adres is (0,1,2,3,...). ¾ Vul voor Lijn de identificatie van de lijn is (b.v. a,b,c,d) ¾ Vul in de kolommen Inhoud de inhoud van de cache in (uitgedrukt in bloknummers) vlak na de cachetoegang (bij associativiteit steeds LRU als vervangingsstrategie gebruiken) ¾ Vul in de kolommen H/M in of het over een hit of een miss gaat. ¾ Vul in de kolom set de identificatie van de gebruikte set in (b.v. A of B)
Opdrachten
Direct mapped cache
Volledig associatief
2-Wegs set associatief
Adres
Lijn
Inhoud
Set
-
Blok
Inhoud
H/M
-| -|-|-
H/M
- - - -
Inhoud
- - | - -
16
|
|
|
|
8
|
|
|
|
12
|
|
|
|
24
|
|
|
|
20
|
|
|
|
40
|
|
|
|
11
|
|
|
|
12
|
|
|
|
48
|
|
|
|
51
|
|
|
|
10
|
|
|
|
16
|
|
|
|
Wat zijn de hit-rates van de drie verschillende caches?
H/M
Vraag 10 (4 punten) Beschouw het volgende Pascal-programma program examen; type arraytype = array[1..10] of integer; var a: arraytype; i, g: integer; function som(a: arraytype): integer; var s, i: integer; begin s := 0; for i := 1 to 10 do s := s + a[i]; som := s; end; begin for i := 1 to 10 do a[i] := i; g := som(a) end.
Verbeter de vier fouten in de bijhorende assembercode: :00403874 :00403875 :00403876 :00403879 :0040387B :0040387E :00403883 :00403885 :00403887 :0040388C :0040388E :00403890 :00403893 :00403894 :00403896 :00403898 :0040389B :0040389C
56 57 83C4D8 8BF0 8D3C24 B90A000000 F3A5 33C9 BA0D000000 8BC4 0308 83C004 4A 75F8 8BC1 83C428 5F 5E
push push add mov lea mov rep xor mov mov add add dec jne mov add pop pop
esi edi esp,FFFFFFD0 esi,eax edi,[esp] ecx,0000000A movsd ecx,ecx edx,0000000A eax,esp ecx,[eax] eax,00000008 edx bca.14 (0040388E) eax,ecx esp,00000028 edi esi
:00403900 :00403905 :0040390A :0040390C :0040390D :00403910 :00403913 :00403915 :0040391A :0040391F
BA01000000 B8D0544000 8910 42 83C004 83FA0B 75F5 B8D0544000 E855FFFFFF 8BD0
mov mov mov inc add cmp jne mov call mov
edx,00000001 eax,004054D0 [eax],edx edx eax,00000004 edx,0000000B bca.20 (0040390A) eax,00405FFF bca.som (00403874) edx,eax
Vraag 11 (4 punten) Gegeven een computersysteem met een onderbrekingssysteem met prioriteiten. Dit wil zeggen dat indien er een onderbreking met hogere prioriteit is, deze als eerste uitgevoerd wordt, en eventuele onderbrekingen van lagere prioriteit zal onderbreken. Gegeven de volgende onderbrekingen: onderbreking 5 3 7
aankomst 2 4 5
verwerkingsduur 4 3 5
De prioriteiten zijn als volgt: 3 > 5 > 7 Gesteld dat het hoofdprogramma begint te lopen op tijdstip 0. Teken het activiteitendiagramma voor de verschillende stukjes programma. main 5 3 7
Vraag 12 (4 punten) Gegeven het volgende recursieve C-programmaatje #include <stdio.h> long fact(long n) { if (n>0) return n*fact(n-1); else return 1; } main() { long g = fact(3); }
Compilatie op de alpha-architectuur (gcc –O4 –S) geeft het volgende resultaat: $fact:
$L3:
lda stq stq mov bgt lda br
$30,-16($30) $26,0($30) $9,8($30) $16,$9 $9,$L3 $0,1 $31,$L9
subq bsr mulq
$9,1,$16 $26,$fact $9,$0,$0
ldq ldq lda ret
$26,0($30) $9,8($30) $30,16($30) $31,($26),1
lda stq lda bsr mulq
$30,-16($30) $26,0($30) $16,2 $26,$fact $0,3,$17
$L9:
main:
Uitleg: lda : load effective address stq: store quadword niet-conditionele controletransfers: tweede argument=bestemming, eerste argument=terugkeeradres. $30 = stapelwijzer
Teken de stapel voor dit programma op het ogenblik dat de LDA $0,1 instructies uitgevoerd wordt.
Welke optimalisatie valt U er op? Had men deze optimalisatie nog verder kunnen doortrekken? Hoe zou het programma er dan uiteindelijk hebben kunnen uitzien (1 punt)
Vraag 13 (4 punten) Beschouw het volgende pascal-programma: program examen; var g: integer; function hack(n: integer): integer; var a: array[1..1] of integer; i: integer; begin if n > 0 then begin i := 2; a[i] := a[i] - 5; hack := n-1 end else hack := n end; begin g := hack(1) end.
Met de bijhorende assembercode: :00403874 :00403875 :00403877 :00403879 :0040387E :00403883 :00403884 :00403885 :004038E9 :004038EE :004038F3
51 85C0 7E0B BA02000000 836C94FC05 48 5A C3 B802000000 E881FFFFFF 8BD8
push test jle mov sub dec pop ret mov call mov
ecx eax,eax examen.18 (00403884) edx,00000002 dword ptr [esp+4*edx-04],05 eax edx eax,00000001 examen.hack ebx,eax
Beschrijf de uitvoering van dit programma als een trace (lijst van uitgevoerde instructies)
Aantal instructies
Vraag 14 (4 punten) Beschouw het volgende C-programma int ggd(int a, int b) { if (a==0) return b; else if (a>b) return ggd(a % b, b); else return ggd(b % a, a); } int main() { ggd(45,60); }
Verbeter de vier fouten in de bijhorende assembercode: :0040125C :0040125D :0040125F :00401260 :00401261 :00401264 :00401266 :00401268 :0040126B :0040126D :00401270 :00401272 :00401275 :00401276 :00401278 :0040127A :0040127B :0040127D :0040127E :00401283 :00401286 :00401288 :00401289 :0040128C :0040128D :0040128F :00401290 :00401295 :00401298 :00401299 :0040129A :0040129B :0040129C :0040129E :004012A0 :004012A5
55 89E5 56 57 8B7508 09F6 7505 8B450C EB2B 3B750C 7E16 8B7D0C 57 89F0 89F9 99 F7F9 52 E8D9FFFFFF 83C408 EB10 56 8B450C 99 F7FE 52 E8C7FFFFFF 83C408 5F 5E 5D C3 6A3C 6A2D E8B7FFFFFF 83C408
push mov push push mov or jne mov jmp cmp jle mov push mov mov cdq idiv push call add jmp push mov cdq idiv push call add pop pop pop ret push push call add
ebp esp,ebp esi edi esi,[ebp+08] esi,esi 0040126D eax,[ebp+0C] 00401299 esi,[ebp+0C] 00401288 edi,[ebp+0C] edi eax,esi ecx,edi ecx eax 0040125C esp,8 00401298 esi eax,[ebp+0C] esi edx 0040125C esp,8 edi esi ebp 3C 2D 0040125C esp,4
Vraag 15 (4 punten) Gegeven het volgende C-programma: #include <stdio.h> float g; float gemiddelde(float a, float b) { return (a+b)/2.0; } int main() { g = gemiddelde(1.3,1.7); return 0; } :00401279 :0040127A :0040127C :0040127D :00401283 :00401286 :00401289 :0040128F :00401292 :00401295 :0040129A :0040129D :004012A3 :004012A4
55 89E5 51 D9053C404000 83EC04 D91C24 D90538404000 83EC04 D91C24 E8C2FFFFFF 83C408 D91D04204000 C9 C3
push mov push fld sub fstp fld sub fstp call add fstp leave ret
ebp ebp,esp ecx dword ptr[0040403C] esp,4 dword ptr[esp] dword ptr[00404038] esp,4 dword ptr[esp] 0040125C esp,8 dword ptr[00402004]
:0040125C :0040125D :0040125F :00401262 :00401265 :0040126B :0040126C
55 89E5 D9450C D84508 DC3548404000 5D C3
push mov fld fadd fdiv pop ret
ebp ebp,esp dword ptr[ebp+0C] dword ptr[ebp+08] dword ptr[00404048] ebp
1. op welke manier worden de argumenten a en b aan de functie gemiddelde doorgegeven? 2. op welke manier wordt het resultaat van de functie gemiddelde geretourneerd?
3. op welke manier wordt de constante 2.0 in het programma opgenomen?
4. wat is de grootte (in bytes) van de vlottende-kommagetallen die hier gebruikt worden?
Vraag 16 (4 punten) Gegeven een harddisk met een effectieve bandbreedte van 33 MB/s. De communicatie met de harddisk gebeurt in blokken van 4 kiB. Per bloktransfer dient er een onderbrekingsroutine opgeroepen te worden die 25 µs duurt. Vraag 1: welk percentage van de tijd zal de processor gemiddeld bezig zijn met het afhandelen van de bloktransfers indien de maximale bandbreedte gehaald wordt?
Vraag 2: hoelang zal een taak die in normale omstandigheden 60 ms duurt nu duren?
Vraag 3: Indien deze taak niet langer dan 70 ms mag duren, tot welke waarde moet de maximale bandbreedte dan beperkt worden?
Vraag 17 (4 punten) Beschouw het volgende C-programma: #include <stdio.h> #include <string.h> int paswoord_ok() { char *secret="wachtwoord"; char s[10];
}
printf("geef wachtwoord: "); gets(s); return !strcmp(s,secret);
int main() { return paswoord_ok(); }
Met de bijhorende assembercode: :0040125C :0040125D :0040125F :00401262 :00401263 :00401264 :0040126A :0040126D :00401272 :00401277 :0040127A :0040127D :0040127E :00401283 :00401286 :00401289 :0040128C :0040128D :00401295 :00401297 :0040129A :0040129C :004012A1 :004012A3 :004012A8 :004012AA :004012AB :004012AC :004012AD
55 89E5 83EC10 53 57 8D3D4E404000 897DFC 683C404000 E891000000 83C404 8D7DF2 57 E86D000000 83C404 FF75FC 8D7DF2 57 E89A000000 89C7 83FF00 7507 BB01000000 EB05 BB00000000 89D8 5F 5B C9 C3
push mov sub push push lea mov push call add lea push call add push lea push call mov cmp jne mov jmp mov mov pop pop leave ret
ebp ebp,esp esp,10 (hexadecimaal!) ebx edi edi,[0040404E] [ebp-04],edi 0040403C printf esp, 4 edi,[ebp-0E] edi gets esp, 4 dword ptr [ebp-04] edi,[ebp-0E] edi strcmp edi,eax edi,0 004012A3 ebx,1 004012A8 ebx,0 eax,ebx edi ebx
:004012AE :004012AF :004012B4 :004012B7
57 E8A8FFFFFF 83C404 C3
push call add ret
edi 0040125C esp,4
Opgave 1. Teken de stapel op het ogenblik dat de instructie 00401295 uitvoert. Ter informatie: de functie strcmp respecteert alle oproepconventies die in de rest van dit programma gebruikt worden (2pt)
2. Welke inputstring zou U moeten ingeven om ervoor te zorgen dat strcmp tweemaal dezelfde string vergelijkt en als gevolg hiervan steeds hetzelfde antwoord teruggeeft (2pt). De stackframepointer (ebp) tijdens de uitvoering van de functie paswoord_ok is: 0012FF50.
