Curs 4 3.2.2. Înmulţirea binară Există numeroase metode de înmulţire binară. Cele mai importante sunt următoarele: • Metoda adunării repetate; • Înmulţirea prin metoda Booth. Fiecare din aceste metode are mai multe variante, care ţin cont de modul reprezentare a numerelor cu semn sau urmăresc creşterea vitezei de execuţie operaţiei. 3.2.2.1. Înmulţirea prin metoda adunării repetate (metoda directă) Această metodă se poate aplica pentru numere reprezentate în mărime MS. Se înmulţesc numerele iar cifra de semn este tratată separat . Dacă numerele sunt reprezentate în C1 sau C2, numerele negative trebuie complementate pentru a obţine reprezentarea numerelor pozitive corespunzătoare (care sunt identice cu reprezentarea în MS). Aceast ă metodă de înmulţire este recomandată pentru numerele reprezentate în C1, când complementarea se realizează simplu. Pentru numerele reprezentate în C2, se preferă utilizarea altor metode care operează direct asupra numerelor în această reprezentare. Fie 12 = X şi 6 = Y . Reprezentând aceste numere în MS şi considerând numai biţii de mărime, înmulţirea binară obişnuită a celor două numere se efectuează astfel: 1100 x Deînmulţit (12) 0110 înmulţitor (6) 0000 1100 Produse parţiale 1100 0000 1001000 Produs final (2 6 +2 3 = 64+8 = 72) După cum se constată procesul de înmulţire constă din testarea succesivă a biţilor înmulţitorului, începând cu bitul cel mai puţin semnificativ (c.m.p.s.) . Dacă bi tul testat este 1, se copiază deînmulţitul, în caz contrar fiind copiate zerouri. Se pot formula următoarele observaţii: 1. Înmulţirea implică generarea unor produse parţiale, câte unul pentru fiecare bit al înmulţitorului. Aceste produse sunt apoi însumate pentru a se obţine produsul final. 2. Dacă bitul testat al înmulţitorului este 0, produsul parţial corespunzător este 0. Dacă acest bit este 1, produsul parţial este egal cu deînmulţitul. 3. Pentru obţinerea produsului final, fiecare produs parţial este deplasat la stânga cu o poziţie faţă de produsul parţial precedent. 4. Înmulţirea a două numere binare fără semn de câte n biţi are ca rezultat un produs cu o lungime de până la n 2 biţi. Pentru implementarea înmulţirii directe se introduc următoarele modificări : - In locul adunării tuturor produselor la final, se realizează adunarea lor, într-
Transcript
Curs 4 3.2.2. Înmulţirea binară Există numeroase metode de înmulţire binară. Cele mai importante sunt
următoarele: • Metoda adunării repetate; • Înmulţirea prin metoda Booth. Fiecare din aceste metode are mai multe variante, care ţin cont de modul
reprezentare a numerelor cu semn sau urmăresc creşterea vitezei de execuţie operaţiei.
3.2.2.1. Înmulţirea prin metoda adunării repetate (metoda directă) Această metodă se poate aplica pentru numere reprezentate în mărime MS.
Se înmulţesc numerele iar cifra de semn este tratată separat. Dacă numerele sunt reprezentate în C1 sau C2, numerele negative trebuie complementate pentru a obţine reprezentarea numerelor pozitive corespunzătoare (care sunt identice cu reprezentarea în MS). Această metodă de înmulţire este recomandată pentru numerele reprezentate în C1, când complementarea se realizează simplu. Pentru numerele reprezentate în C2, se preferă utilizarea altor metode care operează direct asupra numerelor în această reprezentare.
Fie 12=X şi 6=Y . Reprezentând aceste numere în MS şi considerând numai biţii de mărime, înmulţirea binară obişnuită a celor două numere se efectuează astfel:
1100 x Deînmulţit (12) 0110 înmulţitor (6) 0000 1100 Produse parţiale 1100 0000 1001000 Produs final (26+23 = 64+8 = 72) După cum se constată procesul de înmulţire constă din testarea succesivă
a biţilor înmulţitorului, începând cu bitul cel mai puţin semnificativ (c.m.p.s.). Dacă bitul testat este 1, se copiază deînmulţitul, în caz contrar fiind copiate zerouri.
Se pot formula următoarele observaţii: 1. Înmulţirea implică generarea unor produse parţiale, câte unul pentru
fiecare bit al înmulţitorului. Aceste produse sunt apoi însumate pentru a se obţine produsul final.
2. Dacă bitul testat al înmulţitorului este 0, produsul parţial corespunzător este 0. Dacă acest bit este 1, produsul parţial este egal cu deînmulţitul.
3. Pentru obţinerea produsului final, fiecare produs parţial este deplasat la stânga cu o poziţie faţă de produsul parţial precedent.
4. Înmulţirea a două numere binare fără semn de câte n biţi are ca rezultat un produs cu o lungime de până la n2 biţi.
Pentru implementarea înmulţirii directe se introduc următoarele modificări: - In locul adunării tuturor produselor la final, se realizează adunarea lor, într-
un registru acumulator, pe măsură ce ele sunt obţinute. In acest mod se elimină necesitatea de a memora toate produsele parţiale, fiind necesare mai puţine registre.
- După obţinerea fiecărui produs parţial acesta este deplasat la dreapta cu o poziţie.
- Testarea înmulţitorului începe cu bitul c.m.p.s. - Pentru fiecare bit de 1 din înmulţitor, este necesară o adunare şi o
deplasare. Pentru fiecare bit de 0 din înmulţitor, când produsul parţial este 0, este necesară numai o deplasare.
Avantajele acestei implementări sunt următoarele: • Se utilizează un sumator de n biţi, chiar dacă rezultatul va avea 12 +n biţi
(ţinând cont şi de semn). • Pentru deînmulţit se utilizează un registru de 1+n biţi. • Registrul acumulator are 1+n biţi. Deoarece rezultatul are 12 +n biţi, registrul acumulator ar trebui completat cu
un registru auxiliar pentru memorarea produsului. O soluţie eficientă constă în utilizarea biţilor care nu mai sunt necesari din registrul înmulţitorului. In acest caz registrul acumulator se plasează în continuarea registrului înmulţitorului, formând un registru combinat care se deplasează la dreapta în fiecare pas al operaţiei. Astfel, în final registrul acumulator păstrează biţii c.m.s. ai rezultatului, iar registrul înmulţitorului păstrează biţii c.m.p.s.
Structura unui dispozitiv de tip paralel care implementează metoda înmulţirii directe este prezentată în figura 3.6. Dispozitivul de înmulţire cuprinde registrele A, B şi Q de n+1 biţi fiecare, un sumator paralel de n biţi şi un bloc de comandă. Aceste registre sunt descrise în continuare.
Fig. 3.6
Ştergere
Bloc de comandă N
Y
Sumator de n biţi
Bn-1 Bn-2 … B1 B0
Bn
An An-1 An-2 … A1 A0 Qn-1 Qn-2 … Q1 Q0
Qn
X
Încărcare
Încărcare
Test Q0
Deplasare
Start Stop
Registrul A este utilizat ca acumulator pentru păstrarea produsului parţial. La sfârşitul operaţiei de înmulţire, nA va conţine semnul rezultatului. Registrul trebuie să aibă intrări paralele pentru înscrierea informaţiei de la sumator şi să funcţioneze ca registru de deplasare spre dreapta. Astfel la început se transferă bitul 0A în poziţia 1−n a registrului Q şi ulterior, pe măsură ce procesul de înmulţire avansează, sunt transferaţi în registru Q biţii care urmează (A1,A2,…An-1)
Fig. 3.7
Registrul B este utilizat pentru încărcarea paralelă a deînmulţitului, iar
conţinutul lui se transferă la una din intrările sumatorului. Registrul Q este utilizat pentru încărcarea paralelă a înmulţitorului. Acesta funcţionează ca un registru de
Start
B←X Q←Y A←0 N←n
Qn←Bn⊕Qn
Q0=1
A←A+B
An←0, Ai←Ai+1 Qn-1←A0, Qi←Qi+1
N←N-1
N=0
An←Qn
Stop
Nu
Da
Nu
Da
deplasare la dreapta, cu excepţia bitului nQ care memorează la început semnul înmulţitorului şi apoi semnul rezultatului.
Blocul de comandă al dispozitivului de înmulţire generează semnalele de comandă în urma cărora se succed operaţiile elementare din care se compune operaţia de înmulţire. Acest bloc conţine un numărător N, care este iniţializat cu numărul biţilor de mărime n şi este decrementat în fiecare pas al operaţiei.
Organigrama operaţiei de înmulţire prin metoda directă este prezentată în figura 3.7.
Operaţia începe cu iniţializarea registrelor. Deînmulţitul şi înmulţitorul se încarcă în registrul B , respectiv Q . Registrul acumulator este iniţializat cu 0, iar numărătorul N este iniţializat cu n, care reprezintă numărul de cifre ale deînmulţitului şi înmulţitorului. Se formează apoi semnul rezultatului, ( nnn BQQ ⊕= ) care este păstrat în bistabilul nQ al registrului Q .
Se testează bitul 0Q al înmulţitorului şi dacă acest bit este 1, se adună deînmulţitul la produsul parţial aflat în registrul acumulator. Se deplasează apoi registrul combinat QA_ la dreapta cu o poziţie; pe poziţia c.m.s. a registrului A se introduce 0. Se decrementează apoi numărătorul N. Dacă numărătorul nu a ajuns la 0, se continuă cu pasul următor al operaţiei, testând următorul bit al înmulţitorului şi repetând operaţiile descrise anterior. Dacă numărătorul este 0, se transferă semnul rezultatului din bistabilul nQ pe poziţia c.m.s. a registrului acumulator.
In continuare vom prezenta următorul exemplu: X = 9, Y = -12. Reprezentarea acestor numere în MS este: X = 0 1001 şi Y = 1 1100. Se iau în consideraţie numai biţi de mărime, deci
1001=X , 1100=Y Determinarea semnului rezultatului se face separat. Execuţia operaţiei de
înmulţire este ilustrată în tabelul 3.2, care prezintă conţinutul registrelor dispozitivului de înmulţire în fiecare pas al operaţiei.
Tabelul 3.2. Execuţia operaţiei de înmulţire 9 x (-12) prin metoda directă Pas A Q B Qn Q0 N Operaţii
3.2.2.2. Înmulţirea prin metoda Booth Dacă numerele din calculator sunt reprezentate în C2, se preferă o
metodă de înmulţire care operează direct asupra numerelor în această reprezentare. Avantajul unei asemenea metode constă în eliminarea operaţiei de complementare a operanzilor şi a rezultatului, dacă aceştia sunt negativi, Pentru rezolvarea acestei probleme s-au elaborat mai multe metode dintre care amintim metoda Burks-Goldstine-von Neumann, metoda Robertson şi metoda Booth. Dintre acestea, metoda Booth este cea mai utilizată.
Pentru a înţelege principiul metodei Booth să considerăm două numere X şi Y , care reprezintă deînmulţitul, respectiv înmulţitorul. Pentru început să presupunem că în cadrul înmulţitorului există un grup compact de cifre 1 înconjurat de cifre 0. Astfel dacă înmulţitorul este
00111110=Y Produsul celor două numere este dat de
=×+×+×+×+×+×+×+×⋅=
=⋅=⋅
)2021212121212020(
)00111110(01234567X
XYX
62)22222( 12345 ⋅=++++⋅= XX Rezultă că pentru calcularea produsului trebuiesc efectuate 5 adunări ale
deînmulţitului. Să observăm acum că grupul de cifre 1 poate fi scris şi sub forma
161612345 22212122222 −=×−×=++++ Justificarea aceste relaţii este prezentată în continuare: 12345 22222 ++++ = 111 110 Dacă adunăm acum la ultimul rezultat numărul 10 = 101 22021 =×+× Se obţine: 111 110 +10=1 000 000 = 62 Rezultă că: 111 110 = 1 000 000 – 10 = 16 22 − Înlocuind acest rezultat în expresia obţinută anterior pentru calcularea
produsului se obţine: 62)22( 16 ⋅=−⋅=⋅ XXYX
Ultima relaţie ne arată că putem calcula acest produs numai printr-o adunare şi o scădere a deînmulţitului. Această schemă poate fi extinsă la orice număr de blocuri de 1 din cadrul înmulţitorului, inclusiv la cazul când unele blocuri conţin o singură cifră 1. Astfel dacă înmulţitorul este
00111010=Y produsul celor două numere poare fi scris ca
58)2222( 1345 ⋅=+++⋅=⋅ XXYX Sau efectuând înlocuirile:
36345 22222 −=++ şi 121 222 −= se obţine: 58)2222( 1236 ⋅=−+−⋅=⋅ XXYX
Algoritmul lui Booth utilizează această schemă, efectuând o adunare a deînmulţitului atunci când întâlneşte prima cifră a unui bloc de 1 )01( şi o
scădere a acestuia atunci când întâlneşte sfârşitul acestui bloc )10( . Acest algoritm poate fi aplicat şi în cazul unui înmulţitor negativ.
Ţinând seama de observaţia de mai sus, rezultă următorul algoritm al metodei Booth: la fiecare pas al operaţiei se testează doi biţi alăturaţi ai înmulţitorului, iy (bitul curent) şi 1−iy (bitul testat în pasul precedent, numit şi bit de referinţă). Testarea se efectuează începând cu bitul c.m.p.s. al înmulţitorului. In funcţie de valoarea biţilor testaţi 1−ii yy , se efectuează operaţiile indicate în tabelul 3.3.
Tabelul 3.3.
1−ii yy Operaţii 00 Deplasare produs parţial la dreapta 01 Adunare deînmulţit, deplasare produs parţial la dreapta 10 Scădere deînmulţit, deplasare produs parţial la dreapta 11 Deplasare produs parţial la dreapta
Structura unui dispozitiv de înmulţire prin metoda Booth este prezentată în
figura 3.8.
Fig. 3.8 Dispozitivul de înmulţire care implementează metoda Booth conţine un
registru combinat QA_ , format din registrul acumulator A şi registrul Q , de câte 1+n poziţii fiecare. In registrul Q se introduce înmulţitorul iar în A se va introduce, în timpul desfăşurării operaţiei de înmulţire, produsul parţial. Toate
Încărcare
Ştergere
Scădere/Adunare Ştergere
Bloc de comandă N
Y
Sumator / Scăzător de n+1 biţi
Bn Bn-1 … B1 B0
An An-1 An-2 … A1 A0 Qn Qn-1 … Q1 Q0
X
Încărcare
Test Q0Q-1
Deplasare
Start Stop
Q-1
poziţiile înmulţitorului inclusiv cea de semn, participă la deplasare. Registrul B , care păstrează deînmulţitul, are de asemenea 1+n poziţii. Aceste registre trebuie să aibă posibilităţi similare cu cele utilizate la metoda de înmulţire directă. Mai este necesar un bistabil 1−Q , care păstrează bitul de referinţă. Sumatorul utilizat trebuie să aibă 1+n poziţii, deoarece se operează cu toate cifrele inclusiv cea de semn.
La fiecare pas al operaţiei, blocul de comandă testează biţii succesivi notaţi cu 0Q , 1−Q . In funcţie de valoarea acestor biţi, se efectuează operaţiile necesare precizate în tabelul 3.4.
Fig.3.9 Observaţii:
1. Iniţial, bistabilul 1−Q este resetat, pentru ca bitul de referinţă pentru cifra 0Q a înmulţitorului să fie zero.
2. La deplasare se tine cont de regula de deplasare pentru numerele cu
Start
B←X Q←Y Q-1=0 A←0 N←n+1
Q-1=1
A←A+B
An←An Ai←Ai+1 Qn = A0 Qi←Qi+1 Q-1=Q0
N←N-1
N=0
Stop
Nu
Da
Nu
Da
Q0=1 Q0=1
A←A-B
Nu
Da Da Nu
00 10 01 11
semn reprezentate în C2 (Tabelul 1.7). Bitul de semn de pe poziţia nA , este deplasat în 1−nA , dar rămâne şi în nA .
3. Se compară toţi biţii înmulţitorului, inclusiv bitul de semn. 4. Rezultatul se formează în registrul QA_ de 2n+2 poziţii, bitul de semn
repetându-se pe primele două poziţii (rezultatul propriu-zis are 2n+1 biţi). Organigrama operaţiei de înmulţire prin metoda Booth este prezentată în
figura 3.9. In etapa de iniţializare, se încarcă deînmulţitul şi înmulţitorul în registrul B ,
respectiv Q , bistabilul 1−Q şi registrul acumulator sunt iniţializate cu 0 , iar numărătorul N este iniţializat cu 1+n .
In continuare se testează bitul de referinţă 1−Q şi bitul 0Q al înmulţitorului. Dacă 0110 =−QQ , se adună deînmulţitul din registrul B la produsul parţial din registrul A . Dacă 1010 =−QQ , se scade deînmulţitul din produsul parţial. Pentru celelalte două combinaţii ale biţilor testaţi, în această etapă nu se efectuează nici o operaţie. La pasul următor se deplasează la dreapta registrul combinat QA_ , astfel încât în poziţia bitului de semn nA să rămână aceeaşi valoare (păstrarea bitului de semn este indicată în organigramă prin transferul nn AA ← ). Se decrementează numărătorul N şi dacă acesta nu a ajuns la zero, se continuă operaţia cu testarea biţilor 10 −QQ . Dacă numărătorul N a ajuns la zero, operaţia se termină.
Exemplul Considerăm 13=X , 10−=Y . Exprimarea binară a acestor numere în C2
este următoarea: 0=X 1101
1=Y 0110 Scăderea deînmulţitului din conţinutul registrului acumulator A se efectuează
prin adunarea complementului faţă de 2 al acestuia X’. X’ = - X = 1 0011 In tabelul 3.4 este prezentat conţinutul registrelor dispozitivului de
înmulţire la fiecare pas al operaţiei. Tabelul 3.4. Execuţia operaţiei de înmulţire 13 x (-10) prin metoda Booth.
Pas A Q Q-1 B Q0Q-1 N Operaţii 0 0 0000 1 0110 0 0 1101 00 5 Iniţializare 1 0 0000+ 0 1011 0 0 1101 10 4 Deplasare A_Q la dreapta 2 1 0011
Observaţie. La deplasarea la dreapta a conţinutului registrelor QA_ se ţine seama de deplasare a numerelor reprezentate în C2 care cere ca pe poziţia rămasă liberă să se repete bitul de semn al numărului. Astfel la paşii 2, 3 şi 5 pe locul rămas liber s-a plasat cifra 1, iar la paşii 1 şi 4 cifra 0.
3.2.3. Împărţirea binară 3.2.3.1. Principiul împărţirii binare Fiind dat deîmpărţitul X şi împărţitorul Y , de câte n cifre de mărime,
împărţirea constă în determinarea câtului Q şi a restului R , astfel încât să fie satisfăcută relaţia:
RYQX +⋅= (3.5) Operaţia de împărţire se reduce la o serie de scăderi ale împărţitorului din
restul parţial, care se efectuează numai dacă restul parţial este mai mare decât împărţitorul, caz în care cifra câtului este 1; în caz contrar, cifra corespunzătoare a câtului este 0.
Să considerăm următoarea operaţie 147:11. In binar avem
1001147 → 0011 101111→
10010011:1011=00001101 Cât 13 1011 1110 Rest parţial 1011 1111 Rest parţial 1011 100 Rest 4 Câtul este 13, iar restul este 4. Pentru împărţire se examinează biţii
deîmpărţitului, de la stânga la dreapta, până când setul biţilor examinaţi reprezintă un număr mai mare sau egal cu împărţitorul. De exemplu, setul biţilor examinaţi este 1, 10, 100, 1001, 10010. Atât timp cât setul biţilor examinaţi este mai mic decât împărţitorul, se obţin cifre de 0 pentru cât. Atunci când acest set este mai mare sau egal cu împărţitorul, se obţine o cifră de 1 pentru cât. In continuare împărţitorul este scăzut din partea corespunzătoare a deîmpărţitului, obţinându-se un rest parţial. La fiecare pas al operaţiei se adaugă câte un bit din deîmpărţit la restul parţial, până când se obţine un număr mai mare sau egal cu împărţitorul. Se scade apoi împărţitorul din restul parţial, obţinându-se un nou rest parţial. Operaţia continuă până când se examinează toţi biţii deîmpărţitului.
In cazul în care împărţitorul este zero, operaţia de împărţire trebuie oprită,
ceea ce impune testarea împărţitorului înaintea operaţiei. Se poate testa şi deîmpărţitul înaintea operaţiei şi dacă acesta este zero, operaţia se poate termina, rezultatul fiind zero.
3.2.3.2. Metode de împărţire binară Există trei metode principale de împărţire:
• Metoda comparaţiei; • Metoda refacerii restului parţial; • Metoda fără refacerea restului parţial.
In cazul metodei comparaţiei, dispozitivul de împărţire conţine un circuit comparator, utilizat pentru compararea restului parţial cu împărţitorul. Circuitele de comparare fiind destul de complexe, această metodă nu se utilizează în mod obişnuit.
Metoda aleasă depinde de forma de reprezentare a numerelor în calculator. Metoda comparaţiei şi cea a refacerii restului parţial se pot aplica numai în cazul reprezentării numerelor în MS. Dacă numerele sunt reprezentate în altă formă, este necesară conversia formei de reprezentare în MS înaintea aplicării metodei şi conversia rezultatului operaţiei. Metoda fără refacerea restului parţial se poate aplica oricărei forme de reprezentare, fiind necesare însă unele corecţii ale rezultatului.
3.2.3.3. Metoda refacerii restului parţial In cazul metodei refacerii restului parţial, în fiecare etapă a operaţiei se
efectuează o scădere a împărţitorului din restul parţial. Dacă rezultatul scăderii este un număr negativ, deci restul parţial este mai mic decât împărţitorul, se reface restul parţial la valoarea anterioară, prin adunarea împărţitorului la restul parţial.
Fiecare etapă a operaţiei de împărţire începe cu o deplasare a restului parţial la stânga cu o poziţie. Se efectuează apoi scăderea împărţitorului din restul parţial, obţinându-se noul rest parţial. Dacă se obţine un număr pozitiv, cifra corespunzătoare a câtului este 1. Dacă se obţine un număr negativ, cifra corespunzătoare a câtului este 0 şi restul parţial este refăcut prin adunarea împărţitorului. Pentru obţinerea unui cât cu n cifre de mărime, aceste operaţii se repetă de n ori. Procesul de împărţire se opreşte dacă restul parţial devine zero sau mai mic decât împărţitorul.
Pentru implementarea algoritmului prezentat se utilizează un registru combinat format din registrul acumulator şi registrul deîmpărţitului. Iniţial registrul acumulator este 0.
Fig. 3.10
Structura dispozitivului de împărţire care utilizează metoda refacerii restului
parţial este prezentată în figura 3.10. Regiştri A , B şi Q au câte 1+n poziţii. Regiştri A şi Q se pot deplasa la
stânga, astfel încât bitul 1−nQ va trece în 0A . Bitul nQ nu participă la deplasare. Sumatorul este de n biţi. Conţinutul registrului B poate fi adunat sau scăzut din conţinutul registrului acumulator A .
Organigrama operaţiei de împărţire prin metoda refacerii restului parţial este prezentată în figura 3.11.
Deîmpărţitul X se încarcă în registrul Q . Semnul deîmpărţitului se păstrează în poziţia nQ a registrului Q . Împărţitorul Y se încarcă în registrul B . Numărătorul N se iniţializează cu numărul cifrelor de mărime n. In fiecare etapă a operaţiei, se deplasează registrul combinat QA_ la stânga cu o poziţie, iar apoi se efectuează o scădere a împărţitorului (registrul B ) din restul parţial (registrul A ). Dacă rezultă un număr pozitiv în acumulator ( 0=nA ), cifra câtului este 1, care se introduce în poziţia 0Q a registrului Q . Dacă rezultă un număr negativ în acumulator ( 1=nA ), cifra câtului care se introduce în poziţia 0Q este 0. Valoarea cifrei câtului care se obţine în această etapă este deci:
nAQ =0 Dacă în urma scăderii a rezultat un număr negativ, se reface restul parţial
prin adunarea registrului B la acumulator. Se decrementează numărătorul N şi dacă acesta nu este zero, operaţia continuă cu o nouă etapă. Dacă N este zero, operaţia este terminată, restul aflându-se în registrul A , iar câtul în registrul Q . In
Adunare Scădere
Încărcare
Ştergere X
Sumator / Scăzător de n biţi
Bn-1 Bn-2 … B1 B0
Bn
Qn
Y
Deplasare
Start Stop
Bloc de comandă
N
Încărcare
An An-1 An-2 … A1 A0 Qn-1 Qn-2 … Q1 Q0
final se stabileşte semnul restului şi al câtului. Semnul restului este semnul deîmpărţitului: nn QA = . Semnul câtului se obţine prin operaţia SAU EXCLUSIV între semnele celor doi operanzi:
nnn BQQ ⊕=
Fig. 3.11 In organigramă nu sunt arătate testele care trebuie efectuate după etapa de
iniţializare. Astfel, trebuie să se testeze dacă împărţitorul este zero; în caz afirmativ, operaţia se opreşte şi se indică o eroare de împărţire cu zero.
Exemplu Considerăm numerele 13=X şi 5=Y . Reprezentarea în MS a acestor
Start
A_Q←X B←Y N←n
Stop
Nu
A0←Qn-1 Ai←Ai-1 Qi←Qi-1
A←A-B
Qo← nA−
A←A + B
Da Nu
N←N-1
Da
An←Qn Qn←Qn⊕Bn
An = 1
N=0
numere este următoarea: 0=X 1101 0=Y 0101
Complementul faţă de 2 al împărţitorului este: Y’ = -Y = 1 1011 Scăderea se efectuează în C2 deoarece în această reprezentare operaţia
se face mai simplu. Cifrele de semn fiind tratate separat, în registrele B şi Q se încarcă numai
cifrele de mărime. La operaţia de adunare sau scădere a împărţitorului din acumulator participă însă toate cifrele. Execuţia operaţiei este prezentată în tabelul 3.7.
Tabelul 3.7 . Execuţia operaţiei de împărţire 13:5 prin metoda refacerii restului parţial. Pas A Q B Q0 Qn N Operaţii
0 0 0000 1101 0101 0 0 4 Iniţializare 1 0 0001+
11011 1 1100 + 0 0101 0 0001
1010 1010
0
0
0
3
Deplasare A_Q la stânga Scădere împărţitor Adunare împărţitor
2 0 0011+ 1 1011 1 1110 + 0 0101 0 0011
010 0 0100
0101
0
0
2
Deplasare A_Q la stânga Scădere împărţitor Adunare împărţitor
3 0 0110 + 1 1011 0 0001
100 0 1001
0101
1
0
1
Deplasare A_Q la stânga Scădere împărţitor
4 0 0011+ 1 1011 1 1110 + 0 0101 0 0011
0010 0010
0101
0
0
0
Deplasare A_Q la stânga Scădere împărţitor Adunare împărţitor
Câtul obţinut este 0 0010=2, iar restul este 0011=3.
Cap.4. UNITATEA DE COMANDĂ Şl CONTROL Funcţiile principale ale unităţii de comandă şi control (UCC) sunt următoarele: • Decodificarea codului operaţiei; • Calculul adresei operanzilor care participă la operaţie şi extragerea lor din
memorie; • Generarea secvenţei de comenzi necesare execuţiei instrucţiunii; • Generarea secvenţei de comenzi necesare memorării rezultatului şi a
informaţiilor de stare; • Calculul adresei instrucţiunii următoare şi citirea acesteia din memorie.
4.1. Microoperaţii Prelucrările efectuate de UCP pentru execuţia unei singure instrucţiuni
reprezintă un ciclu de instrucţiune. Fiecare ciclu de instrucţiune constă din următoarele subcicluri:
• Subciclul de extragere a instrucţiunii din memorie; • Subciclul de execuţie; • Subciclul de întrerupere. Pe lângă aceste subcicluri, la execuţia unei instrucţiuni mai poate apărea
subciclul de indirectare. Execuţia unei instrucţiuni poate necesita extragerea unuia sau a mai multor operanzi din memorie. Aceşti operanzi pot fi adresaţi direct sau indirect. După extragerea instrucţiunii, se verifică dacă operandul necesar este adresat în modul indirect. In caz afirmativ, se încarcă operandul respectiv utilizând adresarea indirectă.
Ciclul de instrucţiune, completat cu subciclul de indirectare, este reprezentat simplificat în figura 4.1.
Fig.4.1 Fiecare subciclu al unei instrucţiuni poate fi descompus într-o serie de
operaţii elementare. O asemenea operaţie elementară, care realizează o prelucrare numerică a informaţiei sau un transfer al acesteia, pe durata unui singur impuls al generatorului de tact, se numeşte microoperaţie. Unitatea de
Subciclul de extragere
Subciclul de întrerupere
Subciclul de execuţie
Subciclul de indirectare
comandă şi control are rolul de a genera succesiunea semnalelor de comandă care asigură secvenţa corectă de execuţie a fiecărei microoperaţii. Această suc-cesiune este specifică fiecărei instrucţiuni, fiind determinată atât de codul operaţiei cât şi de recepţionarea unor semnale de stare de la circuitele controlate, prin care se verifică îndeplinirea unor condiţii.
In continuare se analizează subciclurile care intră în componenţa unei instrucţiuni şi microoperaţiile din care se compune fiecare subciclu. Pentru aceasta să presupunem că UCP utilizează următorii regiştri:
- Registrul de adrese al memoriei (RA). Acest registru este conectat la liniile de adresă ale magistralei sistem şi conţine adresa din memorie a unei instrucţiuni sau a unei date. - Registrul de date al memoriei (RD). Acest registru este conectat la liniile de date ale magistralei sistem şi conţine valoarea care trebuie depusă în memorie sau ultima valoare citită din memorie. - Contorul de program (PC) conţine adresa următoarei instrucţiuni care se va executa. - Registrul de instrucţiuni (Rl) conţine ultima instrucţiune citită.
4.1.1. Subciclul de extragere In acest subciclu este adusă în UCP o instrucţiune din memorie. Operaţiile
executate în acest subciclu sunt indicate în figura 4.2. Registrul PC conţine adresa instrucţiunii care urmează să fie executată. Această adresă este depusă în RA [1] şi apoi este plasată pe magistrala de adrese (MA) [2]. Unitatea de comandă solicită o operaţie de citire a memoriei, trimiţând pe magistrala de comandă (MC) o comandă către Unitatea de memorie [3]. Conţinutul locaţiei de memorie a cărei adresă a fost transmisă Unităţii de memorie este plasat pe magistrala de date (MD) şi reţinut în registrul de date (RD) [4]. In acelaşi timp UCC elaborează comanda de incrementare a registrului Program Counter (PC) [5], pregătind astfel următorul ciclu de extragere. Registrul, RD fiind unica poartă de intrare/ieşire în UCP, trebuie golit de informaţiile pe care le conţine, astfel încât instrucţiunea care se află în acesta este transferată în registrul de instrucţiuni (RI) [6]. In RI instrucţiunea este decodificată şi este păstrată pe toată perioada executării acesteia.
Generatorul de tact al sistemului de calcul generează impulsuri de tact (ceas) la intervale constante. Fiecare impuls de ceas defineşte o unitate de timp. Această unitate de timp este aleasă astfel încât fiecare microoperaţie să poată fie executată pe durata unui singur impuls de ceas. Unităţile de timp sunt notate cu
321 ,, ttt . Simbolic, secvenţa de microinstrucţiuni care descrie microoperaţiile
prezentate anterior se poate scrie astfel:
Fig.4.2 Subciclul de extragere
:1t RA←PC :2t RD←Mem
PC←PC+1 :3t RI←RD
A treia microoperaţie se poate executa şi în unitatea de timp t3, fără a afecta subciclul de extragere.
4.1.2. Subciclul de indirectare După extragerea instrucţiunii din memorie, urmează să se încarce
operanzii care participă la operaţie specificată de această instrucţiune. O instrucţiune este formată din cel puţin două câmpuri. Primul câmp conţine codul operaţiei ce trebuie executată iar cel de al doilea câmp conţine adresa din memorie a operandului implicat în operaţie.
Unitatea de comandă examinează câmpul de adresă a instrucţiunii din registrul Rl şi, dacă este indicată o adresare directă, aduce în RD conţinutul locaţiei de memorie a cărei adresă este specificată în câmpul de adresă a instrucţiunii. Adresarea directă se referă la situaţia în care câmpul de adresă conţine adresa efectivă a operandului (Figura 4.3):
PC RA
UCC
RD RI
Memorie
MA MD MC UCP
1 2
3
4
4 6
5
Fig. 4.3 Acest mod de adresare presupune o singură referire la memorie şi nu
necesită un calcul de adresă. In acest caz după subciclul de extragere urmează subciclul de execuţie.
In cazul adresării indirecte, înaintea subciclului de execuţie este necesar un subciclu de indirectare. Adresarea indirectă se referă la situaţia în care în câmpul de adresă al instrucţiunii se găseşte o referinţă ADR1 la un cuvânt de memorie, care conţine adresa completă ADR2 a operandului. Vezi figura 4.4.
Fig. 4.4 Adresa ADR1 din câmpul de adresă al registrului de instrucţiuni Rl este
transferat în RA [1] şi este apoi depusă pe magistrala de adrese [2]. Unitatea de comandă generează semnalele de comandă [3] necesare pentru aducerea în registrul de date RD a adresei ADR2 a operandului [4]. In continuare, câmpul de adresă din Rl este actualizat pentru a conţine adresa directă a operandului [5]. Această adresă este utilizată apoi pentru încărcarea operandului în registrul de date RD.
ADR 2 Operand
CO ADR 1
Instrucţiune
Memorie
CO Adresă
Instrucţiune
Operand
Memorie
Fig.4.5 Subciclul de indirectare După executarea acestor operaţii urmează subciclul de execuţie. Operaţiile
executate în subciclu de indirectare sunt indicate în figura 4.5. Descrierea simbolică a microoperaţiilor prezentate este următoarea:
1t : RA ← RI(câmpul de adresă) (ADR1 în RA) 2t : RD ← Mem (ADR2 din memorie în RD) 3t : Rl(câmpul de adresă) ← RD (ADR2 în RI)
4.1.3. Subciclul de execuţie Subciclurile de extragere şi de indirectare, ca şi subciclul de întrerupere,
implică secvenţe fixe de microinstrucţiuni. Subciclul de execuţie diferă în funcţie de instrucţiune, pentru fiecare instrucţiune existând o secvenţă proprie de microinstrucţiuni care trebuiesc executate.
Considerăm ca exemplu instrucţiunea: ADD X
care adună valoarea variabilei X din memorie la conţinutul registrului A, rezultatul fiind memorat tot în A. Acest registru cu funcţie specială este numit registru acumulator. In acest context X reprezintă adresa din memorie a valorii variabilei X.
Execuţia acestei instrucţiuni poate fi descrisă prin următoarea secvenţă de microinstrucţiuni:
:1t RA←RI(câmpul de adresă) (ADR X în RA) :2t RD←Mem :3t A←A+RD
Rl conţine codul instrucţiunii ADD. La primul pas (t1), partea de adresă din Rl, care reprezintă adresa variabilei X, este încărcată în RA. La pasul t2 se copie,
UCP
RA
UCC
RD RI
Memorie
MA MD MC
1 2
3
4 5
din locaţia de memorie adresată, valoarea variabilei X şi se depune în RD. In final (t3), conţinutul registrului A (registru acumulator) şi al RD sunt adunate de UAL şi rezultatul este memorat tot în registrul A.
4.1.4. Subciclul de întrerupere Sistemul de întreruperi este acea parte a unui sistem de calcul care
permite detectarea unor evenimente externe sau interne şi declanşarea unor acţiuni corespunzătoare pentru tratarea lor. Aceste evenimente pot fi: tentativa de execuţie a unui cod de instrucţiune nepermis, terminarea unei anumite operaţii de către un dispozitiv de I/E, o eroare produsă în timpul execuţiei unei operaţii aritmetice (împărţire la zero, depăşire superioară sau inferioară), situaţii critice in funcţionarea unui sistem de calcul (ex: eroare de paritate, fluctuaţii ale tensiunii de alimentare, etc.).
Pentru a stabili ordinea de deservire a cererilor concurente de întrerupere, sistemele de întrerupere utilizează o ierarhie de priorităţi. Prioritatea unei întreruperi se stabileşte pe baza importantei acordate evenimentului tratat si a restricţiilor de timp în soluţionarea acesteia. Sistemul de întreruperi al unui calculator poate să identifice mai multe niveluri de întrerupere. Adresele de început ale acestor rutine se păstrează intr-un tabel din memorie. In funcţie de cerinţele programului executat, anumite niveluri de întrerupere pot fi invalidate, temporar sau pe toată durata aplicaţiei.
La terminarea subciclului de execuţie, în cazul în care întreruperile sunt validate, se testează dacă a apărut o cerere de întrerupere. In caz afirmativ, se execută un subciclu de întrerupere. Secvenţa de operaţii executate este următoarea:
1. Se salvează contextul programului curent. Prin context se înţelege conţinutul registrului PC, în care se găseşte adresa instrucţiunii ce urmează să fie executată după reluarea execuţiei programului, conţinutul registrului de stare PSW, precum şi a altor registre care conţin date semnificative pentru programul respectiv.
2. Se încarcă în contorul de program adresa programului de servire a întreruperii. UCP va executa în continuare instrucţiunile din rutina de servire, după care va reveni la programul întrerupt.
Transferurile de date din subciclul de întrerupere se prezintă în figura 4.6.
Fig.4.6 Subciclul de întrerupere Subciclul de întrerupere poate fi descris prin următoarea secvenţă de
microinstrucţiuni: :1t RD ← PC :2t RA ← Adresa_salvare
PC ← Adresa_rutina :3t Mem ← RD
După cum se constată, în momentul t2, adresa rutinei de tratare a întreruperii se transferă în PC. Ca urmare, următorul ciclu de instrucţiune va începe prin extragerea primei instrucţiuni din rutina de tratare a întreruperii.
Procesoarele actuale au extins sistemul de întreruperi pentru a eficientiza funcţionarea UCP. De exemplu, cele mai multe periferice sunt mult mai lente în comparaţie cu UCP şi aceasta ar trebui să rămână inactivă până la terminarea unei operaţii de transfer cu un dispozitiv I/E. Prin mecanismul întreruperilor, în timpul unei operaţii de I/E, UCP poate executa instrucţiunile altui program.
Sistemul de întreruperi este utilizat de asemenea pentru rularea mai multor programe în acelaşi timp (time sharing). Datorită vitezei mari de lucru a procesorului se lansează în execuţie mai multe programe, pentru fiecare dintre acestea alocându-se o anumită cuantă de timp. In acest mod utilizator are senzaţia că programele sunt executate simultan.
4.2.1 Semnale de control ale UCC Pentru a-şi realiza funcţiile, unitatea de comandă trebuie să primească o
serie de semnale care să-i permită determinarea stării sistemului iar pe baza acestor informaţii elaborează semnale care controlează funcţionarea sistemului. Intrările şi ieşirile unei unităţi de comandă şi control sunt prezentate în figura 4.7. UCC are următoarele intrări:
- Semnalul de ceas. UCC comandă execuţia unei microinstrucţiuni (sau a
PC
RD
UCC
RA Memorie
UCP MA MD MC
1
3
2
4
6 6
unui set de microinstrucţiuni simultane) la fiecare impuls de ceas. Perioada semnalului de ceas se mai numeşte ciclu de ceas.
- Codul operaţiei este citit din registrul de instrucţiuni, care păstrează instrucţiunea curentă, şi se utilizează pentru a determina microinstrucţiunile care trebuie executate în timpul ciclului de execuţie.
- Indicatorii de condiţii sunt necesari pentru a determina starea UCP şi rezultatul operaţiei precedente executate de UAL, în scopul executării instrucţiunilor de salt condiţionat.
- Semnale de control. Magistrala de control transmite către UCC semnale de întrerupere, sau de achitare (terminare) a unei întreruperi.
Fig. 4.7 Semnale de control UCC
UCC elaborează următoarele semnale de ieşire: - Semnale prin care se comandă funcţionarea UCP. Acestea sunt de două
tipuri: semnalele care determină transferul datelor dintr-un registru în altul şi semnalele care activează funcţii specifice ale UAL.
- Semnale de control transmise pe magistrala de control. Acestea sunt tot de două tipuri: semnale de control către memorie şi semnale de control către modulele de I/E.
Pentru a înţelege funcţionarea UCC să considerăm din nou ciclul de încărcare al unei instrucţiuni. Adresa instrucţiunii care urmează să fie executată este păstrată în registrul PC. Primul pas constă în transferul:
RA ←PC Acest transfer se efectuează prin activarea unui semnal de control care
deschide (activează) porţile dintre cele două registre. Următorul pas constă în citirea din memorie a instrucţiunii de la adresa
indicată, aducerea acesteia în registrul de date şi incrementarea contorului de program PC:
RD ← Mem PC ← PC + 1 Aceste operaţii se efectuează prin activarea simultană de către UCC a
următoarelor semnale de control:
Indicatori de condiţie
Ceas
Semnale de la MC
Semnale de control la MC
UCC
RI Semnale de control UCP
MC
1. un semnal de control care validează depunerea conţinutului RA pe magistrala de adrese.
2. un semnal de control trimis pe magistrala de control, pentru citirea memoriei.
3. un semnal de control care validează memorarea conţinutului de pe magistrala de date în registrul de date RD.
4. semnale de control prin care se incrementează cu 1 conţinutul PC şi se depune rezultatul înapoi în PC.
Ultimul pas constă în transferul: RI ← RD
pentru care se activează un alt semnal de control care validează transferul. In continuare UCC trebuie să decidă dacă urmează un ciclu de indirectare
sau un ciclu de execuţie. Pentru aceasta, examinează conţinutul registrului de instrucţiuni Rl şi testează dacă se utilizează o adresare indirectă, caz în care stabileşte secvenţa corespunzătoare de microoperaţii.
Pentru ciclul de execuţie, UCC testează codul de operaţie al instrucţiunii, pe baza căruia decide secvenţa de microoperaţii care va fi executată.
4.2.2. Implementarea UCC Pentru implementarea UCC se utilizează diferite metode, care se pot
încadra într-una din următoarele două categorii: • UCC cablată; • UCC microprogramată.
O unitate de comandă cablată este, în principiu, un circuit secvenţial care transformă semnalele logice de intrare într-un set de semnale electrice de ieşire, ce reprezintă semnalele de control. Modificarea funcţiilor unei astfel de unităţi de comandă necesită modificări ale structurii hardware a circuitului.
4.2.3. UCC cablată care utilizează un decodificator UCC preia de la registrul RI codul instrucţiunii curente şi pe baza acestuia
va stabili acţiunile ce urmează să fie executate. In cazul unităţii de comandă, luată în discuţie, codul instrucţiunii este decodificat cu ajutorul unui decodificator care activează la un moment dat un singur semnal de ieşire.
Impulsurile generatorului de ceas al sistemului acţionează asupra unui generator de faze, care generează semnalele de intrare nTTT ,...,, 21 ce asigură secvenţierea în timp a semnalelor de comandă. In fiecare din aceste momente UCC activează semnalele de comandă cerute de codul instrucţiunii. La sfârşitul fiecărui ciclu de instrucţiune, UCC reiniţializează generatorul de faze pentru a relua generarea secvenţei nTTT ,...,, 21 .
Structura unei UCC cu decodificator este prezentată în figura 4.8. Codul instrucţiunii este preluat din registrul RI şi transformat de circuitul de decodificare în semnalele binare D1, D2, …Dn. La fiecare din momentele T1,T2,…Tn UCC va elabora câte un semnal de comandă C1, C2,… Cn, care vor declanşa acţiunile implicate de execuţia instrucţiunii decodificate.
Fig. 4.8 UCC cu decodificator 4.2.4. Unităţi de comandă microprogramate Semnalele de comandă elaborate de UCC pot fi reunite sub forma unei
succesiuni de cifre binare, numită cuvânt de comandă. Fiecare microoperaţie se caracterizează printr-un cuvânt specific de comandă, iar succesiunea cuvintelor de comandă prin care se indică secvenţa corectă a microoperaţiilor, pentru fiecare operaţie, poate fi memorată într-o memorie de comandă.
O unitate de comandă în care succesiunea cuvintelor de comandă, este memorată, se numeşte unitate de comandă microprogramată. Fiecare cuvânt de comandă memorat în memoria de comandă formează o microinstrucţiune, iar secvenţa de microinstrucţiuni formează un microprogram.
O unitate de comandă microprogramată are două funcţii principale: - Funcţia de control propriu-zis, prin care se stabilesc microinstrucţiunile
care trebuiesc executate pentru instrucţiunea decodificată. - Funcţia de secvenţiere, prin care se determină adresa microinstrucţiunii
următoare. In conformitate cu aceste funcţii pe care trebuie să le îndeplinească
unitatea ce comandă microprogramată, o microinstrucţiune este formată din următoarele câmpuri principale (Fig. 4.9):
- Câmpul semnalelor de comandă generate pentru controlul UCP. Acest câmp conţine câte un bit pentru fiecare semnal de comandă intern al UCP.
- Câmpul semnalelor de comandă pentru magistrala sistem. Acest câmp conţine câte un bit pentru fiecare semnal de comandă al magistralei sistem.
- Câmpul de condiţii, de care depinde următoarea microinstrucţiune care va fi executată.
- Câmpul de adresă, care conţine adresa următoarei microinstrucţiuni care se va executa, dacă o anumită condiţie este adevărată. De exemplu, dacă bitul de indirectare din codul instrucţiunii este 1 (condiţia aste adevărată), se va executa secvenţa de microinstrucţiuni pentru calcularea adresei efective a operandului.
Dn D2 D1
Indicatori de condiţii
T1 T2 Tn
Cn … C2 C1
Decodificator
RI
UCC
Generator
de faze
Ceas
Dacă acest bit este 0 (condiţia este falsă), se va executa următoarea microinstrucţiune din memoria de comandă, a cărei adresă este indicată în câmp.
Fig. 4.9 Acest tip de microinstrucţiune se numeşte microinstrucţiune orizontală. Spre
deosebire de acestea se utilizează şi microinstrucţiuni verticale care utilizează un cod pentru fiecare operaţie care trebuie executată.
Totalitatea microinstrucţiunilor care constituie o unitate logică formează un microprogram.
O microinstrucţiune orizontală este interpretată în modul următor: 1. Pentru execuţia unei microinstrucţiuni, se activează toate semnalele de
control cărora le corespunde un bit de 1 în câmpul semnalelor de comandă şi se dezactivează cele cărora le corespunde un bit de 0.
2. In cazul în care condiţia indicată de câmpul de condiţie este falsă, se trece la execuţia următoarei microinstrucţiuni din microprogram. In cazul în care condiţia indicată de câmpul de condiţie este adevărată, se trece la execuţia microinstrucţiunii indicată de câmpul de adresă.
In figura 4.10 se prezintă amplasarea microprogramelor în memoria de comandă.
Fiecare rutină este constituită dintr-un microprogram. Microinstrucţiunile din fiecare rutină sunt executate secvenţial. Fiecare rutină se termină cu o instrucţiune de salt care indică următoarea rutină care va fi executată. Există o rutină specială pentru începutul unui subciclu de execuţie, care după încărcare şi decodificare indică rutina care va fi executată pentru diferitele instrucţiuni (ADD, AND, ..., JMP), în funcţie de codul instrucţiunii.
Memoria de comandă reprezintă o descriere completă a funcţionării UCC, deoarece defineşte secvenţa de microinstrucţiuni care trebuie executate în timpul fiecărui subciclu (de extragere, de indirectare, de execuţie, de întrerupere) şi specifică secvenţierea acestor subcicluri.
Adresă microinstrucţiune Câmp de condiţii
- Salt necondiţionat - Zero - Depăşire - Bit de indirectare Semnale de control pentru magistrala sistem Semnale de control pentru UCP
Fig. 4.10
In figura 4.11 se prezintă elementele principale ale unei unităţi de comandă microprogramate.
Registrul de microadrese RMA conţine adresa următoarei microinstrucţiuni care va fi citită din memoria de comandă. După citirea din memoria de comandă, microinstrucţiunea este transferată în registrul de microinstrucţiuni RMI.
Unitatea microprogramată are aceleaşi intrări (Rl, indicatori de condiţii ai UAL, ceas) şi ieşiri (semnale de comandă) ca şi o unitate de comandă cablată. Unitatea de comandă microprogramată funcţionează astfel:
1. Instrucţiunea din RI este decodificată de decodificatorul 1 rezultând adresa din memoria de comandă a următoarei microinstrucţiuni.
2. Pentru extragerea microinstrucţiunii a cărei adresă se găseşte în RMA, logica de secvenţiere activează un semnal de citire a memoriei de comandă.
3. Microinstrucţiunea extrasă din memoria de comandă este depusă în registrul de microinstrucţiuni (RMI).
4. După decodificarea microinstrucţiunii din RMI sunt activate semnalele de control pentru UCP, magistrala de control şi pentru blocul de secvenţiere.
5. Logica de secvenţiere încarcă o nouă adresă în registrul de microadrese, pe baza informaţiilor despre adresa următoare de la registrul de microinstrucţiuni RMI şi a indicatorilor de condiţii ai UAL.
Dezavantajul unităţilor microprogramate este că sunt mai lente decât cele cablate realizate într-o tehnologie comparabilă.
.
. Salt la indirectare sau execuţie. . . Salt la execuţie . . Salt la extagere Salt la decodificarea codului op. . . Salt la întrerupere sau extragere . . Salt la întrerupere sau extragere
Rutina pentru ciclul de extragere Rutina pentru ciclul de indirectare Rutina pentru ciclul de întrerupere Început ciclu de execuţie Rutina pentru ADD Rutina pentru AND Rutina pentru JMP
.
.
.
.
. Salt la întrerupere sau extragere
Fig. 4.11 Unitate de comandă microprogramată
Cu toate acestea, micro-programarea este tehnica cea mai utilizată pentru implementarea unităţilor de comandă.
RI
Decodificator 1
RMA
Memorie de comandă
RMI
Logică de
secvenţiere
Indicatori de condiţii
Ceas
READ
Semnale de control UCP
Decodificator 2
Semnale de control pe magistrala
Cap.5. Magistrale 5.1 Noţiuni generale Prin magistrală se înţelege un ansamblu de linii conductoare, grupate
funcţional, menite să conecteze două sau mai multe unităţi ale unui sistem de calcul. Pe fiecare linie a unei magistrale se poate transfera, la un moment dat, o singură valoare logică (asignată unui nivel de tensiune bine definit), ce reprezintă o cantitate de informaţie de 1 bit. Dacă magistrala are n linii, atunci pe magistrală se transferă n biţi de informaţie în paralel şi vom spune că magistrala transferă cuvinte de informaţie de dimensiune n.
Anumite dispozitive conectate la magistrală sunt active şi pot iniţia un transfer, iar altele sunt pasive şi aşteaptă cererile de transfer. Dispozitivele active se numesc dispozitive master, iar cele pasive - dispozitive slave. Atunci când UCP solicită unui controler de disc citirea sau scrierea unui bloc, UCP are rol de master, iar controlerul are rol de slave. Controlerul de disc poate deveni master, de exemplu atunci când solicită memoriei acceptarea cuvintelor citite de pe disc. Memoria nu poate deveni master în nici o situaţie.
Pentru amplificarea semnalelor, dispozitivele master se conectează la magistrală prin drivere de magistrală (bus driver). Similar, dispozitivele slave sunt conectate prin receptoare de magistrală (bus receiver). Pentru dispozitivele care pot fi atât emiţătoare cât şi receptoare, se utilizează circuite emiţătoare/receptoare de magistrală (bus transceiver).
5.2. Clasificarea magistralelor După modul de transfer al informaţiilor, magistralele pot fi: - magistrale unidirecţionale la care transferul de informaţii se efectuează pe
toate liniile într-un singur sens, de la o unitate emiţătoare către una sau mai multe unităţi receptoare;
- magistrale bidirecţionale la care transferul se poate efectua în ambele sensuri, alternativ prin multiplexare în timp, la un moment dat transferându-se informaţii într-un singur sens. Astfel, unităţile conectate la o magistrală bidirecţională pot fi pe rând unităţi emiţătoare sau receptoare de semnale.
După tipul informaţiilor transferate, magistralele pot fi: - magistrale primare pe care au loc transferurile informaţiilor utile ce se
doresc a fi transmise între subsistemele unui calculator. Acestea pot fi: magistrale de instrucţiuni sau magistrale de date. Deoarece memoria sistemului este comună pentru programe şi date, cele două tipuri de informaţii primare sunt transferate pe o magistrală bidirecţională, numită generic magistrală de date.
- magistrale secundare pe care au loc transferurile de informaţii suplimentare, necesare obţinerii informaţiilor primare. Acestea pot fi: magistrale de adrese, magistrale de comenzi sau magistrale de stări, considerate în general unidirecţionale. Cele două magistrale, de comenzi şi de stări transferă informaţii în sensuri opuse şi formează împreună o magistrală bidirecţională pe linii separate, numită magistrală de control.
După rata de transfer şi implicit după numărul de unităţi conectate, putem
avea: - magistrale locale care sunt amplasate în apropierea unităţilor foarte rapide
cum este, de exemplu, procesorul. Aceste magistrale sunt caracterizate de o rată mare de transfer şi un număr mic de unităţi ce pot fi conectate la ele. Ca exemple, pot fi date: magistrala locală a procesorului, magistrala locală a memoriei;
- magistrale de extensie (magistrale I/O), care sunt magistrale accesibile utilizatorului, fiind terminate cu conectoare de extensie.
Magistralele de extensie sunt amplasate mai departe de procesor şi sunt caracterizate de o rată mai mică de transfer şi un număr relativ mare de unităţi ce pot fi conectate la ele. După modul de control al transferului de informaţii, magistralele pot fi:
- Magistrale sincrone. Toate operaţiile magistralelor sincrone sunt sincronizate de un semnal de ceas şi orice transfer durează un număr întreg de perioade de ceas, numite cicluri de magistrala. In cazul acestor magistrale, dacă un transfer se termină înaintea unui număr întreg de cicluri, următorul transfer poate începe numai după sfârşitul ciclului în curs de desfăşurare. Această situaţie conduce la întârzieri inutile.
- Magistrale asincrone. O magistrală asincronă elimină dezavantajele magistralelor sincrone. In locul semnalului de ceas se utilizează un protocol logic între emiţător şi receptor (numit handshake). In cadrul acestui protocol are loc un schimb de informaţii între unitatea master şi unitatea slave care permit corelarea şi coordonarea transferului de date. Fiecare acţiune a celor doi participanţi la transfer este condiţionată de o acţiune anterioară şi nu de un impuls de ceas.
Magistralele asincrone necesită mai multe linii de semnal şi o logică mai complexă, fapt care ridică preţul acestora. Pentru acest motiv, în ciuda avantajelor prezentate de magistralele asincrone, magistralele sincrone sunt mai des utilizate.
Dacă la o magistrală sunt conectate dispozitive cu viteze diferite (unele lente, altele rapide), viteza de transfer trebuie aleasă după dispozitivul cel mai lent, dispozitivele rapide fiind întârziate.
5.3. Arbitrajul de magistrală La majoritatea sistemelor, există mai multe module care pot prelua controlul
asupra magistralei (care pot deveni module master). Pentru acest motiv, dacă apar mai multe cereri simultane de magistrală, este necesar să existe un mecanism de arbitrare prin care să se determine modulul care va deveni master. Modulul master va putea apoi iniţia un transfer cu un alt modul care, pentru acest transfer, va avea rolul de modul slave.
Metodele de arbitrare pot fi clasificate ca fiind centralizate sau descentralizate (distribuite).
5.3.1. Arbitrarea centralizată In cazul arbitrării centralizate, alocarea magistralei este realizată de un dispozitiv
hardware numit arbitru de magistrală. Acest dispozitiv poate fi un modul separat sau poate face parte din UCP.
In figura 5.1 se prezintă un exemplu simplu de arbitrare centralizată. In cadrul acestei soluţii există o singură linie de cerere a magistralei, care poate fi activată de
unul sau mai multe dispozitive în orice moment. Arbitrul nu poate distinge dacă există mai multe cereri simultane sau o singură cerere, ci numai dacă există sau nu cereri la un moment dat.
Fig. 5.1 Arbitrarea centralizată Dacă apare un semnal pe linia de cerere, arbitrul activează linia de acordare a
magistralei, la care sunt conectate în serie toate dispozitivele. Dispozitivul cel mai apropiat fizic de arbitru detectează semnalul de pe această linie şi, în cazul în care a efectuat o cerere, preia controlul asupra magistralei. Dacă nu a efectuat o cerere, transmite semnalul următorului dispozitiv, care procedează la fel, până când un dispozitiv preia controlul asupra magistralei.
In această schemă de tip daisy chain, prioritatea dispozitivelor este dată de distanţa la care se află faţă de arbitru. Dispozitivul cel mai apropiat de arbitru are prioritatea maximă. Pentru a modifica aceste priorităţi implicite, magistralele pot avea mai multe niveluri de prioritate. In acest caz pentru fiecare prioritate există o linie de cerere şi una de acordare a magistralei.
5.3.2. Arbitrarea descentralizată In cazul arbitrării descentralizate nu există un arbitru de magistrală. Fiecare modul
are o prioritate unică şi conţine o logică pentru controlul accesului la magistrală care ţine cont de priorităţile celorlalte module. Atunci când un anumit modul solicită accesul la magistrală, acesta verifică mai întâi dacă există vreun modul cu prioritate mai mare care, de asemenea, solicită magistrala. In cazul în care o asemenea cerere nu există, iniţiază transferul. Dacă un modul cu prioritate mai mare iniţiază o cerere în acelaşi ciclu de ceas, modulul iniţial menţine cererea până magistrala este eliberată.
5.4. Parcarea magistralelor Anumite dispozitive master ale unui sistem de calcul ca, de exemplu, unităţile
centrale, sunt active în marea majoritate a timpului, în timp ce altele sunt active în mod sporadic. Un dispozitiv din prima categorie poate păstra controlul asupra magistralei chiar şi după terminarea transferului curent, deoarece este foarte probabil că va utiliza magistrala şi în continuare. Procedura prin care magistrala nu este eliberată automat după terminarea transferului curent ci numai în cazul în care există o cerere
magistrala
Acordare
Arbitru
D1
D2
D4
D3
Dispozitive de I/E
Cerere magistrala
de magistrală, se numeşte parcarea magistralei. Prin utilizarea acestei metode, nu este necesară executarea operaţiilor de
eliberare a magistralei şi de arbitrare pentru fiecare transfer. Dacă se utilizează parcarea magistralei orice alt modul care solicită accesul la magistrală începe cu o cerere adresată dispozitivului master de a elibera magistrala.
5.5. Magistrale locale Aceste magistrale deservesc unităţile foarte rapide cum sunt UCP şi
memoria principală. Magistrala procesorului este calea de comunicaţie între UCP şi subsistemele
cu care acesta lucrează direct. Magistrala procesorului este utilizată, de exemplu, pentru a transfera date între UCP şi magistrala principală a sistemului sau între UCP şi memoria externă rapidă (memoria cache). Deoarece de performanţele acestei magistrale depind în mare măsură performanţele calculatorului, această magistrală lucrează la o viteză mult mai mare decât orice altă magistrală din sistem.
Magistrala procesorului are în componenţa magistrala de date, magistrala de adrese şi pe cea de control. De exemplu, magistrala procesorului unui sistem Pentium are 64 linii de date, 32 linii de adresă şi un număr de linii de control asociate.
Magistrala memoriei este utilizată la transferul informaţiei între UCP şi memoria principală - memoria RAM a sistemului. Această magistrală este implementată printr-un set de circuite dedicate şi este responsabilă cu transferul informaţiilor între magistrala procesorului şi memorie. In componenţa magistralei memoriei intră şi o magistrala de adrese utilizată pentru selecţia locaţiei de memorie în care urmează să se efectueze o operaţie de citire/scriere.
Fig. 5.2 Magistrale locale Dimensiunea magistralei de memorie este strâns legată de mărimea
memoriei pe care unitatea centrală o poate adresa direct. In figura 5.2 sunt
Magistrala procesorului
Magistrala principală a sistemului
Magistrala principală a sistemului
UCP Memorie externă rapidă
Controlerul de memorie
RAM
Magistrala memoriei
prezentate magistralele locale ale unui sistem de calcul. 5.6. Magistrala de extensie Magistrala de extensie, numită şi magistrală l/O, permite unităţii centrale să
comunice cu dispozitivele periferice. Magistrala l/O face posibilă, de asemenea, adăugarea de noi dispozitive pentru a extinde posibilităţile de prelucrare ale calculatorului. In conectorii de extensie pot fi introduse componente de bază, cum sunt controlerele de hard disc şi plăcile adaptoare video; de asemenea, se pot introduce dispozitive mai specializate, cum ar fi plăci de sunet şi plăci de interfaţă cu unităţi CD-ROM.
De-a lungul evoluţiei sistemelor de calcul s-au dezvoltat mai multe tipuri de magistrale de I/O. Dintre acestea cele mai importante sunt:
- ISA; - EISA; - MCA; - Magistrala locală; - Magistrala VESA locală; - Magistrala PCI; - Magistrala PCMCIA. Aceste magistrale se deosebesc în principal prin numărul de informaţii
transferate simultan şi prin viteza cu care se face acest transfer. Arhitectura magistralei este realizată cu un set de circuite care este conectat la magistrala procesorului.
5.6.1 Magistrala ISA Magistrala ISA (Industry Standard Architecture) este arhitectura de
magistrală introdusă odată cu primul IBM PC, în 1982 şi care a fost mai târziu îmbunătăţită la modelul IBM PC/AT. Până nu de mult magistrala ISA stătea la baza calculatorului personal modern şi era principala arhitectură folosită în marea majoritate a sistemelor PC de pe piaţă. Longevitatea acestei magistrale se datorează siguranţei, accesibilităţii şi compatibilităţii sale. Magistrala ISA a fost concepută să lucreze cu arhitecturi pe 8 biţi şi mai târziu a fost extinsă pentru 16 biţi.
5.6.2 Magistrala EISA
EISA sunt iniţialele pentru Extended Industry Standard Architecture. Aşa cum arată şi numele, magistrala EISA este o extindere a magistralei ISA, astfel încât să permită arhitecturi de 32 de biţi şi viteze de transfer superioare, păstrând însă compatibilitatea cu plăcile de extensie existente şi cu perifericele. In comparaţie cu arhitectura de sistem ISA pe 16 biţi, EISA permite mai multe extensii cu mai puţine conflicte intre plăcile adaptoare.
Pentru a mări viteza sistemului, EISA utilizează o tehnologie numită bus mastering (controlul total al magistralei). In esenţă, un dispozitiv cu opţiunea de control total al magistralei este un adaptor prevăzut cu un procesor, care poate executa operaţii independent de UCP. Pentru a funcţiona corespunzător,
tehnologia bus-mastering se bazează pe un circuit de arbitrare EISA (EISA arbitration unit), numit de obicei cip ISP (Integrated System Peripheral - sistem periferic integrat). De exemplu, un controler de disc în tehnologia bus-mastering schimbă un volum de date mult mai mare cu o unitate rapidă de hard disc, în comparaţie cu un controler obişnuit.
Unitatea ISP decide care dispozitiv primeşte controlul, printr-un sistem de patru niveluri de prioritate. Ordinea dată de nivelurile de prioritate este următoarea:
- Reîmprospătarea memoriei - Transferuri DMA (Direct Memory Access) - UCP - Plăci bus-master Dispozitivul adaptor cu bus-mastering semnalează unităţii ISP că doreşte să
preia controlul sistemului. In cel mai scurt timp posibil (după ce au fost satisfăcute priorităţile mai mari), ISP predă controlul dispozitivului. Aceste dispozitive au incluse la rândul lor circuite care le împiedică să păstreze controlul pe perioade de timp mai mari decât cele necesare operaţiilor ciclice cum este, de exemplu, împrospătarea memoriei.
5.6.3 Magistrala MCA Apariţia procesoarelor pe 32 de biţi a făcut ca magistrala ISA să nu mai
corespundă noii generaţii de procesoare. Microprocesoarele 386 transferă 32 de biţi de date simultan, iar magistrala ISA putea să transfere doar maxim 16 biţi. In loc să extindă din nou magistrala ISA, IBM a decis să construiască o nouă magistrală; aşa a apărut magistrala MCA (Micro Channel Architecture). MCA admite controlul total al magistralei (bus-mastering). Prin implementarea tehnologiei bus-mastering, descrisă în aliniatul anterior, s-au realizat îmbunătăţiri semnificative ale performanţelor în comparaţie cu magistrala ISA. Dispozitivul de arbitrare controlează competiţia pentru transferul pe magistrală, asigurând accesul tuturor dispozitivelor la magistrală dar împiedicând, în acelaşi timp, monopolizarea acesteia de singur dispozitiv.
Sistemul de arbitraj al magistralei are în structura sa 4 linii de prioritate, care stabilesc 16 nivele de prioritate. Fiecărui dispozitiv master i se atribuie un nivel de prioritate între 0 şi F, nivelul F fiind cel mai puţin prioritar. Dispozitivul cu nivelul de prioritate F este numit master implicit. Atunci când nu există nici un alt master sau la apariţia unei condiţii de excepţie, magistrala este acordată acestui dispozitiv.
Un dispozitiv conectat la magistrala Micro Channel, care doreşte să utilizeze magistrala, trimite numărul de prioritate, ce i-a fost acordat, pe cele 4 linii de prioritate: fiecare dispozitiv sau placă de extensie urmăreşte aceste semnale şi renunţă la magistrală, dacă detectează existenţa unei cereri de prioritate mai mare. Procesorul principal (UCP) are prioritatea cea mai mică (F) fiind master implicit.
5.6.4 Magistrala locală Magistralele l/O prezentate până acum aveau o rată de transfer relativ
scăzută. In timp ce rata de transfer magistralei procesorului a crescut, magistrala
l/O a cunoscut doar ajustări neimportante ale acestui parametru, în principal prin creşterea numărului de căi paralele. Magistrala l/O a trebuit să lucreze la o rată de transfer scăzută deoarece majoritatea adaptoarelor instalate funcţionau doar la viteze mai mici.
Figura 5.3 prezintă schema bloc de principiu a magistralelor unui sistem de calcul.
Fig. 5.3 Dacă pentru majoritatea dispozitivelor periferice cum sunt tastatura,
imprimantele, scannere, etc. această rată de transfer este suficientă, au apărut dispozitive pentru care era necesar transferul rapid al unor blocuri mari de date. Această necesitate apare mai ales la următoarele subsisteme:
- Adaptoare grafice. Interfeţele grafice ale sistemelor de operare Windows, OS/2 şi Unix X-Windows necesită actualizarea rapidă a imaginii grafice pentru deplasarea, redimensionarea şi actualizarea ferestrelor multiple. Acelaşi lucru este valabil şi pentru imaginile video în mişcare. Procesorul trebuie să actualizeze şi să transfere blocuri mari de date în cadrul memoriei video.
- Adaptoare pentru interfaţa SCSI. Interfaţa SCSI este utilizată mai ales pentru memorii de masă, ca unităţile de disc fix, unităţile CD-ROM şi unităţile de bandă încasetată. Creşterea vitezei de transfer ale acestor dispozitive influenţează semnificativ performanţele globale ale sistemului.
O soluţie evidentă a acestei probleme este mutarea unora dintre extensiile l/O într-o zonă unde pot avea acces la vitezele sporite ale magistralei procesorului, la fel ca şi cea de care beneficiază şi memoria imediată. Figura 5.4 descrie această nouă dispunere.
Această dispunere a componentelor a devenit cunoscută sub denumirea de magistrală locală (local bus), deoarece dispozitivele externe (plăci adaptoare) pot accesa acea parte a magistralei care aparţinea până acum doar procesorului şi anume, magistrala procesorului.
Soluţiile local-bus nu înlocuiesc standardele anterioare, cum ar fi ISA şi
(Viteză mare)
Magistrala memoriei
(Viteză mică) (Viteză mică)
Magistrala I/O
Magistrala procesorului (Viteză mare)
UCP
Memoria imediată (cache)
Controlerul de
magistrală
RAM
Plăci adaptoare
I/O
Adaptoare I/O
incluse
Magistrala I/O
EISA, ci sunt proiectate pentru a le îmbunătăţi. Pentru acest motiv, un sistem uzual este bazat pe standardele ISA sau EISA fiind în acelaşi timp dotat şi cu unul sau mai mulţi conectori local-bus. Astfel, plăcile mai vechi rămân compatibile cu sistemul, iar plăcile adaptoare de mare viteză beneficiază acum de conectorii local-bus.
Fig. 5.4 Magistrală de extensie de tip local-bus
5.6.5 Magistrala locală VESA La început, magistrala locală era folosit în principal pentru adaptoarele
grafice. Această magistrală a apărut în sistemele de vârf în care strangulările erau evidente. Din nefericire, spre sfârşitul anului 1992, erau în competiţie pe piaţă mai multe sisteme local-bus şi fiecare dintre aceste sisteme erau brevetate. Această lipsă a standardizării a stânjenit acceptarea largă a soluţiei local-bus.
Pentru a depăşi această problemă, Video Electronics Standard Association (VESA) a dezvoltat un standard de magistrală local-bus cunoscut sub numele de VESA Local-Bus sau, mai simplu, VL-Bus. La fel ca în implementările anterioare, sistemele VL-Bus ofereau accesul direct la memoria sistemului, cu viteza procesorului. Magistrala VL-Bus transfera 32 de biţi de date simultan şi deci permitea ca transferul datelor între UCP şi un subsistem compatibil video sau un hard disc să se facă pe lungimea integrală de 32 de biţi a cuvântului prin care comunica microprocesorul 486.
Magistrala locală VESA nu a mai fost dezvoltată pentru a fi adaptată la procesoarele Pentium astfel încât a rămas inevitabil legată de procesorul 486.
5.6.6 Magistrala PCI In paralel cu grupul care a dezvoltat magistrala VESA, Intel a dezvoltat
magistrala PCI (Peripheral Component Interconnect bus) care răspundea, de
(Viteză mare)
Magistrala memoriei
(Viteză mică) (Viteză mică)
Magistrala I/O
Magistrala procesorului (Viteză mare)
UCP
Memoria imediată (cache)
Controlerul de
magistrală
RAM
Plăci adaptoare I/O
Adaptoare I/O incluse
Magistrala I/O
Plăci Adaptoare I/O
asemenea, necesităţii de a se depăşi slăbiciunile magistralelor ISA şi EISA. In acest scop, între CPU şi magistrala l/O existentă, a fost intercalată o nouă magistrală denumită PCI.
Fig. 5.5 Pentru faptul că magistrala PCI lucrează în paralel cu magistrala
procesorului, rata de transfer a acesteia este considerabil crescută. Unul dintre avantajele majore ale magistralei PCI constă în faptul că, în timp ce UCP transferă sau primeşte date de la memoria imediată, PCI se poate ocupa cu transferarea informaţiilor între alte elemente ale sistemului.
Un alt avantaj al magistralei PCI este faptul că aceasta admite transferuri în mod exploziv (burst). Un asemenea transfer constă dintr-o singură fază de adrese urmată de mai multe faze de date. In acest caz arbitrajul de magistrală trebuie executat o singură dată la începerea fazei de adrese. In timpul fazei de adrese se transmite adresa de început a blocului de date şi tipul tranzacţiei care urmează; citire sau scriere. Dispozitivul slave memorează adresa de început într-un contor de adrese şi va incrementa adresa în fiecare fază de date. La magistralele care nu permit transferuri în mod exploziv, blocul de date se transmite utilizând o serie de tranzacţii separate şi, în acest caz, este necesar arbitrajul de magistrală pentru fiecare dintre aceste tranzacţii. In aceste condiţii, între două tranzacţii, un alt dispozitiv master poate obţine magistrala fapt care limitează sever rata de transfer.
Dezvoltarea ulterioară a magistralei PCI a condus la apariţia magistralei PCI X şi aceasta cu diverse variante.
Magistrala ISA
CD-ROM
LAN
Magistrala SCSI
Magistrala PCI
memoriei
Magistrala
locală a UCP
Magistrala UCP Punte
UCP/PCI
Memoria
principală
Periferic audio
Periferic video
Memorie video
Adaptor SCSI
Adaptor grafic
Adaptor LAN
Punte PCI / ISA
Disc
Bandă
Master magistrală
Slave memorie
Slave I/E
Buffer de cadre video
Din cauza tendinţei de dezvoltare a funcţiilor grafice, posibilităţile magistralei PCI au fost repede depăşite, în special pentru motivul că aceasta a fost concepută pentru a deservi mai multe dispozitive. Această situaţie a condus la dezvoltarea unei magistrale dedicate pentru adaptoarele grafice numită Accelerated Graphic Port (AGP). Magistrala AGP a fost utilizată, în primul rând, pentru a accelera grafica 3D. Magistrala AGP a fost înlocuită între anii 2004 – 2007 de magistrala PCI Express, care avea performanţe îmbunătăţite.
Fig. 5.6 In figura 5.6 sunt prezentate toate magistralele care sunt implicate în
realizarea unui sistem de calcul actual. Punţile care conectează diverse magistrale între ele au în acest caz denumiri
consacrate. Astfel puntea care conectează magistrala procesorului (FSB) cu magistrala memoriei şi magistrala plăcii grafice se numeşte Northbridge. Placa grafică şi magistrala corespunzătoare poate fi de tip AGP sau, mai nou, PCI Expres. O a doua punte numită Southbridge, conectează magistrala de extensie care acum este de tip PCI cu porturile rapide (IDE, SATA, USB) şi cu magistrala perifericelor lente numită LPC.
Magistrala LPC (Low Pin Count) conectează unităţile periferice de viteză
UCP
Northbridge
Southbridge
IDE SATA
USB
Controler grafic on
board
Cabluri şi porturi
off board
Slot pentru placă grafică
Magistrală AGP sau
PCI Expres Magistrala memoriei
Sloturi pt. memorie
RAM
Front side bus
Magistrala internă
Chipset
Magistrala PCI
ROM (BIOS)
Porturi seriale Porturi paralele
Floppy disk Tastatura
Mouse
Magistrala PCI
Sloturi PCI
Magistrala LPC
redusă cum sunt tastatura mouse-ul, controlerul de floppy disk, porturile seriale şi paralele (la care poate fi conectată, de exemplu, o imprimantă), la circuitul Southbridge. La aceeaşi magistrală este conectată şi memoria ROM în care se găseşte BIOS-ul (Basic Input/Output Sistem). Această magistrală a fost concepută pentru a înlocui magistrala ISA şi are avantajul că necesită mai puţine căi pentru comunicaţia cu perifericele, fapt important pentru plăcile de bază actuale care sunt în general foarte aglomerate. Punţile Northbridge şi Southbridge sunt conectate între ele prin magistrala internă şi împreună formează ceea ce se numeşte chipset.
5.6.7 Magistrala PCMCIA Din dorinţa de a oferi calculatoarelor laptop şi notebook aceeaşi calitate de a
fi extensibile pe care o au sistemele desktop, Personal Computer Memory Card International Association (PCMCIA) a stabilit câteva standarde pentru plăcile de extensie de dimensiuni reduse (credit-card-size) care se potrivesc in conectorii mici ai calculatoarelor laptop şi notebook.
Standardele PCMCIA, care au fost elaborate de un consorţiu format din peste 300 de producători (inclusiv IBM, Toshiba şi Apple), au fost considerate a fi un progres major în domeniul calculatoarelor portabile, deoarece conectorii PCMCIA pentru laptop şi notebook admit plăci de extensie de memorie, plăci fax/modem, adaptoare SCSI, plăci de reţea locală (LAN) şi multe alte tipuri de dispozitive. Ideea de bază a standardului PCMCIA a fost aceea de a da posibilitatea ca toate dispozitivele periferice PCMCIA existente la producători să poată fi utilizate de orice notebook.
Deşi implementarea standardului PCMCIA a fost un progres considerabil pentru calculatoarele de tip laptop şi notebook totuşi acesta nu este întotdeauna respectat de producători de calculatoare şi dispozitive periferice.
Dorind să rezolve aceste probleme de compatibilitate, PCMCIA a continuat să stabilească noi standarde. In urma acestei activităţi au rezultat, de fapt, 4 standarde: PCMCIA tip I până la tip IV. Cu toate acestea, există încă probleme de compatibilitate, mai ales datorită faptului că standardele PCMCIA sunt opţionale.
Cap.6. UNITATEA DE MEMORIE Memoria este acea parte a sistemelor de calcul care se utilizează pentru
păstrarea şi regăsirea ulterioară a datelor şi instrucţiunilor. Operaţiile principale în care este implicată memoria sunt următoarele:
• Preluarea datelor de intrare în memorie; • Păstrarea datelor pentru a putea fi prelucrate de către UCP sau pentru a
putea fi preluate de echipamentele de ieşire; • Transmiterea datelor din memorie către UCP sau către echipamentele de
ieşire. Sistemele de memorie influenţează în mod determinant performanţele
calculatoarelor. Deoarece în memorie sunt păstrate atât datele cât şi instrucţiunile, sistemul de memorie trebuie să satisfacă cererile simultane pentru prelucrarea datelor, execuţia instrucţiunilor şi transferul între memorie şi exterior.
Există o mare varietate de tipuri, tehnologii, organizări, performanţe şi costuri ale memoriilor utilizate în sistemele de calcul. Nici una din acestea nu este optimă pentru satisfacerea tuturor cerinţelor. Ca o consecinţă, sistemele de calcul sunt echipate cu o ierarhie de subsisteme de memorie, unele interne sistemului (accesibile direct de UCP), iar altele externe (accesibile de către UCP printr-un modul de I/E).
6.1. Caracteristicile sistemelor de memorie Cele mai importante caracteristici sunt următoarele: - Amplasarea. Sistemele de calcul dispun de memorii interne şi externe.
Memoria internă este numită, de cele mai multe ori, memorie principală. Există însă şi alte forme de memorie internă. Astfel UCP necesită o memorie locală proprie, constituită dintr-un număr de registre de memorie. Unitatea de comandă şi control din cadrul UCP poate necesita de asemenea o memorie proprie, în cazul unităţilor de comandă microprogramate. Memoria externă constă din diverse dispozitive periferice, ca discurile sau benzile magnetice, unităţile de CD-ROM sau DVD-ROM şi altele, care sunt accesibile de către UCP prin controlere (module) de I/E.
- Capacitatea. Se exprimă prin dimensiunea cuvântului de memorie (8, 16, 32, 64 sau 128 de biţi) şi numărul de cuvinte (Kocteţi, Mocteţi, Gocteţi) din care este compusă memoria.
- Unitatea transferabilă. Pentru memoria internă, unitatea transferabilă este egală cu numărul liniilor de date către şi de la modulul de memorie, deci cu numărul de biţi transferaţi simultan. Unitatea transferabilă nu trebuie să fie egală neapărat cu un cuvânt de memorie. Pentru memoria externă, datele sunt transferate de multe ori în unităţi mai mari decât un cuvânt, numite blocuri.
- Metoda de acces. Există următoarele tipuri de acces la unităţile de date: 1. Acces secvenţial. Memoria este organizată în unităţi de date, numite înregistrări. Fiecare înregistrare poate fi regăsită pe baza adresei acesteia. Pentru a accesa o anumită înregistrare trebuie parcurse toate înregistrările anterioare. Pentru acest motiv timpul de acces la o înregistrare oarecare este variabil şi
depinde de poziţia înregistrării în cadrul fişierului. Unităţile de bandă sunt echipamente cu acces secvenţial. 2. Acces direct. Blocurile sau înregistrările individuale au o adresă unică pe baza amplasării fizice a acestora. Timpul de acces este de asemenea variabil şi depinde de poziţia înregistrării accesată anterior. Unităţile de discuri fixe sunt echipamente cu acces direct. 3. Acces aleator. Fiecare locaţie adresabilă a memoriei are un mecanism de adresare încorporat. Timpul de acces a fiecărei locaţii este independent de secvenţele acceselor anterioare şi este constant. Fiecare locaţie poate fi, deci, selectată aleator şi poate fi adresată şi accesată direct. Memoria principală poate fi accesată în mod aleatoriu, de unde provine şi numele acesteia (Random access memory-RAM). 4. Acces asociativ. Memoria asociativă este un tip de memorie cu acces aleator, care permite regăsirea unui cuvânt de memorie pe baza unei părţi a conţinutului acestuia şi nu pe baza adresei (memorie adresabilă prin conţinut). Acest lucru se realizează prin compararea unor biţi dintr-un cuvânt cu o anumită valoare specificată şi efectuarea acestei comparări în mod simultan pentru toate cuvintele. In acest fel regăsirea este foarte rapidă.
- Tehnologia de realizare. Dispozitivele de memorie ale unui sistem de calcul pot fi semiconductoare, magnetice sau optice. Memoria principală este de obicei semiconductoare (RAM) iar memoria secundară este constituită din unul sau mai multe discuri dure (Hard Disk - HDD) care memorează informaţia pe un substrat magnetic. In ultimul timp au luat tot o mai mare dezvoltare dispozitivele optice de memorare, dintre care amintim CD-ROM, DVD-ROM, BLU-ray (BD).
- Metoda de scriere. In funcţie de modul de funcţionare a memoriilor acestea pot fi reversibile sau permanente. O memorie reversibilă este caracterizată de faptul că informaţiile pot fi scrise şi citite în timpul funcţionării acesteia. Memorarea informaţiilor într-o astfel de memorie este temporară, acestea fiind pierdute la deconectarea memoriei. Un exemplu de memorii cu citire/scriere sunt memoriile RAM.
Memoriile al căror conţinut nu poate fi modificat în timpul funcţionării sunt numite memorii numai cu citire (ROM - Read-Only Memory). Memoriile ROM sunt scrise în procesul de fabricaţie şi conţinutul lor nu mai poate fi modificat ulterior.
O altă clasă de memorii din aceasta categorie o constituie memoriile PROM (Programmable Read-Only Memory). Procesul de scriere al acestor memorii este executat prin semnale electrice de către furnizor sau utilizator într-un moment ulterior fabricaţiei circuitului, utilizând un echipament special. Memoria PROM asigură flexibilitate la un cost moderat, dar are dezavantajul că nu poate fi ştearsă.
O altă variantă a memoriei ROM este memoria EPROM (Erasable Programmable Read-Only Memory). Aceasta este citită şi înscrisă electric, ca şi memoria PROM, însă înaintea unei operaţii de scriere toate celulele de memorare trebuie şterse pentru a avea aceeaşi stare iniţială prin expunerea capsulei la o radiaţie ultravioletă. Acest proces de ştergere poate fi executat în
mod repetat. O formă actuală de memorie ROM este memoria EEPROM (Electrically
Erasable Programmable Read-Only Memory). Această memorie poate fi înscrisă în orice moment fără a-i şterge conţinutul. Operaţia de scriere trebuie efectuată pe blocuri şi necesită un timp considerabil mai lung decât operaţia de citire. Memoria EEPROM are avantajul că poate fi actualizată on-line, utilizând semnale obişnuite de control, adrese şi date. Acest tip de memorie este potrivită pentru păstrarea programelor de control şi ca un înlocuitor al memoriei secundare în anumite aplicaţii. Programul BIOS (Basic input/output system) este păstrat într-o memorie de tip ROM situată pe placa de bază a sistemului de calcul.
- Durata de viaţă a informaţiilor memorate. Din acest punct de vedere dispozitivele de memorare se împart în două categorii: volatile şi nevolatile. Sunt volatile memoriile care pierd informaţia la deconectarea acestora de la sursa de energie electrică. Din această categorie fac parte memoriile RAM care se şterg la oprirea calculatorului.
Memoriile nevolatile păstrează informaţiile memorate şi după deconectare. Dintre acestea amintim memoriile de tip ROM, Hard Disk-ul, dispozitivele optice de memorare, etc.
La anumite tehnologii de memorie, informaţiile memorate se pierd după o perioadă de timp dacă acestea nu sunt refăcute. Pierderea informaţiilor memorate poate avea loc în următoarele cazuri: citirea distructivă şi memorarea dinamică. La anumite memorii metoda de citire distruge informaţiile memorate; acest fenomen este numit citire distructivă (DRO - Destructive Readout). Memoriile la care citirea nu afectează informaţiile memorate sunt caracterizate prin citire nedistructivă (NDRO -Non-Destructive Readout). La memoriile DRO fiecare operaţie de citire trebuie urmată de o operaţie de scriere care reface starea originală a memoriei. Această refacere este efectuată automat utilizând un registru buffer. Operaţia de citire transferă cuvântul din locaţia adresată într-un registrul buffer. Conţinutul bufferului este rescris apoi în locaţia originală.
Anumite memorii au proprietatea că informaţia memorată are tendinţa să se modifice după un anumit timp, datorită unui proces fizic. De exemplu, la anumite memorii semiconductoare o sarcină electrică dintr-un condensator reprezintă valoarea binară 1, iar absenţa sarcinii reprezintă valoarea binară 0. In timp, condensatorul tinde să se descarce, determinând pierderea informaţiei. Pentru a evita acest lucru sarcina este refăcută printr-un proces numit reîmprospătare. Memoriile care necesită o reîmprospătare periodică sunt numite memorii dinamice, spre deosebire de memoriile statice, care nu necesită reîmprospătare. Această operaţie se efectuează în acelaşi mod în care sunt refăcute informaţiile într-o memorie cu citire distructivă. Conţinutul fiecărei locaţii este citit periodic în registre buffer, iar apoi este rescris sub formă amplificată în locaţia originală.
6.2. Indicatori de performanţă ai memoriilor Din punctul de vedere al utilizatorului, cele mai importante caracteristici ale
unei memorii sunt capacitatea şi performanţa. 1. Capacitatea reprezintă cantitatea de informaţie care poate fi memorată
de un dispozitiv de memorie. Cea mai mică unitatea adresabilă a unei memorii este octetul compus din opt biţi. De obicei, memoria este organizată pe cuvinte de 16 biţi (2 octeţi), 32 biţi (4 octeţi ) sau 64 biţi (8 octeţi).
Capacitatea memoriei se exprimă în Kocteţi (KB - Kilobait)) sau multipli ai acestuia:
1 KB=210B=1024B 1MB=210KB=220B 1GB = 210 MB = 230 B Preţul pe bit al unei memorii scade o dată cu creşterea capacităţii de
memorare a acesteia. 2. Performanţa. Performanţa unei memorii este determinată în principal de
viteza cu care informaţiile pot fi citite din memorie sau scrise în memorie. Cei mai importanţi indicatori de performanţă utilizaţi sunt timpul de acces, durata ciclului, rata de transfer şi fiabilitatea.
- Timpul de acces al unei memorii cu acces aleator, notat cu At , este intervalul de timp necesar pentru a executa o operaţie de citire sau scriere pentru o cantitate fixă de informaţie, de exemplu, un cuvânt. Acest interval de timp este calculat din momentul în care memoria primeşte o cerere de citire sau scriere până în momentul în care datele sunt disponibile pentru utilizare sau sunt memorate. Timpul de acces pentru citire nu este întotdeauna egal cu timpul de acces pentru scriere. Pentru o memorie cu acces non-aleator, timpul de acces este timpul necesar pentru a poziţiona mecanismul de citire-scriere la locaţia dorită.
- Durata ciclului, notată cu Mt , se referă în primul rând la memoriile cu acces aleator. Durata ciclului constă din timpul de acces la care se adaugă timpul suplimentar necesar înainte de a putea începe un al doilea acces. Anumite memorii cu citire distructivă nu pot iniţia un nou acces înainte de a fi executată o operaţie de refacere sau reîmprospătare. Pentru acest motiv, timpul minim care trebuie să treacă între începerea a două operaţii de acces consecutive poate fi mai mare decât timpul de acces At .
- Rata de transfer, notată cu Mr , este cantitatea maximă de informaţii care pot fi transferate în sau din memorie în unitatea de timp. Această rată este măsurată în biţi pe secundă sau cuvinte pe secundă. Dacă w este numărul de biţi care pot fi transferaţi simultan în memorie, rata de transfer este MM twr /= biţi/s. Dacă AM tt = , atunci AM twr /= .
- Fiabilitatea este măsurată prin timpul mediu între defecte (MTBF -Mean Time Between Failures). In general, memoriile fără părţi în mişcare au o fiabilitate mult mai ridicată decât memoriile care implică o deplasare mecanică, precum discurile magnetice. Chiar şi la memoriile fără părţi în mişcare, apar probleme de fiabilitate, în particular atunci când se utilizează densităţi de
memorare sau rate de transfer foarte ridicate. Codurile detectoare de erori şi codurile corectoare de erori pot creşte fiabilitatea oricărui tip de memorie.
6.3. Ierarhia de memorii Principalele caracteristici de care trebuie să se ţină cont la realizarea unui
sistem de memorie sunt capacitatea şi performanţele memoriei. Dintre astea din urmă cel mai important este timpul de acces. Pe lângă acestea, trebuie să se ia în considerare şi costul memoriei. Aceste caracteristici sunt contradictorii. De exemplu, există în general următoarele relaţii între capacitatea, timpul de acces şi costul pe bit al diferitelor tehnologii utilizate pentru implementarea sistemelor de memorie: - O capacitate mai mare implică un timp de acces mai mare; - O capacitate mai mare implică un cost pe bit mai mic; - Un timp de acces mai mic implică un cost pe bit mai mare.
Ţinând seama de aceste considerente, un sistem de calcul trebuie să conţină memorii cât mai rapide pentru a asigura cerinţele de performanţă dar şi memorii de mare capacitate pentru a permite prelucrarea unui volum mare de date. Aceste cerinţe contradictorii se pot asigura dacă se utilizează în cadrul unui sistem de calcul mai multe componente şi tehnologii de memorare, care formează o ierarhie de memorii.
La ierarhizarea memoriei s-a ţinut seama de modul în care operează programele. Astfel, prin analize statistice ale unor programe tipice s-a constatat că, în orice interval de timp dat, referinţele la memorie tind să se restrângă într-o anumită zonă a acesteia. Această proprietate este cunoscută sub numele de localitate a referinţelor. Localitatea referinţelor poate fi spaţială sau temporală. Aceste concepte sunt definite în continuare.
- Localitatea spaţială. De multe ori, un program utilizează date şi instrucţiuni ale căror adrese sunt apropiate unele de altele în spaţiul de adrese. De exemplu, referinţele la elementele unui tablou apar întotdeauna în cadrul unei anumite zone limitate din spaţiul de adrese. Similar, dacă UCP face referire la o instrucţiune I , memorată la o adresă dată A , instrucţiunea cea mai probabilă de a fi referenţiată în continuare de către UCP este cea imediat următoare după I , a cărei adresă este 1+A .
- Localitatea temporală. Datele sau instrucţiunile referite recent au o probabilitate ridicată de a fi referite din nou în viitorul apropiat. De exemplu, un grup de instrucţiuni dintr-o buclă iterativă sau o subrutină pot fi executate în mod repetat, rezultând o frecvenţă ridicată a referinţelor la adresele acestora.
O ierarhie tipică este ilustrată în figura 6.1. In mod uzual, se poate considera că diferitele unităţi de memorie dintr-un
sistem tipic formează o ierarhie de memorii ),...,,( 21 nMMM , după cum se arată în figura 6.1. Nivelul cel mai înalt, 1M este reprezentat de unitatea de memorie cea mai rapidă, cu dimensiunea cea mai redusă şi cu costul cel mai ridicat, fiind amplasat cel mai aproape de procesor.
Următorul nivel, 2M , este mai lent, are dimensiuni mai mari şi un cost mai redus decât nivelul 1M , fiind amplasat mai departe de procesor. Acelaşi lucru
este valabil pentru nivelurile 3M până la nM . Componentele sistemului de memorie pot fi plasate în patru grupe,
prezentate în continuare. Registrele UCP. Registrele de viteză ridicată ale UCP sunt utilizate ca
memorie de lucru pentru păstrarea temporară a instrucţiunilor şi datelor. Fiecare registru poate fi accesat pentru citire sau scriere într-un singur ciclu de ceas.
Memoria principală (primară). Această memorie externă, rapidă păstrează programe şi date care sunt în uz curent. Locaţiile memoriei principale sunt adresate direct prin instrucţiunile de încărcare şi memorare ale UCP. Cu toate că se utilizează o tehnologie similară cu cea a setului de registre al UCP, accesul este mai lent din cauza faptului că memoria principală este separată fizic de UCP. Capacitatea memoriei principale poate ajunge în prezent la unităţi sau zeci de Gocteţi, iar timpii de acces tipici sunt de câteva cicluri de ceas.
Fig.6.1 Memoria secundară. Acest tip de memorie are o capacitate mult mai mare
dar, în acelaşi timp, este mult mai lentă decât memoria principală. Memoria secundară păstrează programe şi date care nu sunt solicitate în mod constant de UCP. Este utilizată de asemenea atunci când capacitatea memoriei principale este depăşită. Informaţia din memoria secundară este accesată indirect prin programe de intrare/ieşire care transferă informaţii între memoria principală şi cea secundară. Tehnologiile reprezentative pentru memoria secundară sunt discurile magnetice fixe şi discurile optice, ambele având mecanisme de acces electromecanice relativ lente. Capacităţile de memorare de zeci sau sute de Gocteţi sau, mai nou, Tocteţi sunt obişnuite, iar timpii de acces se măsoară în milisecunde.
Memoria cache. Majoritatea calculatoarelor mai au încă nivel de memorie (uneori mai multe asemenea niveluri) numită memorie cache. Logic memoriile
Procesor
Memorie nivel M1
Memorie nivel M2
Memorie nivel Mn
Viteză Dimensiune Cost
Cea mai mică Cel mai ridicat
Cea mai mare
Cel mai scăzut Cea mai mare
Cea mai mică
cache sunt poziţionate între registrele UCP şi memoria principală. Capacitatea de memorare a memoriei cache este mai mică decât cea a memoriei principale, dar poate fi accesată mai rapid decât aceasta. Deoarece o parte a acesteia sau întreaga memorie cache se poate afla în aceeaşi capsulă cu UCP, timpul de acces este de la unul la trei cicluri de ceas. Memoriile cache sunt componente esenţiale ale calculatoarelor cu performanţe ridicate.
Spre deosebire de celelalte trei tipuri de memorii, memoriile cache sunt de obicei transparente pentru programator.
Figura 6.2 prezintă unele exemple de ierarhii de memorie cu două, trei şi patru niveluri. Ierarhia cu două niveluri din figura 6.2(a) este tipică pentru calculatoarele din generaţiile anterioare. La ierarhia din figura 6.2(b) este adăugată o memorie cache numită memorie cache divizată, deoarece aceasta are zone separate pentru memorarea instrucţiunilor (Cache I) şi a datelor (Cache D). Al treilea exemplu din figura 6.2(c) are două niveluri de memorii cache, ambele de tip nedivizat.
Fig.6.2 6.4. Memoria principală semiconductoare Memoria principală semiconductoare este de obicei o memorie cu acces
aleator (RAM). Acest tip de memorie se distinge prin faptul că fiecare locaţie de memorare poate fi accesată independent, cu un timp de acces fix care este
D D D D
I I I I
D D D
I I I M1
I
D
D
I UCP
Memorie principală M1
Memorie
secundară M2
UCP
Cache I
Cache D
Memorie principală M2
Memorie secundară M3
UCP
Cache nivel 1 M1
Cache nivel 2 M2
Memorie principală M3
Memorie secundară M4
a
b
c
independent de poziţia locaţiei accesate. 6.4.1. Celula de memorie şi unitatea de memorie O unitate de memorie este compusă dintr-un anumit număr de celule de
memorie. Deşi, pentru realizarea celulelor de memorie, se utilizează o diversitate de tehnologii, toate celulele de memorie semiconductoare prezintă următoarele proprietăţi:
• Au două stări stabile (sau semi-stabile), care pot fi utilizate pentru a reprezenta valorile binare 0 şi 1.
• Pot fi înscrise (cel puţin o dată) prin setarea stării. • Pot fi citite prin sesizarea stării.
O schemă bloc a unei celule care memorează un bit de informaţie este prezentată în figura 6.3. Linia de selecţie realizează selectarea (validarea) celulei. Linia R/W (Read/Write) stabileşte dacă trebuie efectuată o operaţie de citire sau de scriere asupra celulei selectate. Atunci când linia R/W este 0, se efectuează o operaţie de citire, care determină trecerea datei memorate printr-un amplificator de detecţie (sense amplifier) şi transmiterea acesteia pe linia de ieşire. Intr-un mod similar, atunci când linia R/W este 1, se efectuează o operaţie de scriere, care determină ca data de pe linia de intrare să fie memorată în celulă.
Fig.6.3
O celulă de memorie poate fi construită, în funcţie de tehnologia utilizată, dintr-un număr de unul până la şase tranzistoare. Restricţia principală la proiectarea unei celule este dimensiunea sa. Obiectivul este ca dimensiunea celulei să fie cât mai redusă, astfel încât să poată fi împachetate mai multe celule în spaţiul disponibil din cadrul unei capsule.
Există două tipuri de memorii cu acces aleator, statice (SRAM) şi dinamice (DRAM). Atât memoriile statice cât şi cele dinamice sunt volatile, deci informaţia memorată este pierdută atunci când alimentarea cu energie este întreruptă. Memoriile statice constau din celule asemănătoare cu bistabilele utilizate în proiectarea logică. Celulele memoriilor SRAM diferă de bistabile în principal prin metodele utilizate pentru adresarea celulelor şi transferul datelor. Memoriile statice reţin datele atunci când un cuvânt este citit din acestea, deci citirea este nedistructivă.
Date de ieşire Date de intrare
Celulă de
memorie
Selecţie
_
R /W
Intr-o celulă de memorie DRAM, stările 1 şi 0 corespund prezenţei sau absenţei unei sarcini memorate într-un condensator controlat de un circuit de comutare, de obicei un tranzistor. Condensatorul unei celule DRAM trebuie reîncărcat periodic. Operaţia de reîncărcare a condensatoarelor este numită reîmprospătare. Deci, o memorie DRAM trebuie să conţină un circuit de reîmprospătare şi să alterneze operaţiile de reîmprospătare cu accesele normale la memorie. Datele conţinute în memoriile dinamice trebuie să fie rescrise în locaţia corespunzătoare de memorie după fiecare operaţie de citire. Cu alte cuvinte, memoriile dinamice sunt caracterizate prin proprietatea că citirea este distructivă.
Deoarece o celulă de memorie DRAM poate fi construită utilizând un singur tranzistor, în timp ce o celulă de memorie SRAM necesită până la şase tranzistoare, la memoriile dinamice se obţine o densitate de memorare mai ridicată. In consecinţă, o memorie RAM dinamică este mai puţin costisitoare decât o memorie RAM statică de aceeaşi capacitate. Pe de altă parte, o memorie RAM dinamică necesită un circuit de reîmprospătare. Pentru memorii de dimensiuni mari, costul circuitului de reîmprospătare este compensat de costul mai redus al memoriilor DRAM. Un alt aspect este faptul că memoriile RAM statice sunt mai rapide decât memoriile RAM dinamice.
O unitate de memorie constă dintr-o matrice de celule de memorie. Structura internă a unei unităţi de memorie de m cuvinte cu n biţi pe cuvânt constă din mxn celule de memorie. Intr-o unitate de memorie, un grup de opt celule (un octet) pot fi adresate simultan, fapt care permite ca acestea să aibă o linie de selecţie comună.
6.4.2. Organizarea memoriilor Fiecare circuit integrat de memorie conţine o matrice de celule de
memorie. Pentru organizarea logicii funcţionale a acestor celule de memorie se utilizează două metode: 1D şi 2D.
Cea mai obişnuită formă de organizare de memorie este organizarea bidimensională (2D) sau linie-coloană prezentată în figura 6.4, unde, pentru simplitate, circuitele de date şi de control sunt omise. Cuvântul de adresă de m biţi este divizat în două părţi, X şi Y , constând din mx, respectiv my biţi. Celulele sunt aranjate într-o matrice rectangulară de xN , linii şi yN coloane, astfel că numărul total de celule este NxxNy. Această memorie funcţionează în felul următor. Mai întâi, adresa locaţiei de memorie, care trebuie accesată, este transferată prin magistrala de adrese către cele două buffere de adrese X şi Y. Cele două componente ale adresei mx şi my sunt apoi decodificate de decodificatoarele de linie şi coloană DCD. O linie de control indică tipul accesului care trebuie executat. Dacă este cerută o operaţie de citire, conţinutul locaţiei adresate este transferat de la matricea de memorie în bufferul de date şi de aici pe magistrala de date. Dacă este cerută o operaţie de scriere cuvântul, care trebuie memorat, este transferat de pe magistrala de date în locaţia selectată din unitatea de memorie.
Fig.6.4
Organizarea 2D necesită un număr mult mai redus de circuite de acces decât organizarea 1D pentru aceeaşi capacitate de memorare. De asemenea, în locul unui singur decodificator de adresă foarte complex, sunt suficiente, în cazul organizării 2D, două decodificatoare de adresă mult mai simple.
Un circuit integrat de memorie RAM conţine în mod tipic toate circuitele de acces, incluzând decodificatoare de adresă, drivere şi circuite de control.
Buffer de adrese
my mx
m
Y X
Magistrală de adrese
Matrice de memorie
DCD
adresă de
linie
DCD adresă de coloană
6.5 Memoria stivă Memoria stivă este o listă liniară de date elementare, în care inserarea,
eliminarea şi accesul la elementele de date se efectuează la un singur capăt al acesteia. Stiva poate fi considerată o listă de tip LIFO (Last-In, First-Out).
In funcţie de modul de implementare, stiva poate fi de mai multe tipuri: - Stivă software, organizată în memoria internă; - Stivă cablată (hardware); - Stivă parţial cablată. Indiferent de modul de implementare, o stivă trebuie să permită efectuarea
următoarelor operaţii: - Introducere (inserare): PUSH; - Extragere (eliminare): POP; - Acces la elementul din vârful stivei. Memoria stivă este utilizată în special pentru memorarea rapidă a contextului
unui program în cazul apariţiei unei situaţii de excepţie sau pentru modul time sharing.
6.5.1. Tipuri de memorii stivă - Stiva implementată în memorie (stivă software) Stiva poate fi simulată în memoria internă a calculatorului, utilizându-se
adresarea convenţională. Gestionarea stivei se poate realiza prin software, existând instrucţiuni speciale şi registre dedicate pentru operaţiile cu stiva (figura 6.5).
Fig. 6.5
Stiva poate fi definită cu ajutorul a două registre ale procesorului. Registrul BP indică baza stivei, iar registrul SP indică vârful stivei. Adresa de bază a stivei rămâne fixă, în timp ce adresa care indică vârful stivei se modifică la fiecare operaţie de introducere sau eliminare din stivă. Instrucţiunile speciale de lucru cu stiva modifică automat conţinutul registrului SP.
De obicei, stivele cresc spre adrese mici, elementul din vârful stivei având adresa cea mai mică, dar există şi stive care cresc spre adrese mari.
Presupunând că stiva creşte spre adrese mici, iar SP indică elementul din vârful stivei, instrucţiunea de introducere a unui element în stivă (PUSH) decrementează registrul SP şi copiază elementul respectiv în stivă. Instrucţiunea
de extragere a unui element din vârful stivei (POP) copiază acest element într-un registru de memorie şi incrementează registrul SP.
In cazul stivei simulate în memorie, pe lângă operaţiile obişnuite cu stiva, se pot citi sau modifica elemente oarecare din stivă, prin adresarea lor relativă faţă de registrul de bază al stivei (BP).
- Stiva cablată Spre deosebire de stiva simulată în memorie, la care vârful stivei se
deplasează în timp ce informaţiile din stivă rămân fixe, în cazul stivei cablate există un vârf fix şi informaţiile din stivă sunt translatate la fiecare operaţie de introducere sau eliminare din stivă.
Stivele cablate pot avea un registru de stare asociat, care indică dacă stiva este goală (EMPTY) sau plină (FULL). La încercarea de extragere a unui element din stiva goală se poate activa un semnal de eroare UNDERFLOW, iar la încercarea de introducere a unui element în stiva plină se poate activa un alt semnal, OVERFLOW.
Stivele cablate au avantajul unei viteze ridicate de efectuare a operaţiilor,dar dimensiunea acestora este limitată.
- Stiva parţial cablată Dacă dimensiunea stivei cablate este redusă, pentru cazurile de depăşire de
capacitate a stivei cablate, este indicată completarea acesteia cu o stivă simulată în memoria internă (figura 6.6).
Fig. 6.6
Acest tip de stivă combină viteza de lucru ridicată a stivei cablate cu
capacitatea nelimitată a stivei software. 6.6 Memoria cache 6.6.1 Principii Deoarece accesul la memoria principală necesită un timp considerabil mai
mare comparativ cu viteza globală a unui procesor, este important să se proiecteze un sistem de memorie cu un timp de acces cât mai redus. O posibilitate de a creşte viteza globală a sistemului de memorie este de a se reduce numărul de accesuri la memoria principală. Acest deziderat poate fi
realizat prin instalarea unei memorii rapide de mici dimensiuni care să conţină, în fiecare moment, o parte din program. In acest mod, datorită proprietăţii de localitate a referinţelor, numărul referinţelor la memoria principală va fi redus în mod considerabil.
O asemenea memorie rapidă, utilizată temporar pentru păstrarea unei porţiuni a datelor şi instrucţiunilor în vederea utilizării imediate, este cunoscută sub numele de memorie cache.
Deoarece memoria cache are un preţ ridicat, un sistem de calcul poate avea doar o memorie cache cu o dimensiune limitată. Pentru acest motiv, un sistem de calcul conţine o memorie principală mai lentă şi de dimensiuni relativ mari, împreună cu o memorie cache mai rapidă şi de dimensiuni mai mici. Memoria cache este amplasată între memoria principală şi UCP şi conţine copii ale anumitor blocuri ale memoriei principale. Astfel, atunci când UCP solicită un cuvânt şi acest cuvânt se află în memoria cache rapidă, nu va mai fi necesar accesul la memoria principală.
Deşi dimensiunea memoriei cache este doar o mică parte din dimensiunea memoriei principale, datorită proprietăţii de localitate a referinţelor, o mare parte din cererile de acces la memorie vor fi satisfăcute de memoria cache.
Performanţa unui sistem poate fi îmbunătăţită în mod semnificativ dacă memoria cache este amplasată în acelaşi circuit integrat cu procesorul. In acest caz, ieşirile memoriei cache pot fi conectate la UAL şi la registre prin legături scurte, reducând timpul de acces. Aceasta este soluţia adoptată la majoritatea procesoarelor actuale.
6.6.2. Organizarea memoriei cache Figura 6.7 prezintă componentele principale ale unei memorii cache.
Cuvintele de memorie sunt păstrate într-o memorie de date şi sunt grupate în pagini de dimensiuni reduse, numite blocuri sau linii. Conţinutul memoriei de date este copia unui set de blocuri ale memoriei principale. Fiecare bloc al memoriei cache este marcat cu adresa sa de bloc, numită marcaj (tag).
care pot fi necontigue, este păstrată într-o memorie specială, numită memorie de marcaje sau director.
Pentru a îmbunătăţi performanţele unui calculator, timpul necesar pentru testarea adreselor de marcaj şi accesarea memoriei cache de date trebuie să fie mai redus decât timpul necesar pentru accesarea memoriei principale. Figura 6.8 prezintă două moduri de amplasare a unei memorii cache într-un sistem de calcul. In organizarea din figura 6.8a, numită organizare "look-aside", memoria cache şi memoria principală sunt conectate direct la magistrala sistem. In acest caz atât cererile UCP către memoria cache cât şi cele către memoria principală, în caz de eşec, utilizează magistrala sistem. De notat că, atât în caz de succes cât şi în cazul eşecurilor la accesul memoriei cache, operaţiile de transfer ocupă magistrala sistem, care nu va fi disponibilă pentru alte operaţii, cum sunt transferurile de I/E.
Fig. 6.8a
Fig. 6.8b In figura 6.8b se prezintă o altă organizare, care este mai rapidă, dar mai
costisitoare; aceasta este numită organizare "look-through". UCP comunică cu memoria cache printr-o magistrală separată (locală) care este izolată de magistrala sistem. In acest mod magistrala sistem este disponibilă pentru utilizarea de către alte unităţi, cum sunt controlere de I/E, care pot comunica cu memoria principală. Prin urmare, accesurile la memoria cache şi accesurile la
Acces la memoria principală
Acces la memoria cache
UCP
Memorie principală M2
Magistrala sistem
Înlocuire bloc
Memoria Cache M1
Magistrala sistem
Acces M2 la magistrala sistem
Acces la memoria cache
UCP
Memorie principală M2
Înlocuire bloc
Memoria Cache M1
Controler memorie
cache
Controler memorie
principală
memoria principală care nu implică UCP se pot desfăşura concurent. UCP transmite o cerere către memoria principală numai după un eşec la accesul în memoria cache. Magistrala locală care conectează 1M şi 2M poate avea o lăţime mai mare decât magistrala sistem, crescând astfel viteza transferurilor între memoria cache şi cea principală.
Dezavantajul principal al organizării "look-through", pe lângă costul său mai ridicat, constă în faptul că este necesar un timp mai lung pentru ca memoria principală să răspundă la cererea UCP atunci când apare un eşec la accesul memoriei cache.
6.6.3 Funcţionarea memoriei cache Atunci când UCP generează o cerere de citire pentru un cuvânt din
memorie, cererea este trimisă mai întâi la memoria cache pentru a verifica dacă acest cuvânt se află deja în această memorie. In cazul în care cuvântul nu este găsit în memoria cache (deci, apare un eşec la citire), cuvântul solicitat este furnizat de memoria principală. O copie a acestui cuvânt, împreună cu blocul din care acesta face parte, este depusă şi în memoria cache pentru referinţele viitoare de către UCP. In cazul în care cuvântul este găsit în memoria cache (deci, apare un succes la citire), cuvântul este furnizat de memoria cache. Astfel, în această situaţie, nu este necesar accesul la memoria principală. Prin aceasta, viteza sistemului creşte considerabil.
Figura 6.9 ilustrează execuţia unei operaţii de citire pentru un sistem simplu de memorie cache. In acest exemplu, se presupune o dimensiune a blocului de memorie de 4 octeţi. Fiecare adresă de memorie are dimensiunea de 12 biţi, astfel încât cei 10 biţi de ordin superior formează marcajul sau adresa blocului, iar cei 2 biţi de ordin inferior definesc un deplasament (index) în cadrul blocului. Atunci când un bloc este adus în memoria cache de date, marcajul acestuia este plasat în memoria cache de marcaje. Figura 6.9 prezintă conţinutul a două blocuri aduse în memoria cache de date; de observat locaţiile aceloraşi blocuri din memoria principală. Pentru citirea cuvântului indicat de săgeată, adresa acestuia iA = 1100 0101 0110 este transmisă la 1M care compară partea de marcaj a adresei iA (în acest caz 1100 0101 01) cu marcajele sale memorate şi găseşte o potrivire. Marcajul memorat adresează blocul corespunzător din memoria de date, iar deplasamentul de 2 biţi (în acest caz 10) este utilizat pentru identificarea cuvântului destinaţie din cadrul blocului. Cuvântul selectat în acest mod (FF) este apoi transmis la UCP.
Atunci când UCP generează o cerere de scriere a unui un cuvânt în memorie, cererea este trimisă mai întâi la memoria cache pentru a verifica dacă locaţia acestui cuvânt se află în memoria cache. In cazul în care locaţia cuvântului nu este găsită în memoria cache (deci, apare un eşec la scriere), se încarcă din memoria principală în memoria cache o copie a blocului căruia îi aparţine locaţia căutată. Apoi, se execută o operaţie de scriere în această locaţie. Dacă locaţia adresată este găsită în memoria cache (deci, apare un succes la scriere), se execută operaţia de scriere direct în memoria cache.
Execuţia unei operaţii de scriere a unei date transmise de UCP pentru
memoria cache din exemplul precedent este ilustrată în figura 6.10. Partea de marcaj a adresei destinaţie iA (identică cu cea din exemplu anterior) este transmisă la 1M împreună cu cuvântul de date care trebuie memorat. Partea de deplasament a adresei Ai (10) localizează locaţia din cadrul blocului selectat
Fig. 6.9 Deoarece locaţia căutată este găsită în memoria cache, (a avut loc un
succes la scriere) noua dată, în acest caz 55, este memorată în locaţia de la adresa iA în memoria de date din 1M , modificând astfel vechea dată FF.
Apare acum o nouă problemă, deoarece data din 1M cu adresa iA diferă de data din 2M cu aceeaşi adresă. O inconsistenţă temporară de acest tip este acceptabilă cât timp nici un dispozitiv (un alt procesor sau un dispozitiv de I/E) nu încearcă citirea datei vechi. Prevenirea utilizării improprii a datei vechi reprezintă problema coerenţei (sau consistenţei) memoriilor cache. Aceasta este o problemă de bază la sistemele multiprocesor, unde mai multe procesoare partajează accesul la aceeaşi memorie principală, dar fiecare dispune de propria memorie cache. Această problemă apare de asemenea în sistemele uniprocesor atunci când este prezent un controler sau procesor de I/E, care are un acces direct la memoria principală, independent de UCP. Inconsistenţele din memoriile cache pot fi minimizate prin implementarea unei strategii care actualizează în mod sistematic, datele din 2M printr-un proces de copiere a datelor corespunzătoare din 1M .
Adresa datei solicitate
1100 0101 11
1100 0101 01
11 10 01 00
39 FF 3D 1A
7B 5A F0 FF
1100 0101 0101
1100 0101 0110
1100 0101 0111
1100 0101 1000
1100 0101 1001
1100 0101 1010
1100 0101 1011
1100 0101 1100
1100 0101 1101
1100 0101 1110
1100 0101 1111
1100 0101 0100
1100 0101 0011
1100 0101 0010 78
CC
1A
3D
FF
F0
FF
00
87
B4
3C
39
5A
7B
1100 0110 0000
1100 0110 0001
67
D5
Selecţie date Comparaţie marcaje
Memorie de marcaje Memorie de date
1100 0101 01 10 Data solicitată Adrese memorie
principală
FF
Date memorie
principală
Pentru executarea unei operaţii de copiere (scriere), există două strategii care pot fi utilizate: "write-back" şi "write-through".
Fig. 6.10 - In cazul strategiei "write-back", numită şi "copy-back", fiecărui cuvânt din
memoria cache i se asociază un bit, numit bit de modificare (dirty bit) sau bit de inconsistenţă, care arată dacă acest cuvânt a fost modificat. Atunci când un cuvânt trebuie eliminat din memoria cache, se testează bitul de modificare al cuvântului; dacă bitul este setat, cuvântul este scris în memoria principală în forma sa actualizată. Avantajul strategiei "write-back" este că, atât timp cât un cuvânt rămâne în memoria cache, acesta poate fi modificat de mai multe ori, iar pentru UCP nu are importanţă dacă cuvântul din memoria principală nu a fost actualizat. Dezavantajul acestei strategii este că memoria cache şi memoria principală pot fi temporar inconsistente. Aceasta creează dificultăţi dacă mai multe procesoare cu memorii cache independente partajează aceeaşi memorie principală, deoarece datele lor pot deveni inconsistente.
- In cazul strategiei "write-through", cuvântul este modificat atât în memoria cache, cât şi în memoria principală la fiecare ciclu de scriere. Avantajele acestei strategii constau în faptul că este uşor de implementat şi memoria principală are întotdeauna date consistente cu memoria cache. Pe de altă parte, această strategie are dezavantajul că încetineşte UCP, deoarece
Adresa datei din UCP
1100 0101 11
1100 0101 01
11 10 01 00
7B 5A F0 FF
1100 0101 0101
1100 0101 0110
1100 0101 0111
1100 0101 1000
1100 0101 1001
1100 0101 1010
1100 0101 1011
1100 0101 1100
1100 0101 1101
1100 0101 1110
1100 0101 1111
1100 0101 0100
1100 0101 0011
1100 0101 0010 78
CC
1A
3D
FF
F0
FF
00
87
B4
3C
39
5A
7B
1100 0110 0000
1100 0110 0001
67
D5
Selecţie date Comparaţie marcaje
Memorie de marcaje Memorie de date
1100 0101 01 10 Data din UCP Adrese memorie
principală Date
memorie principală
55
39 55 3D 1A
toate operaţiile de scriere necesită accesuri ulterioare la memoria principală. Totuşi, numai o fracţiune redusă, probabil 10%, din toate accesurile la memorie sunt operaţii de scriere. Anumite procesoare permit utilizarea ambelor strategii de scriere, astfel încât utilizatorul poate selecta strategia cea mai avantajoasă pentru un program particular.
6.6.4. Maparea adreselor O caracteristică de bază a memoriei cache este funcţia de mapare (de
translatare), care atribuie blocurilor din memoria principală locaţii în memoria cache. Se utilizează trei tipuri de mapare a adreselor:
Pentru a ilustra aceste trei tipuri de mapare ale adreselor, presupunem că memoria principală are o capacitate de 64 K cuvinte de câte 16 biţi fiecare, fapt care înseamnă că magistrala de adrese are 16 biţi. De asemenea, presupunem că memoria cache care poate păstra maxim 256 de cuvinte. Considerăm că UCP generează o cerere de citire. Cererea de scriere este gestionată într-un mod similar. Vom urmări acum strategiile celor trei tipuri de mapare.
- Memorie cache cu maparea asociativă In cazul unei memorii cache cu mapare asociativă (numită şi memorie
cache cu asociativitate totală), adresa şi conţinutul unei locaţii de memorie sunt memorate ca şi cuvinte separate în memoria cache. Ca rezultat, un cuvânt de memorie poate fi memorat în orice locaţie a memoriei cache, ceea ce face ca acest tip de memorie cache să fie cel mai flexibil. Figura 6.11 prezintă organizarea unei memorii cache cu mapare asociativă pentru sistemul considerat.
Fig. 6.11 De observat că, indiferent de adresele lor absolute din memoria principală,
cuvintele sunt memorate în locaţii arbitrare. Adresele cuvintelor sunt memorate în partea asociativă, în timp ce datele
sunt memorate în partea de date (de tip RAM) a memoriei cache. Astfel, atunci când UCP generează o adresă pentru referinţa la memorie, aceasta este transferată în registrul argument şi este comparată simultan cu adresele tuturor cuvintelor aflate în memoria cache. Dacă s-a găsit locaţia cu o adresă care se potriveşte, datele corespunzătoare pot fi accesate din memoria de date.
Dezavantajul principal al mapării asociative este că necesită o memorie asociativă de dimensiuni mari, care este foarte costisitoare.
- Memorie cache cu maparea directă Pentru implementarea mapării directe sunt necesare numai memorii de tip
RAM. Memoria cache 1M este împărţită într-un număr de regiuni numite seturi de date, fiecare din acestea memorând n cuvinte de memorie consecutive. Memoria principală 2M este divizată similar în blocuri, fiecare dintre aceste blocuri putând fi mapat într-un set din 1M .
Figura 6.12 reprezintă arhitectura unei memorii cache cu mapare directă., Pentru simplificare considerăm că un set al memoriei cache, ca şi un bloc al memoriei principale, conţine un singur cuvânt de memorie (n=1). Pentru implementarea mapării directe, adresele de memorie de 16 biţi (4 cifre hexazecimale) sunt divizate în două părţi: cei 8 biţi de ordin inferior ai adresei din memoria principală formează un câmp de index iar ceilalţi opt biţi de ordin
Memorie cache M1
Adresa UCP (16biţi)
0100 0900 25FF FFFF
0000
3826 1234 3800 3675 0135
0900 25FF 0100
3800 3675 1234
Registru argument
Memorie asociativă
DATE
Memorie principală M2
superior formează un câmp numit marcaj. Indexul identifică în mod unic un set al memoriei cache unde se poate memora un bloc din memoria M2. Dar în M2 există de regulă mai multe blocuri de date cu acelaşi index. Pentru a preciza blocul de date care trebuie referit se utilizează marcajul.
In afară de memoria de date această arhitectură mai conţine o memorie de marcaje şi un circuit de comparare. Comparatorul activează linia de potrivire, indicând existenţa cuvântului adresat în memoria cache. La adresa specificată de index, este memorat un marcaj în memoria de marcaje şi un set de date în memoria de date. Dacă marcajul adresei de memorie solicitate se potriveşte cu marcajul din memoria cache, cuvântul din memoria de date este transmis la UCP. In caz contrar, se accesează memoria principală, iar cuvântul căutat este încărcat şi transmis la UCP.
In figura 6.12. este prezentată funcţionarea unei memorii cache cu mapare directă. Dacă, de exemplu, UCP solicită citirea cuvântului de memorie de la adresa 0900 indexul va fi 00 iar marcajul 09. Astfel, la adresa 00 din memoria de marcaje se găseşte valoarea 09 care corespunde cu marcajul cuvântului solicitat. Rezultă că, în acest caz, a fost înregistrat un succes la căutare şi conţinutul memoriei de date de la indexul 00 (care este 3800) este preluat de UCP. Dacă apoi, UCP solicită citirea conţinutului adresei 0000, indexul care este 00 se potriveşte, dar marcajul 00 este diferit. A fost înregistrat deci un eşec la căutare şi, în consecinţă, este accesată memoria principală, iar cuvântul de date 3826 este transferat la UCP. Cuvintele din memoria de marcaje şi memoria de date de la indexul 00 sunt înlocuite apoi cu 00 şi respectiv 3826.
Avantajul mapării directe faţă de maparea asociativă constă în faptul că nu necesită memorie asociativă, care este mult mai scumpă. Dezavantajul principal este că performanţele pot fi reduse considerabil dacă două sau mai multe cuvinte având acelaşi index, dar marcaje diferite, sunt accesate în mod frecvent. De exemplu, cuvintele de memorie de la adresele 25FF şi FFFF trebuie plasate ambele în memoria cache la indexul FF, astfel încât se pierde un timp important pentru interschimbarea lor. Aceasta încetineşte sistemul, anulând efectul memoriei cache. Totuşi, considerând proprietatea de localitate a referinţelor, probabilitatea de a referi, în mod repetat, două cuvinte cu acelaşi index este redusă.
Fig. 6.12 - Maparea cu seturi asociative (k-way set associative) O metodă mai eficientă de mapare a adreselor pentru memoriile cache
este maparea cu seturi asociative. In timp ce la maparea directă fiecare set, identificat de un anumit index, memorează un singur bloc din memoria M2, la maparea cu seturi asociative fiecare set memorează un număr de k astfel de blocuri. In practică sunt utilizate doar valori mici ale parametrului k, cum ar fi de exemplu k=2 sau k=4.
De exemplu, o memorie cache cu seturi asociative cu k blocuri de memorie, numit set asociativ cu k căi, poate memora k blocuri de date având acelaşi index, împreună cu marcajele lor.
Considerăm din nou că un set conţine un singur cuvânt de date. Fiecare bloc din memoria cache are aceeaşi structură ca şi o memorie cache cu mapare directă. Pentru a determina dacă un cuvânt adresat se află în memoria cache, marcajul acestuia este comparat în paralel (asociativ) cu marcajele datelor din toate blocurile de memorie. O potrivire în oricare din blocurile de memorie validează semnalul de potrivire pentru a indica existenţa cuvântului în memoria cache.
Dacă apare o potrivire, cuvântul corespunzător de date este transferat la UCP. In caz contrar, cuvântul de date este încărcat din memoria principală şi este transmis la UCP. Cuvântul de date, împreună cu marcajul acestuia, este depus apoi într-unul din blocurile de memorie.
00 01 FF
Adresa de la UCP
Memorie cache M1
0301 0900 25FF FFFF
0000
3826 1234 3800 3675 0135
09 03 25
3800 1234 3675
Memorie principală M2
Marcaj Index
Date
Fig. 6.13 Un exemplu ilustrând funcţionarea memoriei cache cu seturi asociative
având două blocuri este prezentat în figura 6.13. Indexului FF îi corespunde marcajul 25 în primul bloc şi marcajul 9C în al doilea bloc, datele de la cele două adrese putând fi astfel memorate simultan. Să presupunem că la un moment dat în primul bloc al memoriei cache este memorat cuvântul de date de la adresa 0900. Dacă acum UCP solicită cuvântul de date de la adresa 0000, la indexul 00 nu găseşte marcajul 00, astfel încât se înregistrează un eşec la căutare. Cuvântul solicitat este deci adus din memoria principală şi în acelaşi timp este memorat şi în cel de al doilea bloc al memoriei cache, astfel încât data de la adresa 0900 nu trebuie înlocuită.
Atunci când nu există spaţiu pentru un anumit index în memoria cache, unul din cele două cuvinte de date stocate la acel index va fi înlocuit conform unei strategii de înlocuire predefinite.
6.6.5. Strategii de înlocuire Atunci când nu mai există spaţiu în memoria cache, trebuie să se utilizeze
o strategie de înlocuire a unui cuvânt de date existent cu o nouă dată care este accesată în acel moment.
Pentru a determina care cuvântul va fi eliminat din memoria cache se utilizează una dintre următoarele strategii .
- Înlocuirea aleatoare; - Înlocuirea cuvântului cel mai puţin frecvent utilizat (LFU - Least
00 01 FF
Marcaj Date Date
Adresa de la UCP
Memorie cache M1
0301 0900 25FF 9CFF
0000
3826 1234 3800 3675 0135
09 03 25
3800 1234 3675
Memorie principală M2
Marcaj Index
Index Marcaj
9C
0135
Frequently Used) - Înlocuirea cuvântului cel mai puţin recent utilizat (LRU - Least Recently Used).
Strategia înlocuirii aleatoare alege un cuvânt în mod aleator şi înlocuieşte
acel cuvânt cu data nou accesată. Această metodă este uşor de implementat prin hardware şi este mai rapidă decât alte metode. Dezavantajul este că acele cuvinte care sunt cel mai probabil de a fi utilizate din nou au aceeaşi şansă de a fi eliminate ca şi cuvintele care probabil nu vor mai fi utilizate. Acest dezavantaj se micşorează pe măsură ce dimensiunea memoriei cache creşte.
Metodă (LFU - Least Frequently Used) înlocuieşte datele care sunt cel mai puţin utilizate. Metoda presupune că datele care nu sunt referite frecvent sunt mai puţin necesare. Pentru fiecare cuvânt, se păstrează un contor al numărului total de utilizări ale cuvântului de la încărcarea acestuia în memoria cache. Cuvântul cu valoarea cea mai mică a contorului este cel care va fi eliminat. Avantajul acestei metode constă în faptul că un cuvânt utilizat frecvent are o probabilitate mai mare de a rămâne în memoria cache decât un cuvânt care nu a este utilizat frecvent. Un dezavantaj al acestei metode îl reprezintă faptul că acele cuvinte care au fost încărcate recent în memoria cache au o valoare mică a contorului, în ciuda faptului că este probabil foarte ca ele să fie utilizate din nou.
Metoda (LRU - Least Recently Used) are performanţa cea mai bună raportată la cost comparativ cu celelalte tehnici, fiind implementată adesea în sistemele reale. Ideea acestei metode de înlocuire constă în faptul că un cuvânt, care nu a fost utilizat pentru o perioadă lungă de timp, conform proprietăţii de localitate temporală, are o şansă mai redusă de a fi utilizat în viitorul apropiat,. Astfel, această metodă reţine cuvintele din memoria cache care au probabilitatea cea mai mare de a fi utilizate din nou. In acest scop, se utilizează un mecanism pentru a păstra evidenţa acelor cuvinte care au fost accesate cel mai recent. Cuvântul care va fi eliminat este cuvântul care nu a fost utilizat pentru perioada cea mai lungă de timp. O posibilitate de a implementa un asemenea mecanism este de a asigna un contor fiecărui cuvânt din memoria cache. De fiecare dată când este accesată memoria cache, contorul fiecărui cuvânt este incrementat, iar contorul cuvântului care a fost accesat este resetat la zero. In acest fel, cuvântul cu contorul cel mai mare este cel care a fost utilizat cel mai puţin recent.
6.7. Memoria virtuală 6.7.1. Principii Memoria virtuală permite sistemului de calcul utilizarea unei memorii cu o
dimensiune mult mai mare decât dimensiunea reală fizică a memoriei principale. Intr-un sistem de memorie virtuală, memoria principală şi cea secundară se prezintă pentru un program al utilizatorului ca o memorie unică, de dimensiuni mari şi adresabilă direct.
Inaintea apariţiei memoriei virtuale, dacă spaţiul de adrese al unui program depăşea dimensiunea memoriei principale disponibile, programatorul era responsabil pentru împărţirea programului în fragmente mai mici, astfel încât fiecare fragment să poată fi încărcat în memoria principală. Toate aceste fragmente erau păstrate în memoria secundară, de exemplu, pe disc, fiind încărcate în memoria principală pe măsură ce erau necesare. Acest proces necesita cunoaşterea locului în care fragmentele trebuiau stocate pe disc, cunoaşterea operaţiilor de intrare/ieşire necesare pentru accesul fragmentelor şi păstrarea evidenţei întregului proces de fragmentare. Acesta presupunea operaţii foarte complexe, ceea ce complica şi mai mult programarea unui calculator.
Conceptul memoriei virtuale a fost creat în principal pentru a elibera programatorul de această sarcină. Memoria virtuală permite utilizatorului să scrie programe care depăşesc limitele fizice ale memoriei principale. De asemenea, memoria virtuală permite multiprogramarea, prin care memoria principală este partajată între mai mulţi utilizatori într-un mod dinamic. In cazul multiprogramării, porţiuni ale mai multor programe sunt plasate în memoria principală în acelaşi timp, iar procesorul îşi împarte timpul de execuţie între aceste programe. Procesorul execută un program pentru o perioadă scurtă de timp (numită cuantă de timp), iar apoi comută la un alt program; acest proces continuă până când fiecare program este terminat.
Atunci când se utilizează memoria virtuală, sistemul de memorie este adresat printr-un set V de adrese logice sau virtuale, fiind numite astfel deoarece, la execuţia programului, ele sunt translatate, în adrese ale memoriei fizice sau reale.
Un set de adrese fizice sau reale R identifică locaţiile fizice de memorare din fiecare unitate de memorie. Adresele virtuale sunt generate de obicei în timpul compilării şi sunt translatate de procesor în adrese fizice în timpul execuţiei. Un mecanism eficient pentru implementarea translatării adreselor este esenţial pentru un sistem de memorie virtuală. Cele două metode principale pentru implementarea unei memorii virtuale sunt paginarea şi segmentarea.
6.7.2. Translatarea adreselor Setul de locaţii abstracte pe care le poate adresa un program reprezintă
spaţiul de adrese virtuale V al programului. Adresele virtuale pot fi specificate explicit sau implicit de identificatorii pe care programatorul îi asignează variabilelor şi etichetelor de instrucţiuni. Pentru execuţia unui program pe un
anumit calculator, adresele sale virtuale trebuie translatate în spaţiul de adrese reale R , definit de memoria care este prezentă fizic în calculator. Acest proces este numit translatare a adreselor sau mapare a adreselor. Spaţiul de adrese reale R este o secvenţă liniară de numere 0, 1, 2, ...., n-1, corespunzând locaţiilor adresabile de memorie şi este distribuit pe toate nivelurile ierarhiei de memorii. Spaţiul de adrese virtuale V este o colecţie de liste, tablouri multidimensionale şi alte structuri neliniare, astfel încât este mult mai complex decât R .
Asignarea şi translatarea adreselor poate fi efectuată în diferitele etape ale unui program şi anume:
• de către programator în timpul scrierii programului; • de către compilator în timpul compilării programului; • de către programul utilitar care realizează încărcarea programului ce urmează să fie executat. • de către sistemul hardware şi/sau software de gestiune a memoriei.
Specificarea explicită a adreselor reale de către programator a fost necesară la primele calculatoare, care nu aveau un sistem hardware sau software de gestiune a memoriei. In cazul calculatoarelor moderne, programatorii utilizează în mod normal doar adrese virtuale. Un sistem hardware sau software specializat determină în mod automat adresele reale cerute de execuţia programului.
Translatarea adreselor se numeşte statică dacă adresele virtuale sunt convertit în adrese fizice în timpul compilării. In acest caz adresele fizice rămân constante pe toată durata execuţiei programului.
Translatarea adreselor este dinamică dacă spaţiul adreselor virtuale este modificat în timpul execuţiei programului şi în consecinţă convertirea acestora în adrese fizice este, de asemenea, efectuată în timpul execuţiei. Pentru translatarea adreselor în timpul execuţiei se utilizează unităţi de gestiune a memoriei (MMU - Memory Management Unit) implementate prin hardware.
Un program executabil cuprinde un set de blocuri care conţin instrucţiunile şi datele programului. Fiecare dintre aceste blocuri este o secvenţă de cuvinte care trebuie memorate în locaţii consecutive de memorie. Un cuvânt C dintr-un bloc are propria adresă reală rA , utilizată de UCP pentru accesul la acest cuvânt. Adresa reală a cuvântului C este specificată prin adresa de bază B a blocului care conţine cuvântul, împreună cu adresa relativă sau deplasamentul D (numit şi offset) al cuvântului din cadrul blocului, după cum se arată în figura 6.14. Deci adresa reală a unui cuvânt de memorie se calculează cu relaţia:
DBAr += Adesea B furnizează biţii de ordin superior ai adresei reale, în timp ce D
furnizează biţii de ordin inferior. In acest caz, adresa reală este formată simplu prin concatenarea adresei de bază B şi a deplasamentului D, un proces care nu creşte în mod semnificativ timpul pentru generarea adresei.
Fig. 6.14 Un mod simplu de implementare a translatării adreselor este de a păstra
adresele de bază ale blocurilor într-o tabelă de adrese ale memoriei controlată de sistemul de gestiune a memoriei. Tabela poate fi păstrată în memorie, în registrele UCP sau în ambele. Logica de generare a adreselor utilizată de UCP constă în calcularea adresei reale rA prin combinarea deplasamentului D cu adresa de bază corespunzătoare B .
Blocurile pot fi relocate cu uşurinţă în memorie prin manipularea adreselor de bază ale acestora. Figura 6.15 ilustrează relocarea blocurilor utilizând modificarea adreselor de bază. Presupunem că două blocuri sunt alocate în memoria principală după cum se arată în figura 6.15a. Se doreşte încărcarea unui al treilea bloc 3K în memoria principală, dar nu este disponibil un spaţiu liber contiguu cu o dimensiune suficientă. O soluţie la această problemă constă în mutarea blocului 2K , după cum se arată în figura 6.15b, prin asignarea acestuia a unei noi adrese de bază 2B şi reîncărcarea blocului în memorie. Astfel, se crează un spaţiu în care poate fi încărcat blocul 3K , prin asignarea acestuia a unei adrese de bază corespunzătoare.
a b
Fig. 6.15
L2
B3
B2
B1
L1
B2
B1
Bloc K1
Bloc K2
L3
L1
L2
Bloc K2
Bloc K1
Bloc K3
Adresa de bază B
Deplasament D
C0
C1
Ci
Cm-1
0 1
i
m-1
B B+1
B+i
B+m-1
Adresă reala (fizică) Ar
La amplasarea blocurilor în memorie, unitatea de gestiune a memoriei trebuie să evite depăşirea limitelor unui bloc. O metodă obişnuită pentru realizarea acestui deziderat este specificarea adresei maxime iL , numită adresă limită, pe care o poate accesa blocul. O altă posibilitate este de a se specifica dimensiunea blocului. Adresa de bază iB şi adresa limită iL , sunt memorate în tabela de adrese ale memoriei. Fiecare adresă reală rA generată de bloc este comparată cu iB şi iL ; accesul la memorie este efectuat dacă şi numai dacă este satisfăcută următoarea condiţie:
iri LAB ≤≤ Figura 6.16 indică modul în care unitatea de gestiune a memoriei
efectuează translatarea adreselor. Adresa de intrare vA este o adresă virtuală constând dintr-o adresă de bază virtuală Bv, concatenată cu un deplasament D . Adresa de bază reală asignată adresei virtuale vB este memorată într-o tabelă de adrese a memoriei principale. Această tabelă poate avea dimensiuni mari. Pentru creşterea vitezei procesului de translatare, o parte a tabelei de adrese ale memoriei este plasată într-o memorie de viteză ridicată din UCP, numită buffer de translatare (TLB - Translation Look-aside Buffer). Intrarea în TLB este deci partea adresei de bază vB a adresei virtuale vA , iar ieşirea acestuia este adresa de bază reală corespunzătoare rB . Această adresă este apoi concatenată cu partea de deplasament D din vA pentru a obţine adresa reală completă rA .
Fig. 6.16 Dacă adresa virtuală vB nu este găsită în bufferul de translatare TLB,
atunci partea tabelei de adrese ale memoriei principale, care conţine vB este transferată mai întâi din memoria externă în TLB. Deci, bufferul de translatare are rolul unei memorii cache pentru translatarea adreselor. Din acest motiv, bufferul de translatare este numit uneori memorie cache de adrese.
Buffer de translatare TLB
Deplasament (offset) D
Adresă reală Ar
La sistemul de memorie
Adresă virtuală Av
Adresă de bază virtuală Bv
Adresă de bază reală
Br
6.7.3. Paginarea Paginarea este tehnica de divizare a unui program (numit în continuare
proces) în blocuri mai mici cu dimensiuni identice şi stocarea acestor blocuri în memoria secundară sub forma unor pagini. Aceste pagini pot fi încărcate apoi în memoria principală în locaţii, de aceeaşi dimensiune cu paginile, numite cadre de pagină.
Fig. 6.17 Pentru ca această metodă să funcţioneze corect, fiecare proces trebuie să
păstreze în memoria principală o tabelă de adrese ale începutului fiecărui cadru de pagină, numită tabelă de pagini. În această tabelă fiecărei adrese virtuale de pagină îi corespunde o adresă reală a unui cadru de pagină. Figura 6.17 ilustrează modul în care funcţionează metoda paginării. Să presupunem că se caută adresa reală a unui cuvânt de memorie a cărui adresă virtuală a fost generată de UCP. O adresă virtuală constă din două părţi: o adresă de bază şi un deplasament.
Registrul de bază conţine adresa de început a tabelei de pagini a fiecărui proces. Tabelele de pagini conţin câte o fişă (entry) pentru fiecare pagină care aparţine procesului. Aceste fişe conţin, de obicei, un câmp de prezenţă de un bit, un câmp de acces şi un câmp de adresă. Câmpul de prezenţă P specifică dacă pagina a fost încărcată în memoria principală. Câmpul de acces specifică
Adresa virtuală generată de UCP
Adresa reală
Memoria principală
+ *
Tabela de pagini
P Acces Adresa
Cadru de pagină i
Cadru de pagină i+1
Dimens. cadru Registru de bază
Adresa de bază Deplasament
Adresa de bază reală a paginii
tipul operaţiilor care pot fi executate asupra paginii. Acest câmp determină dacă pagina poate fi doar citită (R/O - Read Only) sau citită şi scrisă (R/W – Read/Write). Câmpul de adresă specifică numărul cadrului în care este încărcată pagina. Adresa reală de început a cadrului de paginii, în memoria principală, este determinată înmulţind numărul cadrului cu dimensiunea cadrului. In continuare la adresa reală a începutului de cadru se adună deplasamentul şi se obţine adresa reală a cuvântului solicitat.
Atunci când se solicită un cuvânt de memorie care nu este încărcat în memorie, este raportată o lipsă de pagină (page fault) iar pagina care conţine cuvântul solicitat este încărcată în memorie. Pagina este depusă într-un cadru liber, dacă un asemenea cadru există. Dacă nu există un cadru liber trebuie selectată una din paginile procesului, care va fi ştearsă, iar noua pagină va fi memorată în locul acesteia. Criteriul pentru selectarea paginii care se va înlocui constituie strategia de înlocuire sau algoritmul de înlocuire.
Fig. 6.18 Să considerăm următorul exemplu. In figura 6.18 sunt prezentate
conţinutul tabelelor de pagini pentru două procese, Proces 1 şi Proces 2. Procesul 1 are trei pagini, 0P , 1P şi 2P , iar procesul 2 are două pagini, 0P şi 1P . Presupunem că toate paginile procesului 1 au acces numai pentru citire, iar paginile procesului 2 au acces pentru citire şi scriere. Adresa fizică de început a fiecărui cadru se calculează înmulţind numărul cadrului cu dimensiunea acestora.
Să presupunem că fiecare cadru are o dimensiune de 4 KB (4096 B).
12K
8K
0
4K
Nr. cadru
Memorie principală
Adresă fizică
Tabela de pagini pentru procesul 2
Tabela de pagini pentru procesul 1
Nr. pagină
Nr. pagină
Proces 1
P0 P1
P2
P0 P1
Proces 2
0
P Acces Adresă
P Acces Adresă
1 R/O 1
0 R/O -
1 R/O 3
1 R/W 2
0 R/W -
1
2
0
1
P0
P0
P2
3
2
1
0
Astfel, dat fiind faptul că paginile 0P şi 2P ale procesului 1 sunt încărcate în cadrele 1 şi 3, adresele de bază reale ale acestor cadre (în memoria principală) vor fi 1 * 4096=4096, respectiv 3 * 4096=12288. Dacă la adresa de bază reală a cadrului de adaugă deplasamentul se obţine adresa reală a datei solicitate de UCP.
Procesul de conversie a adreselor virtuale în adrese fizice poate fi efectuat mai rapid prin utilizarea unui buffer de translatare TLB (Translation Look-aside Buffer) care va memora o parte dintre fişele conţinute de tabela de pagini a procesului respectiv. Pentru micşorarea timpului de răspuns al TLB acesta poate fi implementat printr-o memorie asociativă.
Eficienţa unui sistem de memorie virtuală depinde de minimizarea numărului lipsurilor de pagină. Deoarece timpul de acces al memoriei secundare este mult mai ridicat decât timpul de acces al memoriei principale, un număr excesiv al lipsurilor de pagină poate încetini sistemul în mod semnificativ.
O problemă specială o ridică situaţia în care una dintre paginile din memoria principală a fost modificată. In această situaţie pagina respectivă trebuie copiată pe disc. Pentru a determina care pagină a fost modificată se adaugă la fiecare pagină un bit suplimentar numit bit de modificare sau bit de inconsistenţă. Dacă o anumită pagină a fost modificată, bitul corespunzător de modificare este setat la 1. Dacă bitul de modificare al unei pagini este 1 şi această pagină a fost selectată pentru a fi eliminată din memorie, atunci vor fi necesare două accesuri la disc: unul pentru salvarea respectivei pagini în memoria secundară şi încă unul pentru aducerea paginii noi în memoria principală. Dacă bitul de modificare este 0 (aceasta însemnând că nu au fost modificări ale acestei pagini), nu este necesară scrierea paginii pe disc aceasta putând fi ştearsă.
6.7.4. Segmentarea O altă metodă de implementare a memoriei virtuale este numită
segmentare. In acest caz, un program este împărţit în secţiuni de lungime variabilă numite segmente. Un segment poate corespunde unei entităţi logice cum ar fi un set de date sau o funcţie în cadrul unui program. Fiecare proces păstrează o tabelă de segmente în memoria principală, tabelă care conţine în principiu aceleaşi informaţii ca şi tabela de pagini, însă, spre deosebire de pagini, segmentele au lungimi diferite şi ele pot începe în orice zonă din memorie. Pentru acest motiv, eliminarea unui segment din memoria principală nu asigură întotdeauna spaţiu suficient pentru aducerea altui segment.
Un cuvânt dintr-un segment este referit specificând o adresă de bază, numită adresă de segment şi un deplasament în cadrul segmentului. Un program şi datele sale pot fi considerate ca o colecţie de segmente înlănţuite. Legăturile provin din faptul că un segment de program utilizează sau apelează alte segmente.
Avantajul principal al segmentării constă în faptul că limitele segmentelor corespund limitelor programului şi ale datelor. In consecinţă, informaţiile care sunt partajate între diferiţi utilizatori sunt organizate adesea în segmente. Din
cauza independenţei logice între segmente, un segment de program poate fi modificat şi recompilat în orice moment fără a afecta alte segmente. Anumite proprietăţi ale programelor, ca de exemplu, domeniul de definiţie al unei variabile sau drepturile de acces, pot fi specificate în mod natural de către segmente. Aceste proprietăţi necesită ca accesurile la segmente să fie verificate pentru a preveni utilizarea lor neautorizată.
Dezavantajul segmentării constă în utilizarea ineficientă a memoriei principale. La sistemele care utilizează segmentarea, blocurile de dimensiuni diferite tind să prolifereze în memoria principală, lăsând între ele spaţii neutilizabile. Acestea pot fi eliminate prin procesul de compactare a memoriei. Existenţa unui spaţiu inutilizabil între zonele ocupate de segmente este numită fragmentare externă. In cazul paginării, deoarece cadrele de pagină sunt contigue, fragmentarea externă nu apare.
Comparând paginarea şi segmentarea, paginarea necesită un sistem mai simplu de alocare a memoriei decât segmentarea, deoarece paginile au aceeaşi dimensiune. Pe de altă parte, paginile nu au semnificaţie logică, deoarece ele nu reprezintă elemente de program.
Administrarea memoriei virtuale poate fi simplificată prin combinarea segmentării cu paginarea. Utilizând această soluţie se obţine şi o mai bună utilizare a memoriei principale. Totuşi, dacă un bloc de k cuvinte este împărţit în p pagini de câte n cuvinte, iar k nu este un multiplu de n, ultimul cadru de pagină căruia îi este asignat blocul nu va fi ocupat complet. Existenţa unui spaţiu inutilizabil în interiorul unui cadru de pagină ocupat parţial este numită fragmentare internă.
6.7.5. Paginarea şi segmentarea Paginarea şi segmentarea pot fi combinate pentru a obţine avantajele
ambelor soluţii. In acest caz, fiecare segment este împărţit în pagini. Avantajul principal al divizării unui segment în pagini este că se elimină necesitatea de a plasa segmentul într-o zonă contiguă din memoria principală. In loc de aceasta, este nevoie doar de un număr de cadre de pagină egal cu numărul paginilor în care s-a împărţit segmentul. Deoarece aceste cadre de pagină nu trebuie să fie contigue, este mai uşor de plasat un segment de dimensiuni mari în memoria principală.
Atunci când paginarea este combinată cu segmentarea, o adresă virtuală are trei componente: un index de segment SI , un index de pagină PI şi un deplasament (offset) D . In acest caz, tabela de adrese ale memoriei constă din una sau mai multe tabele de segmente şi tabele de pagini. Pentru translatarea rapidă a adreselor, se pot utiliza două buffere de translatare TLB, unul pentru tabelele de segmente şi unul pentru tabelele de pagini (figura 6.19).
Fiecare adresă virtuală Av, generată de un program, este translatată printr-un proces în două etape. Mai întâi, se utilizează indexul de segment SI pentru a citi tabela curentă de segmente cu scopul de a obţine adresa de bază PB a tabelei de pagini necesare.
Această adresă de bază este combinată cu indexul de pagină PI (care
este un deplasament în cadrul tabelei de pagini) pentru a genera o adresă de pagină, care este utilizată apoi pentru accesul la o tabelă de pagini. Rezultatul este o adresă reală de pagină, deci un număr al cadrului de pagină, care poate fi combinat cu partea de deplasament D a adresei virtuale vA pentru a obţine adresa reală finală rA .
Fig. 6.19 6.7.6. Alocarea memoriei Diferitele niveluri ierarhice ale unui sistem de memorie sunt împărţite în
seturi de pagini sau segmente, care păstrează blocuri de date. Blocurile sunt transferate în mod automat între aceste niveluri în scopul minimizării timpului de acces al ierarhiei de memorie. Plasarea acestor blocuri într-un sistem de memorie se numeşte alocarea memoriei. Metoda de selectare a părţii memoriei principale 1M în care trebuie plasat un nou bloc K constituie strategia de înlocuire. Strategiile simple de înlocuire plasează blocul K în memoria 1M numai atunci când este disponibilă o regiune neocupată cu o dimensiune suficientă (alocare non-preemptivă). Alte strategii realizează realocarea
5 4
3
1
2
Cadru de pagină
Index de pagină PI
Index de segment SI
Adresă de bază a tabelei de pagini PB
Adresă de bază a tabelei de
segmente SB pentru un proces
Deplasament (offset) D
Adresă reală Ar
La sistemul de memorie M
Adresă virtuală Av
TLB
tabelă de segmente
TLB
tabelă de pagini
M
M
(mutarea) blocurilor existente în memorie pentru a face loc blocului K (alocare preemptivă). In general, metodele de alocare ale memoriei care sunt eficiente au ca efect o rată ridicată de succes şi un timp mediu de acces scăzut. O alocare eficientă a memoriei minimizează de asemenea spaţiul neocupat din memoria 1M .
Atunci când un bloc este transferat din memoria 2M în memoria 1M , sistemul de gestiune a memoriei crează o intrare corespunzătoare în lista spaţiilor ocupate. Atunci când un bloc nu mai este necesar în memoria 1M , acesta este eliberat (dealocat) şi regiunea pe care o ocupă este transferată din lista spaţiilor ocupate în lista spaţiilor disponibile. Un bloc este dealocat atunci când un program care îl utilizează îşi termină execuţia sau când blocul este înlocuit de către un alt bloc.
6.7.6.1. Alocarea non-preemptivă Presupunem că un bloc Ki, de ni cuvinte trebuie transferat din memoria
2M în 1M . Dacă nici unul din blocurile care ocupă deja memoria 1M nu poate fi înlocuit de către blocul Ki, atunci este necesar să se găsească sau să se creeze o regiune disponibilă de ni, sau mai multe cuvinte, care permite plasarea blocului Ki. Acest proces este cunoscut ca alocare non-preemptivă a memoriei.
Alocarea non-preemptivă poate fi implementată mai simplu într-un sistem cu paginare, unde toate blocurile (paginile) au o dimensiune fixă. Harta memoriei (tabela de pagini) este parcursă pentru a găsi un cadru de pagină disponibil; dacă se găseşte unul, acesta este asignat blocului Ki. Această metodă simplă de alocare este motivul principal al utilizării pe scară largă a paginării. Dacă spaţiul de memorie este divizat în regiuni de lungime variabilă (segmente), devine însă mai dificil să se aloce în mod eficient noi blocuri.
Doi algoritmi utilizaţi pe scară largă pentru alocarea non-preemptivă a blocurilor de dimensiune variabilă (segmente care nu sunt paginate, de exemplu) sunt primul potrivit, cel mai potrivit şi cel mai nepotrivit.
Primul potrivit. Această metodă plasează blocul dat în prima regiune liberă cu dimensiunea potrivită. Se parcurge harta memoriei în mod secvenţial până când se găseşte o regiune disponibilă Rj de ni sau mai multe cuvinte, iar apoi se alocă blocul Ki regiunii Rj .
Principalul avantaj al acestei metode este că favorizează formarea unor zone libere la adresele mari de memorie prin plasarea blocurilor la adresele joase de memorie ori de câte ori este posibil. Totuşi, această metodă produce zone libere care pot fi prea mici pentru a păstra un bloc. Această problemă este cunoscută sub numele de fragmentare. Atunci când apare fragmentarea, până la urmă trebuie rulat un anumit algoritm de compactare pentru a colecta toate zonele libere de dimensiuni mici într-o zonă cu dimensiunea mai mare. Aceasta procedură poate reduce performanţele.
Cel mai potrivit. Această metodă alocă regiunea disponibilă cu dimensiunea cea mai mică, care este suficient de mare pentru a păstra blocul dat. Ca şi strategia primului potrivit, strategia celui mai potrivit produce de asemenea, fragmentarea memoriei. Această strategie poate crea un număr
mare de blocuri mici care sunt inutilizabile în majoritatea cazurilor. Comparând algoritmii primului potrivit şi celui mai potrivit, algoritmul
primului potrivit are avantajul timpului de execuţie mai redus. Studiile de simulare sugerează că, în practică, algoritmul primului potrivit tinde să aibă performanţe mai bune decât algoritmul celui mai potrivit.
Cel mai nepotrivit. Această metodă alocă, pentru blocul ce urmează să fie adus în memorie, regiunea disponibilă cu dimensiunea cea mai mare. Această metodă, ca şi celelalte două metode, produce fragmentarea memoriei. Totuşi, spre deosebire de primele două metode, metoda celui mai nepotrivit reduce numărul regiunilor mici.
6.7.6.2. Alocarea preemptivă
Alocarea non-preemptivă nu poate utiliza eficient memoria în toate situaţiile. Este posibil să apară refuzarea unei cereri de alocare a memoriei datorită spaţiului insuficient, deşi memoria M1 este doar parţial ocupată. Utilizarea mult mai eficientă a spaţiului disponibil din memorie poate fi realizată prin relocarea blocurilor existente în memorie M1, pentru a face loc blocurilor ce urmează a fi aduse din memoria M2.
Dacă, la aducerea unui bloc din memoria M2, nu se mai găseşte totuşi un spaţiu suficient pentru acesta este necesară înlocuirea (dealocarea) unor blocuri, neutilizate sau mai puţin utilizate, din memoria M1. Metodă preemptivă necesită deci o strategie de selecţie a blocurilor care trebuie dealocate.
Dealocarea necesită stabilirea unei distincţii între blocurile care au fost modificate de la încărcarea lor în memoria 1M şi blocurile care nu au fost modificate. Blocurile de instrucţiuni rămân nemodificate, în timp ce blocurile de date pot fi modificate. Pentru înlocuirea unui bloc care nu a fost modificat, sistemul de gestiune a memoriei poate înlocui în mod simplu blocul dealocat cu noul bloc şi poate actualiza intrarea acestuia în harta memoriei. Înainte ca un bloc modificat să fie înlocuit, acesta trebuie copiat în memoria 2M .
Strategiile de înlocuire mai des utilizate sunt: - FIFO (First-In, First-Out);
- LRU (Least Recently Used). FIFO este una din cele mai simple strategii de înlocuire. Blocul selectat
pentru înlocuire este blocul cel mai puţin recent încărcat în memoria 1M . Avantajul strategiei FIFO constă în faptul că este foarte simplu de implementat. Fiecărui bloc i se asociază un contor în lista spaţiilor ocupate; contoarele asociate cu blocurile indică secvenţa lor de încărcare. De fiecare dată când un bloc este transferat în memoria 1M , contoarele indicând secvenţa de încărcare sunt actualizate. Prin inspectarea acestor contoare, unitatea de gestiune a memoriei poate determina cu uşurinţă primul bloc care a fost încărcat.
Dezavantajul strategiei FIFO este că poate mări în mod semnificativ timpul necesar pentru execuţia unui proces, deoarece poate înlocui cu aceeaşi probabilitate blocuri utilizate intens şi blocuri utilizate rar. De exemplu, dacă un bloc încărcat în memorie de mai mult timp conţine o variabilă globală care este utilizată în mod constant, acest bloc va fi unul din primele care va fi înlocuit. La
următorul acces la variabila globală, va apare o nouă lipsă a blocului, iar blocul va trebui reîncărcat, înlocuind un alt bloc.
Strategia LRU (Least Recently Used) selectează pentru înlocuire blocul care nu a fost utilizat de cel mai mult timp. Această strategie se bazează pe presupunerea rezonabilă că blocul cel mai puţin recent utilizat este cel mai puţin probabil de a fi utilizat în viitor. Strategia LRU evită înlocuirea blocurilor încărcate de mai mult timp, dar frecvent utilizate, ca în cazul strategiei FIFO. Totuşi, strategia LRU este mai dificil de implementat decât FIFO, deoarece sistemul de gestiune a memoriei trebuie să păstreze informaţii despre momentele referinţelor la toate blocurile din memoria 1M . Strategia LRU poate fi implementată prin asocierea unui contor hardware sau software pentru fiecare bloc din 1M . De fiecare dată când un bloc este referit, contorul acestuia este setat la o valoare pozitivă predeterminată. La intervale fixe de timp, contoarele tuturor blocurilor sunt decrementate. In orice moment, blocul cel mai puţin recent utilizat este cel al cărui contor conţine valoarea cea mai mică.
Cap. 7. SISTEME PIPELINE
Tehnica pipeline reprezintă o metodă de îmbunătăţire a performanţelor unui procesor sau a unei unităţi aritmetice prin executarea simultană a mai multor instrucţiuni sau operaţii. Această tehnică utilizează paralelismul, prin suprapunerea fazelor de execuţie ale instrucţiunilor sau a etapelor de execuţie ale unei operaţii aritmetice. Un sistem pipeline poate fi comparat cu o linie de asamblare a unui produs, în care există mai multe posturi de lucru, fiecare dintre acestea fiind specializat pentru o anumită operaţie, iar la capătul benzii este obţinut produsul final.
7.1. Structura unui sistem pipeline Tehnica pipeline descompune un proces secvenţial în mai multe
subprocese care sunt executate de unităţi (etaje) diferite. Un etaj execută un subproces şi produce un rezultat intermediar, care reprezintă o intrare pentru etajul următor. Rezultatul final este obţinut numai după ce toate subprocesele au trecut prin întregul sistem pipeline. Figura 7.1 ilustrează structura de bază a unui sistem pipeline cu m etaje.
Fig. 7.1
Un etaj iE constă dintr-un registru de intrare iR şi un circuit de prelucrare iC care poate fi secvenţial, combinaţional sau inteligent. Registrele păstrează
rezultatele parţiale pe măsură ce acestea se deplasează prin sistemul pipeline. Un semnal comun de ceas determină ca registrele să îşi schimbe starea în mod sincron. In fiecare ciclu de ceas, fiecare etaj transferă rezultatele sale parţiale la următorul etaj şi calculează un nou set de rezultate. Perioada semnalului de ceas trebuie să fie suficient de mare pentru ca etajul cel mai lent să termine execuţia operaţiei sale. In plus, trebuie să existe un interval de timp suficient pentru ca un registru să memoreze datele elaborate de etajul anterior. Deci, perioada ceasului trebuie să fie mai mare decât întârzierea maximă a etajului cel mai lent, plus timpul necesar pentru memorarea datelor într-un registru.
Date de intrare
Date de ieşire
Etaj E1 Etaj E2 Etaj Em
R1 R2 Rm
C1 C2 Cm
Unitate de Control
Avantajul acestei tehnici constă în faptul că un sistem pipeline cu m etaje poate procesa simultan până la m seturi independente de subprocese. Aceste subprocese se deplasează prin sistemul pipeline etaj cu etaj astfel încât, atunci când sistemul pipeline este plin, sunt executate în mod concurent m operaţii distincte, fiecare într-un etaj diferit. In acest mod un nou rezultat final este generat la ieşirea sistemului pipeline în fiecare ciclu de ceas.
7.2. Tipuri de sisteme pipeline Sistemele pipeline sunt împărţite, de obicei, în două categorii: de
instrucţiuni şi aritmetice. Un sistem pipeline de instrucţiuni este realizat pentru a îmbunătăţi performanţele unui calculator prin suprapunerea eficientă a fazelor de execuţie ale instrucţiunilor. Sistemele pipeline aritmetice implementează anumite funcţii ale unităţii aritmetice şi logice cum ar fi adunarea, înmulţirea şi împărţirea în virgulă mobilă.
Un sistem pipeline din oricare categorie poate fi proiectat în două moduri: static sau dinamic.
Un sistem pipeline static poate executa un singur tip de operaţie la un moment dat. Operaţia executată de un asemenea sistem poate fi schimbată numai după ce acesta este golit, atunci când ultimele date de intrare au trecut prin toate etajele. De exemplu, să considerăm un sistem pipeline static care poate executa operaţiile de adunare şi înmulţire. De fiecare dată când sistemul pipeline comută de la o operaţie de înmulţire la una de adunare, acesta trebuie golit şi trebuie setat pentru noua operaţie. Performanţele sistemelor pipeline statice vor fi reduse în mod semnificativ dacă tipul operaţiilor se modifică în mod frecvent.
Un sistem pipeline dinamic poate executa mai multe tipuri de operaţii la un moment dat. Pentru a executa o anumită operaţie asupra unor date de intrare, datele trebuie să parcurgă anumite etaje într-o anumită ordine. Să presupunem că figura 7.2 reprezintă un sistem pipeline dinamic cu trei etaje, care poate executa adunarea şi înmulţirea în acelaşi timp asupra unor date diferite.
Pentru execuţia operaţiei de înmulţire, datele de intrare trebuie să parcurgă etajele 1, 2 şi 3; pentru execuţia operaţiei de adunare, datele trebuie să parcurgă numai etajele 1 şi 3.
La intrarea etajului 1 se pot aplica două seturi de date D1 şi D2. Deoarece ambele seturi de date urmează să utilizeze etajul 3, intervalul de timp dintre aplicarea datelor 1D şi 2D la intrările sistemului pipeline trebuie să fie astfel ales încât aceste date să nu ajungă în etajul 3 în acelaşi ciclu de ceas; în caz contrar, apare o coliziune. In general, în cazul sistemelor pipeline dinamice mecanismul care controlează momentul în care datele trebuie aplicate la intrare este mult mai complex decât în cazul sistemelor statice.
Fig. 7.2
7.3. Sisteme pipeline de instrucţiuni 7.3.1. Principi In cazul unei arhitecturi von Neumann, procesul de execuţie a
instrucţiunilor implică mai multe faze. Mai întâi, unitatea de control a procesorului încarcă instrucţiunea din memoria cache sau din memoria principală. Apoi, unitatea de control decodifică instrucţiunea pentru a determina tipul operaţiei care trebuie executată. Dacă operaţia necesită operanzi, unitatea de control determină adresa fiecărui operand după care îi încarcă din memoria cache sau din memoria principală. Operaţia este apoi executată şi, în sfârşit, rezultatul este memorat în locaţia specificată.
Un sistem pipeline de instrucţiuni îmbunătăţeşte performanţele unui procesor prin suprapunerea prelucrării mai multor instrucţiuni diferite. Acest lucru se realizează prin divizarea procesului de execuţie a instrucţiunilor în mai multe faze. Un sistem pipeline de instrucţiuni este în mod normal transparent programatorilor şi este gestionat automat de către unitatea de control a UCP şi de către compilatoare.
In general execuţia unei instrucţiuni se poate descompune în următoarele operaţii simple:
1. Extragerea instrucţiunii (IF - Instruction Fetch): aducerea instrucţiunii din memoria cache sau din memoria principală.
D1, D2
Intrare
Ieşire
Etaj 1
Etaj 2
Etaj 3
Registru
Registru
Registru
Circuit de prelucrare
Circuit de prelucrare
Circuit de prelucrare
2. Decodificarea instrucţiunii (ID - Instruction Decoding): identificarea operaţiei care trebuie executată.
Figura 7.4 prezintă un sistem pipeline de instrucţiuni cu cinci etaje, fiecare etaj având ca obiectiv executarea uneia dintre operaţiile precizate mai sus. Un sistem pipeline de instrucţiuni suprapune operaţiile executate de aceste etaje asupra unor instrucţiuni diferite cu scopul de a obţine, pentru o secvenţă de instrucţiuni, un timp total de execuţie mult mai redus.
Fig. 7.4
Ca un exemplu, se consideră figura 7.5, care prezintă execuţia unei secvenţe de patru instrucţiuni.
Registru
Registru
Registru
Registru
Registru
Etaj 1
Etaj 2
Etaj 3
Etaj 4
Etaj 5
Registre, memorii cache, memorie
principala
Extragere instrucţiune IF
Decodificare instrucţiune ID
Încărcare operanzi OF
Execuţie EX
Scriere rezultate WB
Fig. 7.5 In timpul primului ciclu, (o perioadă de ceas) instrucţiunea 1i este încărcată
din memorie. In cel de-al doilea ciclu, instrucţiunea 1i este decodificată în timp ce instrucţiunea 2i este încărcată din memorie. Acest proces continuă până când toate instrucţiunile sunt executate. Ultima instrucţiune se termină după opt cicluri de ceas.
Deşi, prin utilizarea tehnicii pipeline, creşte viteza de execuţie a instrucţiunilor, această tehnică poate pune anumite probleme. Unele din aceste probleme şi soluţiile posibile sunt prezentate în secţiunile următoare.
7.3.2. Indisponibilitatea instrucţiunilor (The fetching problem) In general, furnizarea rapidă a instrucţiunilor pentru un sistem pipeline este
costisitoare din punct de vedere al resurselor necesare. O metodă simplă pentru îmbunătăţirea gradului de utilizare al unui sistem pipeline este utilizarea bufferelor pentru memorarea instrucţiunilor şi a datelor care vor fi transmise la intrarea sistemului. Gradul de utilizare al unui sistem pipeline este definit ca raportul între timpul în care etajele sistemului sunt utilizate şi timpul total. Un sistem pipeline este utilizat 100% din timp dacă fiecare etaj este utilizat în fiecare ciclu de ceas.
In unele situaţii, sistemul pipeline trebuie golit şi reîncărcat, de exemplu, atunci când apare o instrucţiune de salt sau o întrerupere. Timpul necesar pentru reîncărcare poate fi minimizat prin încărcarea în avans a instrucţiunilor şi a datelor în memoria cache din cadrul procesorului, fapt care va permite transferul acestora imediat la intrarea sistemului pipeline. Dacă instrucţiunile şi datele necesare execuţiei vor fi încărcate şi memorate în memoria cache înainte ca acestea să fie necesare, sistemul pipeline va avea o sursă continuă de informaţii. Utilizarea unor algoritmi de preîncărcare adecvaţi asigură faptul că instrucţiunile potenţial necesare vor fi disponibile în majoritatea timpului.
Dacă, în schimb, nu este asigurat un flux continuu de instrucţiuni sau operanzi, sistemul pipeline nu va fi alimentat corespunzător şi vor exista etaje care nu lucrează în fiecare ciclu de ceas. In această situaţie gradul de utilizare al sistemului va scădea.
7.3.3. Întârzierea introduse de etaje (bottleneck problem) Această problemă se referă la complexitatea operaţiilor executate de
etajele sistemului pipeline. Dacă un etaj execută operaţii mai complexe faţă de
Cicluri → 1 2 3 4 5 6 7 8
i1 IF ID OF EX WB
i2 IF ID OF EX WB i3 IF ID OF EX WB i4 IF ID OF EX WB
alte etaje, timpul necesar pentru terminarea acestor operaţii va creşte. Ca urmare, perioada ceasului trebuie aleasă în funcţie de acest timp, ceea ce reduce performanţele întregului sistem. O soluţie posibilă a acestei probleme este divizarea etajului respectiv în mai multe etaje. O altă soluţie este de a se realiza mai multe copii ale acestui etaj, care să execute în paralel respectiva operaţie.
7.3.4 Emiterea instrucţiunilor (The issuing problem) Această problemă apare atunci când o instrucţiune disponibilă nu poate fi
executată. Cauzele care pot genera o astfel de situaţie sunt următoarele: - resursa necesară nu este disponibilă (hazard structural); (în acest
context, prin resursă se înţelege o unitate hard) - există o dependenţă de o instrucţiune anterioară (hazard de date); - intervenţia instrucţiunilor de salt care modifică succesiunea de execuţie a
instrucţiunilor (hazardul de control). 7.3.4.1 Hazardul structural Hazardul structural se referă la situaţia în care o resursă necesară nu este
disponibilă pentru execuţia instrucţiunii. Un hazard structural apare ca rezultat al conflictelor la accesarea resurselor între instrucţiuni. Un tip de hazard structural care poate apare se datorează modului de proiectare al unităţilor de execuţie. Dacă o unitate de execuţie, care necesită mai multe cicluri de ceas, nu este de tip pipeline şi nu există mai multe unităţi de acelaşi tip, atunci nu se pot lansa în execuţie mai multe instrucţiuni care utilizează această unitate.
Un alt tip de hazard structural care poate apare se datorează proiectării setului de registre. Dacă un set de registre nu are mai multe porturi de citire/scriere, atunci operaţiile multiple de citire/scriere nu pot fi executate simultan. De exemplu, în anumite situaţii sunt necesare două operaţii de scriere în registre în acelaşi ciclu de ceas. Aceste operaţii nu sunt posibile dacă setul de registre are un singur port de scriere.
Efectul unui hazard structural poate fi eliminat în mod simplu prin implementarea unităţilor de execuţie multiple şi prin utilizarea unui set de registre cu porturi multiple de citire sau scriere.
7.3.4.2. Hazardul de date Hazardul de date apare atunci când există dependenţe de date între
instrucţiunea curentă şi o instrucţiune precedentă. In cazul unui procesor care nu utilizează tehnica pipeline, instrucţiunile sunt executate secvenţial, iar execuţia unei instrucţiuni este terminată înaintea începerii execuţiei următoarei instrucţiuni. Astfel, instrucţiunile sunt executate în aceeaşi ordine în care apar în program. Situaţia este diferită în cazul unui procesor care utilizează tehnica pipeline, la care execuţia instrucţiunilor este suprapusă. O instrucţiune poate fi lansată în execuţie şi terminată înaintea terminării instrucţiunii precedente. Hazardul de date, cunoscut şi sub numele de problema dependenţei datelor, apare ca rezultat al suprapunerii execuţiei (sau schimbării ordinii de execuţie) a
instrucţiunilor între care există dependenţe de date. Pentru a înţelege această problemă să considerăm că într-un program apare următoarea secvenţă de instrucţiuni:
Instrucţiunea 2i depinde de 1i , deoarece utilizează rezultatul instrucţiunii 1i (conţinutul registrului R2) ca o dată de intrare. In figura 7.6 este prezentată execuţia celor două instrucţiuni în sistemul pipeline considerat.
Cicluri → 1 2 3 4 5 6
i1 IF ID OF EX WB i2 IF ID OF EX WB
Fig. 7.6 După cum se constată instrucţiunea 2i ajunge în faza OF înainte ca 1i să
treacă prin faza WB. Această situaţie conduce la utilizarea vechiului conţinut al registrului R2 pentru calcularea unei noi valori a variabilei R5 şi deci, la un rezultat invalid. Pentru a se obţine un rezultat valid, instrucţiunea 2i nu trebuie să ajungă în faza OF până când 1i nu trece prin faza WB. In timpul execuţiei problema semnalată poate fi rezolvată în două moduri (figura 7.7):
- execuţia fazei OF a instrucţiunii 2i este întârziată cu două cicluri cu ceas sau
- lansarea în execuţie a instrucţiunii 2i este întârziată cu două cicluri de ceas.
In ambele cazuri faza OF a instrucţiunii 2i este executată după ce conţinutul registrului R2 a fost reactualizat de faza WB a instrucţiunii 1i .
Cicluri → 1 2 3 4 5 6 7 8
i1 IF ID OF EX WB i2 IF ID - - OF EX WB
Cicluri → 1 2 3 4 5 6 7 8 i1 IF ID OF EX WB i2 - - IF ID OF EX WB Fig. 7.7 Pentru realizarea acestor întârzieri, se adăugă la sistemul pipeline un
circuit suplimentar, numit circuit de interblocare (pipeline interlock). Acest circuit detectează dependenţele între date şi întârzie instrucţiunile dependente până la rezolvarea conflictului.
O altă posibilitate constă în rezolvarea acestui tip de hazard în timpul compilării. Compilatorul detectează aceste dependenţe şi rearanjează instrucţiunile astfel încât hazardurile de date să fie eliminate.
De exemplu, considerăm cele patru instrucţiuni de mai jos. După cum se poate observa există un conflict de date între instrucţiunile 1i şi 2i . Acest conflict poate fi eliminat prin reordonarea instrucţiunilor astfel încât instrucţiunile 3i şi 4i , care nu sunt dependente de 1i şi 2i , să fie inserate între acestea din urmă. (figura 7.8).
i1 IF ID OF EX WB i3 IF ID OF EX WB i4 IF ID OF EX WB i2 IF ID OF EX WB
Fig. 7.8 Dacă nu este posibilă rearanjarea instrucţiunilor, întârzierile necesare pot
fi realizate de către compilator prin inserarea un număr necesar de instrucţiuni NOP (No Operation).
Există trei tipuri principale de hazarduri de date: RAW (Read After Write), WAR (Write After Read) şi WAW (Write After Write). Numele hazardului indică ordinea de execuţie a operaţiilor pentru a se obţine un rezultat valid; dacă această ordine nu este respectată, se poate obţine un rezultat invalid. Aceste hazarduri sunt explicate în continuare. Se presupune că există două instrucţiuni 1i şi 2i , iar 2i trebuie executată după 1i .
RAW. Acest de hazard indică faptul că 2i trebuie să citească sursa de date după ce 1i a scris această dată. Dacă această ordine nu este respectată se produce un rezultat invalid deoarece data din locaţia citită nu a fost reactualizată.
De exemplu, în secvenţa următoare: 1i : ADD R2, R3, R4 ; R2 = R3 + R4 2i : ADD R5, R2, R1 ; R5 = R2 + R1
se poate obţine un rezultat invalid dacă 2i citeşte registrul R2 înainte ca 1i să scrie în acest registru.
WAR. Acest hazard indică faptul că 2i trebuie să scrie într-o anumită locaţie după ce 1i a citit data conţinută în acea locaţie. Dacă această ordine nu este păstrată conţinutul acelei locaţii de memorie este alterat. De exemplu, în secvenţa:
se poate obţine un rezultat invalid dacă 2i scrie în registrul R4 înainte ca 1i să citească acest registru, caz în care instrucţiunea 1i va utiliza un conţinut incorect al registrului R4.
WAW. Acest hazard indică faptul că 2i trebuie să scrie într-o anumită locaţie după ce 1i a scris în aceeaşi locaţie. De exemplu, în secvenţa:
valoarea din registrul R2 este recalculată de către 2i . Dacă ordinea de execuţie este inversată, iar 2i scrie în registrul R2 înainte ca 1i să scrie în acest registru, R2 va conţine o valoare incorectă.
Hazardurile de tip WAR şi WAW nu pot apare atunci când ordinea de execuţie a instrucţiunilor din program este păstrată.
In arhitecturile actuale, dependenţele între instrucţiuni (Data Dependancy) sunt verificate în mod static de compilator şi/sau în mod dinamic (în timpul execuţiei) de circuite specializate.
Au fost dezvoltate numeroase tehnici statice de verificare a dependenţelor pentru a se utiliza avantajul paralelismului. Aceste tehnici pot detecta majoritatea dependenţelor. Totuşi, anumite dependenţe nu pot fi detectate la compilare. De exemplu, nu este posibil să se determine întotdeauna adresele efective de memorie utilizate de instrucţiunile de încărcare şi memorare pentru a putea detecta posibilele dependenţe între acestea. In cazul indirectării, de exemplu, adresele efective de memorie vor fi cunoscute numai după execuţia instrucţiunii şi, astfel, dependenţele între instrucţiuni pot fi determinate numai în mod dinamic. In general, verificarea dinamică a dependenţelor are avantajul că poate detecta dependenţele care sunt imposibil sau dificil de detectat la compilare. Pentru a se folosi avantajele ambelor metode, în practică se utilizează adesea o verificare combinată (statică şi dinamică) a dependenţelor.
Una dintre mai des utilizate tehnici pentru verificarea dinamică a dependenţelor este metoda tabelei de rezultate (scoreboard). Ideea de bază a acestei metode este utilizarea unui mecanism pentru identificarea disponibilităţii operanzilor şi a unităţilor funcţionale în calculele succesive.
7.3.5 Metoda tabelei de rezultate (Scoreboard) Metoda tabelei de rezultate poate fi utilizată la calculatoarele ale căror
unităţi funcţionale multiple permit terminarea execuţiei instrucţiunilor într-o ordine diferită de cea în care apar în program. Conform acestei metode se păstrează în anumite buffere (care constituie tabela de rezultate) informaţii despre starea fiecărei instrucţiuni lansate în execuţie, starea fiecărui registru şi a fiecărei unităţi funcţionale. Prin consultarea tabelei de rezultate unitatea de comandă poate determina dacă, la un moment dat, trebuie să aştepte pentru execuţia unei anumite instrucţiuni. Dacă aşteptarea nu este necesară, unitatea funcţională corespunzătoare începe imediat execuţia instrucţiunii. Dacă trebuie să se aştepte (de exemplu, unul din operanzii de intrare nu este încă disponibil), execuţia noii instrucţiuni este întârziată.
O tabelă de rezultate este fi formată din trei părţi: starea instrucţiunilor, starea unităţilor funcţionale şi starea registrelor destinaţie. Figura 7.9 reprezintă un instantaneu al conţinutului acestor tabele pentru următorul program care calculează expresia C+D+A*B.
LOAD R1, A LOAD R2, B LOAD R3, C LOAD R4, D MUL R5, R1, R2 ; R5 = A ∗ B ADD R2, R3, R4 ; R2 = C + D ADD R2, R2, R5 ; R2 = R2 + R5 = C + D + A * B Starea instrucţiunilor
Instrucţiune
Lansată
Faza OF
terminată
Faza EX
terminată
Faza WB terminată
LOAD R1, A Da Da Da Da LOAD R2, B Da Da Da Da LOAD R3, C Da Da Da Da LOAD R4, D Da Da Da MUL R5, R1, R2 Da Da ADD R2, R3, R4 Da ADD R2, R2, R5
Starea unităţilor funcţionale
ID Unita-te
Nume unitate
Ocupată
Registru destinaţie
Registre sursă
RS1 Disp Rs2 Disp 1 LOAD/STORE Da R4 2 Înmulţire Da R5 R1 Da R2 Da 3 Adunare_1 Da R2 R3 Da R4 Nu 4 Adunare_2 Nu
Starea registrelor destinaţie
R1 R2 R3 R4 R5 R6
ID unitate 3 1 2
Fig. 7.9 Presupunem că sistemul de calcul dispune de următoarele patru unităţi
funcţionale: o unitate de încărcare şi memorare - LOAD/STORE, o unitate de înmulţire, şi două unităţi de adunare.
Tabela de stare a instrucţiunilor arată dacă o instrucţiune este sau nu lansată în execuţie. Dacă o instrucţiune este lansată în execuţie, tabela arată în care fază de execuţie se află instrucţiunea. După ce o instrucţiune este încărcată din memorie şi decodificată, se va încerca lansarea execuţiei acesteia
utilizând unitatea funcţională corespunzătoare. O instrucţiune va fi lansată în execuţie dacă unitatea funcţională este disponibilă şi nu există altă instrucţiune activă care utilizează acelaşi registru destinaţie; în caz contrar, lansarea este întârziată. Cu alte cuvinte, o instrucţiune este lansată în execuţie atunci când nu există hazarduri structurale şi hazarduri WAW. Atunci când există asemenea hazarduri, lansarea în execuţie acestei instrucţiuni şi a instrucţiunilor următoare este întârziată până când hazardurile sunt eliminate. In acest fel, instrucţiunile dependente sunt lansate în execuţie în ordinea în care apar în program, în timp ce instrucţiunile independente pot fi executate într-o ordine diferită.
Tabela de stare a unităţilor funcţionale arată dacă o unitate funcţională este ocupată sau nu. O unitate funcţională este consideră ocupată dacă execuţia unei instrucţiuni de către această unitate nu a fost încă terminată. Pentru o unitate ocupată, tabela identifică, de asemenea, disponibilitatea registrul destinaţie şi a registrelor sursă. Un registru sursă al unei unităţi este disponibil dacă nu apare ca destinaţie pentru nici o altă unitate anterioară, care este în curs de execuţie.
Tabela de stare a registrelor destinaţie indică destinaţia registrelor care nu au fost încă înscrise. Pentru fiecare din aceste registre se identifică unitatea funcţională activă care va executa scrierea în registru.
In timpul fazei de extragere a operanzilor, tabelele sunt monitorizate pentru a determina dacă registrele sursă sunt disponibile pentru a fi citite de către o unitate funcţională activă. Dacă nici unul din registrele sursă nu este utilizat ca registru destinaţie de către alte unităţi funcţionale active, unitatea citeşte operanzii din aceste registre şi începe execuţia operaţiei. După terminarea execuţiei, tabela de rezultate testează dacă există hazarduri WAR înainte de a permite scrierea rezultatului în registrul destinaţie. Dacă nu există hazarduri WAR, tabela de rezultate indică unităţii funcţionale să scrie rezultatul în registrul destinaţie.
In figura 7.9, tabelele indică faptul că execuţia primelor trei instrucţiuni LOAD a fost terminată şi operanzii acestora au fost înscrişi în registrul destinaţie. Ultima instrucţiune LOAD a fost lansată în execuţie de către unitatea LOAD/STORE (unitatea 1). La această instrucţiune, s-a terminat extragerea operandului, dar nu s-a înscris încă operandul în registrul R4. Unitatea de înmulţire execută instrucţiunea MUL, iar prima instrucţiune ADD este transmisă unităţii Adunare_1. Această unitate aşteaptă pentru ca registrul R4 să fie înscris de către unitatea LOAD/STORE înainte de a începe execuţia. Acest lucru este necesar deoarece există un hazard RAW între ultima instrucţiune LOAD şi prima instrucţiune ADD. In acest moment, a doua instrucţiune ADD nu poate fi lansată în execuţie, deoarece utilizează registrul R2 ca registru sursă şi destinaţie. Registrul R2 este ocupat în acest moment cu prima instrucţiune ADD. Atunci când registrul R4 este înscris de unitatea LOAD/STORE, unitatea Adunare_1 va începe execuţia.
Ulterior conţinutul tabelei de rezultate se modifică. După cum se ilustrează în figura 7.10, dacă unitatea LOAD/STORE (unitatea 1) a terminat execuţia (a înscris în R4 valoarea variabilei D), unitatea Adunare_1 poate termina faza de încărcare a operanzilor şi începe faza de execuţie. După terminarea execuţiei
rezultatul poate fi înscris în registrul R2 deoarece unitatea de înmulţire a terminat faza de citire a operanzilor şi este acum în faza de execuţie. A doua instrucţiune ADD va fi transmisă acum unităţii Adunare_2.
Cât timp unitatea de înmulţire nu a citit conţinutul registrului R2 unităţii Adunare_1 nu i se va permite scrierea rezultatului în registrul R2; aceasta deoarece există un hazard WAR între instrucţiunea MUL şi prima instrucţiune ADD.
Starea instrucţiunilor Instrucţiune Lansată Faza OF
terminată Faza EX
terminată Faza WB terminată
LOAD R1, A Da Da Da Da LOAD R2, B Da Da Da Da LOAD R3, C Da Da Da Da LOAD R4, D Da Da Da Da MUL R5, R1, R2 Da Da Da ADD R2, R3, R4 Da Da Da Da ADD R2, R2, R5 Da
Starea unităţilor funcţionale
ID unitate
Nume unitate
Ocupată Registru destinaţie
Rd
Registre sursă Rs1 Disp Rs2 Disp
1 LOAD/STORE
Nu 2 Înmulţire Da R5 R1 Da R2 Da 3 Adunare_1 NU 4 Adunare_2 Da R2 R2 Da R5 Nu
Starea registrelor destinaţie
R1 R2 R3 R4 R5 R6 ID unitate
4 2
Fig. 7.10
Componenta principală în cazul metodei tabelei de rezultate este tabela de stare a registrelor destinaţie. Această tabelă este utilizată pentru a soluţiona hazardurile de date între instrucţiuni. De fiecare dată când o instrucţiune este lansată în execuţie, registrul destinaţie al instrucţiunii este marcat ca fiind ocupat. Registrul destinaţie rămâne ocupat până când execuţia instrucţiunii este terminată. Atunci când se pregăteşte lansarea unei noi instrucţiuni, sunt testaţi operanzii acesteia pentru a nu exista conflicte între registre cu instrucţiunile precedente a căror execuţie nu a fost terminată.
7.5. Hazardul de control Hazardul de control se referă la situaţia în care o anumită instrucţiune,
cum ar fi o instrucţiune de salt, modifică fluxul execuţiei programului. 7.5.1. Instrucţiuni de salt In orice limbaj de programare, salturile determină modificarea ordinii sec-
venţiale de execuţie a instrucţiunilor. In general, în jur de 20 - 30% din totalul in-strucţiunilor dintr-un program sunt salturi. Pentru acest motiv, instrucţiunile de salt executate de un sistem pipeline pot reduce în mod semnificativ rata de pre-lucrare. Ori de câte ori este executat un salt, trebuie să se încarce o nouă adre-să în contorul de program, ceea ce poate invalida toate instrucţiunile a căror execuţie a început sau cele care au fost preîncărcate într-un buffer. Această go-lire a etajelor pipeline la fiecare salt reduce performanţele sistemului. De notat că un salt condiţionat, care nu este executat permite continuarea execuţiei sec-venţiale a instrucţiunilor, deci această problemă apare numai în cazul în care saltul este executat.
In general, instrucţiunile de salt se pot clasifica în trei categorii: 1) Salturi necondiţionate; 2) Salturi condiţionale; 3) Bucle. Un salt necondiţionat modifică întotdeauna ordinea secvenţială de execu-
ţie şi, în loc de a incrementa contorul de program, încarcă adresa destinaţiei sal-tului în acesta.
Un salt condiţionat încarcă adresa destinaţiei în contorul de program nu-mai dacă o anumită condiţie, bazată pe starea unor indicatori de condiţii, este îndeplinită. In caz contrar, contorul de program este incrementat ca de obicei. Cu alte cuvinte, un salt condiţionat selectează o cale de urmat pe baza unei condiţii. In cazul în care condiţia este îndeplinită, această cale începe de la adresa destinaţiei saltului şi este numită cale destinaţie. In caz contrar, această cale începe de la următoarea instrucţiune şi este numită cale secvenţială.
O instrucţiune de buclare determină de obicei saltul la începutul buclei, ca-re este executată de un anumit număr de ori, fix sau variabil.
Dintre aceste tipuri de salturi, salturile condiţionate sunt cel mai dificil de gestionat. Ca un exemplu, considerăm următoarea secvenţă de instrucţiuni:
i1 i2 (salt condiţionat la i5)
3i i4 i5 (destinaţie) i6 Figura 7.11 prezintă execuţia acestei secvenţe de instrucţiuni într-un sis-
tem pipeline atunci când se selectează calea destinaţie. In această figură, c in-dică penalizarea datorită saltului, reprezentând numărul de cicluri pierdute
atunci când este selectată calea destinaţie.
Cicluri → 1 2 3 4 5 6 7 8 9 10 11
i1 IF ID OF EX WB i2 IF ID OF EX WB i3 IF ID OF EX i4 IF ID OF i5 IF ID OF EX WB i6 IF ID OF EX WB
Fig. 7.11 Prin calcule statistice s-a determinat că întâlnirea unor instrucţiuni de salt
poate reduce viteza de execuţie a unui program cu până la 72% din viteza ma-ximă. Pentru a se reduce efectul salturilor asupra performanţelor unui procesor, au fost propuse diferite tehnici. Cele mai cunoscute tehnici sunt predicţia salturi-lor, întârzierea salturilor şi preîncărcarea multiplă. Aceste tehnici sunt prezentate în continuare.
7.5.2. Predicţia salturilor In cazul acestei metode se realizează o predicţie a rezultatului unei decizii
legate de execuţia saltului. Pe baza acestei predicţii, se alege pentru execuţie calea secvenţială sau calea destinaţie. Deşi prin alegerea căii respective se re-duce adesea penalizarea datorită saltului, penalizarea poate creşte în cazul unei predicţii eronate.
Există două tipuri de predicţii: predicţii statice şi predicţii dinamice. - In cazul unei predicţii statice, se decide înaintea execuţiei programului
preîncărcarea instrucţiunilor dintr-una din cele două căi. De exemplu, o tehnică simplă este aceea de a presupune că saltul trebuie executat întotdeauna. Prin această tehnică, la întâlnirea unei instrucţiuni de salt se încarcă în contorul de program adresa de destinaţie a saltului. O altă tehnică este de a alege o anumi-tă cale (secvenţială sau destinaţie) pentru anumite tipuri de salturi şi cealaltă ca-le pentru celelalte tipurilor. In cazul în care alegerea este eronată, sistemul pipeline este golit şi se încarcă instrucţiunile corespunzătoare căii corecte.
- In cazul predicţiei dinamice, în timpul execuţiei programului, procesorul ia o decizie bazată pe informaţiile despre salturile executate anterior. Metoda cea mai simplă este predicţia dinamică utilizând un bit de control p, asignat fiecărei instrucţiuni de salt. Dacă la prima execuţie se realizează saltul, p va avea valoa-rea 1. In caz contrar p=0. La următoarea întâlnire a acestei instrucţiuni se ur-mează calea anterioară. Dacă predicţia a fost eronată se schimbă valoarea bitu-lui de control p astfel încât, la următoarea execuţie, se va urma cealaltă cale.
O metodă mai eficientă constă în a se asocia un contor C de n biţi fiecărei instrucţiuni de salt. Această metodă este numită metoda de predicţie bazată pe
C
un contor (counter based branch prediction). Această metodă funcţionează în felul următor: după ce instrucţiunea de salt a fost executată prima dată, contorul C ia o valoare de prag T dacă a fost executat saltul sau valoarea T-1 dacă saltul nu a fost executat.
In continuare, de fiecare dată când instrucţiunea de salt trebuie executată, dacă TC ≥ , este selectată calea destinaţie. Dacă predicţia a fost corectă, conto-rul este incrementat; dacă predicţia a fost incorectă, contorul este decrementat.
In cazul în care TC ≤ , se alege calea secvenţială. Dacă predicţia a fost corectă, contorul este decrementat; dacă predicţia a fost incorectă contorul este incrementat.
Dacă C ajunge !a valoarea maximă 12 −n , contorul nu mai este incremen-tat, chiar dacă a fost selectată calea destinaţie şi predicţia a fost corectă. In mod similar, contorul nu este decrementat la o valoare mai mică de 0.
In practică, pentru n şi T se alege adesea valoarea 2 (10 în binar). Studiile au arătat că metodele de predicţie cu 2 biţi sunt aproape la fel de eficiente ca şi metodele care utilizează un număr mai mare de biţi. Figura 7.12 prezintă stările posibile în cazul metodei de predicţie cu 2 biţi.
Fig. 7.12 Este convenabil să se memoreze statisticile salturilor într-o tabelă numită
tabelă de istorie a salturilor (branch history table), împreună cu adresa instrucţi-unii de salt şi adresa destinaţiei saltului. Pentru accesul rapid, majoritatea pro-cesoarelor plasează tabela de istorie a salturilor într-o memorie cache de di-mensiuni reduse, numită buffer al destinaţiei salturilor (BTB - Branch Target Buffer). De obicei, fiecare tabelă a acestei memorii cache păstrează adresa unei instrucţiuni de salt, adresa destinaţiei saltului şi statisticile de predicţie.
Metodele de predicţie statice necesită de obicei mai puţine circuite, dar pot determina creşterea complexităţii compilatorului. Spre deosebire de acestea, metodele de predicţie dinamice determină creşterea complexităţii circuitelor, dar necesită operaţii mai simple în timpul compilării. In general, prin utilizarea pre-
Predicţie corectă
Predicţie eronată
Predicţie cale destinaţie
10 Predicţie
cale destinaţie 11
Predicţie corectă
Predicţie eronată
Predicţie corectă
Predicţie corectă
Predicţie eronată
Predicţie cale secvenţială
00
Predicţie cale secvenţială
01
Predicţie corectă
dicţiei dinamice se pot obţine rezultate mai bune. Pentru a determina efectul predicţiei salturilor asupra performanţelor, este
necesară reevaluarea numărului mediu al ciclurilor de ceas pentru execuţia unei instrucţiuni. Există două cazuri posibile: calea anticipată este corectă sau inco-rectă.
Considerăm secvenţa de instrucţiuni din tabelul 6.11. Să presupunem că trebuie urmată calea destinaţie. Sunt posibile următoarele două situaţii:
- dacă calea destinaţie a fost estimată corect (figura 7.13a) penalizarea este d;
- dacă calea destinaţie a fost estimată greşit (figura 7.13b) penalizarea es-te c.
Dacă trebuie aleasă calea secvenţială există, de asemenea, două posibili-tăţi:
- dacă calea secvenţială a fost aleasă corect (figura 1.14) penalizarea este 0;
- dacă calea secvenţială a fost estimată greşit (figura 7.11) penalizarea es-te c. Observaţie: adresa căii estimate este obţinută în momentul decodificării instruc-ţiunii de salt; aceasta este confirmată în momentul execuţiei instrucţiunii de salt.
i1 IF ID OF EX WB i2 IF ID OF EX WB i3 IF i4 i5 IF ID OF EX WB i6 IF ID OF EX WB
Fig. 7.13a
d
destinaţie - incorect
Cicluri →
1 2 3 4 5 6 7 8 9 10 11
i1 IF ID OF EX WB i2 IF ID OF EX WB i3 IF IF ID OF EX WB i4 IF ID OF EX WB i5 IF ID IF ID OF EX i6 IF IF ID OF
Fig. 7.13b sursă - corect
Cicluri → 1 2 3 4 5 6 7 8 9 10 11 i1 IF ID OF EX WB i2 IF ID OF EX WB i3 IF ID OF EX WB i4 IF ID OF EX WB i5 IF ID OF EX WB i6 IF ID OF EX WB
Fig. 7.14 In acest caz în care se utilizează predicţia salturilor sistemul pipeline func-
ţionează la 78% din viteza sa maximă. 7.5.3. Întârzierea salturilor Întârzierea salturilor (delayed branching) elimină sau reduce în mod sem-
nificativ efectul penalizării datorită salturilor. In cazul acestei metode se încarcă şi se execută un anumit număr de instrucţiuni după instrucţiunea de salt, indife-rent de calea care va fi selectată pentru salt. De exemplu, un procesor cu o în-târziere a salturilor egală cu k execută următoarele k instrucţiuni secvenţiale iar apoi, fie continuă pe aceeaşi cale, fie începe execuţia instrucţiunilor de la adre-sa destinaţiei saltului. De câte ori este posibil, compilatorul încearcă să plaseze după instrucţiunea de salt k instrucţiuni care sunt independente de instrucţiunea de salt. Dacă nu există suficiente instrucţiuni de acest tip, compilatorul va insera instrucţiuni NOP. Ca un exemplu, considerăm următoarea secvenţă:
c
1i : LOAD R1, A 2i : LOAD R2, B 3i : BRZ R2, 7i ; salt la 7i dacă R2 = 0 4i : LOAD R3, C 5i : ADD R4, R2, R3 ; R4 = B + C 6i : MUL R5, R1, R2 ; R5 = A * B 7i : ADD R4, R1, R2 ; R4 = A + B
Presupunând k=2, compilatorul modifică această secvenţă prin mutarea
instrucţiunii 1i şi inserarea unei instrucţiuni NOP după instrucţiunea de salt 3i . Secvenţa modificată este următoarea:
După cum se observă din secvenţa modificată, instrucţiunea 1i este execu-
tată indiferent de rezultatul evaluării saltului. Pentru a înţelege efectul de redu-cere a penalizării prin utilizarea întârzierii salturilor ne vom referi la figura 7.11. In cazul în care nu se utilizează metoda întârzierii salturilor, atunci când predic-ţia sugerează ca probabilă calea secvenţială, se începe execuţie instrucţiunilor care urmează după instrucţiunea de salt. Dacă, după execuţia instrucţiunii de salt de constată că predicţia a fost eronată, sistemul pipeline se goleşte pentru a începe execuţia instrucţiunilor de pe calea de destinaţie. In acest caz cele trei perioade de ceas în care se încerca execuţia instrucţiunilor de pe calea secven-ţială au fost irosite. Dacă pe cale secvenţială sunt introduse instrucţiuni care sunt independente de instrucţiunea de salt, în cazul considerat, se continuă cu execuţia acestora şi abia după finalizarea acelor instrucţiuni, se trece la execu-ţia instrucţiunilor de pe calea destinaţie. In acest mod nu a fost pierdut nici un ciclu de ceas.
7.5.4. Preîncărcarea multiplă (multiple prefetching) In acest caz, procesorul extrage instrucţiuni din ambele căi posibile. După
ce s-a luat decizia despre execuţia saltului, calea nedorită este abandonată. Prin extragerea prealabilă a instrucţiunilor din ambele căi posibile, se evită pe-nalizarea datorită extragerii instrucţiunilor în cazul unei predicţii incorecte.
Pentru extragerea instrucţiunilor din ambele căi, se utilizează două buffere.
La execuţia normală, primul buffer este încărcat cu instrucţiuni aflate pe calea secvenţială iar cel de al doilea buffer cu instrucţiuni de pe calea destinaţie. Dacă saltul este executat, conţinutul primului buffer este invalidat şi este utilizat conţi-nutul celui de-al doilea buffer.
Această metodă de extragere dublă asigură un flux constant de instrucţiuni şi date pentru sistemul pipeline şi reduce întârzierile datorate golirii şi reîncărcă-rii sistemului pipeline.
In concluzie, fiecare din tehnicile prezentate anterior reduce diminuarea ratei de transfer a sistemului pipeline. Alegerea uneia din aceste tehnici pentru un sistem particular depinde de factori ca cerinţele ratei de transfer şi restricţiile de cost. In practică, datorită acestor factori, într-un procesor se implementează de obicei o combinaţie a acestor tehnici.
7.6. Îmbunătăţirea ratei de transfer a sistemelor pipeline Rata de transfer a unui sistem pipeline este definită ca fiind numărul tasku-
rilor de intrare pe care le poate prelucra acesta în unitatea de timp. O posibilitate de creştere a ratei de transfer a unui sistem pipeline de in-
strucţiuni este de a se utiliza paralelismul la nivelul instrucţiunilor (instruction-level parallelism - ILP). Acest procedeu constă dintr-un set de tehnici ale proce-sorului şi compilatorului care îmbunătăţesc performanţa prin executarea opera-ţiilor independente în paralel. Sistemele bazate pe paralelismul la nivelul instruc-ţiunilor preiau un program convenţional într-un limbaj de nivel înalt scris pentru procesoare secvenţiale şi utilizează tehnici statice (ale compilatorului) şi dinami-ce (implementate în cursul execuţiei) pentru a exploata în mod automat parale-lismul implicit al programului.
Metodele obişnuite pentru a exploata paralelismul la nivelul instrucţiunilor sunt prelucrarea superscalară, prelucrarea superpipeline şi cuvintele foarte lungi de instrucţiuni (Very Long lnstruction Word — VLIW). O metodă mai nouă este numită EPIC (Explicitly Parallel lnstruction Computing). Fiecare din aceste me-tode încearcă iniţierea mai multor instrucţiuni în acelaşi ciclu de ceas.
7.6.1. Prelucrarea superscalară Metoda de prelucrare superscalară constă în execuţia concurentă a mai
multor operaţii în unităţi separate de prelucrare. Această metodă realizează multiplicarea execuţiei instrucţiunilor într-un ciclu de ceas prin lansarea mai mul-tor instrucţiuni către diferite unităţi funcţionale. Un procesor superscalar conţine unităţi multiple de execuţie, fiecare din acestea fiind de obicei de tip pipeline, Un astfel de procesor este constituit dintr-un set de sisteme pipeline de instrucţiuni, fiecare dintre acestea lucrând independent. Unitatea de control a unui procesor superscalar este proiectată pentru a încărca şi a decodifica mai multe instrucţi-uni în mod concurent. Aceasta poate lansa sau expedia până la k instrucţiuni simultan către diferitele unităţi de execuţie, unde k poate avea o valoare egală cu şase sau, utilizând tehnologia actuală, mai mare. Necesitatea de a prelucra mai multe instrucţiuni simultan fără conflicte complică mult proiectarea unităţii de
control. Figura 7.15 prezintă într-o formă ideală diferenţele din punct de vedere al posibilităţilor de prelucrare ale instrucţiunilor între trei organizări UCP: un pro-cesor secvenţial (care nu este de tip pipeline), un procesor de tip pipeline şi un procesor superscalar, fiecare dintre acestea executând acelaşi şir de instrucţiuni
,...,, 321 III . Presupunând că fiecare instrucţiune necesită un număr total de cinci cicluri, putem observa că un singur sistem pipeline k=1 cu cinci etaje oferă o creştere a vitezei de 5 ori, în timp ce un sistem superscalar cu două instrucţiuni lansate simultan (k=2) oferă o creştere potenţială a vitezei de 10 ori. La începu-tul ciclului 15, procesorul secvenţial a terminat numai două instrucţiuni, în timp ce procesorul de tip pipeline şi cel superscalar au terminat 10, respectiv 20 de instrucţiuni. Mai mult, procesorul superscalar a început prelucrarea instrucţiuni-lor 21I la 30I .
După cum se ilustrează în figura 7.15, prezenţa a k unităţi de execuţie de tip pipeline cu m etaje permite unui UCP superscalar să atingă factori de creşte-re a vitezei care se apropie de k x m, comparativ cu un UCP care nu dispune de paralelism la nivelul instrucţiunilor. Ocuparea a k sisteme pipeline necesită ca UCP să încarce cel puţin k instrucţiuni în fiecare ciclu de ceas. Volumul ridicat al traficului de instrucţiuni de la memoria de program la UCP necesită ca sistemul să dispună de o memorie cache rapidă şi de dimensiuni mari, adesea sub forma unei memorii cache de instrucţiuni (I-cache) pentru păstrarea programului, com-pletată cu o memorie cache de date (D-cache) pentru păstrarea operanzilor. Pentru extragerea instrucţiunilor, există de obicei un buffer sau o coadă de in-strucţiuni în cadrul UCP, care păstrează instrucţiunile preîncărcate şi parţial de-codificate. Unitatea de control expediază instrucţiunile din bufferul de instrucţiuni către diferitele unităţi de execuţie.
Unitatea de control a unui procesor superscalar este responsabilă pentru determinarea momentului în care poate fi executată fiecare instrucţiune şi pen-tru asigurarea accesului la resursele pe care instrucţiunea le necesită, cum sunt operanzi din memorie, unităţi de execuţie şi registre UCP. Pentru aceasta, unita-tea de control trebuie să ţină cont de următorii factori:
• Tipul instrucţiunii: De exemplu, o instrucţiune de adunare în virgulă mobi-lă trebuie expediată la o unitate de execuţie în virgulă mobilă şi nu la o unitate în virgulă fixă.
• Disponibilitatea unităţii de execuţie: O instrucţiune poate fi expediată la o unitate de execuţie de tip pipeline numai dacă nu vor rezulta coliziuni.
Fig. 7.15 • Dependenţe de date: Pentru a evita conflictele la utilizarea registrelor,
trebuie satisfăcute restricţii privind dependenţele de date între operanzii instruc-ţiunilor active.
• Dependenţe de control: Pentru a menţine performanţe ridicate, sunt ne-cesare tehnici pentru a reduce impactul instrucţiunilor de salt asupra eficienţei sistemelor pipeline.
• Ordinea instrucţiunilor: Instrucţiunile trebuie să genereze rezultatele în ordinea specificată de programul care se execută. Rezultatele pot fi însă calcu-late intern într-o ordine diferită pentru a îmbunătăţi performanţele UCP.
Pentru păstrarea ordinii de execuţie a instrucţiunilor între care există de-pendenţe şi pentru a asigura obţinerea unor rezultate valide, un procesor super-
scalar trebuie să utilizeze un mecanism de control, care poate fi bazat pe meto-da tabelei de rezultate. In practică, majoritatea procesoarelor se bazează pe tehnica superscalară şi utilizează metoda tabelei de rezultate.
Pentru a rezolva problema salturilor întârziate se utilizează diferite metode arhitecturale, cum sunt memorii cache (sau buffere) pentru destinaţia saltului şi execuţia speculativă. Execuţia speculativă implică predicţia direcţiei unui salt dependent de date şi execuţia instrucţiunilor corespunzătoare. Cu seturi multiple de registre virtuale şi utilizând metoda tabelei de rezultate, un procesor poate urmări ambele căi ale unui salt şi poate alege şirul corect de instrucţiuni.
7.6.2. Prelucrarea superpipeline Metoda superpipeline asigură performanţe ridicate prin suprapunerea exe-
cuţiei unui număr mai mare de instrucţiuni într-un singur sistem pipeline de in-strucţiuni. Un procesor superpipeline conţine de obicei un sistem pipeline de in-strucţiuni cu un număr mai mare de etaje decât un sistem pipeline obişnuit. Cu alte cuvinte, procesul de execuţie al unei instrucţiuni este divizat în etape cu complexitate mai redusă. Prin creşterea numărului de etaje ale sistemului pipeline de instrucţiuni este posibilă creşterea frecvenţei ceasului, deoarece această frecvenţă depinde de întârzierea introdusă de etajul cel mai lent.
Metoda superpipeline are anumite avantaje. O singură unitate funcţională necesită un spaţiu mai redus şi circuite mai simple comparativ cu structurile ba-zate pe prelucrarea superscalară. Spaţiul suplimentar care rămâne disponibil permite implementarea unor circuite speciale pentru obţinerea unor viteze mai ridicate, memorii cache de dimensiuni mai mari şi căi de date cu un număr mai mare de linii.
Majoritatea procesoarelor actuale utilizează metoda superpipeline. De exemplu, sistemul pipeline al familiei de procesoare cu arhitectura Intel actuală constă din 20 etaje, faţă de 5 la procesorul Intel Pentium şi 6 la procesorul Intel Pentium cu extensiile MMX. Aceasta permite familiei de procesoare cu arhitec-tura Intel actuală să ajungă la o frecvenţă cu aproximativ 50% mai ridicată faţă de procesorul Pentium cu aceeaşi tehnologie de fabricaţie.
Să considerăm un procesor care divizează extragerea instrucţiunilor şi ac-cesul la memoria cache de date pentru a crea un sistem pipeline cu opt etaje. Operaţiile executate în fiecare etaj al sistemului pipeline permit un ciclu de ceas cu o frecvenţă dublă. Cele opt etaje ale sistemului pipeline sunt ilustrate în figu-ra 7.16.
Fig. 7.16. Faze corespunzătoare celor opt etaje ale sistemului pipeline sunt descrise
mai jos. 1. IF (Instruction Fetch, First Half): Sistemul de comandă selectează o
adresă de instrucţiune şi începe extragerea acestei instrucţiuni din memoria cache de instrucţiuni. In aceeaşi fază, bufferul de translatare (TLB) pentru in-strucţiuni, începe translatarea adresei virtuale într-o adresă fizică.
2. IS (Instruction Fetch, Second Half): Extragerea instrucţiunii din memoria cache de instrucţiuni şi translatarea adresei virtuale într-o adresă fizică sunt terminate.
3. RF (Register Fetch): Instrucţiunea este decodificată şi marcajul memori-ei cache de instrucţiuni este comparat cu numărul cadrului de pagină obţinut din bufferul de translatare pentru instrucţiuni. Operanzii necesari sunt încărcaţi din setul de registre.
4. EX (Instruction Execution): UAL execută operaţia aritmetică sau logică pentru instrucţiunile care operează cu registrele. Pentru instrucţiunile de încăr-care şi memorare, UAL calculează adresa virtuală a datelor. Pentru instrucţiuni-le de salt, UAL determină dacă condiţia de salt este adevărată şi calculează adresa virtuală a destinaţiei saltului.
5. DF (Data Fetch, First Half): Pentru instrucţiunile de încărcare şi memo-rare, începe extragerea datelor din memoria cache de date şi translatarea adre-sei virtuale într-o adresă fizică. Pentru instrucţiunile de salt, începe translata-rea adresei şi actualizarea TLB. Pentru instrucţiunile care operează cu re-gistrele, nu se execută nici o operaţie în timpul fazelor DF, DS şi TC.
6. DS (Data Fetch, Second Half): Pentru instrucţiunile de încărcare şi me-morare, extragerea datelor din memoria cache de date şi translatarea adresei virtuale într-o adresă fizică sunt terminate. Pentru instrucţiunile de salt, transla-tarea adresei şi actualizarea TLB sunt terminate.
7. TC (Tag Check): Pentru instrucţiunile de încărcare şi memorare, memo-ria cache execută testarea marcajului. Adresa fizică din TLB este comparată cu marcajul memoriei cache pentru a determina dacă există un succes sau un eşec la accesul memoriei cache.
8. WB (Write Back): Pentru instrucţiunile care operează cu registrele, re-zultatul instrucţiunii este scris în setul de registre. Pentru instrucţiunile de salt, nu se execută nici o operaţie în timpul acestei faze.
7.7. Controlul sistemelor pipeline După cum se ştie există două tipuri de sisteme pipeline: statice şi dinamice.
Un sistem pipeline static poate executa o singură operaţie la un moment dat, în timp ce un sistem pipeline dinamic poate executa mai multe operaţii. Controlul secvenţierii operaţiilor prezentate unui sistem pipeline pentru execuţie este foarte important pentru creşterea eficienţei acestuia. Astfel dacă se iniţiază două operaţii care necesită acelaşi etaj pipeline în acelaşi timp, apare o coliziune, care nu este de dorit. Pentru evitarea unor astfel de situaţii este necesară planificarea sistemelor pipeline.
In continuare este prezentată o metodă de control pentru planificarea unui sistem pipeline.
7.7.1. Planificarea Pentru a înţelege această metodă mai întâi trebuie definite conceptele de
tabelă de rezervare şi latenţă. O tabelă de rezervare indică momentele în care etajele unui sistem pipeline
sunt utilizate pentru o anumită funcţie. Fiecărui etaj i se alocă o linie în tabela de rezervare. Fiecare linie este împărţită în coloane, câte una pentru fiecare ciclu de ceas. Numărul de coloane indică numărul total al unităţilor de timp necesare pentru execuţia unei anumite funcţii. Pentru a indica faptul că un anumit etaj E este utilizat la momentul de timp ti este plasat un semn „x” la intersecţia liniei cu coloana momentului de timp respectiv din tabelă.
a b Fig. 7.16
Figura 7.16 reprezintă o tabelă de rezervare pentru un sistem pipeline static
cu trei etaje. Momentele de timp 0t , 1t , 2t , 3t şi 4t indică cinci cicluri de ceas consecutive. In exemplul considerat poziţia semnelor „x” indică faptul că, pentru a produce rezultatul scontat datele de intrare trebuie să treacă succesiv prin etajele 1, 2, 2, 3 şi 1. Tabela de rezervare este utilizată pentru a determina diferenţele de timp necesare între aplicarea unor date succesive la intrare astfel încât să nu
6
5
4 3
2
1
X
Moment t0 t1 t2 t3 t4 Ieşire
Intrare
Etaj 1
Etaj 2
Etaj 3
Etaj 1 Etaj 2 Etaj 3
X X
X
X
apară coliziuni. Latenţa este dată de numărul unităţilor de timp (ciclurilor de ceas) care
separă aplicarea la intrare a două seturi de date. Va apare o coliziune dacă două seturi de date de intrare sunt aplicate cu o latenţă egală cu distanţa între două semne „x” într-o linie a tabelei de rezervare. De exemplu, în tabela din figura 7.16 există două semne „x” consecutive în a doua linie. Astfel, dacă al doilea set de date este aplicat la intrare cu o latenţă de o unitate de timp după primul, va apare o coliziune în etajul 2.
7.7.2. Planificarea sistemelor pipeline statice Planificarea sistemelor pipeline statice începe prin crearea unui set de liste a
latenţelor interzise pe baza tabelelor de rezervare ale funcţiilor. Se obţin apoi vectorii de coliziune şi se întocmeşte diagrama stărilor.
Lista latenţelor interzise. Fiecare tabelă de rezervare cu două sau mai multe semne „x” într-o anumită linie are una sau mai multe latenţe interzise, care, în cazul în care nu sunt evitate, vor determina coliziunea datelor. Lista latenţelor interzise este un şir de numere întregi care corespund acestor latenţe. Valoarea zero este considerată întotdeauna ca o latenţă interzisă, deoarece nu este posibilă iniţierea a două taskuri în acelaşi moment. Un element al acestei liste se poate determina calculând distanţa între două semne „x” dintr-o anumită linie. De exemplu, lista latenţelor interzise a tabelei de rezervare din figura 7.16 este (4, 1, 0).
Vectori de coliziune. Un vector de coliziune este un şir de cifre binare de lungime 1+N , unde N este latenţa interzisă maximă din lista latenţelor interzise. Vectorul de coliziune iniţial C este creat din lista latenţelor interzise în felul următor: fiecare element ci din C , pentru Ni ,...,0= , este 1 dacă i este un element al listei latenţelor interzise; în caz contrar ci este zero. Valorile zero din vectorul de coliziune indică latenţe permise sau, altfel spus, momente în care aplicarea datelor este permisă.
In cazul listei precedente a latenţelor interzise (4, 1, 0), unde pentru i=0 există o latenţă interzisă; i=1 există o latenţă interzisă; i=2 latenţa este permisă; i=3 latenţa este permisă; i=4 există o latenţă interzisă,
se obţine următorul vector de coliziune: 4 3 2 1 0
01234 c c c c cC = 1) 1 0 0 1(= In acest vector de coliziune, elementele c2 şi c3 sunt egale cu 0 deoarece
latenţele 2 şi 3 sunt permise, în timp ce elementele c0, c1 şi c4 sunt egale cu 1 deoarece latenţele 0, 1 şi 4 sunt interzise,.
Diagrama stărilor. Diagramele de stări se utilizează pentru a indica diferitele stări ale unui sistem pipeline pentru un interval de timp dat. Diagrama stărilor, permite evitarea coliziunilor printr-o planificare mai simplă a datelor de intrare.
Diagrama stărilor unui sistem pipeline începe întotdeauna cu vectorul de coliziune iniţial. Figura 7.17 reprezintă o diagramă de stări pentru sistemul pipeline din figura 7.16. Vectorul de coliziune 10011 reprezintă starea iniţială. Deoarece latenţele permise sunt 2 şi 3, un nou set de date poate fi aplicat la intrare după două sau trei cicluri de ceas ( 2=i sau 3=i ). Pentru aceste latenţe, prin deplasarea la dreapta a vectorului de coliziune curent cu i poziţii, se obţine un vector de tranziţie. Pe poziţiile din stânga rămase libere în urma deplasării se introduc zerouri. In acest fel pentru i=2 din vectorul de coliziune iniţial C0=(10011) se obţine vectorul de tranziţie T0=(00100).
Fig. 7.17 Pentru a se genera un nou vector de coliziune şi o nouă stare, se efectuează
operaţia SAU logic între vectorul de tranziţie T0 şi vectorul de coliziune C0. După aceasta operaţie se obţine un nou vector de coliziune C1=(10111). Acestei tranziţii îi corespunde în diagrama stărilor din figura 7.17 arcul a1.
Pentru i=3, prin deplasarea la dreapta cu trei poziţii a vectorului de coliziune C1, se obţine vectorul de tranziţie T1=(00010). Aplicând operatorul SAU vectorului iniţial C0 şi T1 se obţine vectorul de coliziune iniţial C0. Acestei tranziţii îi corespunde arcul a2.
Pentru i 5 vectorul de tranziţie este T2=(00000) şi, după efectuarea operaţiei SAU cu vectorul C0, se obţine tot vectorul C0 (arcul a3). Latenţa 5≥i corespunde situaţiei în care noul set de date de intrare se aplică după 5 sau mai multe cicluri de ceas. După o perioadă de timp mai mare sau egala cu 5 cicluri de ceas, sistemul pipeline s-a golit şi este evident că aplicarea unui nou set de date găseşte sistemul în faza iniţială.
Procesul de generare a noilor vectori de coliziune continuă până când nu se
C0
C1
a3
I = 2 a1
10011
10111
C1=C0 T0 C0=C0 T1 I = 3 a2
C0=C0 T2 i
mai pot genera noi vectori. Latenţa medie. Latenţa medie se determină pentru un anumit ciclu din
diagrama stărilor. Un ciclu într-o diagramă a stărilor este o secvenţă formată de vectori de coliziune şi arce, 0110 ,,...,,, CaCaC n , în care fiecare arc ia conectează vectorul de coliziune 1−iC cu iC şi toţi vectorii de coliziune sunt distincţi cu excepţia primului şi ultimului. In diagrama din figura 7.17 există ciclurile 02110 ,,,, CaCaC şi C0a3C0.
Pentru simplitate, un ciclu poate fi reprezentat printr-o secvenţă de latenţe ale arcelor sale. Astfel ciclul 02110 ,,,, CaCaC , poate fi reprezentat ca ciclul
)3,2(=C , unde 2 şi 3 sunt latenţele arcelor 1a , respectiv 2a . Lungimea unui ciclu este dată de numărul arcelor din care este constituit. Astfel 02110 ,,,, CaCaC are lungimea 2, iar ciclul 030 ,, CaC are lungimea 1.
Latenţa medie pentru un ciclu se determină prin adunarea latenţelor arcelor ciclului şi împărţirea sumei cu numărul total de arce din ciclu. De exemplu, în figura 7.17 ciclul )3,2(=C are latenţa medie:
5,22/)32( =+ Latenţa medie minimă. Un sistem pipeline poate avea mai multe latenţe
medii asociate cu diferite cicluri. Latenţa medie minimă este latenţa cu valoarea cea mai mică din acestea. De exemplu, pentru diagrama din figura 7.17, latenţele medii sunt următoarele:
(2 + 3)/2 = 2.5 din ciclul 02110 ,,,, CaCaC 5/1=5 din ciclul 030 ,, CaC Astfel, latenţa medie minimă (LMM) este 2,5. Deşi ciclul cu latenţa medie
minimă maximizează rata de transfer a sistemului pipeline, uneori, pentru a se reduce complexitatea implementării circuitului de control, se poate alege un ciclu mai puţin eficient. De exemplu, pentru ciclul C = (2, 3), cu valoarea LMM egală cu 2.5, este necesar un circuit de comandă care să contorizeze două unităţi de timp, apoi trei unităţi de timp, din nou două unităţi de timp şi aşa mai departe. Dacă însă se acceptă să se aplice un set de date de intrare la fiecare trei unităţi de timp, complexitatea circuitului de comandă va fi mai redusă. Astfel, latenţa minimă pentru acest sistem pipeline este 3.
7.7.3. Planificarea sistemelor pipeline dinamice La planificarea unui sistem pipeline static, trebuie evitate doar coliziunile
între diferitele date de intrare pentru o anumită unitate funcţională. In cazul unui sistem pipeline dinamic, este posibil ca diferitele seturi de date de intrare necesitând unităţi funcţionale diferite să fie prezente în sistemul pipeline în acelaşi timp. Pentru acest motiv, trebuie să se ia în considerare şi coliziunile între aceste date. Ca şi în cazul sistemelor pipeline statice, planificarea sistemelor pipeline dinamice începe cu determinarea unui set de liste a latenţelor interzise pe baza tabelelor de rezervare ale funcţiilor. In continuare se obţin vectorii de coliziune, iar în final se reprezintă diagrama stărilor.
Fig. 7.14 Listele latenţelor interzise. In cazul unui sistem pipeline dinamic, numărul de
liste ale latenţelor interzise este egal cu pătratul numărului seturilor de date care partajează sistemul pipeline. In figura 7.18, numărul seturilor de date este 2, notate cu A şi B ; astfel, numărul de liste ale latenţelor interzise este 4, acestea fiind notate cu AA , AB , BA şi BB . Acestea sunt:
)0,3(=AA , )0,1,2,4(=AB , )0,1,2(=BA , )0,2,3(=BB Vectori de coliziune şi matrice de coliziune. Vectorii de coliziune se
determină în acelaşi mod ca şi pentru un sistem pipeline static; 0 indică o latenţă permisă, iar 1 indică o latenţă interzisă. Pentru exemplul precedent, vectorii de coliziune sunt următorii:
)01001(=AAC )00111(=BAC )10111(=ABC )01101(=BBC
Vectorii de coliziune pentru unitatea funcţională A formează matricea de coliziune AM :
=
AB
AAA C
CM
Vectorii de coliziune pentru unitatea funcţională B formează matricea de coliziune BM :
=
BB
BAB C
CM
Pentru vectorii de coliziune din exemplul precedent, matricele de coliziune sunt următoarele:
=
1011101001
AM
=
0110100111
BM
Diagrama stărilor. Diagrama stărilor pentru un sistem pipeline dinamic este construită în acelaşi mod ca şi pentru un sistem pipeline static. Diagrama rezultată
5
4
3
2
1
0
5
4
3
2
1
0 A
Moment t0 t1 t2 t3 t4
A A
A
Ieşire A
Intrare B
Moment t0 t1 t2 t3 t4
Ieşire B
Intrare A
Etaj 1
Etaj 2
Etaj 3
A
B B
B
B B
Etaj 1 Etaj 2 Etaj 3
Etaj 1 Etaj 2 Etaj 3
1
este mult mai complexă decât diagrama stărilor unui sistem pipeline static, datorită numărului mai mare de coliziuni potenţiale.
Ca un exemplu, considerăm diagrama stărilor din figura 7.19. Pentru început, ne referim la matricea de coliziune AM . Există două tipuri de coliziuni: A cu A (vectorul de sus) sau A cu B (vectorul de jos). Dacă se alege prima latenţă permisă pentru vectorul AAC (în acest caz, 1), întreaga matrice este deplasată la dreapta cu o poziţie, în poziţiile din stânga fiind introduse zerouri. Apoi se execută o operaţie SAU logic între noua matrice şi matricea de coliziune iniţială AM , deoarece latenţele interzise originale pentru unitatea funcţională A trebuie luate în considerare şi în continuare.
Fig. 7.19 Dacă se alege prima latenţă permisă pentru vectorul ABC din matricea AM
(în acest caz, 3), întreaga matrice este deplasată la dreapta cu trei poziţii, în poziţiile din stânga fiind introduse zerouri. Apoi se execută o operaţie SAU logic între noua matrice şi matricea de coliziune iniţială pentru unitatea funcţională B , deoarece coliziunile originale pentru unitatea funcţională B sunt încă posibile şi trebuie luate în considerare. Operaţia de deplasare şi operaţia SAU logic continuă până când se iau în considerare toate latenţele posibile şi diagrama stărilor va fi completă.
Cap. 8. Arhitecturi RISC 8.1. Introducere In general, arhitecturile calculatoarelor au evoluat progresiv spre o
complexitate mai ridicată ca, de exemplu, un număr mai mare de instrucţiuni, un număr mai mare de moduri de adresare, o putere de calcul mai ridicată a instrucţiunilor individuale, registre mai specializate. Calculatoarele care se încadrează în asemenea tendinţe sunt numite calculatoare cu set complex de instrucţiuni (CISC - Complex Instruction Set Computer).
S-a constatat la un moment dat că adăugarea unei instrucţiuni complexe la un set de instrucţiuni existent afectează eficienţa şi costul procesorului. Efectele unei asemenea instrucţiuni trebuie evaluate înainte ca aceasta să fie adăugată la setul de instrucţiuni. Unele din instrucţiunile puse la dispoziţie de procesoarele CISC sunt utilizate rareori de compilatoare. Conceptul de bază de a nu se adăuga
instrucţiuni utilizate rar la setul de instrucţiuni reprezintă un concept inovativ al arhitecturilor de calculatoare, numit calculator cu set redus de instrucţiuni (RISC - Reduced Instruction Set Computer). Filozofia de proiectare a arhitecturilor RISC este de a se adăuga la setul de instrucţiuni numai acele instrucţiuni care determină un câştig de performanţă.
Caracteristicile comune ale majorităţii acestor calculatoare sunt următoarele: - Un set de instrucţiuni limitat şi simplu; - Un număr mare de registre generale sau memorii cache aflate în aceeaşi
capsulă cu procesorul; - Un compilator care maximizează utilizarea registrelor şi minimizează astfel
accesurile la memoria principală; - Accentul pus pe optimizarea sistemului pipeline de instrucţiuni. 8.2. Cauze ale complexităţii arhitecturale crescute Există mai multe motive ale tendinţei spre o complexitate progresivă mai
ridicată a arhitecturilor de calculatoare. Acestea cuprind următoarele deziderate: - Facilitarea utilizării limbajelor de nivel înalt. Pe parcursul anilor, mediul de
programare a evoluat de la programarea în limbaj de asamblare la programarea în limbaje de nivel înalt, astfel încât proiectanţii au prevăzut instrucţiuni mai puternice pentru a facilita codificarea eficientă a programelor scrise în limbaje de nivel înalt. Aceste instrucţiuni au determinat nu numai creşterea dimensiunii setului de instrucţiuni ci şi creşterea complexităţii acestuia, datorită puterii de calcul relativ ridicate a instrucţiunilor.
- Migrarea funcţiilor de la implementarea prin software la implementarea prin hardware. O instrucţiune care este implementată prin hardware va fi mai eficientă decât una implementată prin software, realizată printr-o secvenţă de instrucţiuni mai simple, datorită numărului mare de accesuri la memorie şi a diferenţei dintre vitezele UCP şi ale memoriei. Pentru a creşte viteza de procesare a calculatoarelor, a avut loc un fenomen de migrare a funcţiilor de la implementarea prin software la cea prin firmware şi de la implementarea prin firmware la cea prin hardware. (Firmware reprezintă o secvenţă de microinstrucţiuni.) Această migrare a implementării funcţiilor din domeniul software în domeniul hardware creşte dimensiunea setului de instrucţiuni, rezultând o complexitate globală crescută a calculatoarelor.
- Compatibilitatea în sus. Compatibilitatea în sus este utilizată adesea de către producători ca o strategie de marketing cu scopul de a prezenta calculatoarele lor ca fiind mai performante decât alte modele existente. Ca rezultat al acestei strategii de marketing, uneori producătorii cresc numărul de instrucţiuni şi puterea de calcul a acestora, indiferent de utilizarea efectivă a acestui set complex de instrucţiuni. Compatibilitatea în sus este un mod de a îmbunătăţi un sistem prin adăugarea unor facilităţi noi şi, de obicei, mai complexe. Ca rezultat, noul set de instrucţiuni este un superset al celui vechi.
8.3. Avantajele arhitecturilor RISC Există totuşi unele criterii care reprezintă obiective universal acceptate de
către proiectanţii de calculatoare pentru toate sistemele: 1. Maximizarea vitezei de execuţie sau minimizarea timpului de execuţie. 2. Minimizarea costului de proiectare. O posibilitate de a îndeplini primul obiectiv constă în a îmbunătăţi tehnologia
componentelor, obţinând funcţionarea acestora la frecvenţe mai ridicate. Viteza mărită poate fi obţinută şi prin minimizarea numărului mediu al
ciclurilor de ceas pe instrucţiune şi/sau execuţia simultană a mai multor instrucţiuni. Arhitecturile RISK au mers pe calea reducerii numărului de instrucţiuni şi a formatelor acestora, a simplificării modurilor de adresare, obţinând în acest fel un circuit de comandă simplu şi de dimensiuni mai reduse. Aceste opţiuni au avut ca rezultat reducerea suprafeţei ocupate de circuitul de comandă de la 40-60% din suprafaţa microprocesorului în cazul arhitecturilor CISC la numai 10% din aceasta în cazul arhitecturilor RISC. Suprafaţa rămasă în cazul unei arhitecturi RISC poate fi utilizată pentru alte componente, cum sunt memorii cache în aceeaşi capsulă şi seturi mai mari de registre, prin care performanţele procesorului pot fi îmbunătăţite.
In continuare sunt prezentate avantajele arhitecturilor RISC. 1. Un prim avantaj al arhitecturilor RISC constă în ridicarea vitezei de calcul
a sistemului prin: - Utilizarea sistemelor pipeline. Arhitecturile RISC sunt mai potrivite pentru
utilizarea sistemelor pipeline de instrucţiuni, deoarece majoritatea instrucţiunilor au o dimensiune uniformă şi o durată egală a execuţiei. Aceste caracteristici reduc perioadele de inactivitate în cadrul sistemului pipeline.
- Implementarea unităţii de comandă prin hardware. Un sistem cu o unitate de control cablată va fi, în general, mai rapid decât unul microprogramat.
- Numărul mare de registre şi memoriile cache în cadrul capsulei vor reduce numărul accesurilor la memorie deoarece datele mai frecvent utilizate pot fi păstrate în registre. Registrele pot păstra, de asemenea, parametrii care trebuie transmişi procedurilor apelate. Spaţiul eliberat, prin reducerea dimensiunilor circuitului de comandă, poate fi utilizat şi pentru introducerea memoriei cache în interiorul capsulei microprocesorului. Această memorie cache are, de obicei, o dimensiune mai redusă decât memoria cache de pe placă şi reprezintă primul nivel al memoriilor cache. Memoria cache de pe placă, care este apropiată de procesor, reprezintă al doilea nivel al memoriilor cache. In general, aceste două niveluri de memorii cache îmbunătăţesc performanţele comparativ cu cazul utilizării unui singur nivel de memorie cache. Uneori fiecare memorie cache este divizată în două memorii cache: o memorie cache de instrucţiuni şi o memorie cache de date. Procesoarele care au memorii cache separate pentru instrucţiuni şi date sunt numite arhitecturi Harvard, după calculatorul Harvard Mark I, care a utilizat pentru prima dată aceasta opţiune. Utilizarea a două memorii cache, una pentru instrucţiuni şi una pentru date, poate îmbunătăţi în mod considerabil timpul de acces şi, în consecinţă, îmbunătăţeşte performanţele unui procesor, în special al unuia care utilizează în mod extensiv tehnica pipeline, cum este un procesor RISC.
2. Un alt avantaj al arhitecturilor RISC constă în faptul că acestea necesită o
perioadă mai scurtă de proiectare. Timpul necesar pentru proiectarea unei noi arhitecturi depinde de complexitatea arhitecturii. Timpul de proiectare este mai lung pentru arhitecturile complexe (CISC). In cazul unei arhitecturi RISC, timpul necesar pentru testarea şi depanarea circuitelor rezultate este mai redus, deoarece nu se utilizează microprogramarea şi dimensiunea unităţii de control este redusă. In cazul unei arhitecturi mai puţin complexe, posibilitatea erorilor de proiectare este mai redusă. Deci, arhitecturile RISC au avantajul unor costuri de proiectare mai reduse şi al unei fiabilităţi de proiectare mai ridicate.
8.4. Caracteristici ale arhitecturilor RISC In general, o arhitectură RISC are următoarele caracteristici: 1. Majoritatea instrucţiunilor accesează operanzii din registre, cu excepţia
unui număr redus dintre ele, cum sunt instrucţiunile LOAD şi STORE, care acce-sează memoria. Cu alte cuvinte, o arhitectură RISC este un calculator de tip load/store.
2. Execuţia majorităţii instrucţiunilor necesită un singur ciclu de ceas, cu excepţia unui număr redus dintre ele, cum sunt instrucţiunile LOAD şi STORE. Totuşi, în prezenţa memoriilor cache aflate în aceeaşi capsulă, chiar şi instrucţi-unile LOAD şi STORE pot fi executate, în medie, într-un ciclu.
3. Unitatea de control este cablată. Deci, arhitecturile RISC nu sunt micro-programate. Codul generat de compilator este executat direct prin hardware şi nu este interpretat prin microprogramare.
4. Există relativ puţine instrucţiuni (adesea, mai puţin de 150) şi foarte pu-ţine moduri de adresare (adesea mai puţin de 4).
5. Există un număr redus de formate ale instrucţiunilor (adesea mai mic decât 4).
6. UCP are un număr mare de registre. Un grup de cercetători de la Uni-versitatea California din Berkeley, a studiat caracteristicile mai multor programe tipice Pascal şi C şi a descoperit că, dintre tipurile de instrucţiuni ale limbajelor de nivel înalt, apelurile de proceduri şi revenirile din acestea consumă cel mai mult timp. Un calculator CISC cu un set redus de registre necesită un timp ridicat pentru gestionarea apelurile de proceduri şi revenirile din acestea, din cauza ne-cesităţii de a salva registrele la apelarea procedurii şi de a le reface la revenire, ca şi din cauza necesităţii de a transmite parametri şi rezultate la şi de la proce-dura apelată. Pentru acest motiv, unul din principiile de proiectare ale arhitecturilor RISC este de a pune la dispoziţie un mijloc eficient de gestiune a mecanismului de apel al procedurilor şi de revenire din acestea. Această pro-blemă poate fi rezolvată prin utilizarea unui număr mare de registre şi a concep-tului de ferestre suprapuse.
Pentru explicarea acestui concept considerăm un calculator RISC cu 100 de registre. Registre de la 0 la 9 sunt utilizate ca registre globale pentru memora-rea variabilelor partajate de toate procedurile. Ori de câte ori este apelată o pro-cedură, acesteia i se alocă o fereastră formată din 20 de registre. Dintre acestea, 5 registre, numite registre de intrare, se alocă pentru păstrarea parametrilor, care sunt transmişi de procedura apelantă, 10 registre numite registre locale, pentru păstrarea variabilelor locale şi 5 registre numite registre de ieşire, pentru păstra-rea parametrilor care trebuie transmişi unei alte proceduri. Figura 8.1 ilustrează registrele alocate pentru trei proceduri X, Y şi Z. Procedurii X i s-au alocat regis-trele de la 10 la 29. Proceduri Y i s-au alocat registrele 25 până la 44 iar proce-durii Z, registrele de la 40 la 59. După cum se observă imediat ferestrele alocate fiecărei dintre cele trei proceduri sunt suprapuse. Astfel registrele 25 până la 29, care conţin parametrii de ieşire ai procedurii X, sunt utilizaţi de procedura Y ca parametrii de intrare şi registrele care conţin parametrii de ieşire ai procedurii Y se suprapun cu registrele care conţin parametrii de intrare ai procedurii Z. In acest mod transferul parametrilor de la procedura apelantă către procedura ape-
lată se realizează în mod firesc, fără a consuma timpul necesar pentru transmite-rea acestora ca în cazul arhitecturii CISC.
Fig. 8.1 O alternativă la un număr mare de registre este amplasarea unei memorii
cache în aceeaşi capsulă. Producătorii procesoarelor actuale au amplasat me-moria cache în aceeaşi capsulă cu procesorul pentru a asigura o viteză mai ridi-cată. Deoarece spaţiul din capsula procesorului este limitat, în această capsulă poate fi amplasată doar o memorie cache de dimensiuni reduse. Pe lângă această memorie cache, se poate amplasa o memorie cache de dimensiuni mari în afara capsulei. In general, se utilizează o ierarhie de memorii cache. Toate da-tele de la nivelul superior (memoria cache din cadrul capsulei) sunt prezente la nivelurile inferioare (memoriile cache din afara capsulei), astfel încât, după o lip-să în memoria cache, în locul efectuării unui acces la memoria principală, memo-ria cache din cadrul capsulei poate fi reîncărcată dintr-o memorie cache de la un nivel inferior.
7. Compilatorul are o complexitate ridicată. De exemplu, compilatorul tre-buie să se ocupe de salturile întârziate. Este posibil să se îmbunătăţească per-formanţele sistemului pipeline prin rearanjarea automată a instrucţiunilor din ca-drul unui program astfel încât instrucţiunile de salt să apară mai târziu decât se intenţiona iniţial.
8. Arhitecturile RISC facilitează operaţiile limbajelor de nivel înalt printr-o alegere judicioasă a instrucţiunilor şi prin utilizarea compilatoarelor care optimi-zează codul.
9. Arhitecturile RISC utilizează sistemele pipeline de instrucţiuni şi metode pentru rezolvarea problemei salturilor, cum sunt tehnicile de preîncărcare multi-plă şi de predicţie a salturilor.
8.5. Comparaţie între arhitecturile RISC şi CISC In general, timpul necesar unui procesor pentru a realiza execuţia unui
program poate fi influenţat de trei factori: 1. Numărul de instrucţiuni din program; 2. Numărul mediu de cicluri de ceas necesare pentru execuţia unei instruc-
ţiuni; 3. Durata ciclului de ceas. Arhitecturile CISC reduc numărul de instrucţiuni necesare într-un program
prin furnizarea unor instrucţiuni speciale care pot executa operaţii complexe. Spre deosebire de acestea, arhitecturile RISC implementează aceste instrucţiuni speciale prin instrucţiunile existente. In acest mod, reduc numărul mediu al ciclu-rilor de ceas necesare pentru execuţia unei instrucţiuni. Atât arhitecturile CISC cât şi cele RISC profită de îmbunătăţirile tehnologiei circuitelor integrate pentru a reduce durata ciclului de ceas.
Arhitecturile RISC sunt calculatoare de tip load/store; acestea pot obţine un nivel ridicat al concurenţei prin separarea execuţiei instrucţiunilor de încărcare şi memorare de alte instrucţiuni. Arhitecturile CISC nu pot obţine întotdeauna ace-laşi nivel al concurenţei din cauza setului lor de instrucţiuni de tip memo-rie/registru.
Majoritatea aspectelor negative ale arhitecturilor RISC sunt direct legate de aspectele lor pozitive. Din cauza instrucţiunilor simple, performanţele unei arhi-tecturi RISC depind de eficienţa compilatorului. De asemenea, datorită numărului mare de registre, alocarea registrelor este mai complexă, crescând astfel com-plexitatea compilatorului. Pentru acest motiv, principalul dezavantaj al unei arhi-tecturi RISC este necesitatea de a scrie un compilator eficient. In general, timpul de dezvoltare al sistemelor software pentru calculatoarele RISC este mai lung decât cel pentru calculatoarele CISC. Un alt dezavantaj este că anumite instruc-ţiuni CISC sunt echivalente cu două sau trei instrucţiuni RISC, ceea ce determină ca programele RISC să fie mai lungi. Deci, considerând avantajele ambelor arhi-tecturi CISC şi RISC, proiectarea unui procesor RISC poate fi îmbunătăţită prin utilizarea unora din principiile CISC care au fost dezvoltate şi îmbunătăţite de-a lungul anilor.
|Cap.9. Introducere în Multithreading, Superthreading şi
Hyperthreading 9.1. Procese şi fire de execuţie
Un sistem de operare execută la un moment dat o multitudine de programe. Utilizatorul poate să ruleze în acelaşi timp un editor de texte, un browser de In-ternet şi un player audio. Toate aceste programe lansate în execuţie poartă nu-mele de procese şi sunt executate într-o manieră secvenţială, numită
multitasking, concurând pentru folosirea resurselor comune ale sistemului de calcul precum procesor, memorie sau hard-disk.
Un proces este constituit din unul sau mai multe segmente de cod şi seg-mente de date mapate într-un spaţiu virtual de adresare. Fiecare proces deţine un număr de resurse alocate de către sistemul de operare, cum ar fi fişiere des-chise sau zone de memorie alocate dinamic. Resursele alocate procesului sunt eliberate la terminarea execuţiei procesului. Un aspect fundamental este faptul că două procese diferite au întotdeauna spaţii de adresă distincte. Astfel proce-sele sunt izolate între ele şi nu pot accesa, în mod direct, datele celorlalte proce-se.
Sistemul de operare şi sistemul hardware cooperează pentru a realiza me-canismul de multitasking, prin care controlul UCP este comutat pe rând între di-verse procese.
Un fir de execuţie este unitatea de execuţie a unui proces. Acesta poate fi văzut ca un program în execuţie fără spaţiu de adresă propriu. Firul de execuţie rulează în cadrul unui proces, partajând spaţiul de adresare al acestuia. Fiecărui fir de execuţie i se asociază o secvenţa de instrucţiuni, un set de registre CPU şi o stiva. Procesul nu executa instrucţiuni, acesta fiind spaţiu de adresare comun pentru unul sau mai multe fire de execuţie. Firele de execuţie sunt cele care exe-cută instrucţiunile.
Fiecare proces are cel puţin un fir de execuţie. Uneori însă apare nevoia să se lucreze în paralel asupra aceloraşi date şi atunci se pot crea mai multe fire de execuţie în cadrul aceluiaşi proces. De exemplu, în cazul editorului de texte de care s-a amintit la început, atât utilizatorul cât şi task-ul, care salvează o copie de siguranţă, lucrează asupra aceloraşi date, deci vom avea două fire de execuţie în cadrul aceleiaşi aplicaţii. Cu toate că firele de execuţie partajează spaţiul de adresă al unui proces, unele resurse sunt individuale, cum ar fi stiva, registrele şi contorul de program. Aceasta permite mai multor fire de execuţie din cadrul ace-luiaşi proces să urmeze căi diferite de instrucţiuni.
In general, un procesor execută la un moment dat un singur fir de execuţie (single-thread CPU).
In figura 9.1. se prezintă funcţionarea unei CPU cu un singur fir de execuţie In CPU au fost evidenţiate unitatea de alimentare cu instrucţiuni formată din
patru sisteme pipeline şi unitatea de execuţie formată din şapte sisteme pipeline funcţionând în paralel.
Dreptunghiurile colorate din RAM reprezintă instrucţiunile a patru procese di-ferite aflate în curs de execuţie. Presupunem că aceste procese sunt constituite dintre-un singur fir de execuţie. In acest moment sunt executate numai instrucţi-unile procesului „roşu”, în timp ce celelalte procese îşi aşteaptă rândul. După cum se observă din această figură, sistemele pipeline conţin o mulţime de etaje goale (dreptunghiurile galbene), numite pipeline bubbles (bule), care apar deoa-rece, din motivele prezentate anterior, CPU nu poate asigura alimentarea conti-nuă a sistemelor pipeline.
Fig. 9.1. Evident, această situaţie reduce eficienţa procesorului. Astfel, deşi unitatea
de alimentare cu instrucţiuni, poate emite patru instrucţiuni în fiecare ciclu de ceas, aceasta emite doar două instrucţiuni şi numai într-un singur ciclu reuşeşte să emită trei instrucţiuni.
In momentul lansării în execuţie a unui fir de execuţie acestuia i se asociază un context de execuţie. Prin context de execuţie se înţeleg toate informaţiile care descriu la un moment dat starea curentă de execuţie a firului (de exemplu conţi-nutul registrelor CPU, program counter (PC), indicatorii de condiţie, etc.).
Firelor de execuţie li se alocă, pe rând, câte o cuantă de timp pentru a fi executate. La un moment dat firul de execuţie este eliminat din procesor, după ce contextul sau a fost salvat şi un alt fir de execuţie este adus în procesor. Acţi-unea de salvare a contextului vechiului fir de execuţie şi încărcarea contextului noului fir de execuţie se numeşte comutarea contextului. Operaţia de comutare a contextului unui fir de execuţie consumă un număr de cicluri de ceas care au ca efect reducerea eficienţei procesorului..
O modalitate de a reduce numărul de comutări ale contextelor şi de a asigu-ra mai mult timp CPU pentru fiecare fir de execuţie este aceea de a construi un sistem care să poată executa mai multe fire de execuţie în acelaşi timp. Modul
CPU
RAM
Unitate de alimentare
Unitate de exe-cuţie
convenţional de a realiza acest lucru este de a adăuga sistemului încă un CPU, obţinând un sistem multiprocesor (SMP). Intr-un SMP sistemul de operare poate programa ca două fire de execuţie să fie executate exact în acelaşi timp, fiecare dintre acestea fiind executat pe un CPU diferit. Evident că nu i se permite niciu-nui proces să monopolizeze CPU şi în acest caz fiecărui fir de execuţie i se alocă o cuantă de timp CPU. In final fiecare fir de execuţie aşteaptă mai puţin până ob-ţine acces la CPU deci procesul va fi executat mai repede.
Fig. 9.2 In figura 9.2 este prezentat un single-thread SMP. După cum se constată în
acest moment sunt executate simultan procesul „roşu” şi procesul „maro”, fiecare pe câte un procesor. După ce cuanta de timp alocată fiecărui fir de execuţie expi-ră, contextul lor este salvat, codul şi datele acestora sunt eliminate din CPU şi două noi procese vor fi pregătite pentru execuţie. Se constată că, deşi acest sis-tem poate executa două fire de execuţie simultan, numărul de bule (pipeline bubbles) s-a dublat pe ansamblu, fiecare din cele două procesoare contribuind la aceasta cu gradul sau de ineficienţă.
CPU 2 CPU 1
RAM
Unitate de alimentare
Unitate de execuţie
Unitate de alimentare
Unitate de execuţie
9.2. Multithreading O metodă de a creşte performanţele procesorului constă în utilizarea tehnicii
multithreading. Un procesor care utilizează această tehnică se numeşte procesor multithreaded. Un astfel de procesor este capabil ca la un moment dat să execu-te mai mult de un singur fir. Figura 9.3 explică cum funcţionează un procesor multithreaded
Fig.9.3 După cum se observă din această figură, deoarece procesorul execută in-
strucţiuni din ambele fire de execuţie, atât unitatea de alimentare cât şi unitatea de execuţie au mai puţine etaje neutilizate (mai puţine pipeline bublles). Săgeţile din stânga arată că, într-un anumit ciclu de ceas, etajele pipeline conţin instrucţi-uni numai dintr-un singur fir de execuţie.
Pentru a înţelege cum funcţionează un procesor multithreaded să analizăm figura 9.3. In cazul procesoarelor prezentate anterior unitatea de alimentare cu instrucţiuni conţinea la un moment dat un singur fir de execuţie, care apoi, când se consuma cuanta de timp alocată, era comutat pentru a face loc altui fir de execuţie.
CPU
RAM
Unitate de alimentare
In acest caz, unitatea de alimentare cu instrucţiuni poate furniza, în fiecare ciclu de ceas, patru instrucţiuni către oricare dintre cele şapte unităţi funcţionale. Toate aceste patru instrucţiuni trebuie însă să provină din acelaşi fir de execuţie. Ca efect, fiecare fir de execuţie este limitat la o cuantă de timp, care acum con-stă dintr-un singur ciclu de ceas.
Procesoarele multithreaded pot asigura atenuarea unor probleme de latenţă introduse de încărcarea operanzilor din memorie. De exemplu să consideram cazul procesorului din figura 9.3, care execută două procese, pe cel roşu şi pe cel maro. Dacă firul roşu necesită încărcarea unei date şi această dată nu este prezentă în memoria cache, acest fir va fi întârziat multe cicluri de ceas aştep-tând data să sosească. Intre timp, totuşi, procesorul va executa procesul maro, menţinând astfel pipeline-ul plin.
Deşi procedeul multithreading poate reduce substanţial întârzierile datorate latenţei sistemului de memorie, în cazul unui paralelism redus la nivelul instrucţi-unilor dintr-un anume fir de execuţie, nu are totuşi efectul scontat. Dacă, la un moment dat, blocul de comandă reuşeşte să găsească în procesul roşu numai două instrucţiuni care pot fi încărcate în paralel în unitatea de execuţie, celelalte două etaje ale unităţii de încărcare vor rămâne neutilizate.
9.3. Simultaneous multithreading Această problemă este rezolvată de procedeul numit simultaneous
multithreading (SMT) sau, cum l-a denumit Intel, hyper-threading. Procedeul hyper-threading elimină restricţia procedeului multithreading de a încărca, într-un anumit ciclu de ceas, instrucţiuni care aparţin numai unui singur fir de execuţie. Această idee este prezentată în figura 9.4.
După cum se poate constata atât unitatea de alimentare cu instrucţiuni cât şi unitatea funcţională sunt utilizate mult mai eficient. Comparând cu sistemul multiprocesor din figura 9.2, se constată imediat că cele două procese care ocu-pau fiecare câte un procesor sunt acum comasate într-un singur procesor. In acest mod toate etajele unităţii de alimentare cu instrucţiuni sunt ocupate iar uni-tăţile de execuţie sunt acum mult mai eficient utilizate. De fapt procesorul hyper-hreading acţionează ca şi cum ar avea două CPU. Evident exemplul prezentat, în care cele două proceses sunt în totalitate complementare, este pur didactic, însă ne permite să ne realizăm eficienţa procedeului hyper-threading.
Din punct de vedere al sistemului de operare, un procesor SMT este com-pus din două procesoare logice şi firele de execuţie pot fi programate să fie exe-cutate de oricare din cele două procesoare, exact ca într-un sistem multiprocesor.
Puterea sistemului hyper-threading constă în faptul că permite maximum de flexibilitate la încărcarea etajelor unităţii de alimentare cu instrucţiuni, îmbunătă-ţind astfel gradul de utilizare al resurselor existente. Dacă comparăm diagramele din figurile 9.2. şi 9.4. constatăm că ambele sisteme execută aceeaşi cantitate de muncă dar sistemul hyper-threading utilizează mai puţine resurse şi are mai pu-ţini cicli de ceas pierduţi în comparaţie cu sistemul SMP.
Fig. 9.4 Pentru a înţelege mai bine cum acţionează în practică un sistem hyper-
threading să considerăm următorul exemplu: Să presupunem unitatea de pro-gramare a extras toate instrucţiunile care pot fi executate în paralel din procesul roşu şi că acestea sunt numai două. Aceasta înseamnă că în următorul ciclu de ceas vor fi încărcate numai două instrucţiuni. Trebuie să remarcăm că acesta es-te un scenariu foarte comun deoarece cercetările au stabilit că media instrucţiu-nilor paralele care pot fi extrase din cele mai multe coduri de program este de 2,5 pe ciclu. Pentru acest motiv, Pentium 4, la fel ca şi multe alte procesoare au fost echipate pentru a putea furniza 3 instrucţiuni în fiecare ciclu de ceas. Deoarece unitatea de programare din exemplul nostru ştie că ea poate furniza până la pa-tru instrucţiuni pe ciclu, va căuta instrucţiuni independente în alt fir de execuţie. In acest mod este eliminată gâtuirea care apare în procesul de alimentare cu in-strucţiuni.
9.4. Implementarea tehnicii hyper-threading. Deşi s-ar putea părea că implementarea tehnicii hyper-threading necesită un
mare număr de circuite de comandă suplimentare, în realitate se pare că nu este
CPU
RAM
Unitate de alimentare
Unitate de execu-
ţie
chiar aşa. Intel raportează că la procesorul Pentium Xeon circuitele suplimentare care implementează sistemul hyper-threading nu depăşesc 5% din suprafaţa pastilei de siliciu.
Pentium Xeon este capabil să execute în paralel cel mult două fire de exe-cuţie pe două procesoare logice. Pentru a prezenta sistemului de operare două procesoare logice, procesorul Xeon trebuie să fie capabil să memoreze informa-ţiile corespunzătoare a două contexte distincte, corespunzătoare celor două fire de execuţie. Acest deziderat a fost realizat prin modificarea microarhitecturii re-surselor; unele dintre acestea au fost replicate iar altele partiţionate.
Pentru a asigura independenţă totală a contextelor pentru fiecare procesor logic există câteva resurse care trebuie dublate. De exemplu este evident că fie-care procesor trebuie să aibă propriul său registrul PC (program counter), denu-mit mai recent instruction pointer (IP).
In mod similar procesorul Xeon are două tabele de alocare a registrelor, fie-care dintre acestea ţinând evidenţa celor 8 registre pentru întregi şi a celor 8 re-gistre pentru virgulă mobilă pentru fiecare din cele două procesoare logice.
De asemenea fiecare procesor logic are propriul său TLB (Translation Look-aside Buffer ).
Cap. 10. Sisteme Multiprocesor 10.1. Taxonomia arhitecturilor de calculatoare Una dintre cele mai cunoscute taxonomii (clasificări) ale arhitecturilor de
calculatoare este taxonomia lui Flynn. Michael Flynn a clasificat arhitecturile de calculatoare în patru categorii, în funcţie de prezenţa unui singur şir sau a mai multor şiruri de instrucţiuni şi de date. Un şir de instrucţiuni este un set de in-strucţiuni secvenţiale executate de un singur procesor, iar un şir de date este fluxul secvenţial de date necesar şirului de instrucţiuni. Cele patru categorii ale lui Flynn sunt următoarele:
1. SISD (Single Instruction stream, Single Data stream). Această categorie corespunde arhitecturii von Neumann, în care se execută în orice moment o singură instrucţiune. Calculatoarele SISD sunt numite şi calculatoare seriale scalare. Aceste calculatoare utilizează un registru numit contor de program – PC, care determină execuţia serială a instrucţiunilor. Pe măsură ce fiecare in-strucţiune este încărcată din memorie, contorul de program este actualizat pen-tru a conţine adresa următoarei instrucţiuni care se va încărca şi se va executa în ordine secvenţială. Există actualmente doar un număr redus de calculatoare SISD; chiar şi procesoarele din calculatoarele personale utilizează paralelismul în scopul creşterii eficienţei. In cele mai multe situaţii, acestea pot executa două sau mai multe instrucţiuni simultan.
2. MISD (Multiple Instruction stream, Single Data stream). In acest caz, mai multe instrucţiuni operează asupra unei singure date. Există două posibilităţi de interpretare a structurii calculatoarelor MISD. Prima posibilitate este de a se considera o clasă de calculatoare la care mai multe unităţi de prelucrare distinc-te primesc instrucţiuni distincte care operează asupra aceloraşi date. Această clasă de calculatoare este considerată ca nepractică sau imposibilă de către unii proiectanţi de calculatoare şi în prezent nu există exemple de acest tip. A doua posibilitate este de a se considera o clasă de calculatoare în care datele sunt trecute printr-o serie de unităţi de prelucrare.
Unele arhitecturile de tip pipeline, ca de exemplu procesoarele vectoriale sau arhitecturile sistolice, sunt considerate calculatoare de acest tip. Arhitecturile de tip pipeline execută o prelucrare vectorială utilizând o serie de etaje, iar fiecare din acestea execută o anumită funcţie şi produce un rezultat in-termediar. Motivul pentru care asemenea arhitecturi sunt clasificate ca sisteme MISD este faptul că elementele unui vector pot fi considerate ca aparţinând ace-leiaşi date, iar fiecare etaj pipeline prelucrează mai multe instrucţiuni care ope-rează asupra acelui vector.
3. SIMD (Single Instruction stream, Multiple Data stream). In acest caz, un singur şir de instrucţiuni prelucrează simultan date diferite. La calculatoarele de acest tip, există mai multe unităţi de prelucrare şi o singură unitate de control. Calculatoarele SIMD pot executa, de asemenea, prelucrări vectoriale. Aceasta se realizează prin asignarea elementelor vectorilor unor unităţi de prelucrare di-ferite pentru o prelucrare concurentă. In această categorie pot fi considerate
procesoarele matriciale. 4. MIMD (Multiple Instruction stream, Multiple Data stream). Această cate-
gorie cuprinde calculatoare cu mai multe unităţi de prelucrare în care mai multe instrucţiuni pot opera simultan asupra unor date diferite. Calculatoarele MIMD reprezintă arhitecturile cele mai complexe, obţinând o eficienţă ridicată prin pre-lucrare concurentă. In acest caz, concurenţa implică faptul că nu există doar procesoare multiple care operează în paralel, dar şi faptul că se execută proce-se multiple în acelaşi timp. Taxonomia lui Flynn s-a dovedit o metodă corespunzătoare pentru clasificarea arhitecturilor de calculatoare. Totuşi, progresele industriei de calculatoare au creat arhitecturi care nu pot fi clasificate în mod clar prin taxonomia lui Flynn. De exemplu, această taxonomie nu clasifică în mod adecvat procesoarele vectoria-le şi arhitecturile hibride. Pentru a rezolva această problemă, au fost propuse mai multe taxonomii.
Fig. 10.1 Figura 10.1 prezintă o taxonomie care cuprinde caracteristici ale mai mul-
tor taxonomii propuse. Această taxonomie clasifică arhitecturile mai recente, dar nu reprezintă o caracterizare completă a arhitecturilor paralele.
După cum se arată în figura 10.1, categoria calculatoarelor MIMD este îm-părţită în patru tipuri de arhitecturi paralele: multiprocesoare, multicalculatoare, multi-multiprocesoare şi calculatoare cu flux de date. In categoria SIMD, există un singur tip de arhitectură, reprezentată de procesoarele matriciale. Categoria MISD este împărţită în două tipuri de arhitecturi: procesoare vectoriale de tip pipeline şi matrice sistolice. Celelalte arhitecturi sunt grupate în două categorii: calculatoare hibride şi procesoare speciale. Aceste arhitecturi sunt descrise în secţiunea următoare.
Arhitecturi de calculatoare
SISD
MIMD
Speciale
Hibride
Arhitecturi von Neuman
Multicalculatoare
Multi-multiprocesoare
Multiprocesoare
MISD
SIMD
Procesoare matriciale
Calculatoare cu flux de date
Procesoare vectoriale pipeline
Matrici sistolice
Calculatoare MIMD-SIMD
Procesoare cu logică fuzzy
Calculatoare MIMD-MISD
Reţele neuronale artificiale
10.2. Prezentare generală a arhitecturilor de calculatoare 10.2.1. Sisteme Multiprocesor Multiprocesorul este un calculator paralel constând din mai multe proce-
soare interconectate care partajează un sistem de memorie. Procesoarele pot fi configurate astfel încât fiecare să execute câte o parte diferită a aceluiaşi pro-gram sau astfel încât fiecare să execute simultan mai multe programe diferite. O schemă bloc a unui multiprocesor este prezentată în figura 10.2.
Fig. 10.2. In general, un multiprocesor constă din n procesoare şi m module de
memorie. Procesoarele sunt notate cu nPPP ,...,, 21 iar modulele de memorie sunt notate cu mMMM ,...,, 21 . Reţeaua de interconectare RI conectează fiecare pro-cesor la un anumit subset al modulelor de memorie. O instrucţiune de transfer determină transferul datelor de la un anumit procesor către memoria cu care es-te conectat procesorul. Pentru transferul datelor între două procesoare, trebuie să se execute o secvenţă programată, care transferă datele între memorii şi procesoare intermediare.
In funcţie de organizarea sistemului de memorie, multiprocesoarele pot fi împărţite în două grupe, cu legătură strânsă şi cu legătură slabă.
In cazul unui multiprocesor cu legătură strânsă, un sistem central de me-morie, numită memorie principală sau memorie globală, asigură acelaşi timp de acces pentru fiecare procesor. Sistemul central de memorie poate fi implemen-tat fie ca un singur modul de memorie, fie ca un set de module de memorie care pot fi accesate în paralel de diferite procesoare. In ultimul caz, se reduce conflic-tul la memorie şi astfel sistemul este mai eficient. Conflictul la memorie se referă la situaţia în care mai multe procesoare solicită acces la memorie într-un interval scurt de timp, rezultând întârzieri mari de acces. Pe lângă sistemul central de memorie, fiecare procesor poate avea şi o memorie cache de dimensiuni redu-se. Aceste memorii cache ajută de asemenea la reducerea conflictelor la memo-rie.
P1 P2 Pn
Reţea de interconectare (RI)
M1 M2 Mm
Procesoare
Module de memorie
In cazul unui multiprocesor cu legătură slabă, pentru a se reduce conflicte-le la memorie, sistemul de memorie este partiţionat între procesoare, deci fiecă-rui procesor i se ataşează o memorie locală. Astfel, fiecare procesor poate ac-cesa în mod direct memoria sa locală şi toate memoriile locale ale celorlalte procesoare. Timpul de acces la o memorie care nu este locală este însă mult mai ridicat decât cel la memoria locală.
Indiferent de tipul multiprocesorului, toate procesoarele acestuia utilizează acelaşi sistem de operare. Sistemul de operare asigură interacţiunea dintre pro-cesoare şi taskurile acestora. De obicei, procesoarele sunt de acelaşi tip; în acest caz, multiprocesorul se numeşte omogen. Dacă procesoarele sunt de ti-puri diferite, multiprocesorul se numeşte eterogen. Oricare din procesoare poate accesa oricare din dispozitivele de I/E.
10.2.2. Sisteme multicalculator Spre deosebire de un multiprocesor, un multicalculator poate fi considerat
un calculator paralel în care fiecare procesor are o memorie locală proprie. Un procesor are acces direct doar la memoria sa locală şi nu poate adresa memo-riile locale ale altor procesoare. Această adresabilitate locală este o caracteristi-că importantă care deosebeşte multicalculatoarele de multiprocesoare. O schemă bloc a acestei arhitecturi este prezentată în figura 10.3.
Fig. 10.3 In figura 10.3, există n noduri de procesare şi fiecare nod constă dintr-un
procesor şi o memorie locală. Reţeaua de interconectare (RI) conectează fieca-re nod de procesare la un anumit subset al celorlalte noduri de procesare. O in-strucţiune de transfer determină transferul datelor de la un anumit nod la unul din nodurile cu care este conectat. Pentru transferul datelor între două noduri care nu pot fi conectate direct prin reţeaua de interconectare, datele trebuie transferate prin noduri intermediare utilizând un mecanism cu transmitere de mesaje.
Intr-un mecanism cu transmitere de mesaje, un procesor poate transmite (sau recepţiona) un bloc de informaţii la (sau de la) fiecare din celelalte proce-soare prin canale de comunicaţie. Aceste canale sunt conexiuni fizice între pro-cesoare, aranjate pe baza unei topologii a reţelei de interconectare. Fiecare
P1 P2 Pn
Reţea de interconectare (RI)
M1
Noduri de procesare
Mn M2
procesor este conectat la un canal de comunicaţie printr-un dispozitiv numit in-terfaţă de comunicaţie. Acest dispozitiv poate transmite sau recepţiona date printr-un canal de comunicaţie şi poate executa funcţii pentru a asigura că date-le sunt transmise şi recepţionate corect.
Înainte ca un bloc de informaţii să fie transmis printr-un canal, blocul este împachetat într-un mesaj cu un câmp al antetului la început şi un câmp al sumei de control la sfârşit. Câmpul antetului constă din informaţii de identificare, cu-prinzând adresa sursă, adresa destinaţie şi lungimea mesajului. Câmpul sumei de control constă din mai mulţi biţi de detecţie a erorilor de transmisie. La anu-mite implementări, interfaţa de comunicaţie este capabilă de a crea şi a decodi-fica câmpul antetului şi al sumei de control.
Comparând multiprocesoarele şi multicalculatoarele, primele pot fi progra-mate mai uşor decât cele din urmă. Multiprocesoarele reprezintă arhitectura dominantă în cazul sistemelor paralele de dimensiuni reduse. In general, pe măsură ce numărul de procesoare creşte, multicalculatoarele devin mai econo-mice decât multiprocesoarele. Multicalculatoarele sunt arhitecturi eficiente pen-tru sistemele paralele de dimensiuni mari. Aceasta se datorează următoarelor motive:
- Calculele ştiinţifice pot fi partiţionate astfel încât aproape toate operaţiile pot fi executate local;
- Se obţine o îmbunătăţire semnificativă a performanţelor dacă majoritatea referinţelor la memorie sunt efectuate la memoriile locale.
10.2.3. Sisteme Multi-multiprocesoare Odată cu progresele tehnologiei VLSI, a devenit posibilă construirea unor
calculatoare paralele de dimensiuni mari utilizând microprocesoare cu perfor-manţe ridicate. Pentru proiectarea unor asemenea calculatoare, pot fi combinate caracteristicile multiprocesoarelor şi multicalculatoarelor, într-o arhitectură numi-tă multi-multiprocesor (sau multiprocesor distribuit). Deci, un multi-multiprocesor poate fi considerat un multicalculator în care fiecare nod de procesare este un multiprocesor. Figura 10.4 prezintă structura generală a unui multi-multiprocesor.
Fig. 10.4. Fiecare nod permite ca taskurile cu un grad relativ ridicat de interacţiune
să fie executate local de către un multiprocesor, reducând astfel timpul necesar
Reţea de interconectare
Multiprocesor 1 Multiprocesor 2 Multiprocesor n
comunicaţiei. Dacă fiecare nod este un multiprocesor, complexitatea programării paralele a unui multicalculator va fi redusă.
10.2.4. Arhitecturi cu flux de date Intr-o arhitectură cu flux de date (dataflow), o instrucţiune este gata pentru
execuţie atunci când datele care reprezintă operanzii instrucţiunii devin disponi-bile. Rezultatele instrucţiunilor executate anterior formează operanzii instrucţiu-nilor care aşteaptă să fie executate. Se formează astfel un flux de date, care declanşează execuţia instrucţiunilor. Astfel nu este necesar un contor de pro-gram care există într-o arhitectură von Neumann pentru a controla execuţia in-strucţiunilor.
Instrucţiunile unui calculator cu flux de date nu adresează variabile într-o memorie partajată globală, ci ele conţin valorile variabilelor utilizate. Intr-o arhi-tectură cu flux de date, execuţia instrucţiunilor nu afectează alte instrucţiuni care sunt gata pentru execuţie. Astfel mai multe instrucţiuni pot fi executate simultan, ceea ce conduce la posibilitatea unor calcule cu un grad ridicat de concurenţă.
Figura 10.5 prezintă o schemă bloc a unui calculator cu flux de date. In-strucţiunile, împreună cu operanzii acestora, sunt păstrate în memoria de in-strucţiuni şi date (I&D). Ori de câte ori o instrucţiune este gata pentru execuţie, aceasta este transferată la unul din elementele de procesare (EP) prin reţeaua de arbitrare. Fiecare element de procesare este un simplu procesor cu o memo-rie locală limitată. La recepţionarea unei instrucţiuni, elementul de procesare execută operaţia cerută şi transmite rezultatul la destinaţia din memorie prin in-termediul reţelei de distribuţie.
Fig. 10.5
Date (rezultate)
Instrucţiuni şi date Memorie de instruc-
ţiuni şi date
Reţea de arbitrare
Reţea de distribuţie
EP
EP
EP
I & D
I & D
I & D RI
RI
Arhitecturile cu flux de date pot fi clasificate în două grupe: statice şi dina-mice. Intr-o arhitectură statică, o instrucţiune este validată ori de câte ori toţi operanzii necesari sunt recepţionaţi şi o altă instrucţiune aşteaptă rezultatul acestei instrucţiuni; în caz contrar, instrucţiunea rămâne invalidată. Această constrângere poate fi impusă prin utilizarea semnalelor de achitare. Intr-o arhi-tectură dinamică, o instrucţiune este validată ori de câte ori toţi operanzii nece-sari sunt recepţionaţi. In acest caz, pot deveni disponibile mai multe seturi de operanzi ale unei instrucţiuni în acelaşi timp. Comparativ cu arhitecturile statice cu flux de date, arhitecturile dinamice permit un grad mai ridicat de paralelism, deoarece o instrucţiune nu trebuie să aştepte după o altă instrucţiune înainte de a-şi plasa rezultatul. In cazul metodei dinamice trebuie stabilit însă un mecanism pentru a distinge diferitele seturi de operanzi pentru o instrucţiune.
10.2.5. Procesoare matriciale Un procesor matricial (figura 10.6) constă dintr-un set de noduri de proce-
sare (NP) şi un procesor scalar, toate funcţionând sub controlul unei unităţi de control centralizate. Unitatea de control încarcă instrucţiunile din memoria prin-cipală, le decodifică şi apoi le transmite fie la procesorul scalar, fie la nodurile de procesare, în funcţie de tipul acestora. Dacă instrucţiunea încărcată este o in-strucţiune vectorială, aceasta este transmisă la toate nodurile de procesare. Toate nodurile execută simultan aceeaşi instrucţiune asupra datelor diferite păs-trate în memoriile lor locale. Astfel, un procesor matricial necesită un singur pro-gram pentru a controla toate nodurile de procesare din sistem şi nu este nece-sară duplicarea codului programului la fiecare nod de procesare.
Fig. 10.6. Un procesor matricial poate fi definit, de exemplu, sub forma unei grile în
care fiecare intersecţie reprezintă un NP, iar liniile dintre intersecţii reprezintă căi de comunicaţie. Fiecare NP din matrice poate transmite (sau recepţiona) date la
Instrucţiuni Date
Date
Instrucţiuni scalare
Instrucţiuni vectoriale
Noduri de proce-
sare
P1 P2 Pn
Reţea de interconectare RI
M1 Mn M2
Memorie principală
Unitate de
control
Procesor scalar
(sau de la) cele patru noduri vecine. Unul dintre procesoare, reprezentând unita-tea de control, decide operaţiile care trebuie executate de fiecare NP în timpul fiecărui ciclu de procesare şi transferurile de date necesare între nodurile de procesare.
Ideea principală a unui procesor matricial este de a se exploata paralelis-mul existent în setul de date al unei anumite probleme şi nu de a se paraleliza secvenţa de execuţie a instrucţiunilor pentru acea problemă. Calculul paralel se realizează prin asignarea fiecărui procesor la o partiţie a datelor. Dacă setul de date este un vector, partiţia va fi un element al vectorului. Matricele de proce-soare îmbunătăţesc performanţele prin operarea simultană asupra tuturor partiţi-ilor de date. Aceste procesoare pot executa eficient operaţii aritmetice sau logi-ce asupra vectorilor. De aceea, ele se mai numesc şi procesoare vectoriale.
10.2.6. Procesoare vectoriale de tip pipeline Un procesor vectorial de tip pipeline poate prelucra în mod eficient ope-
ranzi vectoriali (şiruri continue de date). In timp ce procesoarele matriciale sunt controlate de instrucţiuni, procesoarele vectoriale de tip pipeline sunt controlate de şiruri continue de date. Aceasta este diferenţa principală între un procesor matricial sau vectorial şi un procesor vectorial de tip pipeline. Figura 10.7 prezin-tă structura de bază a unui procesor vectorial de tip pipeline.
Fig. 10.7 Există două procesoare principale: un procesor scalar şi un procesor vec-
torial. Procesorul scalar execută instrucţiunile scalare, iar procesorul vectorial execută instrucţiunile vectoriale utilizând mai multe etaje de prelucrare. Unitatea de control încarcă instrucţiunile din memoria principală, le decodifică şi apoi le transmite fie la procesorul scalar, fie la procesorul vectorial realizat sub formă de sistem pipeline, în funcţie de tipul acestora.
Memorie principală
Instrucţiuni
Date
Instrucţiuni scalare
Instrucţiuni vectoriale
Procesor vectorial
Etaj 1
Unitate de
control
Procesor scalar
Mn M2 M1
Etaj 2 Etaj n
Procesoarele vectoriale de tip pipeline utilizează mai multe module de
memorie pentru a furniza etajelor de prelucrare un şir continuu de date. Adesea se utilizează un compilator cu vectorizare pentru a aranja datele într-un şir care poate fi utilizat apoi de cele două procesoare.
10.2.7. Matrice sistolice Pentru calculele ştiinţifice, adesea este necesară rezolvarea unor sisteme
de ecuaţii liniare de dimensiuni mari. De obicei, pentru rezolvarea unor aseme-nea sisteme de ecuaţii se utilizează algebra matriceală. Datorită secvenţelor lungi ale calculelor aritmetice, majoritatea operaţiilor algebrice matriciale sunt executate pe calculatoare digitale cu viteză ridicată utilizând pachete software dedicate. Un dezavantaj major al execuţiei operaţiilor algebrice matriciale pe calculatoare generale este timpul de execuţie ridicat. De asemenea, în cazul unui calculator general memoria principală nu are o dimensiune suficientă pen-tru a permite plasarea unor matrice foarte mari. Pentru acest motiv sunt necesa-re numeroase transferuri de I/E, ceea ce creşte timpul de execuţie.
Pentru rezolvarea acestei probleme, au fost introduse arhitecturi speciale. O soluţie constă în utilizarea unei matrice sistolice (figura 10.8). In cazul acestei arhitecturi, există un număr mare de elemente de procesare (EP) identice.
Fig. 10.8 Fiecare element de procesare are o memorie locală redusă ca dimensiune
şi, pentru a nu se limita numărul de elemente de procesare plasate într-o matri-ce, fiecare EP poate fi conectat, prin reţele de interconectare, numai cu elemen-tele de procesare vecine. Deci, elementele de procesare sunt aranjate într-o structură de tip pipeline, sub forma unei matrice liniare sau bidimensionale. Intr-o matrice sistolică elementele de date şi rezultatele parţiale parcurg elementele de procesare în timpul execuţiei, constând din mai multe cicluri de procesare. In fiecare ciclu de procesare, anumite elemente de procesare execută aceeaşi operaţie relativ simplă (de exemplu, adunare sau înmulţire) asupra elementelor de date şi transmit aceste elemente sau rezultate parţiale la alte elemente de procesare vecine.
Ieşiri Intrări
EP
EP
EP
RI
RI EP
EP
EP EP
EP
EP
Utilizând tehnologia VLSI, este posibil să se obţină o putere de calcul foar-te ridicată cu un sistem constând dintr-un număr mare de procesoare identice organizate într-o manieră structurală.
10.2.8. Arhitecturi hibride Pentru a obţine performanţe mai ridicate ale calculelor paralele, se utili-
zează arhitecturi hibride, care cuprind caracteristici ale unor arhitecturi diferite. In general, există două tipuri de paralelism care se pot utiliza: paralelism de con-trol şi paralelism de date. In cazul paralelismului de control, se execută simultan două sau mai multe operaţii de către procesoare diferite. Calculatoarele MIMD sunt ideale pentru implementarea paralelismului de control. Acestea sunt adec-vate pentru probleme care necesită executarea simultană a unor operaţii diferite asupra datelor diferite. In cazul paralelismului de date, se execută aceeaşi ope-raţie asupra mai multor partiţii ale datelor de către mai multe procesoare. Calcu-latoarele SIMD sunt ideale pentru implementarea paralelismului de date. Aces-tea sunt adecvate pentru probleme în care aceeaşi operaţie poate fi executată simultan asupra unor porţiuni diferite ale datelor. Calculatoarele MISD sunt de asemenea potrivite pentru paralelismul de date. Aceste calculatoare permit pro-cesarea vectorilor utilizând tehnica pipeline.
In practică, cele mai mari avantaje se obţin prin utilizarea paralelismului de date deoarece, în acest caz, se beneficiază de pe urma paralelismului în mod proporţional cu cantitatea datelor implicate în calcule. Totuşi, uneori nu este po-sibil să se exploateze la maxim paralelismul de date, fiind necesară utilizarea atât a paralelismului de control cât şi a celui de date. De exemplu, în cazul unor programe de aplicaţie rezultatele cele mai bune se pot obţine atunci când aces-te programe sunt divizate în mai multe părţi care utilizează paralelismul de date, iar părţile componente utilizează paralelismul prin tehnica pipeline. Un grup de procesoare culege datele şi execută anumite prelucrări preliminare. Procesoare-le transmit apoi rezultatele lor la al doilea grup de procesoare care execută alte calcule asupra rezultatelor. Al doilea grup transmite rezultatele obţinute la al trei-lea grup de procesoare, care obţine rezultatele finale. Deci, un calculator paralel care cuprinde atât caracteristici ale arhitecturilor MIMD, cât şi cele ale SIMD (sau MISD) poate rezolva în mod eficient o gamă largă de probleme.
10.2.9. Reţele neuronale artificiale Un exemplu de arhitectură specială este o reţea neuronală artificială. O
asemenea reţea constă dintr-un număr mare de elemente de procesare (EP) care funcţionează în paralel. Aceste reţele pot rezolva într-un mod mai eficient unele probleme pentru care arhitecturile von Neumann sunt ineficiente, ca de exemplu emularea informaţiilor naturale sau recunoaşterea formelor. Arhitecturile bazate pe reţele neuronale sunt capabile de învăţare şi sunt adapti-ve la schimbările de mediu.
Fig. 10.9 Figura 10.9 prezintă structura generală a unei reţele neuronale artificiale.
Fiecare element de procesare emulează unele caracteristici ale neuronului bio-logic. Acesta are un set de intrări şi una sau mai multe ieşiri. Fiecărei intrări i se asignează o pondere numerică. Această pondere corespunde potenţialului si-naptic al unui neuron biologic. O sinapsă reprezintă conexiunea dintre un neu-ron şi un terminal al altui neuron (terminal numit axon). Transmiterea informaţii-lor de la un neuron la altul are loc prin intermediul sinapselor şi axonilor. Intrările unui element de procesare sunt multiplicate cu ponderile lor şi sunt apoi însu-mate pentru a determina nivelul de activare al neuronului. După determinarea nivelului de activare, se aplică o funcţie de activare pentru a produce semnalul de ieşire. Ieşirile combinate ale unui strat (nivel) precedent devin intrările urmă-torului strat, în care acestea sunt din nou însumate şi evaluate. Acest proces es-te repetat până când se traversează reţeaua şi se ajunge la o anumită decizie.
Spre deosebire de arhitecturile von Neumann, la care elementul primar de calcul este procesorul, în cazul reţelelor neuronale artificiale acest element este reprezentat de conexiunile dintre elementele de procesare. Pentru o problemă dată, trebuie să se determine valorile corecte ale ponderilor astfel încât reţeaua să poată executa prelucrările necesare. Cu scopul de a creşte performanţele re-ţelei, determinarea valorilor corespunzătoare ale ponderilor se realizează prin ajustarea iterativă a acestora. Regula de ajustare a ponderilor este numită regu-lă de învăţare, iar întregul proces de obţinere a ponderilor corespunzătoare este numit învăţare.
Toate modelele de reţele neuronale artificiale sunt caracterizate prin ope-rarea paralelă şi interconectarea densă între elementele de procesare. In ace-laşi timp, există diferenţe majore între modelele individuale în ceea ce priveşte arhitectura lor, regulile de învăţare şi modul de interacţiune cu mediul.
O taxonomie generală a acestor modele este prezentată în continuare. Distincţia cea mai generală între diferitele modele de reţele neuronale artificiale este metoda de învăţare. Dacă mediul furnizează exemplele de învăţare sub forma perechilor de vectori de intrare/ieşire, metoda de învăţare este numită su-pervizată. Această metodă este numită şi învăţare cu un profesor, deoarece mediul are rolul unui profesor pentru reţeaua neuronală, punând la dispoziţie
Ieşiri
EP
EP
EP EP
EP
EP EP
EP
EP
Intrări
exemple detaliate despre ceea ce trebuie învăţat. Dacă, din contră, mediul spe-cifică intrarea dar nu şi ieşirea, învăţarea este nesupervizată. In acest caz, re-ţeaua neuronală trebuie să descopere soluţia la problema de învăţare.
Intr-o altă metode de învăţare, numită învăţare cu ajutor (reinforcement learning), mediul furnizează anumite informaţii de ieşire, dar aceste informaţii sunt sub forma evaluării unei performanţe a reţelei neuronale şi nu sub forma unor exemple de învăţare. Această metodă este numită şi învăţare cu un critic, spre deosebire de învăţarea cu un profesor, deoarece mediul nu specifică ceea ce trebuie învăţat, ci numai dacă ceea ce se învaţă este corect.
O altă distincţie între diferite modele de reţele neuronale artificiale se ba-zează pe arhitectura acestora. Arhitectura se referă la tipul de prelucrare execu-tată de neuronii artificiali şi la interconexiunile dintre aceştia. Modelele de reţele neuronale artificiale pot fi împărţite în două grupe: deterministe şi stohastice. Reţelele deterministe produc întotdeauna acelaşi rezultat la ieşire pentru ace-eaşi intrare, în timp ce la reţelele stohastice ieşirea pentru o intrare dată poate varia în funcţie de o anumită distribuţie a probabilităţii de ieşire. Modelele sto-hastice sunt de obicei mai dificil de analizat şi simulat, dar în acelaşi timp ele sunt mai realiste în numeroase aplicaţii.
Adesea, modelele de reţele neuronale artificiale sunt simulate prin pro-gram. Această metodă este flexibilă, dar este lentă. Metoda cea mai eficientă pentru implementarea unei reţele neuronale artificiale este implementarea prin hardware. In ultimii ani, au fost dezvoltate mai multe circuite pentru reţelele neu-ronale artificiale. In general, sunt disponibile trei tehnologii diferite pentru im-plementarea prin hardware a unei reţele neuronale artificiale: electronică, optică şi electro-optică.
Tehnologia electronică poate fi împărţită la rândul ei în trei tipuri de im-plementări: analogică, digitală şi hibridă. O implementare analogică reduce complexitatea circuitului, dar este mai puţin precisă şi, de multe ori, nu permite obţinerea unui grad de precizie de 6 biţi. Aceasta se datorează în principal nive-lului redus de precizie al rezistoarelor. O implementare digitală asigură o preci-zie mai ridicată, dar de multe ori necesită un spaţiu mai mare în cadrul circuitului integrat. O implementare hibridă conţine elemente analogice şi digitale pentru a obţine avantajele ambelor implementări.
Tehnologia optică poate soluţiona anumite probleme ale tehnologiei elec-tronice, în special cele legate de conectivitatea între neuroni, din cauza întârzie-rilor şi a spaţiului necesar în cadrul circuitului integrat. Prin utilizarea intercone-xiunilor optice, nu este necesară nici o izolaţie între traseele semnalelor, deoa-rece razele de lumină pot trece unele prin altele fără a interacţiona între ele. De asemenea, traseele semnalelor pot fi realizate tridimensional. In sfârşit, ponderi-le pot fi memorate sub forma unor holograme. Cu toate aceste avantaje, există numeroase probleme asociate cu tehnologia optică, în special faptul că unele caracteristici fizice ale dispozitivelor optice nu sunt compatibile cu cerinţele reţe-lelor neuronale.
Intr-o implementare electro-optică, interconexiunile sunt realizate optic. Deoarece reţelele neuronale artificiale sunt puternic interconectate, această me-todă devine o alternativă atractivă de implementare.
10.2.10. Procesoare bazate pe logica fuzzy Un alt exemplu de arhitectură specială este reprezentată de un procesor
bazat pe logica fuzzy. Logica fuzzy a fost propusă de Lofti Zadeh pentru a îm-bunătăţi utilizarea tehnicilor inteligenţei artificiale în anumite domenii cum este recunoaşterea vorbirii. In inteligenţa artificială, logica cu două valori reprezintă semnificaţia unei propoziţii ca adevărată sau falsă, dar nu poate reprezenta o propoziţie cu o semnificaţie imprecisă. In logica fuzzy, o propoziţie poate fi ade-vărată sau falsă, sau poate avea o valoare intermediară (de exemplu, foarte adevărat).
Logica fuzzy se ocupă de principiile formale ale raţionamentului aproxima-tiv. Această logică încearcă să trateze în mod eficient complexitatea procesului cognitiv uman şi elimină unele dezavantaje asociate cu logica clasică binară, ca-re nu reflectă în mod corespunzător procesele cognitive umane complexe. Logi-ca clasică binară consideră clase cu limite clare, de exemplu, negru sau alb. In acest fel, un obiect este fie un membru al unei clase, fie nu. Spre deosebire de această logică, logica fuzzy consideră clase care nu au limite clare, o măsură indicând gradul de apartenenţă al unui obiect la o clasă.
Logica fuzzy a fost aplicată în numeroase domenii, cum sunt controlul proceselor, recunoaşterea imaginilor, robotică şi sisteme expert. Controlul fuzzy este prima aplicaţie industrială a logicii fuzzy. Un controler fuzzy poate controla sisteme care puteau fi controlate anterior numai de către operatori experimen-taţi. In Japonia, s-au obţinut progrese semnificative în logica fuzzy, iar această logică a fost aplicată unei mari varietăţi de produse, cum sunt sisteme de control al navigaţiei pentru automobile, camere video şi maşini de spălat. Deşi imple-mentarea prin software a logicii fuzzy asigură rezultate bune pentru unele apli-caţii, pentru implementarea aplicaţiilor cu performanţe ridicate sunt necesare procesoare fuzzy dedicate, numite acceleratoare fuzzy.
1. Dupa subciclul de intrerupere urmeaza intodeauna subciclul de
-extragere
2. Np/q=C+r/q reprezinta relatia de conversie
- din baza p in baza q
3. Operatia de impartire cu refacerea restului partial incepe cu
- deplasarea spre stanga a registrului combinat A_Q
4. Magistralele primare sunt
- cele pe care circula datele
5. Cel mai mare numar denormalizat, in valoare absoluta, care poate fi reprezentat in simpla
precizie este
1.18x10 la puterea -38
6. O magistrala de extensie de tip magistrala locala este caracterizata prin faptul ca
- conecteaza unitatile rapide la magistrala UCP
7. Reprezentarea in MS a numarului -12 (pe 4 + 1 biti) este
- 11100
8. Incosistenta memoriei cache trebuie evitata
-in cazul sistemelor multiprocesor si in cazul sistemelor uniprocesor daca exista un
controler sau procesore de I/E care are un acces direct la memoria principala independenta de
UCP.
9. Problema indisponibilitatii intrstructiunilor se rezolva prin
- Utilizare unor buffere pentru memorarea instructiunilor si a datelor
10. Campul de acces al tabelei de pagini specifica
- tipul operatiilor care pot fi executate asupra paginii (citita, citita si scris, sau
executata)
11. Registrul de date este utilizat pentru
- a aduce datele si instructiunile din memorie
12. In cazul unitatilor de memorie cu acces direct timpul de acces este
- variabil
13. Bitul de modificare (dirty bit) este utilizat in cazul strategiei
- write-back
14. In cazul planificarii sistemelor pipeline prin latenta se intelege
-numarul ciclurilor de ceas care separa aplicarea datelor de intrare
15. Ce reprezinta figura urmatoare?
- Un sumator paralel de n biti (un sumator serie de n biti/un sunmator cu anticiparea
transportului de n biti)
16. O ierarhie de memorii prevede ca cel mai aproape de procesor sa gaseasca
- unitatea de memorie cea mai rapida, cu dimensiunea cea mai redusa si costul cel mai
ridicat
17. La o arhitectura de tip matrice sistolica elementele de procesare sunt aranjate intr-o
structura de tip
- pipeline
18. O instructiune orizontala este interpretata in modul urmator
- Se activeaza toate semnalele de comanda carora le corespunde un bit de 1 in campul
semnalelor de comanda si se dezactiveaza cele carora le corespunde un bit de 0. Daca conditia
indicata de campul de conditie este falsa se executa urmatoarea microinstruciune din
microprogram. Conditia indicata de campul de conditie este adevarata, se executa
microintructiunea indicata de campul de adresa.
19. In cazul inmultirii Booth daca doi biti succesivi ai inmultitorului sunt 11 se efectueaza
- o deplasara a produsului partial la dreapta
20. In cazul metodei EPIC planul de executie al programului este elaborat de
- compilator
21. Arhitectura SISD se refera la calculatoarele in care
- care executa la un moment dat o singura instructiune
22 O adresa virtuala se converteste intr-o adresa reala in modul urmator:
- Adresa de baza virtuala se converteste intr-o adresa de baza reala, utlizand TLB, iar
deplasamentul ramane nemodificat
23. Compilatorul calculatoarelor RISC
- maximizeaza utlizarea registrelor si minimalizeaza astfel accesurile la memoria
principala
24. In codul Gray
- trecerea de la o cifra zecimala la urmatoarea necesita modificarea unui singur bit
25. Semisumatorul elementar are
-doua intrari si doua iesiri
26. Un proces consta din
- segmente de cod si segmente de date mapate intr-un spatiu virtual de adresare
27. In cazul metodei scoreboard, o instructiune va fi lansata in executie daca
-Unitatea functionala este disponibila si nu exista alta instructiune activa care
utilizeaza aceasi registru de destinatie
28. Un etaj de prelucrare poate fi format dintr-un circuit
- secvential, combinational sau inteligent
29. Salturile conditionate sunt mai greu de gestionat de un sistem pipeline deoarece
- nu se cunoaste calea ce va fi urmata decat dupa executia instructiunii
30. In cazul inmultirii Booth rezultatul se formeaza in
-registrul combinat A_Q de 2n+2 biti
31. In cazul impartirii cifra catului Q0 se calculeaza cu relatia
- Q0 <- NOT an
32. La arhitecturile RISC instructiunile complexe sunt implementate prin
- functii care utilizeaza instructiunile existente
33. Un numar reprezentat in VM care are C=255 si F diferit de 0 reprezinta
- NaN
34. In cazul metodei Tomasulo, in campul de marcaj al unui registru va fi memorata
- eticheta registrului sursa
35. Ce reprezinta figura urmatoare (un dreptunghi cu ss in mijloc)
-un semisumator elementar (un circuit elementar de inmultire/un sumator elementar)
36. La arhitecturile cu flux de date instructiunile si datele sunt memorate
- intr-o memorie unica
37. Bufferul de translatare (TLB) este
- o tabela de conversie a adreselor de baza virtuala in adrese de baza reala amplasata in
memoria rapida din UCP
38. Primul rezultat al unui sistem pipeline va fi elaborat
- dupa timpul necesar parcurgerii tuturor etajelor de catre primul subproces
39. Un sumator de n biti calculeaza suma celor doua numere dupa
- n ciclii de ceas
40. In cazul memorie cache cu mapare directe la un esec la cautare are ca efect
- transferarea in memoria cache a marcajului si a datei cu acelasi index
41. Reprezentarea in C1 a numarului -9 (pe 4+1 biti) este
-10110
42. Magistrala PCI este
- o magistrala la care se conecteaza periferice rapide
43. Cel mai mic numar denormalizat, in valoare absoluta, care poate fi reprezentat in simpla
precizie este
- 1.4x10 la puterea -45
45. Tehnica superthreading permite ca in fiecare ciclu de ceas sa fie furnizate mai multe
instruciuni
- apartinand aceluiasi fir de executie
46. La inmultirea a doua cifre binare, produsul este 1 numai daca deinmultitul si inmultitorul
sunt
- 1 si 1
47. In organizarea look-trought memoria cache si memoria principala sunt conectate
- printr-o magistrala separata (locala) care este izolata de magistrala sistem
48. La un sistem de numeratie pozitional
- fiecare cifra contribuie la valoarea numarului cu o pondere data de puterea bazei
49. Stiind ca in cazul utilizarii combinata a segmentarii si paginarii adresa virtuala are trei
campuri, cate campuri are adresa reala corespunzatoare
- doua campuri; adresa de baza si deplasamentul
50. O UCC microprogramata functioneaza astfel
-Pentru executia instructiunii din RL logica de secventiere activeaza un semnal de
citire a memorie de comanda. Cuvantul a carei adresa este specificata in registrul de
microadrese va fi citit si depus in registrul de microinstructiuni. Continutul registrului de
microinstructiuni activeaza semnalele de comanda si genereaza informatii despre adresa
urmatoare pentru logica de secventiere. Logica de secventiere incarca o noua adresa in
registrul de microadrese, pe baza informatiilor despre adresa urmatoare de la registrul de
microinstructiuni si a indicatorilor de conditii ai UAL.
51. Contorul de program este un registru din procesor care
- memoreaza adresa instructiunii ce urmeaza sa fie executata
52. In cazul metodei scoreboard, tabela de stare a instructiunilor arata
- daca o instructiune este lansata in executie si in ce faza se gaseste
53. Memoria principala este considerata
- memoria RAM
54. Codul NBCD are ponderile
-8421
55. Conectorii de extensie fac parte integranta din
- magistrala de I/E
56. Un vector de coliziune este un
-sir de cifre binare de lungime N-1. unde N este latenta interzisa maxima din lista
latentelor interzise
57. Un cod se numeste autocomplementar daca
- cuvantul de cod al complementului fata de 9 al cifre N (deci 9-N) se poate obtine din
codul cifrei N prin complentarea fiecaruia din cei 4 biti
58. Arhitecturile RISC sunt caracterizate de
- utilizarea sistemelor pipeline
59. Un hazard de tip RAW se poate rezolva prin
- inserearea unor instructiuni independete dupa prima instructiune care trebuie sa scrrie
in registru
60. Celula D utilizata in cazul impartirii matriciale implementeaza functiile (patrat cu D mij)
- z=x minus y minus t pentru a=0 si z=x, pentru a=1
61. In cazul arhitecturilor hibride cele mai bune rezultate se obtin prin
- utilizarea paralelismului de date
62. Magistrala AGP este superioara magistralei PCI deoarece
- este dedicata adaptoarelor grafice
63. Vectorul de coliziune corespunzator listei latentelor interzise (4,1,0) este
- (10011)
64. In cazul utilizarii combinate a segmentarii si a paginarii adresa virtuala
- contine un index de segment si un index de pagina
65. In cazul impartii cu refacerea restului partial succesiunea operatiilor desfasurate pe doi
pasi consecutivi este
- A<-A-B , A<-A-B+B , A<- 2*A , A<-2*A-B
66. Pentru trecerea de la un tip de operatie la altul in cazul sistemului pipeline static trebuie
- sa goleasca etajele sistemului
67. In cazul predictiei statice a salturilor
- se decide inainte executiei instructiunii de salt preincarcarea instructiunilor dintr-una
din cele doua
68. Prin microoperatie se intelege
- operatia elementara care se desfasoara pe durata unei perioade de ceas
69. Codul Gray este
- neponderat
70. In cazul memoriei virtuale prin mapare dinamica se intelege sitatia in care
- spatiul adreselor fizice se modifica pe durata executie programului
71. Subciclul de intrerupere este compus din urmatoarele microinstructiuni
- t1: RD<-PC
t2: RA<-Adresa_salvare
PC<-Adresa_rutina
t3: Mem <- RD
72. Care este tipul de celula de memorie care necesita reimprospatare?
- DRAM
73. Subciclul de extragere este compus din urmatoarele microinstructiuni
- t1: RA<_PC
t2: RD<_MEM
PC<_PC+1
t3: RI<_RD
74. Registrul de instructiuni primeste instructiunea ce urmeaza sa fie decodificata
- de la registrul de date
75. La o arhitectura de tip matrice sistolica fiecare element de procesare dintr-un ciclu de
procesare
- executa aceasi operatie asupra unor date diferite
76. Magistralele primare sunt
- cele pe care circula datele
77. Tehnica superthreading are performante limitate din cauza
- paralelismului redus la nivelul instructiunilor
78. Pentru a se reduce efectul salturilor asupra performantelor unui sistem pipeline se pot
utiliza urmatoarele tehnici
- predictia salturilor, intarzierea salturilor si preincarcarea multipla
79. In cazul inmultirii Booth daca doi biti succesivi ai inmultitorului sunt 10 se efectueaza
- o scadere a deinmultitului urmata de o deplasare a produsul partial la dreapta
80. Reprezentarea in C2 a numarului -14 (pe 4+1 biti) este
- 10010
81. Un multicalculator este caracterizat de faptul ca
- fiecare procesor are o memorie locala proprie si nu poate adresa direct memoriile
locale ale altor procesoare.
82. Utilizarea unui numar mare de registre este una dintre caracteristicile distinctive ale
arhitecturilor
- RISC
83. Procesoarele superpipeline asigura cresterea ratei de transfer prin
- marirea numarului de etaje de prelucrare a sistemului pipeline
84. Registrul de adresa este utilizat pentru
- a pastra adresa din memorie a operandului sau instructiunii ce urmeaza sa fie adus in
registrele procesorului
85. Un timp de acces la memorie mai mic implica
- un pret pe bit mai mare
86. In cazul unitatilor de memorie cu acces aleator timpul de acces este
- constant
87. Caracteristica unui numar reprezentat in VM este un numar
- pozitiv
88. In cazul memoriilor organizate dupa metoda 1D cuvintele de memorie sunt amplasate sub
forma
- vectoriala
89. Ciclul C0a1C1a2C0 poate fi reprezentat ca cilcul
- C=(2,5)
90. Reprezentarea in C2 a numarului -13 (pe 4+1 biti) este
- 10011
91. Hazardul RAW se produce atunci cand
- o instructiune citeste un registru inainte ca o instructiune precedenta sa scrie in acel
registru
92. La iesirea unui sistem pipeline este elaborat un rezultat
- in fiecare ciclu de ceas
93. Planul de executie al programului in cazul metodei VLIW este elaborat de
- compilator
94. Dispozitivul slave este acel dispozitiv care
- asteapta cererea de transfer de date pe magistrala
95. In fiecare din momentele T1,T2,...,Tn generate de generator de faze utilizat de UCC cu
decodificator
- sunt activate semnalele de comanda cerute de codul instructiunii
96. In organizarea look-through
- magistrala sistem nu este ocupata cu transferul blocurilor de date intre M1 si M2
97. In strategia write-back
- cuvantul modificat este copiat in memoria principala in momentul eliminarii din
memoria cache a blocului din care face parte
98. Prin localitate temporala se intelege faptul ca
- datele sau instructiunile referite recent au o probabilitate ridicata de a fi referite in
viitorul apropiat
99. O microinstructiune orizontala este interpretata in modul urmator
- Se activeaza toate semnalele de comanda carora le corespunde un bit de 1 in campul
semnalelor de comanda si se dezactiveaza cele carora le corespunde un bit de 0. Daca conditia
indicata de campul de conditie este falsa, se executa urmatoarea microinstructiune din
microprogram. Conditia indicata de campul de conditie este adevarata, se executa
microinstructiunea indicata de campul de adresa.
100. Ce reprezinta figura urmatoare (incepe cu un patratel cu OV in mij)?
- un sumator paralel de n biti
101. Daca adresa virtuala de baza nu se gaseste in TLB se procedeaza astfel
- blocul care contine adresa virtuala cautat este adus din memoria primara in TLB
102. Prin paralelism la nivel de instructiune se intelege
- posibilitatea de executie simultana a instructiunilor independete.
103. Inmultirea prin metoda Booth opereaza asupra unor numere reprezentate in
- C2
104. Memoria cache este
- utilizata temporar pentru pastrarea unei portiuni a datelor si instructiunilor in vederea
utilizarii imediate.
105. Un sumator serie de n biti calculeaza suma celor doua numere dupa
- n cicli de ceas
106. In cazul stivei implementate in memorie
- adresa de baza a stivei ramane fixa, in timp ce adresa care indica varful stivei se
modifica la fiecare operatie de introducere si eliminare din stiva
107. Magistrala VESA a fost proiectata pentru procesorul
-486
108. Strategia cel mai putin recent utilizata de inlocuire blocurilor are dezavantajul ca
- necesita o logica complicata care poate mari timpul de acces la memoria cache
109. In cazul metodei scoreboard, tabela de stare a unitatilor functionale urmareste
hazardurile
- war
110. Pentru pastrarea oridinii de executie a instructiunilor intre care exista dependente un
procesor superscalar utilizeaza
- metoda tabelei de rezultate
111. Latenta interzisa este
- numaru de ciclii de ceas dintre doua semne x ale aceluiasi etaj
112. Indicatorul de conditie Zero din cuvant de stare al programului are valoarea 1 atunci
cand
- rezultatul operatiei este zero
113. Baza unui sistem de numeratie este data de
- numarul de simboluri permise pentru reprezentarea numerelor
114. In cazul impartirii cu refacerea restului partial
- bitul Qn nu participa la deplasare
115. Tehnica pipeline reprezinta o metoda de imbunatatire a performantelor
-unui procesor
116. Timpul de acces a memoriei cache in comparatie cu cea a memoriei principale este
- mai mic
117. Care este rolul registrului B din schema urmatoare
- memoreaza unul dintre cele doua numere ce trebuie adunate
118. Existenta unui numar redus de formate ale instructiunilor este caracteristica
- arhitecturilor RISC
119. In cazul metodei scoreboard, care sunt instructiunile care se executa in ordinea din
program
- instructiunile dependente
120. In cazul inmultirii Booth rezultatul se gaseste in registrul combinat A_Q pe primele
- 2n+1 pozitii
121. Magistrala ISA a fost utilizata in versiunile
- de 8 si 16 biti
122. Problema intarzierii introduse de etaje se rezolva prin
- realizarea mai multor copii ale etajului care produce intarzierea
123. Un ciclu instructiune reprezinta
- totalitatea prelucrarilor efectuate de UCP pentru executia unei singure instructiuni
124. Intr-o arhitecturile cu flux de date statica o instructiune este validata atunci cand
- toti operanzii necesari sunt receptionati si o alta instructiune asteapta rezultatul
acestei instructiuni
125. Indicatorul de conditie Egal din cuvant de stare al programului are valoarea 1 auntci cand
- rezulta o egalitate in urma unei operatii de comparare
126. Cadrele de pagina sunt
- blocuri de memorie de aceasi dimensiune cu paginile
127. La o UCC cu decodificator codul instructiunii ca fi decodificat cu ajutorul unui
decodificator care
- activeaza un singur semnal de iesire
128. Reimprospatarea este operatia prin care
- informatia este rescrisa in memorie
129. In cazul inmultirii Booth daca doi biti succesivi ai inmultitorului sunt 01 se efectueaza
- o adunare a deinmultitului urmata de deplasarea produsului partial la dreapta
130. In cazul impartirii cu refacerea restului partial rezultatul final se regaseste astfel
- catul in registrul Q, restul in registrul A.
131. In cazul metodei Tomasulo, magistrala comuna de date permite ca
- o instructiune aflata in curs de executie sa poata avea acces la rezultatul unei
instructiuni precedente inainte ca rezultatul acestei instructiuni sa fie inscris in registrul
destinatie
132. Conversia unui numar intreg din baza p in baza q cu proprietatea q=pr, unde r este
numar intreg, se realizeaza mai simplu prin
- partitionarea de la dreapta spre stanga a numarului din din baza p in grupe de cate r
cifre si inlocuirea fiecarei grupe cu echivalentul sau in baza q
133. La un multicalculator transferul datelor intre doua noduri care nu sunt interconectate
- se realizeaza utilizand un mecanism cu transmitere de mesaje.
134. Un numar reprezentat in VM care are C=255 si F=0 reprezinta
- + sau – infinit
135. In cazul magistralei sincrone
- fiecare transfer dureaza un numar intreg de perioade de ceas
136. Un etaj al unui sistem pipeline consta
- dintr-un registru de intrare si un circuit de prelucrare
137. Strategiile de inlocuire a blocurilor din memoria cache stabilesc
- care bloc trebuie eliminat atunci cand blocul ce trebuie adus nu mai are loc
138. Calculatoarele CISC sunt caracterizate de
- un numar mare de instructiuni, un numar mai mare de noduri de adresare, o putere de
calcul mai ridicata a instructiunilor individuale, registre mai specializate
139. Metoda Hamming se utilizeaza pentru
- corectarea erorilor
140. In cazul sistemului de bus mastering, prioritatile stabilite de unitatea ISP sunt:
