UL/FRI/UNI-RI/ARS1/Izpiti/2004-09-14

Naloga 1

Imamo računalnik s 5 stopenjskim cevovodom (kot HIP), ki operandne nevarnosti odpravlja z vstavljanjem mehurčkov, kontrolne nevarnosti pa ne zazna. Računalnik ima vgrajena ločena direktna predpomnilnika za ukaze in podatke velikosti 16KB z velikostjo bloka 128B. Dostopni čas do predpomnilnikov je 1 urina perioda, zgrešitvena kazen znaša 12 period, Na začetku sta predpomnilnika prazna.

a) koliko urinih period se izvaja spodnji program?

b) Spremenite vrstni red ukazov tako, da se program izvede v čim manj urinih periodah. Program zapišite.

Program:

$00E8026C	    ADDI	R3, R0, #10
$00E80270	    LHI		R5, R0, #$00F0
$00E80274	    ADDUI	R6, R5, #$40E8
$00E80278	    ADDUI	R7, R5, #$C080
$00E8027C    LOOP: LW		R4, 0(R5)	; R4 ← M[R5+0]
$00E80280	    LW		R1, 0(R6)	; R1 ← M[R6+0]
$00E80284	    ADD		R2, R1, R4	; R2 ← R1+R4
$00E80288	    SW		0(R7), R2	; M[R5] ← R2
$00E8028C	    ADDI	R5, R5, #4	; R5 ← R5+4
$00E80290	    ADDI 	R6, R6, #4	; R6 ← R6+4
$00E80294	    ADDI	R7, R7, #4	; R7 ← R7+4
$00E80298	    SUBI	R3, R3, #1	; R3 ← R3-1
$00E8029C	    BNE		R3, LOOP	; če R3 ≠ 0, potem PC ← LOOP
$00E802A0	    NOP
$00E802A4	    NOP

Rešitev

a) Predpomnilnik je tu zelo pomemben. Sta ločena in direktna (to pomeni, da se vsaka lokacija v pomnilniku preslika v točno določen blok predpomnilnika). Pri direktnem predpomnilniku so zato pogoste konfliktne zamenjave bloka.

Če ne upoštevamo predpomnilnika, se program izvaja tako:

$00E8026C	    ADDI	R3, R0, #10
$00E80270	    LHI		R5, R0, #$00F0
                     3 čakalne periode
$00E80274	    ADDUI	R6, R5, #$40E8
$00E80278	    ADDUI	R7, R5, #$C080
$00E8027C    LOOP:  LW		R4, 0(R5)	; R4 ← M[R5+0]
                     pri prvem izvajanju zanke 1 čakalna perioda
$00E80280	    LW		R1, 0(R6)	; R1 ← M[R6+0]
                     3 čakalne periode
$00E80284	    ADD		R2, R1, R4	; R2 ← R1+R4
                     3 čakalne periode
$00E80288	    SW		0(R7), R2	; M[R5] ← R2
$00E8028C	    ADDI	R5, R5, #4	; R5 ← R5+4
$00E80290	    ADDI 	R6, R6, #4	; R6 ← R6+4
$00E80294	    ADDI	R7, R7, #4	; R7 ← R7+4
$00E80298	    SUBI	R3, R3, #1	; R3 ← R3-1
                     3 čakalne periode
$00E8029C	    BNE		R3, LOOP	; če R3 ≠ 0, potem PC ← LOOP
$00E802A0	    NOP
$00E802A4	    NOP

Program se torej izvaja

4up + 4čp + 10*(11up + 9čp) = 208up,

vendar brez upoštevanja predpomnilniških zgrešitev. Ker ima predpomnilnik bloke po 128B, to nanese 32 ukazov/blok. Vsak blok predstavlja torej pomnilniško lokacijo z obliko naslova $xxxxxx00 ali $xxxxxx80.

$00E8026C ukazni predpomnilnik, prenese se 32 ukazov od $00E80200 do $00E80280

$00E80280 ukazni predpomnilnik, prenese se 32 ukazov od $00E80280 do $00E80300

$00F04080 operandni predpomnilnik, prenese se pomnilniška lokacija od $00F04080 do $00F04100

$00F04100 operandni predpomnilnik, 7. ponovitev zanke, prenese se pomnilniška lokacija od $00F04100 do $00F04180

$00F0C080 operandni predpomnilnik, prenese se pomnilniška lokacija od $00F0C080 do $00F0C100

$00F00000 operandni predpomnilnik, prenese se pomnilniška lokacija od $00F00000 do $00F00080

Ker ima procesor direktni predpomnilnik s 64 bloki (16KB/128B), se vsaka pomnilniška lokacija, ki ima zadnjih 13 bitov enakih (64*128), preslika v isti blok. Žal se to pri nas zgodi pri operandnem predpomnilniku:

$00F04080 -> 00000000 11110000 01000000 10000000

$00F0C080 -> 00000000 11110000 11000000 10000000

V sedmi zanki pa je naslov prvega bloka že

$00F04100 -> 00000000 11110000 01000001 00000000

To v praksi pomeni, da imamo pri prvih 6 zankah konfliktne zamenjave bloka.

Če povzamemo:

• 2x zgrešitev ukaznega predpomnilnika
• 12x zgrešitev operandnega predpomnilnika (6x po dve konfliktni zamenjavi)
• 2x zgrešitev operandnega predpomnilnika (obvezna zamenjava, $00F04100 in $00F00000)

To pomeni dodatnih 16*12up = 192 urinih period samo zaradi zgrešitev v predpomnilniku.

Sedaj moramo upoštevati še sočasnost vstavljanja mehurčkov in čakanja zaradi zgrešitve v ukaznem predpomnilniku, zato ne upoštevamo 1 čakalne periode za ukazom LW R4,0(R5).

Torej skupno izvajanje traja 208up + 192up - 1up = 399up

b) Še čaka.

Ta del članka je potrebno dopolniti oz. popraviti. Urednik strani te snovi ni razumel oz. je ne zna pravilno. Iščejo se prostovoljci, ki bodo to popravili.

Naloga 2

Imamo MIMD računalnik z 32 procesorji, na katerem se izvajajo programi dveh vrst. Programi prve vrste se lahko izvajajo maksimalno vzporedno (na vseh procesorjih hkrati), programi druge vrste pa le strogo zaporedno (izkoristijo le 1 procesor).

a)Kolikšen del časa lahko tak računalnik poganja strogo zaporedne programe, da bo za celotno množico programov doseženih 50% maksimalne možne hitrosti?

b)S spremembo algoritmov smo strogo zaporedne aplikacije uspeli pohitriti za dvakrat. Kolikšna je zdaj skupna pohitritev izvajanja aplikacij, če se prej omenjene dvakrat pohitrene zaporedne aplikacije izvajajo enak odstotek časa kot v točki a?

Rešitev

a) Rešujemo z amdahlovim zakonom: delež časa izvajanja strogo zaporednih programov je 1/31 b) Glede na točko a je pohitritev le 1,64%, skupna pohitritev (s stališča enoproc.računalnika) pa je potem 1626%

Naloga 3

Računalnik ima 8-bitne pomnilniške besede in navidezni pomnilnik s čistim ostranjevanjem z naslednjimi lastnostmi:

• dolžina navideznega naslova je 41 bitov,
• dolžina fizičnega naslova je 32 bitov.

Določite optimalno velikost strani, če dodatni parametri V, P, RWX in C v deskriptorju v tabeli strani zasedejo 7 bitov, povprečna velikost programa pa je 27MB (1M = 10^6). Kakšna bi bila optimalna velikost strani, če bi bil povprečni program dolg 1MB, 100MB?

Rešitev