336 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice Delay = 2 cicli. b) aplicând forwarding Delay = 0 cicli. (necesar R 1 la… [610350]

12. INDICATII DE SOLUTIONARE
1.
A. i1: LOAD R 1, 9(R 5)
i2: ADD R6, R1, R3
a)
Delay = 2 cicli.
b) aplicând forwarding
Delay = 1 ciclu.
B. i1: ADD R1, R6, R7
i2: LOAD R5, 9(R 1)
a)
336 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
Delay = 2 cicli.
b) aplicând forwarding
Delay = 0 cicli. (necesar R 1 la începutul fazei ALU a i2 pentru
calcularea adresei de memorie de unde va fi citita
data; daca modul de adresare ar fi indirect registru,
R1 ar fi necesar doar la începutul fazei MEM, deci
între cele doua instructiuni dependente RAW mai
poate exista înca o a treia fara a implica penalizari)
2. i1: SUB Rk, Ri, #4
i2: LOAD Rk, (R k+0)
i3: ADD Rk, Rk, #12
i4: ADD Rl, #5, R j
i5: LOAD R l, (R l+0)
i6: XOR Rl, Rl, Rk
i7: AND Rm, Rk, Rl
a)
651
2
3Rk
Rk4
Rl
Rl
Rk
7Rl
Rk

Indicatii de solutionare 337
b)
Delay = 1 ciclu.
1 – nop – 2 – nop – 3 – 4 – nop – 5 – nop – 6 – nop – 7  Tex = 12
cicli executie.
c) 1 – 4 – 2 – 5 – 3 – nop – 6 – nop – 7  Tex = 9 cicli executie.
d) Aplicând forwarding-ul rezulta Delay = 0 cicli Secventa se executa:
1 – 4 – 2 – 5 – 3 – 6 – 7  Tex = 7 cicli executie.
3.
a)IRmax = 2 instr. / ciclu.
FR = 4 instr. / ciclu  fiind 20 instructiuni de executat  vor fi 5 accese
(citiri) la IC.
RmissIC = 40% 2 accese la IC vor fi cu miss. Consideram primele 2
accese la cache.
Configuratia buffer-ului de prefetch în fiecare ciclu de executie:
C1 – se executa în 10 cicli (primul miss în IC – aducere instructiuni din
memoria principala); în buffer nefiind nici o instructiune nu se executa
nimic.
C2 – se executa în 10 cicli (al doilea miss în IC – aducere instructiuni din
memoria principala); în buffer sunt instructiuni, se executa i1 si i2.338 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
C3 – se executa în 2 cicli (nu se face fetch instructiune nefiind spatiu
disponibil în buffer); în buffer sunt instructiuni, se executa i3 datorita
dependentelor RAW dintre i3 si i4.
C4 – se executa în 2 cicli (hit în IC – aducere instructiuni din cache); se
executa i4 si i5.
C5 – se executa în 2 cicli (nu se face fetch instructiune nefiind spatiu
disponibil în buffer); se executa i6 datorita dependentelor RAW dintre
i6 si i7.
C6 – se executa în 2 cicli (hit în IC – aducere instructiuni din cache); se
executa i7 si i8.
C7 – se executa în 2 cicli (nu se face fetch instructiune); se executa i9 si i10.
C8 – se executa în 2 cicli (nu se face fetch instructiune); se executa i11
datorita dependentelor RAW dintre i11 si i12.
C9 – se executa în 2 cicli (hit în IC – aducere instructiuni din cache); se
executa i12 si i13.
C10 – se executa în 2 cicli (nu se mai face fetch instructiune – s-au adus
toate instructiunile); se executa i14 si i15.
C11 – se executa în 2 cicli; se executa i16 si i17.
C12 – se executa în 2 cicli; se executa i18 si i19.
C13 – se executa în 2 cicli; se executa i20 – s-a golit buffer-ul nu mai sunt
instructiuni de executat.
Tex = 10 (C1) + 10 (C2) + 2 (C3) + 2 (C4) + 2 (C5) + 2 (C6) + 2 (C7) + 2
(C8) + 2 (C9) + 2 (C10) + 2 (C11) + 2 (C12) + 2 (C13) = 42 impulsuri
de tact
IR = 20 instr. / 42 imp. = 0,476 instr. / tact
b)IRmax = 4 instr. / ciclu.
Configuratia buffer-ului de prefetch în fiecare ciclu de executie:

Indicatii de solutionare 339
Tex = 10 (C1) + 10 (C2) + 2 (C3) + 2 (C4) + 2 (C5) + 2 (C6) + 2 (C7) + 2
(C8) = 32 impulsuri de tact
IR = 20 instr. / 32 imp. = 0,625 instr. / tact
Cresterea performantei = (IR(4) – IR(2)) / IR(2) = 31%
4.
a) MOV R10, R6
ST (R9), R6
b) ADD R3, R5, #4 /* Calculeaza adresa pentru ST */
ADDR4, R6, #8 /* Calculeaza adresa pentru LD */
LD R9, 8(R6) /* Daca adresele difera efectuam anticipat LD */
BEQ R3, R4, et /* Daca adresele sunt egale, salt pentru a încarca
în R9 valoarea corecta (R8)*/
J end
et: MOV R9, R8
end: ST 4 (R5), R8 /* Daca adresele coincid sau nu se memoreaza R8
la adresa ceruta */
5.
a) MOV R6, R7
ADD R3, R6, R5Ra) MOV R6, R7
ADD R3, R7, R5
b) MOV R6, #4
ADD R7, R10, R6
LD R9, (R7)Rb) MOV R6, #4
ADD R7, R10, #4
LD R9, 4(R10)
c) MOV R6, #0
ST 9(R1), R6Rc) MOV R6, #0
ST 9(R1), R0
d) MOV R5, #4
BNE R5, R3, LabelRd) MOV R5, #4
BNE R5, #4, Label
e) ADD R3, R4, R5
MOV R6, R3Re) ADD R3, R4, R5
ADD R6, R4, R5340 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
6.
a) IRmax = 4 instr. / ciclu.
FR = 4 instr. / ciclu  fiind 32 instructiuni de executat  vor fi 8 accese
(citiri) la IC.
RmissIC 1 = 50% 4 accese la IC vor fi cu miss. Consideram primele 4
accese la cache.
Configuratia buffer-ului de prefetch în fiecare ciclu de executie:
C1 – se executa în 10 cicli (primul miss în IC – aducere instructiuni din
memoria principala); în buffer nefiind nici o instructiune nu se executa
nimic.
C2 – se executa în 10 cicli (al doilea miss în IC – aducere instructiuni din
memoria principala); în buffer sunt instructiuni, se executa i1, i2 si i3.
C3 – se executa în 10 cicli (al treilea miss în IC – aducere instructiuni din
memoria principala); în buffer sunt instructiuni, se executa i4, i5 si i6
datorita dependentelor RAW dintre i6 si i7.
C4 – se executa în 10 cicli (al patrulea miss în IC – aducere instructiuni din
memoria principala); se executa i7, i8, i9 si i10.
C5 – se executa în 2 cicli (nu se face fetch instructiune nefiind spatiu
disponibil în buffer); se executa i11 datorita dependentelor RAW
dintre i11 si i12.
C6 – se executa în 2 cicli (hit în IC – aducere instructiuni din cache); se
executa i12, i13, i14 si i15.
C7 – se executa în 2 cicli (hit în IC); se executa i16 si i17 datorita
dependentelor RAW dintre i17 si i18.
C8 – se executa în 2 cicli (hit în IC); se executa i18, i19, i20 si i21.
C9 – se executa în 2 cicli (nu se face fetch instructiune nefiind spatiu
disponibil în buffer); se executa i22 datorita dependentelor RAW
dintre i22 si i23.
C10 – se executa în 2 cicli (hit în IC); se executa i23, i24, i25 si i26.

Indicatii de solutionare 341
C11 – se executa în 2 cicli; (nu se mai face fetch instructiune – s-au adus
toate instructiunile); se executa i27 datorita dependentelor RAW
dintre i27 si i28.
C12 – se executa în 2 cicli; se executa i28, i29, i30 si i31.
C13 – se executa în 2 cicli; se executa i32 – s-a golit buffer-ul nu mai sunt
instructiuni de executat.
Tex = 10 (C1) + 10 (C2) + 10 (C3) + 10 (C4) + 2 (C5) + 2 (C6) + 2 (C7) + 2
(C8) + 2 (C9) + 2 (C10) + 2 (C11) + 2 (C12) + 2 (C13) = 58 impulsuri
de tact
IR = 32 instr. / 58 imp. = 0,55 instr. / tact
b)FR = 8 instr. / ciclu  fiind 32 instructiuni de executat  vor fi 4 accese
(citiri) la IC.
RmissIC 2 = 50% RmissIC 1RmissIC 2 = 25%  1 acces la IC va fi
cu miss. Consideram primul acces la cache.
Configuratia buffer-ului de prefetch în fiecare ciclu de executie:
Tex = 10 (C1) + 2 (C2) + 2 (C3) + 2 (C4) + 2 (C5) + 2 (C6) + 2 (C7) + 2
(C8) + 2 (C9) + 2 (C10) + 2 (C11) + 2 (C12) + 2 (C13) + 2 (C14) = 36
impulsuri de tact
IR = 32 instr. / 36 imp. = 0,89 instr. / tact
Cresterea performantei = (IR(FR=8) – IR(FR=4)) / IR(FR=4) = 61,8%
(substantiala).
Limitarea prformantei consta în capacitatea buffer-ului de prefetch egala cu
rata de fetch ( IBS=FR ).342 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
7.
a)
Delay = 1 ciclu.
1 – nop – 2 – 3 – 4 – nop – 5 – 6 – nop – 7 – 8 – nop – 9 – nop – 10  Tex =
15 cicli executie.
b) Dupa aplicarea tehnicii de renaming la registrul R 1 în instructiunea i8
obtinem:
i8: ADD R1’, R13, R14
i9: DIV R1’, R1’, #2
i10: STORE (R i), R 1’62
4
5Rj
R2
8
R1
WAR(R 1)1
Ri
WAR(R 1)3
R1Ri
R1
R2
79
10R4
R1Ri

Indicatii de solutionare 343
1 – 8 – 2 – 3 – 4 – 9 – 5 – 6 – 10 – 7  Tex = 10 cicli executie.
c) Prin înlocuirea registrilor R 13 cu R 3 si R 14 cu R 4, secventa realizeaza
determinarea maximului dintre elementele x[i] si x[i+4] ale unui sir de date
stocat în memorie. Se obtine formula:
2 x[i]4] x[i x[i])4] (x[i4]) x[i max(x[i],
8.
a)
Secventa se executa astfel:
1 – 2 – nop – 3 – nop – 4 – 5 – nop – 6 – nop – 7  Tex = 11 cicli executie.
b) Se aplica tehnica de renaming pe ramura 5 – 6 – 7  R3 = R 3’.
Astfel având 3 unitati ALU la dispozitie executia secventei ar fi urmatoarea:
Nr. Tact Instructiuni executate în paralel
1 – 2 – 5
3 – 6
4 – 7
Tex = 3 cicli executie.1
3
4R1
R52 (WAW)R 3
765
R3
R8R3R3
(WAW)R 3
(WAR)R 3344 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
9.
a) Da. La startarea sistemului se încarca programul încarcator care verifica
perifericele, citeste informatii din EPROM. E posibil sa existe hit la citire
din cache care nefiind initializat contine “prostii ”si daca nu ar exista bitul
de validare (V) sistemul ar prelua valoarea din cache eronata.
b) O exceptie Page Fault implica întotdeauna o exceptie TLB miss.
Reciproc, nu e obligatoriu.
10.a) Rezultate statistice bazate pe simulari laborioase pe benchmark-uri
reprezentative (SPEC '95, '00) arata ca un basic-block contine doar 4-5
instructiuni în medie, ceea ce înseamna ca rata de fetch (FR) a
instructiunilor e limitata la cca. 5, aducerea simultana a mai multor
instructiuni fiind inutila (fetch bottleneck). Aceasta limitare fundamentala ar
avea consecinte defavorabile si asupra ratei medii de executie a
instructiunilor (IR – Issue Rate) întrucât IR FR. Cercetarile actuale insista
peîmbunatatirea mecanismelor de aducere a instructiunilor prin
urmatoarele tehnici:
predictia simultana a mai multor ramificatii / tact rezultând deci rate IR
sporite.
posibilitatea accesarii si aducerii simultane a mai multor basic- block-
uri din cache, chiar daca acestea sunt nealiniate, prin utilizarea unor
cache-uri multiport.
pastrarea unei latente reduse a procesului de aducere a instructiunilor,
în contradictie cu cele 2 cerinte anterioare.
Alti factori care determina limitarea ratei de fetch a instructiunilor
sunt: largimea de banda limitata a interfetei procesor – cache, missurile în
cache, predictiile eronate ale ramificatiilor.
O solutie interesanta fata de limitarile mai sus mentionate, o constituie
trace-procesorul , adica un procesor superscalar având o memorie trace-
cache (TC). Ca si cache-urile de instructiuni (IC), TC este accesata cu
adresa de început a noului bloc de instructiuni ce trebuie executat, în paralel
cu IC. În caz de miss în TC, instructiunea va fi adusa din IC sau – în caz de
miss si aici – din memoria principala. Spre deosebire însa de IC, TC
memoreaza instructiuni contigue din punct de vedere al secventei lor de
executie, în locatii contigue de memorie. O linie din TC memoreaza un
segment de instructiuni executate dinamic si secvential în program (trace-
segment). Evident, un trace poate contine mai multe basic-block-uri (unitati
secventiale de program). Asadar, o linie TC poate contine N instructiuni sau
M basic- block-uri, N>M, înscrise pe parcursul executiei lor.

Indicatii de solutionare 345
b) Hazardurile constituie acele situatii care pot sa apara în procesarea
pipeline si care pot determina blocarea (stagnarea) procesarii, având deci o
influenta negativa asupra ratei de executie a instructiunilor. Conform unei
clasificari consacrate hazardurile sunt de 3 categorii : hazarduri structurale,
de date (RAW, WAR si WAW) si de ramificatie.
Considerând instructiunile i sij succesive, hazardul RAW (Read
After Write) apare atunci când instructiunea j încearca sa citeasca o sursa
înainte ca instructiunea i sa scrie în aceasta. Pentru o procesare corecta,
instructiunea j trebuie stagnata cu un ciclu masina. Solutia software consta
în inserarea unei instructiuni NOP între i sij (umplerea " delay slot "-ului)
sau a unei alte instructiuni utile, independenta de instructiunea i. O alta
modalitate de rezolvare consta în stagnarea hardware a instructiunii i,
stagnare determinata de detectia hazardului RAW de catre unitatea de
control. Realizarea întârzierii hardware se poate baza pe tehnica
"scoreboarding " propusa pentru prima data de catre Seymour Cray (1964 –
CDC 6600). Se impune ca fiecare registru al procesorului din setul de
registri sa aiba un " bit de scor " asociat. Daca bitul este zero, registrul
respectiv e disponibil, daca bitul este 1, registrul respectiv este ocupat. Daca
pe un anumit nivel al procesarii este necesar accesul la un anumit registru
având bitul de scor asociat pe 1, respectivul nivel va fi întârziat, permitându-
i-se accesul doar când bitul respectiv a fost sters de catre procesul care l-a
setat. De remarcat ca ambele solutii bazate pe stagnarea fluxului
(software – NOP sau hardware – semafoare) au acelasi efect defavorabil
asupra performantei.
Exista situatii în care hazardul RAW se rezolva prin hardware fara sa
cauzeze stagnari ale fluxului de procesare. Aceste tehnici de rezolvare se
numesc tehnici forwarding (bypassing) bazate pe "pasarea anticipata" a
rezultatului instructiunii i, nivelului de procesare aferent instructiunii j care
are nevoie de acest rezultat. În implementarea controlului mecanismelor de
forwarding, pot apare si situatii conflictuale care trebuiesc rezolvate pe baza
dearbitrare-prioritizare .
Scheduler-ul HSS [VinFlor00] (dezvoltat la universitatea din
Hertfordshire) foloseste tehnica “merging ”pentru a depasi limitarile
introduse prin dependentele reale de date. Aceasta implica combinarea a
doua instructiuni într-una singura. Exista trei categorii de astfel de
instructiuni. Prima categorie, numita MOV Merging implica o pereche de
instructiuni în care prima din ele este MOV. A doua categorie numita
Immediate Merging se caracterizeaza prin faptul ca ambele instrutiuni au
ca operanzi sursa valori immediate. A treia categorie se numeste MOV
Reabsorption si are ca a doua instructiune o instructiune MOV sau
instructiunea ce se va infiltra va fi convertita la tipul primei instructiuni.346 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
MOV Merging
Secventa initiala:
MOV R6, R7
ADD R3, R6, R5Secventa modificata:
MOV R6, R7; ADD R3, R7, R5
Immediate Merging
Secventa initiala:
SUB R3, R6, #3
ADD R4, R3, #1Secventa modificata:
SUB R3, R6, #3; ADD R4, R6, #-2
MOV Reabsorption
Secventa initiala:
ADD R3, R4, R5
MOV R6, R3Secventa combinata:
ADD R3, R4, R5; ADD R6, R4, R5
c) În cadrul arhitecturii lui Tomasulo , detectia hazardurilor si controlul
executiei instructiunilor sunt distribuite iar rezultatele instructiunilor sunt
"pasate anticipat" direct unitatilor de executie prin intermediul unei
magistrale comune numita CDB (Common Data Bus). Statiile de Rezervare
(SR) detin câmpuri de TAG (de identificare) necesare în controlul
hazardurilor de date între instructiuni. Qj, Qk – codifica pe un numar de biti
unitatea de executie (ADD, MUL, etc.) sau numarul bufferului LB (aferent
instructiunilor Load), care urmeaza sa genereze operandul sursa aferent
instructiunii din SR. Daca acest câmp este zero, rezulta ca operandul sursa
este deja disponibil într-un câmp Vi sau Vj al SR sau pur si simplu nu este
necesar. Câmpurile Qj, Qk sunt pe post de TAG, adica atunci când o unitate
de executie sau un buffer LB "paseaza" rezultatul pe CDB, acest rezultat se
înscrie în câmpul Vi sau Vj al acelei SR al carei TAG coincide cu numarul
sau numele unitatii de executie sau bufferului LB care a generat rezultatul.
Arhitectura lui Tomasulo nu ar functiona corect fara câmpurile de tag Qj,
Qk deoarece în cazul unei dependente RAW între instructiuni acestea ar
stagna pâna când registrii (operanzii necesari) sunt înscrisi în setul de
registri generali (la finele fazei WB si nu la finele EX/MEM cum ar fi fost
daca existau cele doua câmpuri de TAG).
11. Daca alegem strategia Greedy obtinem rata de procesare
cicluinstr 0,27113IR
Daca alegem strategia non – Greedy rata de procesare obtinuta este:
cicluinstr 0,2541IR

Indicatii de solutionare 347
În acest caz e mai avantajos sa alegem stategia Greedy.
13. a) Procesarea vectoriala reprezinta prelucrarea informatiei numerice sub
forma de vectori. Ea urmareste în principiu cresterea ratei de procesare la
nivelul programului, fiind deci o tehnica de exploatare a paralelismului la
nivelul datelor din program . De multe ori arhitecturile vectoriale se
întâlnesc în literatura sub numele de sisteme SIMD.
Datorita dependentelor de date existente (rezultatul x depinde si de
valoarea sa de la pasul anterior), secventa nu este vectorizabila. Timpul de
executie este T=201 cicli (O atribuire, 100 de înmultiri si 100 de adunari).
Secventa modificata implica folosirea unui registru vectorial
suplimentar dar care permite vectorizarea partiala a buclei.
x = 0
for i = 1 to 100 do //vectoriz abila
C[i]= A[i]*B[i]
endfor
for i = 1 to 100 do //nevectorizabila
x = x + C[i];
Timpul de executie este substantial ameliorat T=102 cicli (O atribuire, 1
înmultire vectoriala si 100 de adunari). Timpul de procesare se
îmbunatateste substantial prin vectorizarea partiala a buclei348 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
b)
c) Arhitectura lui Tomasulo a fost proiectata si implementata pentru prima
data în cadrul unitatii de calcul în virgula mobila din cadrul sistemului IBM
– 360/91. Arhitectura este una de tip superscalar având mai multe unitati de
executie, iar algoritmul de control al acestei structuri stabileste relativ la o
instructiune adusa, momentul în care aceasta poate fi lansata în executie si
respectiv unitatea de executie care va procesa instructiunea. Logica de

Indicatii de solutionare 349
detectie a hazardurilor este distribuita. Arhitectura permite executia multipla
si Out of Order a instructiunilor si constituie modelul de referinta în
reorganizarea dinamica a instructiunilor într-un procesor superscalar.
Algoritmul de gestiune aferent arhitecturii permite anularea hazardurilor
WAR si WAW printr-un ingenios mecanism hardware de redenumire a
registrilor. Acest lucru este posibil pentru ca resursele tip sursa folosite si
aflate în starea "BUSY", nu se adreseaza ca nume de registri ci ca nume de
unitati de executie ce vor produce aceste surse. Mecanismul de forwarding
din arhitectura lui Tomasulo, are meritul de a reduce semnificativ din
presiunea la "citire" asupra setului general de registri logici, speculând
dependentele RAW între instructiuni.
14. a) În procesul de proiectare al procesoarelor, aferent generatiilor
viitoare, accentul principal nu se mai pune pe implementarea hardware, ci
pe proiectarea arhitecturii în strânsa legatura cu aplicatiile potentiale. Se
porneste de la o arhitectura de baza (generica), puternic parametrizata, care
este modificata si îmbunatatita dinamic, prin simulari laborioase pe
programe de test (benchmark-uri) reprezentative. Figura 0.1. "Etapele de
simulare, comparare si determinare efectiva ale unei arhitecturi optime,
pornind de la sursa HLL (High Level Languages) a programelor de test si
pâna la implementarea hardware a arhitecturii " din cadrul prezentei
lucrari evidentiaza tocmai pasii ceruti.
Codul original sursa (în limbajul C/Fortran) al benchmarkului este
trecut întâi printr-un cross-compilator (de exemplu generatorul de cod
obiect “gnuCC ”sub Unix) care produce formatul corect al codului în
mnemonica de asamblare, precum si directive de asamblare, comenzi de
alocare a memoriei etc. Optional, codul rezultat în acest punct poate fi
“rearanjat ”prin intermediul unui scheduler , care împacheteaza
instructiunile în grupuri de instructiuni independente. Codul obiect rezultat
este trecut printr-un simulator execution driven puternic parametrizabil,
care produce la iesire un fisier trace de instructiuni. Acesta reprezinta
totalitatea instantelor dinamice, aferente instructiunilor statice (codul masina
al benchmark-urilor în mnemonica de asamblare) scrise în ordinea executiei
lor. În final, aceste trace-uri constituie intrari pentru simulatorul trace
driven , de asemenea parametrizabil, care genereaza parametrii completi
aferenti procesarii, pentru determinarea optimului de performanta în
anumite conditii de intrare.
b) Problema optimizarii programelor în vederea procesarii lor pe arhitecturi
superscalare si VLIW este una de mare interes în cercetarea actuala.
Optimizarea se refera în general la 2 aspecte: optimizarea locala, adica în
cadrul unitatilor secventiale de program (basic-block-uri) si respectiv350 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
optimizarea globala, adica a întregului program. Optimizarea locala a basic-
block-urilor se realizeaza folosind algoritmi cvasioptimali într-o singura
trecere, de tip "List Scheduling" (LS). Optimizarea globala a programului se
bazeaza pe algoritmi deterministi de tip "Trace Scheduling" sau pe algoritmi
euristici de tip "Enhanced Percolation". Paralelismul la nivelul basic-block-
urilor, este relativ scazut (2-3 instructiuni). Deoarece majoritatea
programelor HLL sunt scrise în limbaje imperative si pentru masini
secventiale cu un numar limitat de registre în vederea stocarii temporare a
variabilelor, este de asteptat ca gradul de dependente între instructiunile
adiacente sa fie ridicat. Asadar pentru marirea nivelului de paralelism este
necesara suprapunerea executiei unor instructiuni situate în basic-block-uri
diferite ( software pipelining ,loop unrolling ), ceea ce conduce la ideea
optimizarii globale. Problema optimizarii globale este de natura NP –
completa.
c) Arhitecturile MEM sunt implementate în doua variante distincte:
procesoare superscalare si respectiv procesoare VLIW (very large
instruction word). În varianta superscalara cade în sarcina hardului sa
verifice independenta instructiunilor aduse în buffer-ul de prefetch si sa le
lanseze în executii multiple spre unitatile de executie pipeline-izate.
Caracteristic procesoarelor superscalare este faptul ca dependentele de date
între instructiuni se rezolva prin hardware, în momentul decodificarii
instructiunilor. Desigur ca aceste arhitecturi au o complexitate hardware
deosebita determinata de detectia si solutionarea hazardului între
instructiuni. Complexitatea logicii de detectie a independentei
instructiunilor ce se doresc a fi lansate în executie simultan, creste
proportional cu patratul numarului de instructiuni. De asemenea, ele sunt
limitate în posibilitatea de a exploata paralelismul la nivelul instructiunilor,
de capacitatea limitata a buffer-ului de prefetch. La ora actuala, pe plan
comercial, piata este dominata de microprocesoarele superscalare, în
principal datorita dezideratelor de compatibilitate între versiunile din cadrul
aceleiasi familii. La procesoarele VLIW, mai rare decât cele superscalare, în
implementari comerciale, cade în sarcina compilatorului de a reorganiza
programul original în scopul “împachetarii ”într-o singura instructiune
multipla a mai multor instructiuni RISC primitive si independente, care vor
fi alocate unitatilor de executie în conformitate stricta cu pozitia lor în
instructiunea multipla. Un procesor VLIW aduce mai multe instructiuni
primitive simultan si le lanseaza în executie concurent spre unitatile
functionale deja alese de compilator (scheduler). Acest model de procesor
nu mai necesita sincronizari si comunicatii de date suplimentare între
instructiunile primitive dupa momentul decodificarii lor, fiind astfel mai
simplu din punct de vedere hardware decât modelul superscalar.

Indicatii de solutionare 351
Dificultatile principale ale modelului VLIW sunt urmatoarele
[VinFlor00]:
Paralelismul limitat al aplicatiei, ceea ce determina ca unitatile de
executie sa nu fie ocupate permanent, fapt valabil de altfel si la modelul
superscalar.
Incompatibilitate software cu modele succesive si compatibile de
procesoare care nu pot avea în general un model VLIW identic datorita
faptului ca paralelismul la nivelul instructiunilor depinde de latentele
operatiilor procesorului scalar, de numarul unitatilor functionale si de alte
caracteristici hardware ale acestuia.
Dificultati deosebite în reorganizarea aplicatiei (scheduling) în vederea
determinarii unor instructiuni primitive independente sau cu un grad
scazut de dependente.
Cresterea complexitatii hardware si a costurilor ca urmare a resurselor
multiplicate, cailor de informatie "latite".
Cresterea necesitatilor de memorare ale programelor datorita
reorganizarilor soft si "împachetarii" instructiunilor primitive în cadrul
unor instructiuni multiple care necesita introducerea unor instructiuni
NOP (atunci când nu exista instructiuni de un anumit tip disponibile spre
a fi asamblate într-o instructiune multipla).
De remarcat ca modelele superscalar si VLIW nu sunt exclusive, în
implementarile reale se întâlnesc adesea procesoare hibride, în încercarea de
a se optimiza raportul performanta pret (HSA, IA64).
Caracteristica principala a arhitecturii HSA (Hatfield Superscalar
Architecture) o constituie exploatarea paralelismului la nivelul instructiunii,
într-un mediu superscalar, prin schedulling agresiv aplicat codului sursa în
momentul compilarii. Scheduler-ul dezvoltat la Universitatea din
Hertfordshire, UK (HSS – Hatfield Superscalar Scheduler) [VinFlor00] a
fost implementat ca parte integranta a proiectului HSA (Hatfield Superscalar
Architecture) – o arhitectura superscalara minima care combina cele mai
bune caracteristici ale conceptelor VLIW si superscalare. HSS rearanjaza
codul HSA scris în limbaj de asamblare pentru a forma grupuri de
instructiuni care pot fi expediate în paralel unitatilor functionale în
momentul executiei.
16. a) Ideal ar fi ca un sistem paralel dotat cu N procesoare sa proceseze un
program de N ori mai rapid decât un sistem monoprocesor, cerinta numita
scalabilitate completa . În realitate, acest deziderat de scalabilitate nu se
realizeaza din multiple motive. În privinta scalabilitatii, aceasta este mai
usor de realizat pe un sistem cu resurse distribuite decât pe unul având
resurse centralizate, întrucât acestea din urma constituie un factor de352 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
“strangulare ”a activitatii. Dintre cauzele care stau în calea unei scalabilitati
ideale, se amintesc [VinFlor00]:
Gradul de secventialitate intrinsec al algoritmului executat. Exista în
cadrul unui algoritm operatii secventiale dependente de date si deci
imposibil de partajat în vederea procesarii lor paralele pe mai multe
procesoare. Legea lui Amdahl sugereaza ca un procentaj ( fx100%) oricât
de scazut de calcule secventiale impune o limita superioara a accelerarii
(1/f) care poate fi obtinuta pentru un anumit algoritm paralel pe un sistem
paralel de calcul, indiferent de numarul N al procesoarelor din sistem si
topologia de interconectare a acestora.
Timpul consumat cu sincronizarea si comunicarea între procesele
rezidente pe diversele ( )procesoare din sistem.
Imposibilitatea balansarii optimale a activitatii procesoarelor din sistem,
adica frecvent nu se poate evita situatia în care anumite procesoare sa fie
practic inactive sau cu un grad scazut de utilizare.
Operatiile de I/O, în cazul nesuprapunerii lor peste activitatea de executie
a task-ului de catre procesor.
Planificarea suboptimala a proceselor din punct de vedere software
(activare proces, punere în asteptare a unui proces, schimbarea
contextului în comutarea proceselor)
b) Memoria cache este o memorie situata din punct de vedere logic între
CPU si memoria principala (uzual DRAM), mai mica, mai rapida si mai
scumpa (per byte) decât aceasta si gestionata – în general prin hardware –
astfel încât sa existe o cât mai mare probabilitate statistica de gasire a datei
accesate de catre CPU, în cache. Din punct de vedere arhitectural, exista 3
tipuri distincte de memorii cache în conformitate cu gradul de asociativitate:
cumapare directa ,semiasociative si complet asociative [VinFlor00].
La cache-urile cu mapare directa , ideea principala consta în faptul ca un
bloc din MP poate fi gasit în cache (hit) într-un bloc unic determinat. În
acest caz regula de mapare a unui bloc din MP în cache este:

Indicatii de solutionare 353
(Adresa bloc MP ) modulo ( Nr. blocuri din cache )
Strictetea regulii de mapare conduce la o simplitate constructiva a acestor
memorii dar si la fenomenul de interferenta al blocurilor din MP în cache.
Lacache-urile semiasociative exista mai multe seturi, fiecare set
având mai multe blocuri componente. Aici, regula de mapare precizeaza
strict doar setul în care se poate afla blocul dorit, astfel:
(Adresa bloc MP ) modulo ( Nr. seturi din cache )
Blocul dorit se poate mapa oriunde în setul respectiv. La un miss în
cache, înainte de încarcarea noului bloc din MP, trebuie evacuat un anumit
bloc din setul respectiv. În principiu exista implementate doua-trei tipuri de
algoritmi de evacuare: pseudorandom (cvasialeator), FIFO si LRU ( “Least
Recently Used ”). Algoritmul LRU evacueaza blocul din cache cel mai
demult neaccesat, în baza principiului de localitate temporala. Daca un set
din cache-ul semiasociativ contine N blocuri atunci cache-ul se mai numeste
“tipN-way set associative ”.
Într-un cache semiasociativ rata de interferenta se reduce odata cu
cresterea gradului de asociativitate (N “mare”). Prin reducerea posibilelor
interferente ale blocurilor, cresterea gradului de asociativitate determina
îmbunatatirea ratei de hit si deci a performantei globale. Pe de alta parte
însa, asociativitatea impune cautarea dupa continut ceea ce conduce la
complicatii structurale si deci la cresterea timpului de acces la cache si
implicit la diminuarea performantei globale. Optimizarea gradului de
asociativitate, a capacitatii cache, a lungimii blocului din cache nu se poate
face decât prin laborioase simulari software, variind toti acesti parametrii în
vederea minimizarii ratei globale de procesare a instructiunilor [instr./cicli].
Memoriile cache complet asociative , implementeaza practic un singur
set permitând maparea blocului practic oriunde în cache. Ele nu se
implementeaza deocamdata în siliciu datorita complexitatii deosebite si a
timpului prohibit de cautare. Reduc însa total interferentele blocurilor la
aceeasi locatie cache si constituie o metrica superioara utila în evaluarea
ratei de hit pentru celelalte tipuri de cache-uri (prin comparatie).
Într-un Sistem Multiprocesor o informatie poate fi privata (locala) –
daca ea este utilizata de catre un singur CPU, sau partajata – daca se
impune a fi utilizata de catre mai multe procesoare [VinFlor00]. În cazul
informatiilor partajate, de obicei acestea sunt memorate în cache-ul local al
unui anumit CPU, reducându-se astfel latenta necesara accesarii lor de catre
un respectivul procesor. Totodata, se reduc coliziunile implicate de accesul354 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
simultan (citiri) al mai multor CPU-uri la respectiva informatie (informatia
necesara mai multor procesoare coincide) si respectiv necesitatile de largime
de banda a busului comun. Din pacate, pe lânga aceste avantaje, partajarea
informatiilor introduce un dezavantaj major, constând în problema
coerentei cache-urilor . În principiu, un sistem de memorie aferent unui
Sistem Muliprocesor este coerent daca orice citire a unei informatii
returneaza informatia scrisa cel mai recent . Astfel, problema coerentei
cache-urilor în SMM se refera la necesitatea ca un bloc din memoria globala
– memorat în mai multe memorii cache locale – sa fie actualizat în toate
aceste memorii, la orice acces de scriere al unui anumit CPU.
În vederea mentinerii coerentei cache-urilor cu precadere în sistemele
multiprocesor – exista 2 posibilitati în functie de ce se întâmpla la o scriere:
Write invalidate – prin care CPU care scrie determina ca toate copiile
din celelalte memorii cache sa fie invalidate înainte ca el sa-si modifice
blocul din cache-ul propriu.
Write Broadcast – CPU care scrie pune data de scris pe busul comun
spre a fi actualizate toate copiile din celelalte cache-uri.
Ambele strategii de mentinere a coerentei pot fi asociate cu oricare
dintre protocoalele de scriere (Write Through, Write Back) dar de cele mai
multe ori se prefera WB cu invalidare.
c) În ce priveste limitarile arhitecturale ale paradigmei superscalare
referitoare la maximizarea ratei de aducere a instructiunilor din memorie la
aceasta întrebare s-a raspunsul prin intermediul problemei 10 pct.a.
Limitarile de tip " issue bottleneck " sunt determinate fundamental de
gradul de secventialitate intrinsec programelor (hazarduri structurale si de
date), dar si de mecanismul de aducere a instructiunilor din memorie
(IRFR). În ultimii ani s-au dezvoltat doua tehnici hardware menite sa
exploateze redundanta existenta în programe, reducând timpului de executie
al acestora prin colapsarea dinamica a dependentelor de date: reutilizarea
dinamica a instructiunilor si predictia valorilor [VinFlor00].
VP ( value prediction ) predictioneaza rezultatele instructiunilor bazat
pe rezultatele cunoscute anterior, efectueaza operatiile folosind valorile
prezise iar executia speculativa este confirmata la un moment ulterior – late
validation – când valorile corecte devin disponibile, deci dupa executia
instructiunii. În cazul unei predictii corecte, calea critica este redusa întrucât
instructiunile care s-ar executa secvential în mod normal, pot fi executate în
paralel. În caz contrar, instructiunile executate cu intrari eronate trebuiesc
reexecutate.
IR (instruction reuse ), recunoaste un lant de instructiuni dependente
executat anterior si nu-l mai executa din nou – early validation – actualizând

Indicatii de solutionare 355
doar diferite date în tabelele hardware aferente. Astfel, IR comprima un lant
de instructiuni din calea critica de executie a programului.
Alti factori care determina limitarea ratei de issue a instructiunilor sunt:
largimea de banda limitata a interfetei procesor – cache, missurile în cache-
ul de date, alias-urile de memorie. Pentru a contracara efectul acestor factori
se poate utiliza cu succes mecanismul Data Write Buffer (DWB). DWB
reprezinta un mic procesor de iesire care lucreaza în paralel cu CPU
degrevându-l pe acesta de sarcina scrierii în cache. DWB ofera porturi de
scriere virtuale multiple spre deosebire de DataCache care contine un singur
port de citire (LOAD) si un singur port de scriere (STORE). DWB rezolva
prin "bypassing" elegant hazardurile de tip "LOAD after STORE" cu adrese
identice, nemaifiind deci necesara accesarea sistemului de memorie de catre
instructiunea LOAD.
17. a) Modelele CISC sunt caracterizate de un set foarte bogat de
instructiuni – masina, formate de instructiuni de lungime variabila,
numeroase moduri de adresare deosebit de sofisticate, lipsa unei interfete
hardware – software optimizate etc. Evident ca aceasta complexitate
arhitecturala are o repercursiune negativa asupra performantei masinii.
Microprocesoarele RISC au aparut ca o replica la lipsa de eficienta a
modelului conventional de procesor de tip CISC. Caracteristicile de baza ale
modelului RISC sunt:
Unitate de comanda hardware în general cablata, cu firmware redus sau
deloc, ceea ce mareste rata de executie a instructiunilor.
Utilizarea tehnicilor de procesare pipeline a instructiunilor, ceea ce
implica o rata teoretica de executie de o instructiune / ciclu , pe
modelele de procesoare care pot lansa în executie la un moment dat o
singura instructiune (procesoare scalare). Sunt mai rapide decât modelele
CISC.
Memorie sistem de înalta performanta, prin implementarea unor
arhitecturi avansate de memorie cache si MMU.
Set relativ redus de instructiuni simple, majoritatea fara referire la
memorie si cu putine moduri de adresare. În general, doar instructiunile
LOAD / STORE sunt cu referire la memorie (arhitectura tip LOAD /
STORE). Caracteristica de "set redus de instructiuni" are sensul de set
optimizat de instructiuni în vederea implementarii aplicatiilor propuse (în
special implementarii limbajelor de nivel înalt – C, C++, Pascal).
Format fix al instructiunilor, codificate în general pe un singur cuvânt de
32 biti, mai recent pe 64 biti (Alpha 21264, IA-64 Merced).
Set de registre generale substantial mai mare decât la CISC-uri, în
vederea lucrului "în ferestre" (register windows), util în optimizarea356 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
instructiunilor CALL / RET. Numarul mare de registre generale este util
si pentru marirea spatiului intern de procesare, tratarii optimizate a
evenimentelor de exceptie, modelului ortogonal de programare. Registrul
R0 este cablat la zero în majoritatea implementarilor, pentru optimizarea
modurilor de adresare si a instructiunilor.
b) Procesarea pipeline a instructiunilor reprezinta o tehnica de procesare
prin intermediul careia fazele (ciclii) aferente multiplelor instructiuni sunt
suprapuse în timp. Se întelege printr-o faza aferenta unei instructiuni masina
o prelucrare atomica a informatiei care se desfasoara dupa un algoritm
implementat în hardware si care dureaza unul sau mai multi tacti.
Arhitectura microprocesoarelor RISC este mai bine adaptata la procesarea
pipeline decât cea a sistemelor conventionale CISC, datorita instructiunilor
de lungime fixa, a modurilor de adresare specifice, a structurii interne bazate
pe registre generale. Microprocesoarele RISC uzuale detin o structura
pipeline de instructiuni întregi pe 4 – 6 nivele (microprocesoarele MIPS au 5
nivele tipice):
1. Nivelul IF(instruction fetch) – se calculeaza adresa instructiunii ce
trebuie citita din cache-ul de instructiuni sau din memoria principala si se
aduce instructiunea;
2. Nivelul RD (ID) – se decodifica instructiunea adusa si se citesc operanzii
din setul de registri generali. În cazul instructiunilor de salt, pe parcursul
acestei faze se calculeaza adresa de salt;
3. Nivelul ALU – se executa operatia ALU asupra operanzilor selectati în
cazul instructiunilor aritmetico-logice; se calculeaza adresa de acces la
memoria de date pentru instructiunile LOAD / STORE;
4. Nivelul MEM – se acceseaza memoria cache de date sau memoria
principala, însa numai pentru instructiunile LOAD / STORE. Acest nivel
pe functia de citire poate pune probleme datorate neconcordantei între
rata de procesare si timpul de acces la memoria principala. Rezulta deci
ca într-o structura pipeline cu N nivele, memoria trebuie sa fie în
principiu de N ori mai rapida decât într-o structura de calcul
conventionala. Acest lucru se realizeaza prin implementarea de
arhitecturi de memorie rapide (cache, memorii cu acces întretesut, etc.).
Desigur ca un ciclu cu MISS în cache pe acest nivel (ca si pe nivelul IF
de altfel), va determina stagnarea temporara a acceselor la memorie sau
chiar a procesarii interne. La scriere, problema aceasta nu se pune
datorita procesorului de iesire specializat DWB care lucreaza în paralel
cu procesorul central dupa cum deja am aratat.
5. Nivelul WB (write buffer) – se scrie rezultatul ALU sau data citita din
memorie (în cazul unei instructiuni LOAD) în registrul destinatie din
setul de registri generali ai microprocesorului.

Indicatii de solutionare 357
Se observa necesitatea suprapunerii a 2 nivele concurentiale: nivelul IF si
respectiv nivelul MEM, ambele cu referire la memorie. În cazul
microprocesoarelor RISC aceasta situatie se rezolva prin busuri separate între
procesor si memoria de date respectiv de instructiuni (arhitectura Harvard).
c) Vezi problema 14c).
d) Procesarea pipeline a secventei de instructiuni este urmatoarea:
ADD: IF ID ALU/
MEMWB
BR: IF ID ALU/
MEMWB
SUB: IF ID ALU/
MEMWB
MUL: IF ID ALU/
MEMWB
Instr. de
la SUB1IF ID ALU/
MEMWB
Instructiunea SUB este extrasa din cache fara a sti daca saltul se va face sau
nu. Abia dupa faza ALU/MEM aferenta instructiunii BR se cunoaste
rezultatul saltului ( taken ). Între timp inclusiv instructiunea MUL a fost
extrasa din cache iar instructiunea anterioara (SUB) a fost decodificata. Din
cauza ca saltul este taken cele doua instructiuni SUB si MUL s-au executat
eronat. În acest moment se va executa faza IF aferenta instructiunii de la
adresa SUB1 iar executia instructiunilor executate eronat se întrerupe.
Valoarea registrilor pipeline este resetata. Delay slot -ul este de 2 cicli de
tact.
19. a) Implementarea memoriei cache are rolul de a micsora timpul mediu
de acces al microprocesorului la memoria DRAM Cache-ul este adresat de
catre CPU în paralel cu memoria principala (MP): daca data dorita a fi358 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
accesata se gaseste în cache, accesul la MP se aborteaza, daca nu, se
acceseaza MP cu penalizarile de timp impuse de latenta mai mare a acesteia,
relativ ridicata în comparatie cu frecventa de tact a CPU. Oricum, data
accesata din MP se va introduce si în cache. Memoriile cache îmbunatatesc
performanta îndeosebi pe citirile cu hit iar în cazul utilizarii scrierii tip
“Write Back ”si pe scrierile cu hit.
Pentru a reduce rata de miss a cache-urilor mapate direct (fara sa se
afecteze însa timpul de hit sau penalitatea în caz de miss), cercetatorul
Norman Jouppi a propus conceptul de “victim cache ”- o memorie mica
complet asociativa, plasata între primul nivel de cache mapat direct si
memoria principala. Blocurile înlocuite din cache-ul principal datorita unui
miss sunt temporar stocate în victim cache. Daca sunt referite din nou
înainte de a fi înlocuite din victim cache, ele pot fi extrase direct din victim
cache cu o penalitate mai mica decât cea a memoriei principale. Algoritmul
de victim cache încearca sa izoleze blocurile conflictuale si sa le memoreze
doar unul în cache-ul principal restul în victim cache. Daca numarul
blocurilor conflictuale este suficient de mic sa se potriveasca în victim
cache, atât rata de miss în nivelul urmator de memorie cât si timpul mediu
de acces va fi îmbunatatit datorita penalitatii reduse implicate de prezenta
blocurilor în victim cache.
Pentru a reduce numarul de interschimbari dintre cache-ul principal si
victim cache, Stiliadis si Varma au introdus un nou concept numit selective
victim cache (SVC). Cu SVC, blocurile aduse din memoria principala sunt
plasate selectiv fie în cache-ul principal cu mapare directa fie în selective
victim cache, folosind un algoritm de predictie euristic bazat pe istoria
folosirii sale. Blocurile care sunt mai putin probabil sa fie accesate în viitor
sunt plasate în SVC si nu în cache-ul principal. Predictia este de asemenea
folosita în cazul unui miss în cache-ul principal pentru a determina daca este
necesara o schimbare a blocurilor conflictuale. Algoritmul obiectiv este de a
plasa blocurile, care sunt mai probabil a fi referite din nou, în cache-ul
principal si altele în victim cache.
b)Memoria virtuala (MV) reprezinta o tehnica de organizare a memoriei
prin intermediul careia programatorul “vede”un spatiu virtual de adresare
foarte mare si care, fara ca programatorul sa “simta ”, este mapat în memoria
fizic disponibila. În cazul MV, memoria principala este analoaga memoriei
cache între CPU ( Central Processing Unit ) si memoria principala, numai ca
de aceasta data ea se situeaza între CPU si discul hard. Deci memoria
principala (MP) se comporta oarecum ca un cache între CPU si discul hard.
Prin mecanismele de MV se mareste probabilitatea ca informatia ce se
doreste a fi accesata de catre CPU din spatiul virtual (disc), sa se afle în MP,

Indicatii de solutionare 359
reducânduse astfel dramatic timpul de acces de la 8  15 ms la 45  70 ns în
tehnologiile anilor 1999!
21. a.
Cache-ul semiasociativ contine 2j seturi, fiecare set contine 2 blocuri.
V – bit de validare (0 – nu e valida data; 1 – valida;). Initial are valoarea 0.
Este necesar numai pentru programe automodificabile la cache-urile de
instructiuni.
D – bit Dirty. Este necesar la scrierea în cache-ul de date.
b.
360 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
În cazul cache-urilor full asociative dispare câmpul set. Practic exista un
singur set. Datele pot fi memorate oriunde (în orice bloc) în cache.
c. În cazul cache-urilor mapate direct , datele vor fi memorate în acelasi loc
de fiecare data când sunt accesate. Din acest motiv vom sti la fiecare acces
ce data va fi evacuata din cache, nemaifiind necesar câmpul LRU (evacuare
implicita).
22. a)
In Order Out of Order
Logica de trimitere în executie .
O instructiune va fi executata abia
dupa ce toate celelalte instructiuni
anterioare, de care ea depinde au
fost executate.Logica de trimitere în executie .
Instructiunile pot fi executate în alta
ordine decât cea initiala cu conditia
de a pastra tot timpul valid contextul
procesorului (consistenta si
integritatea registrilor).
Extrage paralelismul la nivel
software cu ajutorul unui scheduler.
•În momentul compilarii rearanjeaza
instructiunile si redenumeste registri.
•Ascunde întârzierile datorate
instructiunilor de salt prin umplerea
branch delay slotului cu instructiuni
valide sau branch prediction static
(întârziind procesarea instructiunilor
urmatoare cu un numar de cicli egal cu
BDS pâna când adresa de salt devine
disponibila ).Extrage paralelismul la nivel
hardware . Trebuiesc tratate
urmatoarele patru procese:
•Branch Prediction Dinamic
•Redenumirea registrilor
•Expedierea instructiunilor spre
executie
•Mentinerea precisa a
întreruperilor

Indicatii de solutionare 361
b) Procesarea «Out of Order» a instructiunilor cu referire la memorie într-un
program este dificila datorita accesarii aceleiasi adrese de memorie de catre
o instructiune Load respectiv una Store. Exemplificam pe secventa de
instructiuni urmatoare:
Presupunem ca la adresa 2000h avem memorata valoarea 100.
LOAD R1, 2000h
ADD R1, R1, #12
STORE R1, 2000h
În urma executiei în registrul R1 si implicit la adresa 2000h vom avea
valoarea 112.
Prin Out of Order aplicat instructiunilor cu referire la memorie
valoarea din registrul R1 precum si cea din memorie de la adresa 2000h ar fi
alterata.
Secventele de program în limbajul unui procesor RISC ar deveni:
R1 x[i];
(R1) a[2i]; STORE Adr1
R2 a[i+1]; LOAD Adr2
R6 (R2) + 5;
(R6) y[i];
Cele doua instructiuni cu referire la memorie ar fi paralelizabile (executabile
Out of Order) daca i  1 (Adr1  Adr2).
Benchmark-ul B2 s-ar procesa mai repede pe un procesor superscalar
cu executie Out of Order a instructiunilor, pentru ca cele doua aliasuri (i=1)
au fost scoase în afara buclei, prin urmare în cadrul buclei B2, paralelizarea
Load / Store e posibila.
23. a. Vezi pr. 44 a), b).
Prin «renaming» aplicat registrului R1 putem elimina hazardul WAW
dintre instructiunile (1 si 5) si (2 si 6), deci le putem trimite în executie în
acelasi ciclu.
Executia: tact 1 – instructiunile: 1, 5, 3.
tact 2 – instructiunile: 2, 6.
tact 3 – instructiunea: 4.
24. Nivelul WR este mai prioritar datorita hazardurilor RAW între doua
instructiuni succesive (vezi si 50.b).362 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
25.FRmed = 5; Da. Predictia a N PC-uri simultan implica FR med N  5.
26. C  (N-1) + (N-2) + … + 2 + 1 = N(N-1) / 2 comparatoare RAW.
Pentru (N+1) instructiuni => N(N+1) / 2 comparatoare  C’
C’/ C = N(N+1) / N(N-1) => C ’= C(N+1) / (N-1)
27.
a)A. Strictetea regulii de mapare conduce la o simplitate constructiva a
memoriilor cache dar si la fenomenul de interferenta al blocurilor din
MP în cache. Presupunând o MP de 64 de blocuri si un cache de 8
locatii rata de interferenta este de 8 (8 blocuri din MP se mapeaza în
acelasi bloc din cache). Crescând dimensiunea cache-ului la 16 blocuri
 rata de interferenta devine 4(se reduce la jumatate numarul
blocurilor conflictuale).
b)F. Justificarea o constituie chiar definitia maparii directe:
(Adresa bloc MP ) modulo ( Nr. blocuri din cache )
c)F. Scrieri în cache au loc si în cazul scrierilor cu hit în cache (se scrie
numai câmpul de date nu si TAG-ul).
d)F. Într-un cache semiasociativ rata de interferenta se reduce odata cu
cresterea gradului de asociativitate. Prin reducerea posibilelor
interferente ale blocurilor, cresterea gradului de asociativitate determina
îmbunatatirea ratei de hit si deci a performantei globale.
28.a)
2 nop
2 nop
b) 5 cicli pentru instr. + 4 cicli nop = 9 cicli executie
c) 1 – 3 – 5 – 2 – nop – nop – 4 => 7 cicli executie1 5 3
2
4

Indicatii de solutionare 363
29. a.)
Branch delay slot = 2 cicli.
b) Motivul implementarii de busuri si memorii cache separate pe
instructiuni, respectiv date în cazul majoritatii procesoarelor RISC (pipeline)
consta în faptul ca nu exista coliziuni la memorie de tipul (IF, MEM).
c) Instructiunile CALL / RET sunt mari consumatoare de timp în cazul
procesoarelor CISC datorita salvarilor si restaurarilor de registri (registrul
stare program, registrul de flaguri, PC) pe care acestea le executa de fiecare
data când sunt apelate. Evitarea consumului de timp în cazul
microprocesoarelor RISC se face prin implementarea ferestrelor de registre
sau prin inlining-ul procedurilor (utilizarea de macroinstructiuni).
30. Codificarea instructiunii este urmatoarea:
7……….0
Opcode
Deplasament (1)
Deplasament (2)
Se efectueaza urmatoarele operatii:
Operatia executata Durata executie (cicli)
Fetch Instructiune 6
Fetch Deplasament (1) 4
Fetch Deplasament (2) 4
Calcul adresa de memorare 2
Scriere A în memorie 4
Total cicli executie = 20.
31. a)Fals! În caz de hit, pe baza compararii tag-urilor, se citeste si data
respectiva => acces simultan la tag si date.
b)Fals! Fiind hit tag-ul nu mai are sens sa-si modifice valoarea.
c)Fals! Datorita interferentelor alternative, rata de hit este egala cu 0.364 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
32. i5: LOAD Rl, (Rl+0)
33. Nu ! O regenerare transparenta (dureaza 250ns) trebuie sa Ҕncapa Ӕntre
2 accese la DRAM ale microprocesorului. Cum un ciclu extern al
procesorului dureaza 3 tacte (150ns) regenerarea transparenta este
imposibila la frecventa maxima a procesorului.
a. ALU: (R9) + 06; MEM: scriere R5 la adresa (R9) + 06;WB: nimic
b. ALU: (R8) + F3; MEM: citire de la adresa (R8) + F3;WB: scriere în R7;
c. ALU: (R7) + (R8); MEM: nimic; WB: scriere în R5.
35.
a. 1 – 2 – nop – 3 – 4 – nop – 5 – 6 => 8 cicli.
b. 1 – 2 – 4 – 3 – 6 – 5 => 6 cicli.
36.
a. Nr.tacte /s consumate pentru interogare mouse: 30 100 = 3000 tacte/ s
0,006%610503000f 

b.sinterogare acces10225
interogare acceso2sko50
sari Nr.interog 
Nr. tacte necesar pentru Nr.interogari/ s = 25 210100 tacte6 42
3
5R1
R1
R21
R3R3R3
R1

Indicatii de solutionare 365
5,12%61050510 25,6f 

c.sinterogare acces202 0,5
interogare acceso4sMo2
sari Nr.interog 
Nr. tacte necesar pentru Nr.interogari/ s = 0,5 220100 tacte
100%61050100202 0,5f 

În cazul hard-disc-ului este imposibila comunicatia dintre procesor si
periferic prin interogare. (Într-o secunda procesorul realizeaza 50 106 tacte,
iar pentru un transfer cu o rata de 2 Mo/ s sunt necesare într-o secunda
50220 tacte, imposibil).
37.a)
•Minimizarea num arul de interschimbari dintre cache-ul principal si
victim cache.
•Mecanismul de predictie bazat pe istoria anterioara a blocurilor existente
în cache-ul principal (conflictual) si cel din victim cache, stabileste daca
blocul adus din memoria principala va fi plasat fie în cache-ul principal
fie în selective victim cache. Algoritmul obiectiv este de a plasa
blocurile, care sunt mai probabil a fi referite din nou, în cache-ul
principal si celelalte în selective victim cache. Predictia este de asemenea
folosita în cazul unui miss în cache-ul principal pentru a determina daca
este necesara o schimbare a blocurilor conflictuale.
39.a) Vezi capitolul 4.3.1. al prezentei lucrari.
c) Val. minima = 1 (procesor scalar)
Val. maxima = IRmax
40. a – cazul memoriei mapate direct cu 4 locatii.
Se acceseaza pe rând locatiile:366 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
Rezulta în cazul memoriei mapate direct un singur acces cu hit R miss =
6 / 7 = 85.71%
b – cazul memoriilor semiasociative cu 2 seturi a câte 2 cuvinte.
Întrucât toate adresele sunt pare se acceseaza doar blocurile din setul
0.
În cazul memoriei two-way asociative sunt 2 accese cu hit R miss = 5 / 7
= 71.42%
c – cazul memoriilor complet asociative.
În cazul memoriei complet asociative sunt 3 accese cu hit R miss = 4 / 7
= 57.14%

Indicatii de solutionare 367
41. a. 1 – 2 – nop – 3 – 4 – nop – 5 => 7 cicli.
b. 1 – 2 – 4 – 3 – nop – 5 => 6 cicli.
42.În 1 s se transfera 25 104 biti.
În x s se transfera 1 octet.
Rezulta x = 8 / (25 104) = 32 s
Fie t r = timpul disponibil dintre 2 transferuri succesive de octeti.
t1 = timpul scurs între aparitia întreruperii si intrarea în rutina de tratare;
t1 = 2 s;
t2 = timpul în care este tratata rutina de întrerupere; t 2 = 10s;
tr = x – t 1 – t2= (32 – 2 – 10) s => t r = 20 s.
43. a. 1,12298,536 0,11 8,5 0,11)(1 => diminuare a performantei cu
 13%.
b. Avantajul implementarii unei pagini de capacitate «mare» într-un
sistem de memorie virtuala consta în principiul localizarii acceselor,
determinând o optimizare a acceselor la disc (se reduce numarul
acestora).
Dezavantajul îl reprezinta aducerea inutila de informatie de pe disc
(pierdere de timp), care trebuie apoi evacuata în cazul unei erori de
tipul PageFault . Dimensiunea paginii se alege în urma unor simulari
laborioase.42
3
51
R1
R1
R2R3368 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
44. a.
1 – nop – 2 – 3 – nop – 4 – 5 – nop – 6 => 9 cicli executie.
b.
1: R1(R11) + (R12)
5: R1’(R14) + (R15)
3: R2(R3) + 4
2: R1(R1) + (R13)
6: R1’(R1’) + (R16)
4: R2(R1) + (R2)
1 – 5 – 3 – 2 – 6 – 4 => 6 cicli executie
45. Daca alegem strategia Greedy obtinem rata de procesare
cicluinstr
72IR
Daca alegem strategia non – Greedy rata de procesare obtinuta este:
cicluinstr
31IR
În acest caz e mai avantajos sa alegem stategia non – Greedy.6
3
01011
110111
111112
1
3645
R1(WAW)
R1
R1
R2R1
R1R1(WAW)
R1(WAR)
3

Indicatii de solutionare 369
46. Algoritmul lui Tomasulo permite anularea hazardurilor WAR si WAW
printr-un mecanism hardware de redenumire a registrilor, favorizând
executia multipla si Out of Order a instructiunilor. Mecanismul de
«forwarding» implementat prin arhitectura Tomasulo (statii de rezervare)
determina reducerea semnificativa a presiunii la «citire» asupra setului de
registri logici, înlaturând o mare parte din dependentele RAW dintre
instructiuni [33].
În cazul unei arhitecturi TTA, numarul de registri generali poate fi
redus semnificativ datorita faptului ca trebuie stocate mai putine date
temporare, acestea circulând direct între unitatile de executie (FU – unitati
functionale), nemaifiind necesara memorarea lor în registri. «Forwarding-
ul» datelor este realizat software prin program, spre deosebire de
procesoarele superscalare care realizeaza acest proces prin hardware
folosind algoritmul lui Tomasulo [33].
47. O instructiune de tip RETURN este dificil de predictionat printr-un
predictor hardware datorita fenomenului de interferenta a salturilor .
Acesta apare în cazul unei predictii incorecte datorate exclusiv adresei de
salt incorecte din tabela de predictii, care a fost modificata de catre un alt
salt anterior. Instructiunile de tip RETURN reprezinta salturi care-si
modifica dinamic adresa tinta, favorizând dese aparitii ale fenomenului de
interferenta. Analog se întâmpla si în cazul salturilor în mod de adresare
indirect [33].
Noutatea «principiala» a predictoarelor corelate pe doua nivele consta
în faptul ca predictia unei instructiuni tine cont de predictia ultimelor n
instructiuni de salt anterioare; se foloseste un registru de predictie (registru
binar de deplasare) care memoreaza istoria ultimelor n instructiuni de salt.
Valoarea acestui registru concatenata cu cei mai putini semnificativi biti ai
PC-ului instructiunii de salt curente realizeaza adresarea cuvântului de
predictie din tabela de predictie [33, 45].
50.a. Sumatorul “sum 2 ”este activat de o instructiune de branch, pentru
calculul adresei de salt.
b. Nivelul WR este mai prioritar datorita hazardurilor RAW. Operatia
de citire ar putea avea nevoie de un registru în care nu s-a înscris înca
rezultatul final, rezulta prioritatea scrierii fata de citire.
c. În cazul unei instructiuni de tip LOAD, unitatea ALU are rol de
calcul adresa.
d. În latch-ul EX/MEM se memoreaza valoarea (R7+05).370 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
52. Se citesc caractere de la intrare pâna se întâlneste conditia de iesire, si se
salveaza acestea în stiva. Conditia de iesire o constituie tastarea caracterului
‘0’. La întâlnirea sa se afiseaza caracterul curent ( ‘0’– primul caracter
afisat) si se va apela functia de afisare. În cadrul acestei functii vom prelua
din stiva caracterele memorate si le vom tipari.
Obs. E necesar un parametru pentru contorizarea caracterelor scrise în stiva.
Programul modificat pentru a nu afisa si caracterul ‘0’, difera prin faptul ca
la întâlnirea conditiei de iesire se apeleaza direct functia de afisare.
53. Este esential sa calculam cmmdc (cel mai mare divizor comun) dintre
cele doua numere, cmmmc (cel mai mic multiplu comun) putându-se calcula
apoi din formula:
cmmdc(a,b) cmmmc(a,b) = a  b
Pentru calcularea cmmdc(a,b) folosim recursivitatea:
a, daca a = b
Cmmdc(a,b) = Cmmdc(a,b-a) , daca a < b
Cmmdc(b,a-b) , daca a > b
Se apeleaza recursiv functia având ca noi parametri minimul dintre cele
doua numere si modulul diferentei dintre cele doua valori, pâna la întâlnirea
conditiei de iesire (a = b), în a (si b) aflându-se chiar cel mai mare divizor
comun.
*************** Sursa în limbaj de asamblare MIPS *****************
#calculeaza recursiv cmmdc si cmmmc dintre n numere naturale (de
preferat < 1000)
.data
n: .space 4
date: .space 100
mesaj: .asciiz "Introduceti nr. de numere:"
mesaj1: .asciiz "Cel mai mic multiplu comun este:"
mesaj2: .asciiz "\nCel mai mare divizor comun este:"

Indicatii de solutionare 371
.text
b program #sare peste proceduri
#functie 2 intrari, 2 iesiri – cmmdc local (de 2 numere)
mare_mic :
add $sp,$sp,-4
lw $t0,0($sp) #citeste numar 1
add $sp,$sp,-4
lw $t1,0($sp) #citeste numar 2
mul $t3,$t0,$t1 #cel mai mic temporar
bge $t0,$t1,cont #daca t0>=t1 sare
add $t2,$0,$t1 #daca nu interschimba
add $t1,$0,$t0
add $t0,$0,$t2
cont:
div $t0,$t1 #imparte numerele
add $t0,$0,$t1 #impartitor devine deimpartit
mfhi $t1 #rest devine impartitor
bnez $t1,cont #daca rest nu=0 reia
sw $t0,0($sp) #pune mare pe stiv a
add $sp,$sp,4
div $t2,$t3,$t0
sw $t2,0($sp) #pune mic pe stiva
add $sp,$sp,4
jr $31 #revine din functie
#sfarsit functie
#functia recursiva
recursiva :
sw $31,0($sp) #pune adresa de revenire pe stiva
add $sp,$sp,4
lw $t0,-8($sp) #citeste stanga de pe stiva si pune in t0
lw $t1,-12($sp) #citeste dreapta de pe stiva si pune in t1
sub $t2,$t1,$t0 #face diferenta intre dreapta si stanga si pune
#in t2
bnez $t2,loc1 #daca nu stanga=dreapta
lw $t6,date($t0) #daca stanga=dreapta citeste din memorie si
# pune pe stiva
lw $31,-4($sp) #citeste de pe stiva adresa de revenire
add $sp,$sp,-12 #reface stiva folosita de aceasta functie
sw $t6,0($sp) #scrie primul rezultat pe stiva372 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
add $sp,$sp,4
sw $t6,0 ($sp) #scrie al doilea rezultat pe stiva
add $sp,$sp,4
jr $31 #revine din functie
loc1:
bgt $t2,4,loc2 #daca diferenta>4 adica mai mult de 2 numere
lw $t6,date($t0) #citeste primul numar
lw $t7,date($t1) #citeste al doilea numar
sw $t6,0($sp) #pune numar 1 pe stiva
add $sp,$sp,4
sw $t7,0($sp) #pune numar 2 pe stiva
add $sp,$sp,4
jal mare_mic #apeleaza functie
add $sp,$sp,-4 #citeste rezultat 1
lw $t6,0($sp)
add $sp,$sp,-4 #citeste rezultat 2
lw $t7,0($sp)
lw $31,-4($sp) #cites te de pe stiva adresa de revenire
add $sp,$sp,-12 #reface stiva folosita de aceasta functie
sw $t7,0($sp) #scrie primul rezultat pe stiva
add $sp,$sp,4
sw $t6,0($sp) #scrie al doilea rezultat pe stiva
add $sp,$sp,4
jr $31 #revine din functie
loc2: #aici se apeleaza recursiv
lw $t0,-8($sp) #citeste stanga
lw $t1,-12($sp) #citeste dreapta
add $t2,$t1,$t0 #imparte (st+dr)/2
add $t3,$0,2
div $t4,$t2,$t3
div $t4,$t4,4 #face mod 4
mul $t4,$t4,4
sw $t4,0($sp) #pune (st+dr)/2 pe stiv a
add $sp,$sp,4
sw $t0,0($sp) #pune st pe stiva
add $sp,$sp,4
jal recursiva #apeleaza recursiva
lw $t0,-16($sp) #citeste stanga
lw $t1,-20($sp) #citeste dreapta
sw $t1,0($sp) #pune dr pe stiva
add $sp,$sp,4

Indicatii de solutionare 373
add $t2,$t1,$t0 #imparte (st+dr )/2+4
add $t3,$0,2
div $t4,$t2,$t3
div $t4,$t4,4 #face mod 4
mul $t4,$t4,4
add $t4,$t4,4
sw $t4,0($sp) #pune (st+dr)/2+4 pe stiva
add $sp,$sp,4
jal recursiva #apeleaza recursiva
lw $t0,-8($sp) #citeste mare 1
lw $t1,-16($sp) #citeste ma re 2
sw $t0,0($sp) #scrie mare 1 pe stiva
add $sp,$sp,4
sw $t1,0($sp) #scrie mare 2 pe stiva
add $sp,$sp,4
jal mare_mic #apeleaza mare_mic
lw $t0,-12($sp) #citeste mic 1
lw $t1,-20($sp) #citeste mic 2
sw $t0,0($sp) #pune mic 1 pe stiva
add $sp,$sp,4
sw $t1,0($sp) #pune mic 2 pe stiva
add $sp,$sp,4
jal mare_mic #apeleaza mare_mic
lw $t0,-16($sp) #t0=mare final
lw $t1,-8($sp) #impartitor
lw $t2,-20($sp) #pt immultit
lw $t3,-28($sp) #pt immultit
mul $t4,$t3,$t2 #mic*mic/mare
div $t5,$t4,$t1 #t5=mic final
add $sp,$sp,-32 #reface stiva
lw $31,-4($sp) #citeste de pe stiva adresa de revenire
add $sp,$sp,-12 #reface stiva folosita de aceasta functie
sw $t0,0($sp) #scrie primul rezultat pe stiva
add $sp,$sp,4
sw $t5,0($ sp) #scrie al doilea rezultat pe stiva
add $sp,$sp,4
jr $31 #revine din functie
#sfarsit functie
program : #program principal
li $v0,4 #afisaza mesaj
la $a0,mesaj374 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
syscall
li $v0,5
syscall
add $v0,$v0,-1 #n este defapt n-1
mul $a3,$v0,4 #a3=n*4
sw $v0,n($0) #pune n in memorie
add $a2,$0,$0 #a2=contor
loc:
li $v0,5 #citeste cate un numar
syscall
sw $v0,date($a2) #scrie in memorie
add $a2,$a2,4 #incrementeaza contor
bge $a3,$a2,loc #daca nu s-au citit destule date se reia
sw $a3,0($sp) #pune n pe stiva
add $sp,$sp,4
sw $0,0($sp) #pune 0 pe stiva
add $sp,$sp,4
jal recursiva #apeleaza functia
li $v0,4 #afisaza mesaj
la $a0,mesaj1
syscall
add $sp,$sp,-4 #citeste rezultat1
lw $a0,0($sp)
li $v0,1 #afisaza r ezultat
syscall
li $v0,4 #afisaza mesaj
la $a0,mesaj2
syscall
add $sp,$sp,-4 #citeste rezultat2
lw $a0,0($sp)
li $v0,1 #afisaza rezultat
syscall
li $v0,10 #terminare program
syscall
*************************************************************
54. Semnificatia celor 3 tije este urmatoarea:
A – sursa
B – destinatie
C – manevra

Indicatii de solutionare 375
Problema pentru n discuri se rezolva usor daca putem rezolva pentru
(n-1) discuri, deoarece rezolvând-o pe aceasta, vom putea muta primele (n-
1) discuri de pe tija A(sursa) pe C(manevra), apoi discul n (cu diametrul cel
mai mare) de pe tija A(sursa) pe tija B(destinatie) si din nou cele (n-1)
discuri de pe tija C(manevra) pe tija B(destinatie).
Conditia de iesire din subrutina o constituie problema transferarii unui
singur disc (n=1) de pe sursa pe destinatie. Pasii algoritmului sunt:
Se citesc de la tastatura numarul de discuri ( n), si identificatorii
(caractere) tijelor sursa, destinatie si manevra si se apeleaza subrutina hanoi
având ca parametrii efectivi cele patru valori citite anterior. În cadrul
functiei hanoi se executa:
Se salveaza în stiva adresa de revenire si cadrul de stiva. Se testeaza
daca se îndeplineste conditia de iesire din subrutina.
Daca da, se afiseaza transferul (tija sursa si tija destinatie), se reface
continutul registrilor PC si fp din stiva si se actualizeaza SP. Se executa
instructiunea de la adresa data de PC.
Daca nu, se executa secventa:
a. Se salveaza în stiva registrii corespunzatori parametrilor (tijelor).
b. Se actualizeaza numarul de discuri, n  (n-1) si rolul fiecarei tije
(noua destinatie va fi tija C, tija A va fi sursa iar tija B va fi
manevra). Se reapeleaza hanoi . [Se muta cele (n-1) discuri de pe
tija sursa pe tija de manevra].
c. Se refac parametrii din stiva (tijele). Se afiseaza transferul [cel de-al
n – lea disc de pe tija sursa(A) pe tija destinatie(B)].
d. Se salveaza în stiva registrii corespunzatori parametrilor (tijelor).
e. Se actualizeaza numarul de discuri, n  (n-1) si rolul fiecarei tije
(noua destinatie va fi tija B, tija C este sursa iar tija A va fi
manevra). Se reapeleaza hanoi . [Se muta cele (n-1) discuri de pe
tija de manevra pe cea destinatie].
55. Se modifica programul de calcul al factorialului unui numar, prezentat în
limbaj de asamblare MIPS (vezi lucrarea “Investigatii Arhitecturale
Utilizând Simulatorul SPIM ”), calculând în paralel cu factorialul si
aranjamentele, folosind formulele:
k)!-(nn!A ;
k!k)!-(nn! k
n k
nC
Parametrii n sik se citesc de la tastatura si sunt salvati în stiva. Se
intra în subrutina unde se executa:376 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
Se verifica daca k = 1 (conditia de iesire din subrutina).
Daca da, se seteaza în registrii rezultat valoarea 1, punctul de plecare
în calcularea produselor 1 2 …k si n(n-1) …[n-(k-1)]. Se reface
continutul registrilor PC si fp din stiva si se actualizeaza SP. Se executa
instructiunea de la adresa data de PC.
Daca nu, se executa secventa:
a. Se actualizeaza parametrii n  (n-1) si k  (k-1). Se reapeleaza
subrutina.
b. Se preiau din stiva termenii salvati si se înmultesc cu rezultatele
calculate pâna la acest pas.
c. Se reface continutul registrilor PC si fp din stiva si se actualizeaza
SP. Se executa instructiunea de la adresa data de PC.
În încheierea programului se calculeaza combinarile cu formula
raportului dintre aranjamente si permutari si afiseaza valorile
aranjamentelor, permutarilor si combinarilor.
57. Se parcurge sirul numerelor naturale din doi în doi (ne intereseaza doar
numerele impare) începând cu numarul 3 (primul numar impar prim) si se
determina daca este prim sau nu (vezi lucrarea “Investigatii Arhitecturale
Utilizând Simulatorul SPIM ”). În cazul în care numarul este prim (fie acesta
k) se verifica daca si urmatorul numar impar ( k+2) este prim si daca da se
afiseaza perechea de numere. Se testeaza daca am ajuns la numarul de
perechi de numere prime cerut si daca nu se continua algoritmul cu numarul
prim mai mic. În momentul în care un numar se dovedeste a nu fi prim se
trece la urmatorul numar impar.
58.Implementare în limbaj de asamblare DLX
/****************** Programul principal *************************/
.data
Prompt: .asciiz "Introduceti n:"
PrintfFormat1: .asciiz "Primul numar din suma %d\n\n"
.align 2
PrintfFormat2: .asciiz "Al doilea numar din suma%d\n\n"
.align 2
PrintfFormat3: .asciiz "Introduce ti va rog un numar par!!\n"
.align 2
PrintfFormat4: .asciiz "Introduceti va rog un numar mai mare de
6!!n"

Indicatii de solutionare 377
.align 2
PrintfPar1: .word PrintfFormat1
PrintfValue1: .space 8
PrintfPar2: .word PrintfFormat2
PrintfValue2: .space 8
PrintfPar3: .word PrintfFormat3
PrintfPar4: .word PrintfFormat4
.text
.global main
main:
addi r1,r0,Prompt
jal InputUnsigned
sle r2,r1,6
bnez r2,eticheta1
add r25,r1,r0
addi r15,r0,2
div r3,r1,r15
mult r4,r3,r15
sub r2,r 1,r4
bnez r2,eticheta2
j eticheta3
eticheta1:
add r14,r0,PrintfPar4
trap 5
j main
eticheta2:
add r14,r0,PrintfPar3
trap 5
j main
eticheta3:
addi r13,r0,1
eticheta4:
sgt r11,r13,r3
bnez r11,end
vprim:
addi r24 ,r24,1
sub r12,r13,1
bnez r12,vp1
j r13prim
vp1:378 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
addi r20,r0,2
eticheta5:
sub r20,r20,r13
beqz r20,nr_e_prim
add r20,r20,r13
div r21,r13,r20
mult r22,r21,r20
sub r23,r13,r22
beqz r23,nueprim
addi r20,r20,1
j eticheta5
nr_e_prim:
sub r24,r24,2
beqz r24,afisare
add r24,r24,2
r13prim:
add r16,r13,r0
sub r13,r25,r13
j vprim
afisare:
sw PrintfValue1,r16
addi r14,r0,PrintfPar1
trap 5
sw PrintfValue2,r13
addi r14,r0,Pri ntfPar2
trap 5
nueprim:
add r24,r0,r0
add r13,r16,2
j eticheta4
end:
trap 0
/************************ Rutina Input.s*********************** */
;****************** Citeste un numar întreg pozitiv ****************
;asteapta în registrul R1 adresa unui sir de caractere terminat cu NULL.
;returneaza valuarea citita în R1
;modifica continutul registrilor R1,R13,R14

Indicatii de solutionare 379
.data
ReadBuffer: .space 80
ReadPar: .word 0,ReadBuffer,80
PrintfPar: .space 4
SaveR2: .space 4
SaveR3: .space 4
SaveR4: .space 4
SaveR5: .space 4
.text
.global InputUnsigned
InputUnsigned: ;*** salveaza continutul registrilor
sw SaveR2,r2
sw SaveR3,r3
sw SaveR4,r4
sw SaveR5,r5
sw PrintfPar,r1
addi r14,r0,PrintfPar
trap 5
addi r14,r0,ReadPar
trap 3
;*** determina valuarea citita
addi r2,r0,ReadBuffer
addi r1,r0,0
addi r4,r0,10 ;Decimal system
Loop: ;*** reads digits to end of line
lbu r3,0(r2)
seqi r5,r3,10 ;LF -> Exit
bnez r5,Finish
subi r3,r3,48 ;´0´
multu r1,r1,r4 ;Shift decimal
add r1,r1,r3
addi r2,r2,1 ;increment pointer
j Loop
Finish: ;*** restore old register contents
lw r2,SaveR2
lw r3,SaveR3
lw r4,SaveR4
lw r5,SaveR5
jr r31 ; Return
/************************************************************/380 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
61.RIC cu largime de banda maxima – retea de tip crossbar, permite
implementarea oricarei bijectii procesoare-module memorie;
SMM cu interconectare “crossbar” este o retea dinamica detinând
complexitatea cea mai ridicata dintre arhitecturile de SMM; în schimb
conflictele procesoarelor la resursele de memorie comuna partajata sunt
minime [VinFlor00]. Comunicatia între orice pereche procesor – memorie
este întârziata în nodul de conexiune aferent. De remarcat ca pot avea loc
simultan pâna la N accese ale procesoarelor la memorie, în ipoteza în care
nu exista doua procesoare care sa acceseze acelasi modul de memorie.
Pentru evitarea conflictelor de acest gen, se încearca atunci când este posibil
“împrastieri ”favorabile ale informatiei în modulele de memorie globala. De
exemplu în aplicatiile pe vectori, daca acestia au pasul 1 atunci scalarii
succesivi sunt situati în blocuri succesive de memorie, rezultând minimizari
ale conflictelor.
Retea crossbar
Desi cea mai performanta, arhitectura devine practic greu realizabila pentru
un numar N ridicat de procesoare, din cauza costurilor ridicate (N2 noduri).
RIC cu largime de banda minima – retea unibus, un singur procesor master
la un moment dat.
SMM pe bus comun constituie o retea statica caracterizata de faptul ca RIC
este un simplu bus comun partajat în timp de catre procesoare (UMA)
[VinFlor00]. Este cea mai simpla arhitectura, dar conflictele potentiale ale
procesoarelor (masterilor) pe busul comun, pot fi ridicate. Desigur, exista un

Indicatii de solutionare 381
singur master activ pe bus la un moment dat. Busul comun si memoria
globala (slave) sunt partajate în timp de catre masteri. Resursele locale ale
masterilor – memorii cache locale – au rolul de a diminua traficul pe busul
comun. Accesul pe bus se face prin intermediul unui arbitru de prioritati,
centralizat sau distribuit.
Arhitectura implica dificultati tehnologice legate de numarul maxim
de masteri cuplabili (în practica pâna la 32), reflexii si diafonii ale
semnalelor pe bus. Cum capacitatile si inductantele parazite cresc
proportional cu lungimea busului, rezulta ca acesta trebuie sa fie relativ
scurt. Exista arhitecturi standardizate de SMM pe bus comun (VME –
dezvoltat de Motorola pe p MC680X0, MULTIBUS – Intel pentru I –
80X86).
62. 1. Operatie “write miss ”pe busul comun.
2. Citire bloc de la unul din cache-urile care îl detine ( “snooping ”).
3. Toate procesoarele care au detinut respectivul bloc în cache-uri, îl
trec în starea “invalid ”(V=0).
4. Procesorul care l-a citit în pasul 2, îl scrie si îl pune în cache în
starea “exclusiv ”.
64.
Timp mediu de acces instructiune = T_acces_cache*R_hit+T_acces_ DRAM *(1-R_hit)
a)T_acces_ DRAM = 1+4+dim_bloc*1
T_acces
_DRAMdim_
blocrata_miss Rezultat
_partialT_acces
_cacherata_hi
tRezultat
_final
6 1 4,5 0.2700 1 0.955 1.225
9 4 2,4 0.2160 1 0.976 1.192
13 8 1,6 0.2080 1 0.984 1.192
21 16 1,0 0.2100 1 0.99 1.2
37 32 0,75 0.2775 1 0.9925 1.27
b)T_acces_ DRAM = 2+1+4+dim_bloc*1
T_acces
_DRAMDim_bl
ocrata_
missRezultat_
partialT_acces
_cacherata_
hitRezultat
_final
8 1 4,5 0.3600 1 0.955 1.315
11 4 2,4 0.2640 1 0.976 1.24
15 8 1,6 0.2400 1 0.984 1.224
23 16 1,0 0.2300 1 0.99 1.22
39 32 0,75 0.2925 1 0.9925 1.285382 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
c)T_acces_ DRAM = 1+4+dim_bloc*0.5 (se pot aduce doua blocuri de 32 de
octeti simultan)
T_acces
_DRAMDim_
blocrata_
missRezultat_
partialT_acces
_cacherata_hit Rezultat
_final
5.5 1 4,5 0.2475 1 0.955 1.2025
7 4 2,4 0.1680 1 0.976 1.144
9 8 1,6 0.1440 1 0.984 1.128
13 16 1,0 0.1300 1 0.99 1.12
21 32 0,75 0.1575 1 0.9925 1.15
75.
Executia trace-ului neoptimizat
DECODIFICARE EXECUTIE
I0 I1 I2 I3 ALU1 ALU2 SHF LS BRN CICLU
1 2 3 4 1
1 2 2
5 6 7 8 3 4 3
4
5 5
6
6 7
9 10 11 12 7 8
13 X X X 12 11 9
13 10
Datorita paralelismului limitat al acestei secvente se obtine o rata
medie de executie de doar 1,3instr. / ciclu. Graful de control al acestei
secvente este complus din 3 basic block-uri ca în figura 1.
De remarcat ca decodificarea unui nou grup de instructiuni poate avea
loc si în tactul imediat urmator lansarii în executie a tuturor instructiunilor
anterior decodificate.

Indicatii de solutionare 383
Graful de control aferent secventei de optimizat
Graful dependen telor pentru trace-ul considerat
384 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
Ordinea de executie în urma optimizarii
Nod / Prioritate
7/5; 13/2
6/4; 11/4; 12/2
5/3
4/3; 3/1
1/1; 2/1
Executia secventei optimizate se face doar în 7 cicli si datorita
hazardurilor structurale la unitatea Load/Store (IR = 13/7  1,86
instr./ciclu):
EXECUTIE
ALU1 ALU2 SHF LS BRN CICLU
1 2 1
3 4 2
3
5 4
5
6 12 11 6
13 7 7
Întrucât basic block-ul care contine instructiunile 11 si 12 se executa
preponderent se obtine un avantaj prin migrarea instructiunilor 11, 12, 13 în
basic block-ul anterior fiind necesare însa coduri compensatoare. Rezultatul
obtinut este optim deoarece unitatile ALU sunt pline în tactul 6 si în plus
instructiunea 13 nu poate percola dincolo de instructiunea 11 (s-ar altera
contextul programului). Codul reorganizat arata astfel:
1: ADD R1, R0, base_a
2: ADD R2, R0, base_b *
3: ADD R3, R0, base_c
4: LD R4, (R1) *
5: LD R5, (R2) *
6: SGT R7, R4, R5
11: ST R4, (R3)
12: ADD R1, R1, 4 *
13: ADD R3, R3, 4
7: BNEZ R7, C2 *

Indicatii de solutionare 385
C1: JMP Gata
C2: ST R5, -4(R3)
C3: ADD R2, R2, 4
C4: SUB R1, R1, 4 (compensare 12)
Gata :
Pentru a pastra semantica programului, unele instructiuni au fost
înlocuite cu altele noi (s-au doar opcode-ul acestora). Pentru instructiunea
13 nu mai este nevoie de cod compensator daca fac scrierea corecta în
memorie la adresa -4(R3) R3 pointând spre locatia curenta (libera –
nescrisa) din tabloul rezultat.
76.a)
IRNT = 7/9 [instr./ciclu]
IRT = 4/6 [instr./ciclu]
b)
1. A B
3. if (A=Q) then goto 8
2. B B – 1
7. X Q BDS umplut!
2 creste performanta întotdeauna
7 creste performanta când saltul se face
4. Q Q +1
5. D E
6. E F
7. X Q
8.
Rezulta:
IRNT = 7/8 [instr./ciclu]
IRT = 4/4 [instr./ciclu]
Obs1: Evident, optimizarea trebuie sa pastreze logica secventei initiale.
Obs2: Când saltul nu se face, executia aditionala în BDS a instructiunii 7 nu
altereaza semantica.
Obs3: Performanta secventei optimizate creste în ambele variante (NT/T).386 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
78.
Bucla optimizata :
ld R4, (R5)0  load 1
xor R7, R4, R9  xor 1 Prolog
ld R4, (R5)4  load 2
Loop: st (R5)0, R7  store (k)
xor R7, R4, R9  xor (k+1) Corp
ld R4, (R5)8  load (k+2) Bucla
add R5, R5, #4 Pipelinizata
sub R6, R6, #1
brnz R6, Loop
st (R5)0, R7  store (n-1)
xor R7, R4, R 9 xor (n) Epilog
st (R5)4, R7  store (n)
Bucla initiala : Hazarduri RAW prin R4, R7  4 cicli (nop  LDS)
Bucla optimizata : Elimina hazardurile RAW din corpul buclei  1 ciclu.
Obs: Orice variatiuni coerente de calcul sunt considerate (load pipelinizat
sau nu, etc).
79.Codificarea instructiunii este urmatoarea:
15……….0
Opcode
Deplasament
Se efectueaza urmatoarele operatii:
Operatia executata Durata executie (cicli)
Fetch Instructiune (Opcode) – 2o 6
Fetch Deplasament – 2o 4
Calcul adresa de memorare (R 9+deplasament) 2
Aducere octetii (0 si 1) din memorie 4
Aducere octetii (2 si 3) din memorie 4
Aducere octetii (4 si 5) din memorie 4
Aducere octetii (6 si 7) din memorie 4
Total cicli executie = 28.

Indicatii de solutionare 387
80.a) Codificarea instructiunii este urmatoarea:
15……….0
Opcode
DDeeppllaassaammeenntt
doar pentru instructiunile Load/Store
Se efectueaza urmatoarele operatii:
Operatia executata Durata
executie (cicli)
Fetch Instructiune (Opcode) – 2o ( 1) 6
Fetch Deplasament – 2o ( 1) 4
Calcul adresa de memorare (R 9+deplasament) ( 1) 2
Aducere octetii (0 si 1) din memorie ( 1) 4
Fetch Instructiune (Opcode) – 2o ( 2) 6
Executa operatia de înmultire si scriere rezultat ( 2) 2
Total cicli executie = 24
b) Codificarea instructiunii se pastreaza;
Se efectueaza urmatoarele operatii:
Operatia executata Durata
executie (cicli)
Fetch Instructiune (Opcode) – 2o ( 1) 6
Fetch Deplasament – 2o ( 1) 4
Calcul adresa de memorare (R 9+deplasament) ( 1)
Fetch Instructiune (Opcode) – 2o – 2 cicli de tact ( 2)2
Aducere octetii (0 si 1) din memorie ( 1)
Fetch Instructiune (Opcode) – 2o – 4 cicli de tact ( 2)4
Executa operatia de înmultire si scriere rezultat ( 2) 2
Total cicli executie = 18
81.a)
•DWB determina prevenirea stagnarilor procesorului acolo unde nu
exista suficiente porturi de scriere în cache-ul de date pentru a
asigura toate cererile de scriere existente.388 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
•Eliminarea hazardurilor RAW prin colapsarea dependentelor de date.
Rezolvarea prin bypassing a hazardurilor de tip “Load after Store ”
cu adrese identice.
•DWB = mic procesor de iesire, implementat ca o coada FIFO de
lungime parametrizabila.
•Lucreaza în paralel cu procesorul eliberându-l pe acesta de sarcina
scrierii în cache-ul de date.
b)
•Posibilitatea de a executa simultan mai multe instructiuni Load fara a
fi necesara multiplicarea porturilor de citire ale cache-ului de date.
•Dimensiunea Cache-ului de date : Un cache mic determina putine
blocuri rezulta posibilitatea ca instructiunile Load sa citeasca date
din acelasi bloc.
•Capacitatea bufferului de prefetch : Un buffer de instructiuni mare
faciliteaza prezenta simultana a mai multor instructiuni Load în
buffer care pot citi din acelasi bloc.
82.Codificarea instructiunii este urmatoarea:
15……….0
Opcode
Deplasament
Se efectueaza urmatoarele operatii:
Operatia executata Durata executie (cicli)
Fetch Instructiune (Opcode) – 2o 6
Fetch Deplasament – 2o 4
Calcul adresa de memorare (R 4+deplasament) 2
Scriere octetii (0 si 1) în memorie 4
Scriere octetii (2 si 3) în memorie 4
Scriere octetii (4 si 5) în memorie 4
Scriere octetii (6 si 7) în memorie 4
Total cicli executie = 28.
83.a)
IRNT = 7/11 [instr./ciclu]
IRT = 4/7 [instr./ciclu]

Indicatii de solutionare 389
b)
1. A B
3. If (D=Q) then goto 8
7. X Q
2. C A – 1 BDS umplut!
2 creste performanta întotdeauna
7 creste performanta când saltul se face
4. Q Q +1
5. D E
7. X Q
6. F D*A
8.
Rezulta:
IRNT = 8/8 [instr./ciclu]
IRT = 4/4 [instr./ciclu]
Obs1: Evident, optimizarea trebuie sa pastreze logica secventei initiale.
Obs2: Când saltul nu se face, executia aditionala în BDS a instructiunii 7 nu
altereaza semantica.
Obs3: Performanta secventei optimizate creste în ambele variante (NT/T).
84.
Executia trace-ului neoptimizat
DECODIFICARE EXECUTIE
I0 I1 I2 I3 ALU1 ALU2 SHF LS BRN CICLU
1 2 3 4 1
1 2
2 3
4
3 5
5 6 7 8 4 6
7 8 7
Datorita paralelismului limitat al acestei secvente se obtine o rata
medie de executie de doar 1,14 instr. / ciclu. Graful de control al acestei
secvente este complus din 3 basic block-uri ca în figura 1.
De remarcat ca decodificarea unui nou grup de instructiuni poate avea
loc si în tactul imediat urmator lansarii în executie a tuturor instructiunilor
anterior decodificate.390 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
Graful de control aferent secventei de optimizat
Graful dependen telor pentru trace-ul considerat
Ordinea de executie în urma optimizarii
Nod / Prioritate
4/5;
3/4; 8/2;
2/3; 7/1;
1/1;

Indicatii de solutionare 391
Executia secventei optimizate se face doar în 5 cicli si datorita
hazardurilor reale de date (IR = 8/5  1,6 instr./ciclu):
EXECUTIE
ALU1 ALU2 SHF LS BRN CICLU
1 1
7 2 2
3
8 3 4
4 5
Întrucât basic block-ul care contine instructiunea 7 se executa
preponderent se obtine un avantaj prin migrarea instructiunilor 7 si 8 în
basic block-ul anterior fiind necesare însa coduri compensatoare. Codul
reorganizat arata astfel:
1: ADD R1, R0, base_a *
2: LD R4, (R1)
7: ADD contor_minus, contor_minus, 1 *
3: SGT R7, R4, R0
8: ADD R1, R1, 4 *
4: BNEZ R7, C2 *
C1: JMP Gata
C2: ADD contor_plus, contor_plus, 1
C3: SUB contor_minus, contor_minus, 1
Gata :
Pentru a pastra semantica programului, unele instructiuni au fost
înlocuite cu altele noi (s-au doar opcode-ul acestora). Pentru instructiunea 8
nu mai este nevoie de cod compensator, ea executându-se indiferent de
ramura pe care se continua procesarea.392 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
89. a)
b) Analog (3 Da, 1 Nu)
44 =256 automate distincte!
90.
a)Din ipoteza problemei rezulta ca:
Daca PC = 2DF4h si HRg=0  Adresa destinatie (TARGET) este 4FC0h si
bitul PRED=1
Daca PC = 2DF4h si HRg=1  Adresa destinatie (TARGET) este 2DF8h si
bitul PRED=0
Preluând informatiile de corelatie(k) si gradul de localizare (i) rezulta:
PC = 2DF4h = 10.1101.1111.0100 2. Concatenând doar cei 11 biti (i) ai PC-
ului cu HRg (1 bit) rezulta
i)HRg=0 10.1 |101.1111.0100 2 + 0 21011.1110.1000 2 = BE8h
TARGET=4FC0h si PRED=1
ii)HRg=1 10.1 |101.1111.0100 2 + 1 21011.1110.1001 2 = BE9h
TARGET=2DF8h si PRED=0
Adresele BE6h s iBE7h sunt neprecizabile nedispunând de alte informatii.
b)Datorita procentajului  50% T si tot la fel NT, saltul 2 este mai greu
predictibil.
91.Pentru a veni în sprijinul solutiei se reamintesc primele 5 instructiuni din
secventa de procesat:

Indicatii de solutionare 393
15. BS 27 9
16. BM 17 28
17. BT 35 38
18. NT 40 41
19. BT 45 27
Se va prezenta doar cazul tabelei de predictie – mapata direct de
capacitate 8 locatii, pentru tabela asociativa problema se rezolva similar din
punct de vedere metodologic, doar parametrii difera: INDEX, TAG,
TARGET.
Notam w=0 – numarul de predictii gresite .
g=0 – numarul de predictii corecte .
Predictia instructiunilor urmeaza cursul:
1 – (BS 27 9 ) – PCcrt=27 locatia accesata din BTB este data de :
INDEX = PCcrt modulo 8 = 3 si TAG = PCcrt div 8
TARGET = 9
Predictia anterioara a fost 0 dar primul caracter B implica faptul ca saltul se
face predictie incorecta w=1 si predictia viitoare (câmpul PRED )
devine 1 (bineînteles pe respectiva locatie).
2 – (BM 17 28 )–PCcrt=17 locatia accesata din BTB este data de
INDEX = PCcrt modulo 8 = 1 si TAG = PCcrt div 8 = 2
TARGET = 28
Predictia anterioara a fost 0 dar primul caracter B implica faptul ca saltul se
face predictie incorecta w=2 si predictia viitoare (câmpul PRED )
devine 1 (pe locatia 1).
3 – (BT 35 38 )–PCcrt=35 locatia accesata din BTB este data de
INDEX = PCcrt modulo 8 = 3 si TAG = PCcrt div 8 = 4
TARGET = 38394 Simularea si optimizarea arhitecturilor de calcul în aplicatii practice
Predictia anterioara a fost 1, primul caracter B implica faptul ca saltul se
face predictie corecta (pe directie) dar Target-ul difera w=3, predictia
viitoare (câmpul PRED ) ramânând 1 (pe locatia 3).
4 – (NT 40 41 )–PCcrt=40 locatia accesata din BTB este data de
INDEX = PCcrt modulo 8 = 0 si TAG = PCcrt div 8 = 5
TARGET = 0 ( nu se va introduce în BTB )
Predictia anterioara a fost 0, primul caracter N implica faptul ca saltul nu se
face predictie corecta dar saltul nu se va introduce în tabela g=1,
predictia viitoare (câmpul PRED ) ramânând 0 (pe locatia 5).
5 – (BS 27 9 )–PCcrt=27 locatia accesata din BTB este data de
INDEX = PCcrt modulo 8 = 3 si TAG = PCcrt div 8 = 4
TARGET = 9
Predictia anterioara a fost 1, primul caracter B implica faptul ca saltul se
face predictie corecta (pe directie) dar Target-ul difera w=3, predictia
viitoare (câmpul PRED ) ramânând 1 (pe locatia 3).