ELEKTRONSKI FAKULTET U NIŠU
Predmet: ARHITEKTURE RAČUNARA
Katedra za računarstvo
ZADACI SA REŠENJIMA
Zadatak AOR 1.
Vaša kompanija koristi benčmark program koji se smatra reprezentativnim za vaše
tipične aplikacije. Jedan od starijih modela računara nema jedinicu za aritmetiku sa pokretnom zapetom i
mora emulirati svaku instrukciju sa pokretnom zapetom nizom celobrojnih instrukcija. Stari model
računara je pri izvršenju benčmark programa procenjem na 120 MIPS-a. Nezavisni isporučilac opreme
nudi numerički koprocesor koji bi ovom računaru mogao produžiti život. Ovaj numerički koprocesor
izvršava instrukcije sa pokretnom zapetom, tako da emulacija nije potrebna. Pri izvršenju benčmark
programa računar sa pridruženim numeričkim koprocesorom procenjuje se na 80 MIPS-a. Koristiti
sledeće oznake za odgovore na pitanja a. do e.
I - broj celobrojnih instrukcija izvršenih u benmark programu,
F - broj instrukcija sa pokretnom zapetom izvršenih u benmark programu,
Y - broj celobrojnih instrukcija izvršenih radi emulacije jedne instrukcije sa pokretnom zapetom,
W - vreme za izvršenje benmark programa na računaru bez koprocesora,
B - vreme za izvršenje benmark programa na računaru sa numeričkim koprocesorom.
a.
Izvesti izraze za procenu MIPS-ova za obe konfiguracije koristeći date oznake.
b.
Za konfiguraciju bez koprocesora izmereno je F=8*10
6
, Y=50 i W=4s. Naći I.
c.
Kolika je vrednost B?
d.
Koliki je iznos MFLOPS-a sistema sa koprocesorom?
e.
Vaš kolega želi da kupi numerički koprocesor čak iako je procenjena MIPS vrednost za
konfiguraciju sa koprocesorom manja nego bez njega. Da li je procena vašeg kolege dobra? Obrazložite
svoj odgovor.
Rešenje:
MIPS
S
=120, MIPS
N
=80, F=8
10
6
, Y=50, W=4s.
a. MIPS
S
= (I+F
Y)/(W
10
6
) ; MIPS
N
= (I+F)/(B
10
6
)
b. Iz (I+F
Y)/(W
10
6
) =120,
I = 120
W
10
6
F
Y = 120
4
10
6
8
10
6
50 = 80
10
6
c. Iz (I+F)/(B
10
6
) = 80 je
B = (I+F)/(80
10
6
) = (80 + 8)
10
6
/(80
10
6
) = 1,1 sec.
d. MFLOPS = F/ (T
FPOP
10
6
) , gde je T
FPOP
vreme potrebno za izvršenje F operacija sa pokretnom
zapetom. Vreme T
FPOP
možemo naći ako od vremena B oduzemo vreme T
I
potrebno za izvršenje I
integer instrukcija. To vreme možemo dobiti iz
T
I
= I/ (MIPS
S
10
6
) = 80
10
6
/ (120
10
6
) = 2/3 = 0,67 sec.
T
FPOP
= B
T
I
= 1,1
0.67 = 0,43 sec.
MFLOPS = F/ (T
FPOP
10
6
) = 8
10
6
/(0,43
10
6
) = 18,6
Procena kolege je dobra jer računar sa numeričkim koprocesorom izvršava programe za kraće
vreme nego računar bez numeričkog koprocesora.
Zadatak AOR 2.
Za novu arhitekturu računara predložena su dva poboljšanja koja daju povećanja
brzine PB1 = 20 i PB2 = 10. Ova poboljšanja odnose se na delove koji se pri radu računara ne preklapaju.
a) Izvesti izraz za Amdahl-ov zakon koji definiše ukupno poboljšanje za dati slučaj, tj. u situaciji kad
postoje dva poboljšana dela. Korišćenjem ovog izraza rešiti delove zadatka pod b i c.
b) Ako su poboljšanja 1 i 2 primenljiva svako u po 30% vremena rada, izračunati njihov uticaj na ukupno
povećanje brzine?
c) Neka je poboljšanje 1 primenljivo na 40% vremena rada. Na koji deo vremena rada treba primeniti i
poboljšanje 2, da bi uz istovremenu primenu oba poboljšanja ukupno povećanje brzine bilo 4?
Rešenje:
PB
1
=20, PB
2
=10,
a) T
N
= T
S
[(1- PD
1
- PD
2
)+ PD
1
/ PB
1
+ PD
2
/ PB
2
]
PB
U
= T
S
/ T
N
= 1/[(1- PD
1
- PD
2
)+ PD
1
/ PB
1
+ PD
2
/ PB
2
]
b) Za PD
1
= PD
2
= 0,3
PB
U
= 1/[(1- 0,3- 0,3)+ 0,3/ 20+ 0,3/ 10] = 2,247
c) Za PD
1
= 0,4 PB
U
= 4 PD
2
= ?
1- PD
1
- PD
2
+ PD
1
/ PB
1
+ PD
2
/ PB
2
= 1/ PB
U
PD
2
(1-1/ PB
2
) = 1- PD
1
+ PD
1
/ PB
1
- 1/ PB
U
PD
2
= [1- PD
1
+ PD
1
/ PB
1
- 1/ PB
U
]/ (1-1/ PB
2
) = 0,411= 41,1%
Zadatak AOR 3.
Razmotriti 2 različite implementacije
procesora, P1 i P2, istog skupa instrukcija, u kome
postoje 4 klase instrukcija (A, B, C i D). U tablici je
prikazano koliko ciklusa traje svaka od klasa za oba
procesora. Procesor P1 radi na učestanosti od 2 GHz, dok
procesor P2 radi na učestanosti od 3 GHz. Kolike su
maksimalne vrednost MIPS-eva za P1 i P2? Ako su
instrukcije u nekom benchmark programu podjednako
raspoređene po klasama, koji procesor brže izvršava dati program? Kolike su vrednosti MIPS-
eva u ovom slučaju? Ako se pomenuti benchmark program smatra reprezentativnim za programe
koje ćete koristiti, za koji biste se procesor odlučili? Zašto?
Rešenje:
P1: f
C1
= 2 GHz , P2: f
C2
= 3 GHz
MIPS= N/(T·10
6
) = N/(N·CPI·T
C
·10
6
) = f
C
/(CPI·10
6
)
Maksimalne vrednosti MIPS-eva dobijaju se ako se uzmu programi koji sadrže samo instrukcije
sa najmanjom vrednošću CPI-a:
MIPS
1max
= f
C1
/(CPI
1A
·10
6
) = 2·10
9
/(1·10
6
) = 2·10
3
[miliona instr./sec]
MIPS
2max
= f
C2
/(CPI
2A
·10
6
) = 3·10
9
/(2·10
6
) = 1,5·10
3
[miliona instr./sec]
Kada su instrukcije u nekom benchmark programu podjednako raspoređene po klasama:
CPI
1sr
= (CPI
1A
+ CPI
1B
+ CPI
1C
+ CPI
1D
)/4 = (1+2+3+4)/4 = 2,5
CPI
2sr
= (CPI
2A
+ CPI
2B
+ CPI
2C
+ CPI
2D
)/4 = (2+2+4+4)/4 = 3,0
MIPS
1sr
= f
C1
/(CPI
1sr
·10
6
) = 2·10
9
/(2,5·10
6
) = 0,8·10
3
[miliona instr./sec]
MIPS
2sr
= f
C2
/(CPI
2sr
·10
6
) = 3·10
9
/(3,0·10
6
) = 1,0·10
3
[miliona instr./sec]
Odlučili bi se za procesor P2 jer on brže izvršava programe ovog tipa.
Zadatak AOR 4.
Program P izvršava se na računaru M, koji radi na 1 GHz, za 10 sec. Izvršena
je optimizacija programa P tako što je svaka instrukcija množenja neke vrednosti X sa 4 (MUL
X,X,4) zamenjena sa dve instrukcije sabiranja te iste vrednosti (ADD X,X,X ; ADD X,X,X).
Nazovimo ovaj optimizovani program P’. CPI za instrukciju množenja je 4, a za instrukciju
sabiranja je 1. Sa ovom optimizacijom, program P’ se na računaru M izvršava za 9 sec. Koliko
instrukcija množenja je u programu P zamenjeno parovima instrukcija sabiranja u programu P’ ?
Rešenje
Za program P imamo T
P
= 10 s, f
C
=1 GHz, CPI
MUL
= 4 TC.
Za program P’ imamo
T
P’
= 9 s, MUL X,X,4
ADD X,X,X; ADD X,X,X; CPI
ADD
= 1 TC.
U programu P možemo izdvojiti operacije množenja sa množiocem 4, kojih ima k, i ostale
operacije sa vremenom izvršenja T
ost
.
T
P
= T
ost
+ k
CPI
MUL
T
C
= 10 s
T
P'
= T
ost
+ k
2
CPI
ADD
T
C
= 9 s
T = T
P
-T
P'
= k
(CPI
MUL
-2
CPI
ADD
)
T
C
odakle je
k =
T /
(CPI
MUL
-2
CPI
ADD
)
T
C
=
T
f
C
/( CPI
MUL
-2
CPI
ADD
)
k = 1
10
9
/(4-2
1) =10
10
8
/2 = 5
10
8
operacija množenja.
Klasa
instrukcija
Ciklusa
za P1
Ciklusa
za P2
A
1
2
B
2
2
C
3
4
D
4
4
c. LDI R5, #0
Pon LW R6, (R3+R5)
ADD R6,R6,R2
SW R6, (R4+R5)
ADDI R5,R5, #4
DEC R1
BNEZ R1, Pon
d. Neka u ovom delu zadatka umesto računara sa Load/Store arhitekturom imamo računar
sa registarsko+memorijkom arhitekturom. Neka se adrese komponenata vektora B i A
čuvaju u memorijskim lokacijama sa adresama PB i PA respektivno. Aritmetičko-logičke
instrukcije dopuštaju da izvorišni i odredišni operandi budu u memoriji.
LDI R1, #100
LW R2, (C)
MOV (PB), #VB
M[PB]
adresa VB
MOV (PA), #VA
M[PA]
adresa VA
Pon ADD @(PA),@(PB),R2
M[M[PA]]
M[M[PB]] + R2
INC (PB), 4
M[PB]
M[PB] + 4
INC (PA), 4
M[PA]
M[PA] + 4
DEC R1
BNEZ R1, Pon
Zadatak AOR 7.
Dat je zapis sa sledećim elementima:
a.
short (*0x 2122 polureč*);
b.
array [1..7 ] of char (*ABCDEFG
bajt*);
c.
doubleint (*0x 4142434445464748
dvostruka reč*);
d.
array [1..3 ] of char (*AKS
bajt*);
e.
integer (*0x 11121314 reč*);
Prikazati smeštanje ovog zapisa u memoriji počev od adrese 0x00 u mašinama sa adresiranjem repa i
adresiranjem glave. Memorijske lokacije su dužine 8 B (dvostruka reč). Pristupi memoriji su poravnati.
Navesti podatke koji se dobijaju pri obraćanju podacima dužine jednog bajta sa adresama 0x03, 0x05,
0x1E i podacima dužine dva bajta (polureči) sa adresama 0x12 i 0x1C pri adresiranju glave i adresiranju
repa.
Rešenje:
Adrese
Podatak(adresiranje repa)
Podatak (adresiranje glave)
0x03
B
B
0x05
D
D
0x1E
12
13
0x12
45 46
43 44
0x1C
13 14
11 12
7
6
5
4
3
2
1
0
0x
(adresa)
F E D C B A
21 22
00
G
08
41 42 43 44 45 46 47 48
10
11 12 13 14
S
K
A
18
Prikaz za adresiranje repa
0x
(adresa)
0
1
2
3
4
5
6
7
00
21 22 A B C D
E
F
08
G
10
41 42 43 44 45 46 47 48
18
A K S
11 12 13 14
Prikaz za adresiranje glave
Zadatak AOR 8.
Promene stanja bloka upravljanja nekog
digitalnog sistema prikazane su tablicom 1, a aktivirani
upravljački signali (ima ih 8) tablicom 2. S0 je početno, a S6 je
krajnje stanje bloka upravljanja. Ovako opisani blok upravljanja
realizovati elementima
za kašnjenje i
potrebnim logičkim
elementima
.
Rešenje
Dijagram promene stanja (graf stanja) bloka upravljanja dobija se direktno prema tablici 1. Sekvencijana
mreža bloka upravljanja formira se na osnovu pravila izloženih u odeljku 3.6.2 knjige. Upravljački signali
y
2,
y
5,
y
6,
y
7
i
y
8
dobijaju se direktno sa izlaza D flip-flopova koji daju odgovarajuća stanja. Upravljački
signali
y
1,
y
3
i
y
4,
koji se aktiviraju iz više stanja, dobijaju se sa izlaza ILI logičkih elemenata čiji su ulazi
izlazi D flip-flopova koji daju odgovarajuća stanja.
Stanje
S
i
Aktivirani
upravlj. sign.
S
0
y
1
S
1
y
2
, y
3
S
2
y
1
, y
4
S
3
y
7
S
4
y
4
, y
5
S
5
y
3
, y
6
S
6
y
8
Tablica 2
x
1
x
2
S
0
S
1
S
2
S
3
S
4
S
5
S
6
0
0
S
0
S
2
S
2
S
4
S
4
S
3
S
6
0
1
S
3
S
1
S
3
S
1
S
5
S
4
S
0
1
0
S
2
S
3
S
4
S
2
S
5
S
6
S
0
1
1
S
1
S
2
S
1
S
5
S
3
S
4
S
6
Tablica 1
odgovarajućih upravljačkih signala i taktne cikluse u kojima upravljačke signale treba aktivirati,
tako da oni mogu da realizuju i instrukciju JM (Jump Memory) kojom se skače na instrukciju
određenu sadržajem adresirane memorijske lokacije. Iskoristiti format instrukcije LW, s tim da
se rt polje ne koristi jer se podatkom iz memorije puni PC umesto odredišnog registra.
JM rs, pom sa dejstvom PC
M[R[rs] + zp(pom)]
Rešenje
JM rs, pom sa dejstvom PC ← M[R[rs] + zp(pom)]
Fetch MAR, A ← PC :
(T0) RegSel=100, RegRd, MARWr, Ō/J=0, AWr;
B ← 4 :
(T0) Ē/F=1, BWr;
IR ← M[MAR ] :
(T1) MemRd, IRWr;
PC ← A+B :
(T2) ALUCont=”+”, IzALU, RegSel=100, RegWr;
Dekodirati instrukciju: (T2);
JM
A ← R[rs] :
(T3) RegSel=000, RegRd, Ō/J=0, AWr;
B ← zp(pomer) :
(T4) ExtOp=1, IzPro{, Ē/F=0, BWr;
MAR ← A+B :
(T5) ALUCont=”+”, IzALU, MARWr;
PC ← M[MAR ] :
(T6) MemRd, RegSel=100, RegWr;
go to Fetch:
(T6) ASM=ap(Fetch);
Zadatak AOR 10.
Kombinaciona logika prikazana na slici sastoji se od šest blokova
kombinacionih mreža A, B, C, D, E i F sa vremenima prostiranja signala kroz njih od 80 ps, 30
ps, 60 ps, 50 ps, 70 ps i 10 ps respektivno. Izlazni signali iz poslednjeg bloka F upisuju se u
registar sa vremenom prostiranja 20 ps. Možemo projektovati protočnu verziju ove mreže
umetanjem protočnih registara sa vremenom prostiranja 20 ps između parova ovih blokova, čime
ovih šest blokova delimo u stepene.
a) Između kojih blokova treba umetnuti jedan protočni registar da formiramo protočnu
verziju mreže sa dva stepena koja će imati maksimalnu propusnost za toliki broj stepena?
Kolika će biti latencija i propusnost takve mreže?
b) Između kojih blokova treba umetnuti dva protočna registra da formiramo protočnu
verziju mreže sa tri stepena koja će imati maksimalnu propusnost za toliki broj stepena?
Kolika će biti latencija i propusnost takve mreže?
c) Između kojih blokova treba umetnuti tri protočna registra da formiramo protočnu verziju
mreže sa četiri stepena koja će imati maksimalnu propusnost za toliki broj stepena?
Kolika će biti latencija i propusnost takve mreže?
IR
A
B
A L U
Polje
registara
(32 registra
op{ te namene
+ PC)
Memorija
Magistrala
ALU
Cont
MUX
Pro{ irenje
ExtOp
funct
IzPro{
AWr
O/J
E/F
rs
RegSel
rt
rd
31(Link)
32(PC)
IRWr
Kod
oper.
BWr
Zero?
MARWr
MAR
IzPom
IzReg
MemRd
RegWr
MemWr
adresa
adresa
podatak
podatak
IzALU
ALUOp
<<2
2
2
4
4
28
26
3
Ze
ro
Zaposlena
AL
Ur
ez
MUX
0
1
MUX0
1
1 0
2
3
4
<<
2
IzA
