ARHITECTURA CALCULATOARELOR

conf. univ. Iulian BREZEANU

UVT 2014

MotivatiePentru ce studiem arhitectura calculatoarelor?

"Calculatorul se gaseste in centrul tuturor sistemelor de calcul. Fara el, majoritatea disciplinelor de calcul actuale nu ar fi decat ramuri ale matematicilor teoretice. Pentru a fi astazi un profesionist al calculului, nu trebuie in nici un caz sa consideri calculatorul ca o simpla cutie neagra, care executa programele prin magie.

Toti studentii care abordeaza aspecte ale calculului - inclusiv cel ingineresc - trebuie sa cunoasca in detaliu un sistem informatic si componentele sale functionale, cu toate caracteristicile, performantele si interactiunile lor specifice. Implicatiile practice ale acestor cunostinte sunt foarte importante.

Este necesar ca studentii sa inteleaga arhitectura calculatorului pentru ca ei sa poata sa-si structureze un program astfel incat el sa functioneze cat mai eficient pe o masina reala.

Alegand sa foloseasca un anumit sistem, utilizatorul trebuie sa poata fi in masura de a intelege diferentele intre diferitele sale componente, cum a fi - de exemplu - frecventa ceasului UC in raport cu capacitatea memoriei interne"

Arhitectura sau organizare

• Arhitectura - este suma atributelor vizibile pentru programator:- setul de instructiuni, numarul de biti utilizati pentru reprezentarea datelor, mecanismele de I/E, tehnicile de adresare; • Organizarea - modul in care atributele sunt implementate:

- unitatile operationale si interconexiunile dintre ele; aceste detalii hardware sunt transparente pentru programator (semnale de comanda, interfete, tehnologiile pentru memorii etc.).

• aceeasi arhitectura poate avea diferite organizari: - intreaga familie Intel x86 poseda aceeasi arhitectura de baza; - familia IBM System/370 partajeaza aceeasi architectura de baza; - arhitectura comuna ofera compatibilitatea codurilor de program.

Continutul cursului

Continutul cursului

Functie sau structura

• Structura reprezinta maniera prin care sunt conectate componentele.

• Functia evidentiaza rolul diferitelor componente care sunt parti ale unei structuri

Functiile de baza ale unui calculator sunt: - prelucrarea datelor; - stocarea datelor; - transferul datelor;

- controlul datelor.

• Calculatorul este un sistem complex, organizat ierarhic. Pentru descrierea acestei ierarhii se uzeaza de o abordare a structurii de sus in jos (top-down).

Planul preliminar al cursului

Prelegerea 1 Introducere: arhitectura de baza si organizarea calculatorului, functiile de baza ale calculatorului, principalele componente, arhitectura von Neumann. (Pentru a ne reimprospata memoria!) Prelegerea 2 Sistemul de memorie: ierarhia memoriei, memoriile cache, memoria virtuala, gestiunea memoriei. Prelegerea 3 Tehnica pipeline (canalul de instructiuni): organizarea unitatilor pipeline, hazardurile in pipeline, reducerea penalitatilor de salt, strategii pentru predictia salturilor. Prelegerea 4 Arhitecturi RISC: analiza executiei instructiunilor din codul provenit din programele scrise in limbaje de nivel inalt, compilatoare pentru arhitecturile RISC, caracteristicile principale ale arhitecturilor RISC, o comparatie RISC-CISC.

Planul preliminar al cursuluiPrelegerile 5 et 6 Arhitecturi superscalare: paralelism la nivel de instructiune si paralelism la nivel de masina, tehnici hardware pentru perfectionarea executiei, dependentele datelor, politici pentru executia paralela a instructiunilor, limitele arhitecturii superscalare. Prelegerile 7 et 8 Arhitecturi VLIW: conceptul VLIW - avantaje si limite, compilatoare pentru arhitecturi VLIW, arhitectura Merced (Itanium). Prelegerile 9, 10,11 Arhitecturi pentru calculul paralel: programe paralele, performantele calculatoarelor paralele, clasificarea arhitecturilor de calculatoare, retele de procesoare, multiprocesoare, multicomputere, procesoare vectoriale, concordanta cache in arhitecturile paralele. Prelegerea 12 Arhitecturi de joasa putere: consumul de energie in circuitele CMOS, baza conceptuala pentru joasa putere, procesorul Crusoe.

1. Ce este un calculator/sistem de calcul? 2. Arhitectura Von Neumann 3. Aplicatii specifice sau uz universal 4. Reprezentarea datelor si a instructiunilor 5. Executia unei instructiuni6. Unitatea de comanda 7. Sistemul informatic 8. Memoria principala si secundara

Calculatorul electronic Chestiuni fundamentale:

Ce este un calculator?

• Un calculator este o masina care prelucreaza automat date, sub comanda unui program (lista de instructiuni stocata in memorie).

Ce este un sistem de calcul?

• Un sistem de calcul (uneori numit sistem informatic) consta dintr-un calculator si perifericele sale.

• Perifericele calculatorului includ dispozitivele de intrare si de iesire, precum si memoria secundara.

Principii de implementare Calculator cu program extern

Calculator cu program memorat

Input Dev

Output Dev

ArithmeticUnit

TemporaryStorage

Sequencer

Input Dev

Output Dev

MemoryUnit

CPU

ArithmeticLogic Unit

ControlUnit

Calculator cu program extern

Lipsa memoriei principale pentru stocarea programului si a datelor. Consecinte:

- Datele nu pot fi reutilizate. Ele trebuie citite de fiecare data.

- Anumite operatii nu pot lucra cu date diferite. Instructiunile respective trebuie citite de fiecare data.

- Nu se pot executa instructiuni de salt absolut sau conditionat.

- Subprogramele sunt imposibile sau dificil de implementat

• Capacitate redusa

• Stocare temporara pentru operanzi si rezultate

Calculator cu program memorat

RAM (Random Access Memory) Fiecare locatie de stocare este unic identificata printr-o

adresa numerica.• Informatia stocata poate fi regasita utilizand adresa ei;• Timpul de acces este acelasi pentru oricare informatie stocata.

Programul si datele sunt stocate in acelasi spatiu de stocare (memoria principala)

• Operatiile asupra datelor se fac in conformitate cu instructiunile din program

• Datele si instructiunile de program pot fi utilizate in mod repetat.• Spatiul de memorie se utilizeaza eficient• Permite utilizarea in program a instructiunilor de salt, direct sau

conditionat• Implementarea facila a suprogramelor

Introduce memoria principala de tip RAM

Arhitectura Von Neumann Principiile: - datele si instructiunile sunt stocate impreuna in memoria principala (conceptul de program stocat); - continutul memoriei este accesibil la nivel de locatie (adresa locatiei este independenta de continutul acesteia); - instructiunile sunt executate secvential (in ordinea in care sunt stocate in memorie), cu exceptia cazurilor cand ordinea este explicit modificata.

Organizarea (arhitectura) calculatorului este urmatoarea: - unitatea centrala (Central Processing Unit - CPU) – contine:

- unitatea de comanda (Control Unit - CU) - coordoneaza executia instructiunilor;- unitatea aritmetica si logica (Arithmetic/Logic Unit - ALU) - efectueaza operatii aritmetice si

logice; - - memoria (zisa principala, interna sau de lucru).

Conceptele principale von Neumann sunt programul si executia sa

Structura generală a unui calculator electronicArhitectura von Neumann

Arhitecturi de uz general (Von Neumann)

Ansamblul de circuite logice numit unitate centrala (UC sau UCP – unit centrala deprelucrare).poate executa sarcini diferite, in functie de instructiunile din programul (softul) executat.

• Functia principala a unei UC este executia instructiunilor, citite din memoria centrala. • Instructiunile indica UC ce operatii de baza trebuie sa execute (o operatie aritmetica sau logica, un

transfer de date, etc.). • Instructiunile sunt decodificate de CU (unitatea de comanda - UCd), care activeaza diferite

componente pentru actiuni specifice.• Ansamblul de registre al UC reprezinta dispozitive de memorare temporare, utilizate pentru stocarea

datelor utilizate temporar sau a rezultatelor intermediare.

Calculatoarele von Neumann sunt calculatoare de uz general, putand rezolva probleme diferite, in functie de programul executat

Reprezentarea datelor

• In interiorul calculatorului, datele si informatiile de comanda (instructiunile) sunt reprezentate in format binar (sau digital, numeric), prin cele doua cifre: " 0 " et " 1 ".

• Cele doua simboluri de baza sunt reprezentate prin semnale electrice.

• Pentru datele numerice reprezentate in sistem binar, valorile pozitionale sunt puteri ale lui 2: 100101 = 1*2 **0 + 0*2 **1 + 1*2 **2 + 0*2 **3 + 0*2 **4 + 1*2 **5 10110 = 0*2 **0 + 1*2 **1 + 1*2 **2 + 0*2 **3 + 1*2 **4

Numerele binare sunt adunate, scazute inmultite sau impartite direct de catre ALU; nu este necesara conversia preliminara a acestora in numere zecimale.

Instructiunile masina

• UC poate executa numai instructiuni masina.

• Fiecare calculator are un set de instructiuni specifice, care pot fi recunoscute si executate de unitatea sa centrala.

• O instructiune masina este reprezentata printr-o secventa de biti. Aceasta secventa trebuie sa defineasca:

- ceea ce trebuie facut (codul operatiei); -cui i se aplica operatia (adrese operanzi sursa); - unde merg rezultatele (adresa rezultatului);

- cum se continua programul dupa terminarea operatiei.

Instructiunile masina

Reprezentarea unei instructiuni masina:

- codul binar este divizat in campuri, organizate in conformitate cu formatului instructiunii;

- fiecare camp contine o specificatie de instructiune (codop, adrese operanzi etc.);

Tipuri de instructiuni masina• Instructiunile masina sunt de patru tipuri:

- pentru transfer de date intre memorie si registrele UC; - pentru operatii aritmetice si logice; - pentru comanda programelor (test si salt);

- pentru transferuri de I/E.

• Caracteristici importante vizand proiectarea setului de instructiuni: - repertoriul de operatii;- formatul instructiunilor; - dimensiunea spatiului de adresare (numarul de locatii de memorie);

- tipurile de operanzi; - moduri de adresare; - accesul la registre;

Structura generală a unui calculator: unitatea centrala

Unitatea centrală (UC) două componente: unitatea aritmetică şi logică

(UAL), unitatea de comandă (UCd)

UAL - execută prelucrări complexe asupra informaţiilor reprezentate prin date (operaţii aritmetice uzuale - adunare, scădere, înmulţire, împărţire; logice - şi, sau, nu, sau exclusiv ş. a.; de comparare, de rotaţie, de deplasare

UCd – generează, gestionează si sincronizeaza traficul semnalelor de comandă, control si stare între ansamblul UC şi celelalte module funcţionale ale sistemului, pe baza interpretarii secventiale a semnificatiilor instructiunilor dintr-un program memorat

Unitatea centrala: ciclul unei instructiuni

ciclul de execuţie al instrucţiunii: prelucrarea în mai mulţi paşi a unei instrucţiuni de

către UCd: citirea şi interpretarea instrucţiunii - I – ciclu

citirea din memorie a instrucţiunii ce trebuie executată şi depunerea ei în registrul IR al UC;

decodificarea instrucţiunii; calculul adreselor operanzilor implicaţi în instrucţiune

execuţia propriu -zisă a instrucţiunii - E-ciclu aducerea operanzilor din memorie în registrele de uz general

ale UC, pe baza calculului de adrese de mai sus; execuţia propriu-zisă a calculelor de către UAL; depunerea rezultatului în RA, urmată de scrierea lui în memorie.

Unitatea centrala: ciclul unei instructiuni

• Fiecare instructiune este efectuata ca o secventa de mai multi pasi; secventa corespunzatoare executiei unei instructiuni se numeste ciclul instructiunii.

O schema simplificata a ciclului unei instructiuni:

Unitatea centrala: ciclul unei instructiuniCiclul de execuţie al instrucţiunii

Unitatea centrala: ciclul unei instructiuni

memorii (8,16,32,64 biti) destinate păstrării datelor (instrucţiuni, operanzi, rezultate intermediare) tratate prin instructiuni

registrele de uz general pot stoca orice tip de dată, în funcţie de context

registrele specializate pot stoca numai anumite informaţii: registrul contor de program (PC)-conţine adresa de

memorie a instrucţiunii următoare din program registrul de instrucţiuni (IR) - conţine codul binar al

instrucţiunii curente registrul de adrese al memoriei (RAM) - conţine adresa

locaţiei de unde se transfera date (citire din memorie), sau unde se depun date (scriere în memorie);

registrul de date al memoriei (RDM) - conţine data citită/scrisă din/în memorie;

registrul acumulator (RA) - conţine fie unul din operanzii asupra cărora se efectuează calculul, fie rezultatul final al acestuia;

registrul indicatorilor de condiţie (al flag - urilor, IC) - conţine informaţii privitoare la modul cum s-au terminat operaţiile aferente instrucţiunii curente, efectuate de UAL.

registrul de întreruperi (RI)-semnalează UC anumite cereri care sosesc de la echipamentele periferice;

Executia unei instructiuni - exempluUrmatoarele patru instructiuni executa Z:=(Y+X)*3:

Executia unei instructiuniPrima instructiune:

Executia unei instructiuniA doua instructiune:

Executia unei instructiuniA treia instructiune:

Executia unei instructiuniA patra instructiune:

Unitatea centrala: unitatea de comanda

Unitatea centrala: unitatea de comanda

Tehnicile de implementare ale unitatilor de comanda: 1. Comanda cablata; 2. Comanda microprogramata.

Sarcina unitatii de comanda este de a face sa lucreze impreuna (adica sincronizat) si corect elementele interne ale unitatii centrale si interfetele externe ale acestora.

Sistemul de calcul

Ansamblul unitate centrala + memorie centrala formeaza un sistem de calcul (sau sistem informatic), care constituie “inima” calculatorului.

Ansamblul memorie secundara + dispozitivele de I/E formeaza perifericele.

Comunicatia intre diferitele componente ale sistemului se efectueaza de obicei utilizand una sau mai multe magistrale.

Memoriile unui sistem de calcul

• Memoria centrala este utilizata pentru a stoca programele si datele care sunt tratate in acel moment de catre UC.

• Memoria secundara este utilizata pentru a stoca pe termen lung cantitati mari de date si de programe.

Pentru a putea fi tratate de UC, datele si programele stocate in memoria secundara trebuie sa fie mai intai incarcate in memoria centrala.

Trasaturi tipice:- memoria centrala este rapida si de talie redusa; - memoria secundara este relativ lenta si cu o dimensiune foarte mare.

• Caracteristicile cele mai importante ale unei memorii sunt viteza, talia (dimensiunea) si costul - ele sunt principalele constrangeri impuse tehnologiilor untilizate pentru implementare.

Caracteristicile unitatii de memorie  

Timpul de acces = timpul necesar obţinerii unui cuvânt de informaţie de la memoria respectivă (cuvânt de tip bit, octet, dublu octet, etc.);

- ta = timpul (în [ms] sau [ns]) de când o unitate master lansează o comandă până când primeşte informaţia de la aceasta;

- ta depinde de caracteristicile fizice ale mediului de memorare (CI, suport magnetic, optic, etc.) de tehnologia de fabricare (CI tip TTL, CMOS, NMOS, etc.), de modul de acces la memorie (aleatoriu sau serial);

Rata de acces = inversul timpului de acces [cuvinte/sec]

Timpul unui ciclu = timpul între două accese succesive la unitatea de memorie şi reprezintă timpul de când o unitate master lansează o comandă spre unitatea de memorie şi până când poate lansa o nouă comandă la aceeaşi unitate de memorie.

Obs: tc ≥ta , de obicei inecuaţia este strictă; in general ta este mai restrictiv ca tc pentru că timpul cât unitatea master aşteptă după lansarea unei comenzi către unitatea de memorie este un timp mort pentru unitatea master. În intervalul de timp rămas tc-ta , unitatea master poate lucra în paralel cu unitatea de memorie (poate iniţia un nou acces la o altă unitate de memorie).

Rata de transfer = inversa tc , reprezintă cantitatea maximă de informaţie ce poate fi transferată la/de la unitatea de memorie într-o secundă [cuvinte/sec]

Caracteristicile unitatii de memorie Capacitatea de memorare - numărul locaţiilor de

memorie ale unităţii de memorie. este dată de numărul liniilor de adresă cu care se adresează memoria respectivă

(în cazul memoriilor CI). depinde de tehnologia de fabricaţie se măsoară în cuvinte de informaţie memorată (bit, octet, dublu octet); poate fi

exprimată în multipli de cuvinte (puteri ale lui 2) : 1kcuv = 210 cuvinte = 1024 cuvinte; 1Mcuv = 220 cuvinte = 210 k cuvinte; 1Gcuv = 230 cuvinte.

Costul unităţii de memorie – se exprimă prin costul unitar de memorare a unui bit de informaţie

include pe lângă costul celulele de memorie propriu-zise, şi costul circuitelor de acces la aceste cuvinte

cu cât memoria este mai rapidă, cu atât costul unitar este mai mare.

Modul de acces – arată ordinea în care informaţia poate fi accesată (serial sau paralel). Dacă locaţiile de memorie pot fi accesate în orice ordine, iar timpul de acces este

independent de locaţia accesată memoria se numeşte memorie cu acces aleator (ex. toate CI de memorie fie ele ROM, RAM, SRAM, DRAM).

Dacă locaţiile de memorie pot fi accesate doar într-o secvenţă predeterminată, iar timpii de acces nu mai sunt independenţi de locaţia accesată, memoria se numeşte memorie cu acces serial (ex; banda magnetică, discul magnetic (hard-diskul), etc.).

Memoria principala

• Memoria centrala poate fi privita ca un ansamblu de celule de stocare (locatii), fiecare din acestea putand fi folosita pentru a stoca un cuvant. • Fiecarei celule i se asigneaza o adresa unica; adresele sunt numerotate

secvential: 0.1.2… • Timpii de acces sunt aceeasi pentru oricare locatie

• In memorie sunt plasate mai multe registre: • registrul de adrese (pentru stocarea adresei cuvantului care trebuie citit/scris)• registrul de date (pentru stocarea datelor care trebuie citite/scrise)• decodificatorul de adrese.

• Comenzile pentru memorie sunt elaborate de unitatea de comanda a memoriei.

Memoria principala

• Tehnologia cea mai larg raspandita pentru implementarea memoriilor centrale este memoria cu semiconductori.

• Tipul comun de memorie cu semiconductori este memoria cu acces selectiv (Random Acces Memory - RAM).

• Informatia stocata intr-o memorie cu semiconductori de tip RAM se pierde la intreruperea alimentarii cu energie electrica.

Memoria secundara

Harddisk (HDD - discul dur):

Datele sunt inregistrate pe suprafata unui disc metalic rigid, acoperit cu material magnetic.

• Discurile si circuitele de comanda sunt de obicei montate impreuna in interiorul unei incinte inchisa ermetic (pentru protectia discurilor contra factorilor poluanti, cum ar fi particulele de praf sau fum).

• Mai multe discuri (platane) sunt montate de obicei pe un ax de antrenare comun. Fiecare platan are propriile sale capete de citire/scriere (cate unul pentru fiecare fata).

• Caracteristici principale: - acces direct; - acces rapid: timpi de pozitionare - 10 ms (? actualizare), debit de transfer - 5 MB/s (? actualizare)- capacitate mare de stocare (de la sute de MB la cativa TB)

Memoria secundaraMemoriile optice

• Discul compact (CD-ROM): cu ajutorul unui fascicul laser de mare putere, pe suprafata discului sunt imprimate “santuri” microscopice care inregistreaza informatia numerica. Cand un alt fascicul laser, de mica putere, baleiaza suprafata, intensitatea luminii reflectate se modifica la intalnirea unui “sant”. Modificarea este detectata de un element fotosensibil si este convertita in semnal numeric.

• Caracteristici principale:. - capacitate mare de stocare (sute MB – cativa GB);- demontabil; - inalterabil;

- timp de acces mare (pana la 1/2 secunda).

• Discul CD-WORM (Write-Once Read-Many): pentru imprimarea modelului retelei de “santuri” se utilizeaza un fascicul laser de intensitate modesta, plasata in unitatea de comanda a discului.

- recomandat pentru arhivarea unor volume mari de date.

• Discul CD-RW (optic reinscriptibil): o combinatie de tehnologie laser si tehnici magnetice. - poate fi scris in mai multe reprize sau rescris; - fiabilitate ridicata si ciclu de viata mai mare decat al discului magnetic.

Resursele de intrare/iesire• Dispozitivele de intrare si de iesire furnizeaza utilizatorilor mijloace de

acces la calculator. • Anumite dispozitive de I/E functioneaza de asemenea ca interfete ale

sistemului de calcul cu alte sisteme. O astfel de interfata se compune in mod obisnuit din convertoare de semnale (analog-numerice sau numeric-analogice)

Dispozitive de intrare tipice:

Resursele de intrare/iesire -continuare

Advanced Architectures

Sa facem calculatoare mai bune

Calculatoare cu performante mai bune

Ce inseamna performanta calculatorului:

Calcul mai rapid Capacitate de stocare mai mare, in special pentru

memoria principala RAM Interfata utilizator prietenoasa Executia facila a programelor

Calculatoare cu performante mai bune:calcul mai rapid

Abordare la nivel de componente

Abordarea la nivel de organizare

Abordarea la nivel arhitectural (setul de instructiuni)

Calcul mai rapid : abordare la nivel de componente

Componentele miniaturizate sunt mai rapide Timpi de comutare mici si intarzieri reduse Limitari ale cresterii gradului de integrare, datorate densitatii

pe chip, prb. disiparii energiei termice si vitezei electronilor Solutii:

Circuite optice Bio-circuite

Calcul mai rapid : abordare la nivel de organizare

Implementarile hardware ale particularitatilor arhitecturale:

Procesor(CPU-ALU) Algoritmi mai rapizi de adunare, inmultire, impartire Conexiunile la magistrala si latimea ei de banda Tipuri de registre

Memoria principala Circuite mai rapide

Bank-uri de memorie Memorii cache

Otimizarea fluxurilor de I/E

Calcul mai rapid : abordare la nivel arhitectural

Echilibrarea componentelor sistemului de calcul (eliminarea gap-urilor):

Procesorul

Sistemul de memorie

Sistemul de I/E

System Parameters

Secondary Storage• Files• Program Library

[C/E Ratio]

I/O Bus

Memory Bus

Data Rate(B)[MB/Sec]

Capacity(C): [MB] Cycle Time

Memory Bandwidth(BW): [MB/Sec]

Instruction Execution Unit

CPU• ALU• Instruction Interpreter• Registers

Memory• Program/data• Work Area• I/O Buffer

[E/B Ratio]

Capacity: [MB]

CPU – unitatea centrala Viteza de executie a instructiunilor - MIPS/MFLOPS MIPS poate fi inselatoare:

• 8-bit 1 MIPS versus 32-bit 1 MIPS

Memoria Latimea de banda (bandwich - BW) = cicli/sec x bytes/acces Pentru un ciclu de acces dat, dublarea BW implica dublarea

dimensiunii cuvantului de memorie

Memoria secundara Rata de transfer - nu reprezinta complet performanta dispozitivului Tehnologia, latenta, timpul de pozitionare etc.

Parametrii sistem

Relatiile dintre parametrii sistem

Constatare 1: Ciclul de acces la memorie este mult mai lung decat ciclul de ceas al CPU Solutii de proiectare:

• registri CPU mari si numerosi• cache• adresarea incrucisata pe mai multe module de memorie

Constatare 2: Rata de transfer in operatiile de I/O este mult mai mica decat banda de trecere a memoriei (BW) – necesitatea unor capacitati mari de stocare Solutii de proiectare:

• memorii RAM cu capacitati mari• sistem de stocare virtual

ConcluziePentru a creste viteza de executie MIPS (E), trebuie crescuta corespunzator si capacitatea memoriei (C) – raportul C/E trebuie sa ramana constant!

Ex: Pentru a face de 10 ori mai rapid un sistem cu 1MIPS CPU si 1MB memorie, acesta va trebui sa aiba 10MB memorie (la 10 MIPS!)

Cerinte: O rata de transfer a datelor ridicata

Nevoia unui raport constant E/B Pentru a creste B, trebuie transferate blocuri mari

Nevoia de a mari C Utilizarea multiprogramarii pentru a reduce timpii de asteptare ai CPU pentru

efectuarea acceselor la memorie Nevoia de a mari C

Relatiile intre parametrii sistem

Constatare 3: indiferent de capacitatea de stocare a memoriei RAM (C), este nevoie de acces rapid la resursele secundare de stocare (memoria externa)

Concluzie

Pentru a obtine o viteza MIPS ridicata(E), este nevoie de echilibrarea rapoartelor C/E si E/B .

Calculatoare mai rapide : Procesorul

Viteza procesorului este limitata de doua cauze majore:

• Interactiunea cu memoria principala, a carei viteza este mult mai mica decat cea a procesorului – memory gap

– Instructiunile si datele din program sunt stocate intotdeauna in memoria principala

– Instructiunile si datele necesare procesarii curente sunt transferate si stocate in registrii procesorului

– Uzual, nu este posibil de a dipune de suficienti registri, astfel incat sa se minimizeze sau sa se evite traficul cu memoria principala

• Deficitul de resurse hardware din interiorul procesoarelor– Deficitul de registri cauzeaza un trafic intens cu memoria– Deficitul de interconexiuni limiteaza viteza procesorului– Deficitul de unitati functionale interne si de interconexiuni ale acestora

limiteaza viteza procesorului

Calculatoare mai rapide: Interactiunea cu memoria

In cazul in care procesorul are un singur registru de instructiuni (Instruction Register - IR):

o singura instructiune poate fi tratata pentru executie de CPU nu pot fi executate concurential mai multe instructiuni

In cazul in care procesorul are un singur registru pentru stocarea datelor (Data Register):

dupa executia unei instructiuni rezultatul trebuie salvat in memoria principala, astfel incat noua data, ceruta de executia urmatoarei instructiuni, sa poata fi stocata in Data Register

Calculatoare mai rapide: Solutii

Multiplicarea resurselor hardware cu functii similare Mai multi registri de instructiuni si de date (executia concurenta a instructiunilor si

reducerea traficului cu memoria) Mai multe circuite sumatoare, pentru executia concurenta a adunarilor

Un sumator pentru calculul adresei de memorie si altul pentru insumarea datelor

Multiplicarea resurselor hardware cu functii diferite Mai multe functii pot fi executate concurent: operatii aritmetice (+. *, / ), operatii logice, etc

Diferite tipuri de informatii pot fi stocate in acelasi timp in CPU

Divizarea resurselor hardware astfel incat fiecare diviziune sa poata opera independent, in paralel cu celelalte Mai multe instructiuni pot fi executate concurent,in diferite faze Calculele pot fi executate concurent, in diferite faze

Furnizarea mai multor cai diferite de prelucrare in cadrul procesorului Informatiile pot circula in procesor pe cai alternative Apar oportunitati pentru operatii concurente

Calculatoare mai rapide: restrictii

Viteza de lucru a memoriei principale este mult mai mica decat cea a CPU Limiteaza viteza CPU Limiteaza viteza sistemului

Capacitatea memoriei principale nu este totdeauna suficienta Creste traficul intre memoria principala si cea secundara Limiteaza si mai mult viteza sistemului

Calculatoare mai rapide: solutii pentru memoria principala

Mai multa capacitate de stocare in CPU Registri de uz general

Cache Memorie de mare viteza, cu capacitate redusa, plasata intre CPU

si memoria principala Informatiile (instructiuni si date) cerute pentru executie de CPU sunt

transferate mult mai rapid din cache decat din memoria principala Sunt necesare anumite mecanisme de predictie

Bankuri multiple de memorie Bankurile pot fi accesate simultan Bankurile pot fi accesate intr-o secventa

Calculatoare mai rapide: sistemul Input/Output

Procesele de intrare/iesire sunt cele mai lente din sistemul de calcul

In sistemele cele mai simple, CPU asteapta pur si simplu ca resursa I/O lenta sa-si termine operatia

- Se pierd un numar semnificativ de cicli masina (cicli CPU)

In sistemele de calcul avansate, sistemul Input/Output executa el insusi, independent de CPU, operatiile de I/O, in timp ce procesorul executa alte activitati de prelucrare, care nu sunt dependente de informatia I/O aflata in transfer curent - Sistemele de I/O trebuie sa aiba capacitati de procesare extinse

Calculatoare mai rapide: memoria virtuala Pentru un sistem de calcul, capacitatea memoriei principale este

limitata de: dimensiunea registrilor de adresa largimea magistralei de adrese Costuri

Solutie: Stocarea alternativa secundara- Hard Disk, CDROM,…

Mult mai ieftina decat memoria principala Mult mai lenta decat memoria principala

Stocarea alternativa alimenteaza iluzia unei capacitati de stocare mare, dar accesul la date este lent.

Solutie: Sistemul de memorie virtuala

informatia din memoria secundara, ceruta de CPU, va fi plasata in memoria principala in avans fata de momentul prelucrarii, atunci aceasta va fi transferata cu viteza memoriei principale

- pentru utilizatori, capacitatea memoriei principale va aparea extinsa la dimensiunile memoriei virtuale

Calculatoare mai rapide: sisteme de calcul prietenoase

Utilizare prietenoasa Limbaj masina usor de utilizat Limbaje de nivel inalt

Compilare facila Usurinta compilatorului de a genera codul masina echivalent

programului de nivel inalt Selectia instructiunilor masina adecvate Selectia registrilor gazda pentru variabilele din programul de nivel inalt

Rezumat• Calculator = Unitate centrala + Memorie centrala • Sistem de calcul = Calculator + Periferice • Unitatea centrala executa instructiuni (stocate impreuna cu datele

in memoria centrala). • Calculatoarele Von Neumann sunt calculatoare programabile, de

uz universal. • Datele si instructiunile sunt reprezentate in format binar. • Un set de instructiuni masina este specific fiecarui tip de

calculator. Instructiunile sunt organizate dupa un anumit format. • O instructiune este executata printr-o succesiune de pasi, numita

ciclul instructiunii. • Programele si datele care sunt tratate la un moment dat sunt stocate

in memoria principala (centrala). Aceasta este organizata ca un ansamblu de celule de stocare - locatiile, fiecare avand o adresa numerica unica.

• Memoria secundara poate fi discul dur, discheta, banda magnetica sau discul optic.

• Dispozitivele de intrare/iesire furnizeaza mijloacele pentru schimbul de informatii intre calculator si utilizatori.

Implementation of Algorithms

Three Different Ways of ImplementationProgram(Software)Microprogram(Firmware)Logic Circuits(Hardware)

Implementation of Algorithms: Program

Load X Read memory location X into MBR and load it into AC

ADD Y Read memory location Y into MBR and add it with AC and store the result into AC

+ AC

Memory

MBR

ADD X, YAdd two numbers stored in the memory at the locations addressed by X and Y, and stored the sum in the register.

Implementation of Algorithms: Microprogram

Read memory location X into MBR F,GMove it to ALU APass ALU(don’t add) DMove the result to AC BRead memory location Y into MBR F,GMove MBR and AC to ALU and + A, C, EMove the result into AC B

+ AC

Memory

MBR

A

B

C

D

EF

MAR

G Gates for control signal

Implementation of Algorithms: Logic Circuit

+ AC

Memory

MBR

A

B

C

D

EF

t0 Apply read control signal to memory with address X, and open the gate F to store into MBR

t1 Apply control signals to D to pass ALU, and B to store into ACt2 Apply read control signal to memory with address Y, and open

the gate F to store into MBRt3 Apply control signals to A and C. Also apply control signal to E

to add, to B to store the result

Comparison of Implementation Methods

Software Firmware HardwareSpeed slow moderate fast

Cost low medium high

Modification cheap medium expensive

Expandability easy medium difficult

Generatii de calculatoare

Generations of Computers(~1951): Prehistoric Wheel - Pascal, Leibnitz

numerical calculations 9 1

8 2

7 3 4 6 5

0

• Punched Card – Hollerith, Hollerith Code– Calculations and data processing

• Electronic Computer– ENIAC(Electronic Numerical Integrator and Calculator)– The first Stored Program Computer– 18,000 vacuum tubes, over 30t, 1,500 ft2

– 10 decimal digits calculation takes 0.2msec

Generations of Computers(1951~1958): First Generation Computers

Vacuum tubes are used to build circuits Magnetic drum is used for main memory Stored Program Computer Sequential storage of programs

PC(Program Address Counter) Development of Machine Language, Symbolic Assembly

Language, and FORTRAN High-level Language Assemblers and compilers

UNIVAC I for census

Generations of Computers(1959~1964): Second Generation Computers

Use of Semiconductor Devices for circuits Transistors and Diodes

Magnetic Core is used for Main Memory Invention of Printed Circuit Board(PCB) Improvements of arithmetic algorithms

ADD time reached the theoritical lower bound in 1964

Generations of Computers(1964~1969): Third Generation Computers

Integrated Circuits(IC) are used to build processors Small Scale IC(SSI)

Earlier computers used magnetic core for main memory, but later computers used semiconductor memories

Employ General Purpose Registers(GPR) in CPU General Purpose Instruction Set(CISC) Microprogrammed Control Unit Multiprogramming and Time-sharing Computer Family design

IBM S/360 family, CDC 6000 series Minicomputers

Multiprogramming and Time-Sharing

Job 1

Job 2

Job 3

Job 4

. . .

Memory

CPU

Multiprogramming

P1 P2 P3 …… Pn P1 P2 P3 …… Pn P1 P2 P3 ...

Time-Sharing

CPU time

Generations of Computers(1970~ ?): Fourth Generation Computers

Medium Scale Integrated Circuits(MSI) Semiconductor Memories High performance memory systems

Virtual Storage System Cache Memory

Microprogrammable computers Supercomputers

Pipelining, vector processing Cray

Microcomputers Apple II, IBM PC/XT, PC/AT, PS2, Macintosh

Main Frame Computers-IBM S/370

Generations of Computers: Future Generation Computers

Beginning of 1980

– Advancement of VLSI technology – Advancement of parallel computer architectures

Large number of processors in a computer system => 10’s~ 10K’s processors

- Interconnection of processors and memories for fail- proof communications is very difficult

- Maximum utilization of so many hardware resources is very difficult

SISTEMUL DE MEMORIE

1. Componentele sistemului de memorie 2. Ierarhia memoriei 3. Memoria cache 4. Organizarea memoriei cache 5. Algoritmi de inlocuire6. Strategii de scriere7. Memoria virtuala

Copyright © 2013 Elsevier Inc. All rights reserved

Processor MemoryAddressMemWrite

WriteDataReadData

WE

CLKCLK

• Performanta calculatorului depinde:– de performanta procesorului– de performanta sistemului de memorie

Memory Interface

Introducere

• Memoria centrala: acces rapid si selectiv, scumpa, plasata aproape (dar nu in interiorul) unitatii centrale.

Este utilizata pentru stocarea programelor si datelor care sunt manevrate la un moment dat de catre UC.

• Memoria secundara: lenta, acces direct, ieftina, plasata mai departe de unitatea centrala.

Componentele sistemului de memorie

Tehnologia cu acces aleator (random): - timpul de acces este acelasi pentru oricare din locatii;

• DRAM: Dynamic Random Access Memory- inalta densitate, putere redusa, ieftina, lenta (~1transistor/bit)

- trebuie “reinprospatata” (refresh) regulat • SRAM: Static Random Access Memory

- densitate scazuta, putere mare, scumpa, rapida (~4-6 transistori/bit)- continutul nu se pierde “niciodata”

Tehnologia cu acces non-aleator (non-so-random):- timpul de aces variaza de la locatie la locatie si de la un moment la altul;

• Example: discuri, unitate de banda, CDROM

Obs.: Vor fi tratate in continuare tehnologiile cu acces aleator (memoria principala DRAM si memoria cache SRAM)

Tehnologii pentru memorii

Parametrii unei memorii

Capacitatea – volumul global de informatie care poate fi stocat (in biti);

Timpul de acces - intervalul de timp dintre cererea de citire/scriere si disponibilitatea datelor;

Durata ciclului (ciclul de acces) – intervalul de timp minim intre doua accese succesive (Tc =1/f, f - frecventa ceasului procesorului);

Debitul – volumul de informatii schimbate in unitatea de timp (biti/secunda);

Nonvolatilitatea – aptitudinea memoriei de a conserva datele atunci cand ea nu mai este alimentata electric.

Latenta – timpul de intarziere in adresarea unui bit (intersectia unei row cu o column) :Ta =Tc +Tl

Ex: Tadram = 60 ns = 35ns Tc + 25 ns Tl. Daca frecventa procesorului este ridicata si Ta este mare, se introduc cicli de

asteptare Tw (wait state). Ex.: daca f = 200 MHz si Tadram = 60 ns, atunci Tc = 5 ns si se introduc 11 cicli Tw. Performanta sistemului scade.

Circuite de memorie RAM

Circuitele RAM se prezinta sub forma unor barete de memorie:

SIMM (Single Inline Memory Module)

30 si 72 conectori (8b, respectiv 32b), invechite (pana la Pentium);

DIMM (Dual Inline Memory Module)

2x84 conectori (64 b). Varianta SO DIMM (Small Outline DIMM), destinata portabilelor, are 144 sau 77 conectori (64b, respectiv 32b);

RIMM (Rambus Inline Memory Module, RD-RAM sau DRD-RAM)

184 conectori (64b), protejate de un film termic pentru disiparea caldurii. Varianta SO RIMM (Small Outline RIMM), destinata portabilelor, are 160 conectori (64b).

Evolutia memorilor DRAM DRAM (Dynamic RAM)

matrice de biti, 1bit = 1 tranzistor cuplat la un condensator Acces in rafala (burst mode) la 4 date consecutive (ex: 5-3-3-3 cicli memorie)

DRAM FPM (Fast Page Mode) paginarea - acces la datele situate pe acceasi coloana, prin modif. numai a nr. de linie

DRAM EDO (Extended Data Out) Hyper-page - rafala 5-2-2-2, astazi perimata

SDRAM (Synchronous DRAM) lectura datelor sincrona cu magistrala placii de baza (EDO si FPM erau asincrone, cu ceas propriu) rafala 5-1-1-1, frecventa <150 MHz, Ta > 10 ns

DR-SDRAM (Direct Rambus DRAM sau RDRAM) 16 biti, 800Mhz, banda de trecere 1,6 Go/s

DDR-SDRAM (Double Data Rate SDRAM) dubleaza frecventa de citire/scriere la aceeasi frecv. externa (indicativul PCxxxx indica debitul in Mo/s)

DDR2- SDRAM Tehnologia QDR (Quadruple Data Rate sau quad-pumped) – canale distincte pentru citire/scriere 240 conectori (184 la DDR)

DDR3 SDRAM Consum de energie diminuat cu 40% fata de DDR2, debit teoretic >10Go/s, latenta mare (comparabila cu

DDR2)

Tablou recapitulativ circuite RAM

Problemele sistemului de memorie

• Cerinte de performanta ? capacitate mare - pentru a stoca programe de mari

dimensiuni si volume mari de date, care vor fi prelucrate de CPU.viteza de transfer - la modul ideal, compatibila cu cea a

procesorului.ieftina – pret per bit cat mai mic

• Probleme de performanta ?

memoriile sunt cu mult mai lente decat (micro)procesoarele !

• Constrangeri:- daca memoria este mai mare, atunci este mai lenta; - daca memoria este mai rapida, atunci costul pe bit este mai mare.

Copyright © 2013 Elsevier Inc. All rights reserved.

Argument pentru o ierarhie a memoriei

Processor – memory gap

Solutii pentru memory gap

Solutia I:Constructia unui sistem care combina in memoria centrala o prima

componenta de capacitate mica, dar rapida, cu o a doua, de mare capacitate, dar lenta. Acest sistem sa se comporte (in majoritatea timpului) ca o memorie rapida de mare capacitate.

Solutia 2:Extinderea sistemul pe doua nivele de mai sus intr-o ierarhie pe mai

multe nivele, incluzand si memoria secundara (in special discurile).

Eficacitatea unei astfel de ierarhii se bazeaza pe o proprietate a programelor numita principiul localitatii.

Principiul localitatiiIn timpul executiei unui program, referintele la memorie efectuate de

procesor, atat pentru instructiuni cat si pentru date, au tendinta de a se grupa

Un segment de program activ efectueaza referinte repetate spre un ansamblu redus de instructiuni (cicluri, subprograme) si de date (componentele unor structuri de date, variabile locale sau parametri din stiva).

• Localitatea temporala Daca un articol de memorie este referit, el va fi foarte probabil referit si in viitorul

apropiat.

• Localitatea spatiala Daca un articol de memorie este referit, este foarte probabil ca si articolele situate la

adrese apropiate sa fie referite in viitorul apropiat.

Ierarhia memoriei

Technology Price / GB AccessTime (ns)

Bandwidth(GB/s)

Cache

Main Memory

Virtual Memory

CapacitySpe

ed

SRAM $10,000 1

DRAM $10 10 - 50

SSD $1 100,000

25+

10

0.5

0.1HDD $0.1 10,000,000

Adapted from Hennessy and Patterson, Computer Architecture: A Quantitative Approach, 5th ed., Morgan Kaufmann, 2012.

Ierarhia memoriei 1. Registrele procesorului:

- capacitate 32 registre de 32 biti fiecare = 128 B - timpi de acces = cateva ns

2. Memoria cache on-chip: - capacitate = 8 la 32 KB- timpi de acces = ~10 ns

3. Memoria cache off-chip: - capacitate = sute de KB- timpi de acces = zeci de nanosecunde

4. Memoria centrala: - capacitate = cativa Gbytes - timpi de acces = ~100 ns

5. Disc dur: - capacitate = sute de Gbytes - timpi de acces = zeci de ms

Mecanismul de lucru in ierarhia memoriei

Localitatea temporala• Daca un articol de memorie este referit, el va fi foarte probabil referit si in viitorul

apropiat.Deci: Se pastreaza cat mai aproape de procesor cele mai recent accesate date

Localitatea spatiala• Daca un articol de memorie este referit, este foarte probabil ca si articolele situate la

adrese apropiate sa fie referite in viitorul apropiat. Deci: Se transfea in memoria de nivel inalt blocuri formate din zone continui

de cuvinte apartinand memoriei de nivel scazut

Ierarhia memoriei - principii de operare

la un moment dat, informatiile sunt copiate numai intre doua nivele adiacente:

• Nivelul inalt - cel situat cel mai aproape de procesor- capacitate mica, rapid, utilizeaza cea mai scumpa tehnologie• Nivelul scazut - cel situat mai departe de procesor- capacitate mare, lent, utilizeaza tehnologii mai ieftine

blocul:- cea mai mica unitate de informatie care poate fi transferata intre

doua nivele ale ierarhiei

Ierarhia memoriei - terminologie• Hit: gasirea datei intr-un bloc de pe nivelul inalt (ex: blocul X)

• Rata hiturilor: proportia acceselor efectuate pe nivelul superior, din total accese la memorie • Timpul per hit: timpul de acces pe nivelul inalt, constand in timpul de acces la SRAM + timpul de determinare a unui hit/miss

• Miss: gasirea datei intr-un bloc de pe nivelul inferior (ex: blocul Y) • Rata missurilor = 1 - (rata hiturilor) • Penalitatea de miss = timpul necesar pentru a transfera un bloc pe nivelul superior + timpul de furnizare al blocului catre procesor

Timpul per hit << Penalitatea de miss

Ierarhia memoriei - valori tipice parametri

Tendinte tehnologice Capacitatea VitezaCircuit logic: 2x in 3 ani 2x in 3 aniDRAM: 4x in 3 ani 1.4x in 10 aniDisk: 2x in 3 ani 1.4x in 10 ani

Ierarhia memoriei - controlul transferului

Cheia succesului unei ierarhii de memorie consta in a distribui datele si instructiunile in acest spatiu in asa maniera incat, in majoritatea timpului, ele sa fie disponibile - atunci cand este necesar - la nivelele superioare ale ierarhiei.

• Datele continute in registre se afla sub comanda directa a compilatorului sau a programatorului in limbaj de asamblare.

• Continutul celorlalte nivele ale ierarhiei este controlat automat: - transferul datelor/instructiunilor in memoria cache este executat sub comanda hardware; - traficul intre memoria centrala si nivelele inferioare este comandat de sistemul de operare (cu contributia hardului).

Ierarhia memoriei calculatoarelor moderne

Memoria cacheMemoria cache este o memorie rapida (de tip SRAM), de capacitate

mica, care pastreaza copii ale informatiilor din memoria centrala recent utilizate .

Ea functioneaza intr-o maniera transparenta pentru programator, deciziile privind ce valori vor fi alese pentru a fi conservate sau inlocuite fiind luate automat.

Memorii cache separateAlternativa la un cache unificat (pentru date si instructiuni) este cea in doua

parti (una dedicata instructiunilor iar cealalta datelor)

• Avantajele memoriilor cache unificate: - pot ameliora echilibrul de sarcina intre instructiuni, date si dinamica executiei unui program; - proiectarea si implementarea sunt mai adecvate pentru piata.

• Avantajele memoriilor cache separate (arhitecturile Harvard): - se elimina concurenta pentru cache intre faza de tratament si executie a instructiunii (fetchul unei instructiuni se poate face in paralel cu accesul la memorie efectuat de unitatea de comanda pentru executia unei alte instructiuni).

Memoria cache

• Procesorul functioneaza la frecventa sa de baza (ridicata) numai atunci cand piesele (datele) din memorie de care are nevoie se gasesc in memoria cache.

• Performanta globala a sistemului depinde esential de proportia acceselor la memorie care pot fi satisfacute de cache:

un acces la un articol plasat in cache: hit. un acces la un articol care nu este plasat in cache: miss.

• Procentul tuturor acceselor la memorie satisfacute de cache: rata hiturilor (proportia succeselor)

• Procentul tuturor acceselor la memorie nesatisfacute de cache: rata missurilor (proportia esecurilor)

Rata missurilor intr-o cache bine proiectata trebuie sa fie de cateva procente

Memoria cache

• Spatiul memoriei cache (~ zeci, sute KBytes) este cu mult mai mic decat cel al memoriei principale (~ sute, mii MBytes);

• Articolele de memorie trebuie sa fie plasate in cache pentru a fi disponibile cand (si preferabil numai atunci cand) ele sunt necesare.

Cum poate fi satisfacuta aceasta cerinta?

Raspunsul este: localitatea

In timpul executiei unui program, referintele la memorie efectuate de procesor, atat pentru instructiuni cat si pentru date, au tendinta

de a se grupa.

Memoria cache - probleme ale proiectarii

Proiectantii unei ierarhii generice a memoriei trebuie sa rezolve urmatoarele probleme:

• P1: Cum va fi plasat un bloc pe nivelul inalt (plasamentul blocului);• P2:Cum este gasit un bloc plasat pe nivelul superior (identificarea

blocului);• P3:Ce bloc trebuie inlocuit la un miss (inlocuirea blocului);• P4:Ce se intampla la scriere (strategia de scriere).

In cazul memoriilor cache, problemele se pot reformula:

• Cate module cache? • Cum se determina un hit sau miss la operatia de citire? • Daca avem un miss si nu mai exista locuri pentru un nou plasament in

cache, ce informatie trebuie inlocuita? • Cum se pastreaza coerenta intre cache si memoria centrala la operatia

de scriere ?

Organizarea memoriei cache Exemplu pentru un cache de 64 Kbytes:

• transferul de date intre cache si memoria centrala se face prin blocuri de 4 bytes; • memoria cache este organizata in linii de 4 bytes; • memoria centrala are 16 Mbytes; fiecare byte este accesibil printr-o adresa de 24 de

biti (2**24 = 16M).

Rezultate: - memoria cache se compune din 2**14 linii (16K)

- memoria centrala se compune din 2**22 blocuri (de 4B).

Intrebari: - cand se introduce un bloc din memoria centrala in cache, unde (pe ce linie) trebuie el plasat? - cand cautam continutul unei anumite adrese de memorie:

- pe ce linie de cache trebuie sa cautam? - cum putem sti daca am gasit informatia corecta (hit) sau nu (miss)?

Solutii:

Organizarea directa Organizarea asociativa Organizarea integral asociativa

Organizarea directa a memoriei cache (direct mapping)

• Blocul de memorie este plasat pe o linie cache unica, aleasa in functie de adresa din memoria interna a blocului respectiv.

• Adresa de memorie este considerata a fi compusa din trei campuri:

1. Partea mai putin semnificativa (2 biti in exemplul nostru) identifica byte-ul in bloc;

2. Restul adresei (22 biti in exemplul nostru) identifica adresa blocului in memoria centrala; pentru logica de control cache, aceasta parte este interpretata ca avand doua campuri: 2a. Partea mai putin semnificativa (14 biti in exemplul nostru) indica linia din

cache; 2b. Partea cea mai semnificativa (8 biti in exemplul nostru) reprezinta o

eticheta (tag), care va fi stocata in cache pe linia selectata. Etichetele permit a face distinctia intre blocurile care se potrivesc pentru stocare pe aceeasi linie cache.

Organizarea directa a memoriei cache(direct mapping)

• Daca avem un miss, blocul va fi plasat pe linia cache care are adresa indicata de campul de 14 biti ai adresei de memorie respective:

Avantaje: - simpla si ieftina; - campul eticheta este scurt; bitii acestuia trebuie stocati, dar ei nu sunt utilizati pentru adresarea memoriei cache (comparati cu tehnicile urmatoare);

- accesul este foarte rapid.

Dezavantaje: - datele unui bloc sunt plasate intr-o locatie fixa din cache. Rezulta ca o linie din cache va trebui inlocuita de fiecare data cand este referit un alt bloc de memorie care se potriveste pe acesta linie, fara a mai verifica statutul altor linii din cache (care pot fi libere).

Acest lucru poate produce o rata scazuta a hit-urilor, in timp ce numai o mica parte a modului cache este utilizata eficace.

Organizarea directa a memoriei cache (direct mapping)

Organizarea asociativa (set associative mapping)

• Un bloc de memorie este plasat pe oricare din liniile unui ansamblu.• adresa ansamblului este determinata de adresa de memorie interna a blocului,

insa linia din interiorul acestuia poate fi oricare.

• Cand un bloc trebuie trensferat in cache, linia ansamblului pe care va fi el plasat va fi desemnata de un algoritm de inlocuire

• Logica cache interpreteaza adresa de memorie ca fiind formata din trei campuri, similar cu organizarea directa. Pentru identificarea ansamblului de linii din cache (a multimii asociative) este utilizat un numar mai mic de biti (13 in exemplul nostru); in acelasi timp, campul de eticheta va fi mai lung (9 biti in exemplu).

• Pentru a se determina existenta unui hit sau a unui miss, trebuie verificate toate etichetele (tag-uri) corespunzand liniilor din ansamblul multime asociativa. In cazul unui hit, logica de comanda pointeaza (indica) linia actuala din cache.

• Numarul de linii din ansamblu (marimea multimii asociative) este ales de proiectant:

- 2 linii/ansamblu: cache asociativ cu doua cai;- 4 linii/ansamblu: cache asociativ cu patru cai;

Organizarea asociativa (set associative mapping) Un modul cache asociativ cu doua cai:

La aparitia unui miss, blocul va fi plasat pe una din cele doua linii cache apartinand unui ansamblu indicat printr-un camp de 13 biti din adresa de memorie interna.

Decizia privind care dintre linii va fi utilizata este luata de un algoritm de inlocuire.

Organizarea asociativa (set associative mapping)• Tehnica conserva majoritatea avantajelor specifice organizarii

directe: - camp eticheta scurt; - acces rapid;

- implementare relativ simpla.

• Se incearca eliminarea imperfectiunilor organizarii directe; se obtine o anumita flexibilitate pentru ca un bloc poate fi transferat pe mai multe linii cache.

• Hardul modulului cache este mai complex decat in cazul organizarii directe.

• Practic, se utilizeaza cu rezultate foarte bune module cache asociative cu doua sau patru cai. Multimile asociative mai mari nu produc ameliorari semnificative ale executiei.

• Atunci cand ansamblul se compune dintr-o singura linie, rezulta organizarea directa.

• Atunci cand ansamblul se compune din toate liniile cache, rezulta organizarea integral asociativa.

Organizarea integral asociativa (associative mapping)

• Un bloc de memorie poate fi plasat pe oricare linie din cache. • Linia particulara din cache pe care va fi plasat blocul va fi determinata de

un algoritm de inlocuire. • Adresa de memorie este interpretata de logica de control cache ca avand

doua campuri: - bitii mai putin semnificativi (2 in exemplul nostru) identifica byte-ul in bloc;

- restul adresei (22 biti inexemplu) este interpretata ca eticheta (tag).

• Pentru a verifica daca avem un hit sau un miss, trebuie verificate toate etichetele, corespunzand fiecarei linii din memoria cache. In cazul unui hit, logica de comanda pointeaza linia actuala din cache.

• Cautarea liniei din cache se bazeaza mai ales pe o parte din continutul acesteia (campul eticheta) decat pe adresa ei. O asemenea structura de memorie se numeste memorie asociativa.

Organizarea integral asociativa (associative mapping)

In cazul unui miss, blocul va fi plasat pe una din oricare cele 2**14 linii din cache. Alogoritmul de inlocuire decide ce linie va fi utilizata.

Organizarea integral asociativa (associative mapping)

Avantaje:• tehnica furnizeaza o flexibilitate mai ridicata atunci cand un bloc nou este

plasat in cache.

Dezavantaje: • complexitatea• campul eticheta este lung; • un acces rapid poate fi realizat numai utilizand pentru cache memorii

asociative de inalta performanta, dificil de fabricat si scumpe.

Algoritmi de inlocuire

Cand un nou bloc trebuie plasat in cache, un alt bloc, stocat pe una din liniile din cache, trebuie inlocuit.

Solutii de inlocuire:- in tehnica organizarii directe, nu exista alternativa de alegere;

- in celelalte doua tehnici, este nevoie de algoritmul de inlocuire, care determina blocul ce va fi inlocuit (si - implicit - pe ce linie cache va fi plasat noul bloc):

• in cadrul tehnicii multimii asociative, liniile candidate sunt cele care fac parte din ansamblul ales;

• -in cadrul tehnicii integral asociative, toate liniile din cache reprezinta potentiali candidati.

Algoritmi de inlocuire

Inlocuirea aleatoare:

- este aleasa aleator oricare din liniile candidate.

Toate celelalte politici sunt bazate pe informatia privind istoria utilizarii blocurilor din cache:

• Cel mai putin recent utilizata (Least Recently Used - LRU): se alege linia candidat unde se gaseste blocul care a stat in cache cel mai lung timp, fara a fi referit.

• First-in-first-out (FIFO): se alege linia candidat unde se gaseste blocul cel mai vechi din cache.

• Cel mai putin frecvent utilizat (Least Frequently Used - LFU): se alege linia candidat unde se gaseste blocul cel mai putin referit.

Algoritmi de inlocuire

• Pentru a fi eficace, algoritmii de inlocuire pentru gestiunea memoriei cache trebuie sa fie pusi in practica de catre hardware.

• LRU este cel mai eficace: relativ simplu de implementat si cu bune rezultate.

• FIFO este simplu de implementat.

• Inlocuirea aleatoare este cel mai simplu de implementat si da rezultate uimitor de bune.

Strategii de scriereProblema:

Cum sa se pastreze coerenta intre cache si continutul memoriei principale, dupa o operatie de scriere?

Tehnicile solutie:• Scrierea dubla Toate operatiile de scriere sunt efectuate in memoria centrala; daca adresa a fost

transferata anterior in cache, este actualizata de asemenea si linia corespunzatoare din cache, pentru asigurarea coerentei.

Pentru efectuarea acestei duble scrieri, procesorul va lucra la viteza scazuta a memoriei centrale.

• Scrierea dubla cu buffer de scriere similara cu scrierea dubla, dar evitand incetinirea lucrului procesorului datorata

scrierii directe in memorie; adresa de scriere si datele sunt stocate intr-un buffer de scriere de mare viteza; transferurile din buffer in memoria centrala se vor face in timp ce procesorul

executa alte sarcini. Performanta: viteza mai mare, dar un hard mai complex.

Strategii de scriere

Tehnicile solutie:• Scrierea intarziata (copy back) Scrierea se face numai in memoria cache. In consecinta, coerenta logica cu

memoria centrala nu se mai mentine; Liniile din cache care au fost modificate sunt marcate; Cand o linie marcata este inlocuita in cache, mai intai continutul ei este copiat in

memoria principala (se reface coerenta).

• Performanta: viteza de executie (de obicei pe o linie cache se efectueaza mai multe scrieri inainte ca ea sa fie inlocuita si sa fie necesara copierea in memoria centrala); hardware complex.

• Observatie:Pentru sistemele multiprocesor, problemele de coerenta in cache sunt foarte complexe si dificil de rezolvat.

Cateva arhitecturi cache

Intel 80486 - un cache simplu on-chip de 8 KB; - marimea liniei: 16 bytes; - organizare asociativa cu patru cai.

Pentium - doua cache on-chip, una pentru date, alta pentru instructiuni; - fiecare cache: 8 KB; - marimea liniei: 32 bytes - organizare asociativa cu doua cai.

PowerPC 601 - un cache simplu on-chip de 32 KB; - marimea liniei: 32 bytes; - organizare asociativa cu opt cai.

Cateva arhitecturi cache

PowerPC 603 - doua cache on-chip, una pentru date, alta pentru instructiuni; - fiecare cache: 8 KB; - marimea liniei: 32 bytes;

-.organizare asociativa cu doua cai (o organizare mai simpla pentru cache decat la 601, dar un procesor mai puternic)

PowerPC 604 - doua cache on-chip, una pentru date, alta pentru instructiuni; - fiecare cache: 16 KB; - lungimea liniei: 32 bytes - organizare asociativa cu patru cai.

PowerPC 620 - doua cache on-chip, una pentru date, alta pentru instructiuni; - fiecare cache: 32 K bytes - lungimea liniei : 64 bytes - organizare asociativa cu opt cai.

Memoria virtuala

• Spatiul de adrese cerut si vazut de catre programe este de obicei mult mai mare decat spatiul fizic disponibil in memoria centrala.

Solutia:In memoria centrala este stocata numai o parte din program;

restul este stocat in memoria secundara (hard disk).

• Atunci cand procesorul solicita ca un anumit segment de program sa fie incarcat in memoria centrala, va fi nevoie sa fie inlocuit un alt segment, care se gaseste plasat deja anterior acolo.

• Deplasarea programelor si a datelor intre memoria principala si cea secundara este executata automat de catre sistemul de operare, iar tehnicile utilizate se numesc tehnici de memorie virtuala.

• Adresa binara calculata de procesor va fi o adresa (logica) virtuala; se ia considerare un spatiu virtual de adrese, cu mult mai mare decat spatiul fizic disponibil in memoria centrala.

Memoria virtuala

• Daca o adresa virtuala se raporteaza la o parte de program sau de date care sunt actualmente in memoria fizica (cache, memoria centrala), locatia respectiva este imediat consultata (adresa fizica respectiva este identica cu adresa virtuala). In caz contrar, respectiva parte de program/data trebuie transferata mai intai din memoria secundara in cea centrala.

• Adresele virtuale sunt tranlatate in adrese fizice de catre o componenta hard - unitatea de gestiune a memoriei (Memory Management Unit - MMU).

Organizarea memoriei virtuale• Spatiul virtual al programului (instructiuni + date) este divizat in parti

egale de talie fixa, numite pagini. • Memoria centrala fizica este organizata ca o secventa de cadre (frames); • Pagina este unitatea de informatie de baza care este transferata intre

memoria centrala si disc, in sistemul de memorie virtuala.• O pagina poate fi stocata intr-un cadru disponibil (talia paginii = talia

cadrului). • Taliile uzuale ale paginilor sunt: 2 - 16 KB.

Paginarea la cerere

• Un program se compune dintr-o mare cantitate de pagini, majoritatea stocate pe disc si doar cateva in memoria centrala.

• Responsabil de incarcarea/inlocuirea paginilor in memoria centrala, in asa fel incat numarul defectelor de pagina (page fault) detectate sa fie redus la minim este sistemul de operare.

• Un defect de pagina apare atunci cand unitatea centrala se refera la o locatie dintr-o pagina care nu este in memoria centrala; aceasta pagina va trebui incarcata si - daca nu este nici un cadru disponibil - ea va trebui sa inlocuiasca pe o alta, incarcata mai devreme in memorie.

Paginarea la cerere

Translatarea adreselor

Accesarea unui cuvant din memorie implica translatarea unei adresa virtuale intr-alta fizica:

- adresa virtuala: numarul paginii + deplasament (offset); - adresa fizica: numarul cadrului + deplasament.

• Translatarea adresei este efectuata de MMU, utilizand o tabela de pagini.

Exemplu: - spatiul de memorie virtuala: 2 GB (31 biti de adresa; 2 **31 = 2 GB) - spatiul de memorie fizica: 16 MB (24 biti de adresa; 2 **24 = 16MB) - dimensiunea paginii: 2KB (2 **11 = 2KB)

Rezulta: Numarul total de pagini: 2 **20 = 1MB Numarul total de cadre: 2 **13 = 8KB

Translatarea adreselor

Tabela de pagini – mecanismul de functionare

• Tabela de pagini are cate o intrare pentru fiecare pagina din spatiul memoriei virtuale.

• Fiecare intrare din tabela retine adresa cadrului din memorie care stocheaza pagina respectiva, daca aceasta pagina este in memoria centrala.

• Fiecare intrare din tabela include de asemenea biti de comanda, care descriu statutul paginii:

- daca pagina este intr-adevar incarcata in memoria centrala sau nu; - daca pagina a fost modificata dupa ultima incarcare; - informatii despre frecventa acceselor etc.

Tabela de paginiProbleme:

tabela de pagini este foarte mare (numarulpaginilor din spatiul memoriei virtuale este foarte mare).

accesul la tabela de pagini trebuie sa fie foarte rapid; tabela de pagini trebuie stocata intr-o memorie foarte rapida, on-chip.

Solutii: • Pentru intrarile tabelei de pagini este utilizat un cache special, buffer de translatie

(Translation Lookaside Buffer - TLB); acesta functioneaza similar ca o memorie cache ordinara si contine intrarile din tabela de pagini care au fost cel mai recent utilizate.

• Tabela de pagini este adeseori prea mare pentru a fi stocata in memoria centrala. De aceea, pentru stocarea tabelei sunt utilizate chiar tehnicile memoriei virtuale:

- la un moment dat, numai o parte din tabela de pagini este stocata in memoria centrala;- tabela de pagini este distribuita ea insasi de-a lungul ierarhiei memoriei:

- TLB (cache) - memoria centrala - discul

Referinta memoriei virtuale cu TLB

Referinta memoriei virtuale TLB

• Accesul la memorie este rezolvat de hardware, cu exceptia situatiei defectului de pagina, care este rezolvat de sistemul de operare.

• Modulul hardware responsabil cu translatarea unei adrese virtuale intr-una fizica este unitatea de gestiune a memoriei (MMU).

Inlocuirea paginii

• Cand o noua pagina trebuie incarcata in memoria centrala si in aceasta nu se mai gaseste nici un cadru liber, trebuie inlocuita o pagina deja incarcata.

• Decizia privind pagina care va fi inlocuita este bazata pe aceleasi speculatii utilizate pentru inlocuirea blocurilor in memoria cache (a se vedea slide-ul corespunzator).

Frecvent, pentru selectia paginii care va fi inlocuita, se utilizeaza strategia LRU.

• Cand continutul unei pagini incarcata in memoria centrala a fost modificat ca urmare a unei scrieri, dupa inlocuirea ei trebuie sa se efectueze o scriere intarziata pe disc.

• pentru a semnala ca pagina a fost modificata se utilizeaza un bit de comanda din tabela de pagini.

Rezumat• Sistemul de memorie trebuie sa stocheze date multe, programe foarte mari si sa

permita in acelasi timp un acces rapid. • Un sistem ierarhic de memorie, bazat pe localitatea referintelor. poate asigura

necesarul de performanta• Memoria cache este o componenta esentiala a sistemului de memorie; ea poate

fi organizata comun sau separat, pentru date si instructiuni. • Memoria cache poate fi organizata direct, cu multimi asociative sau integral

asociativa.• Cand un nou bloc este introdus in cache, trebuie inlocuit un altul; pentru a

decide ce bloc va fi inlocuit, se pot utiliza diferite strategii: aleatorie, LRU, FIFO, LFU etc.

• Pentru mentinerea coerentei logice intre cache si memoria centrala, sunt utilizate cateva strategii de scriere: scrierea dubla, scrierea dubla cu buffer, scrierea intarziata.

• Spatiul de adrese vazut de programe este virtual si este mult mai mare decat spatiul fizic disponibil.

• Paginarea la cerere se bazeaza pe ideea ca numai o parte din pagini se gaseste in memoria centrala la un moment dat; sistemul de operare incarca paginile in memorie, atunci cand acestea sunt necesare prelucrarii.

• Unitatea MMU traduce o adresa virtuala intr-una fizica, utilizand o tabela de pagini. Insasi tabela de pagini este distribuita in cadrul ierarhiei memoriei: TLB (cache), memoria centrala, discul hard.

OPERATII DE INTRARE/IESIRE

1. Dispozitive de intrare/iesire si magistralele sistemului2. Arbitrajul magistralei 3. Sincronizarea magistralei 4. Module de I/E5. Decodificarea adreselor de I/E 6. I/E programate si gestionate prin intreruperi7. Accesul direct la memorie (DMA)

Resurse de intrare/iesire

• Dispozitivele de intrare si de iesire furnizeaza mijloace pentru stocarea informatiei si asigura interfata ordinatorului cu mediul inconjurator (utilizatorii).

® memoria secundara: permite stocarea pe termen lung a unor mari cantitati de date si de programe (dischete, hard-disk, banda magnetica, CD-ROM).

® senzori si elemente de executie: sunt utilizate pentru interactiunea directa cu mediul.

® interfata utilizator: tastatura, monitor, mouse, imprimanta.

® resurse de comunicare: modem, controler (placa) de retea.

Magistralele sistemului

• Magistrala este o cale electrica comuna intre mai multe dispozitive

• intr-un sistem de calcul, pentru a lega impreuna unitatea centrala, memoria si dispozitivele, pot fi utilizate una sau mai multe magistrale.

• in plus fata de acest ”sistem de transport", magistralele sunt instalate de asemenea in interiorul unitatii centrale (magistrale interne).

• magistralele sistemului difera in functie de numarul si organizarea liniilor, mecanismele de arbitraj si de sincronizare, operatiile specifice.

• pentru a lega la magistrala un dispozitiv, controlerul dispozitivului trebuie sa se adapteze la respectivele caracteristici ale magistralei.

• Controler: comanda un dispozitiv de I/E si asigura accesul acestuia la magistrala.® Ex: cand controlerul discului dur primeste, de exemplu, o cerere de lectura provenind de la

unitatea centrala, el da comenzile corespunzatoare dispozitivului pentru a executa cererea si organizeaza datele intr-un tren binar care va fi transmis pe magistrala

® Pentru a transmite si/sau a primi date, controlerul trebuie sa interactioneze cu magistrala, conform unui anumit protocol de comunicatie.

Resurse de intrare/iesire – arhitectura cu magistrala unica

Resurse de intrare/iesire

• Magistrala este utilizata: - de controlere, pentru comunicatia spre/de la UC sau memorie; - de UC, pentru a citi sau stoca instructiuni si date de la/spre memorie (rezulta posibilitatea de aparitie a conflictelor intre controlerele de I/E si UC).

• In caz de conflicte, un dispozitiv (chip), numit arbitru de magistrala, decide prioritatea de acces.

- in general, dispozitivele de I/E au prioritate fata de UC; in mod obisnuit, aceste dispozitive nu pot fi oprite (a le forta oprirea poate duce la pierderi de date!): - cand nici o I/E nu este lansata, UC are controlul total al magistralei, pentru a accesa memoria. - cand un anumit dispozitiv de I/E cere acces la magistrala, el il va obtine imediat (tehnica numita cycle stealing - furt de cicli - incetineste calculatorul).

Resurse de intrare/iesire - arhitecturi cu magistrale multiple

• Magistrale ISA (Industry Standard Architecture): versiunea noua a magistralei vechi a PC - ului (relativ lenta).

• Magistrale PCI (Peripheral Component Interconnect): mai noua, mai rapida. • UC si memoria sunt legate prin memory bus - magistrala dedicata de mare viteza.

• Magistrale SCSI (Small Computer System Interface) reprezinta o norma de magistrala pentru periferice cu o rata inalta de transfer; este de asemenea interfata hard-disk-ului.

• la o magistrala SCSI se pot atasa pana la sapte dispozitive (hard-disk, CD-ROM, scanner etc.)..

Resurse de intrare/iesire - arhitecturi cu magistrale multiple

• Diferitele magistrale sunt legate prin punti (bridges) adecvate (care executa de asemenea si buffering-ul informatiei)

• Avantajele arhitecturilor cu magistrale multiple:

se evita conflictele de magistrala; traficul UC- memorie este separat de traficul de I/E; permite sistemului sa suporte o varietate de dispozitive de I/E, care lucreaza dupa

diferite norme de magistrala.

Interfata externa a circuitului unitatii centrale

Pinii UC pot fi impartiti in: pini de adrese, pini de date si pini de comanda.• Pinii de adresa: pe aici, adresele sunt trimise catre magistrala sistemului, pentru

operatii de citire/scriere in memoria interna- cu m pini de adresa, pot fi adresate 2** m locatii.

• Pinii de date: pe aici, bitii de informatii sunt trimisi/receptionati pe/de pe magistrale.- cu n pini de date, pprintr-o operatie simpla poate fi citit/scris un cuvant de n biti.

Interfata externa a circuitului unitatii centrale

• Pinii de comanda:- comanda magistralei: UC utilizeaza acesti pini pentru a comanda restul sistemului si a-i indica acestuia actiunile pe care sa le faca; semnalele de comanda se propaga pe magistralele sistemului;

- pinii de intreruperi: pe acesti pini UC obtine semnale trimise de catre modulele de I/E; ei indica de obicei ca o operatie de I/E a fost terminata;

- arbitrajul magistralei: sunt utilizati pentru a regla traficul in sistemul de magistrale si pentru a interzice dispozitivelor sa incerce sa ocupe in acelasi timp o magistrala;

-pinii coprocesoarelor: sunt destinati sa faciliteze comunicatia cu circuitele coprocesoarele, cum ar fi chip-urile in virgula flotanta, chip-urile grafice etc.

• O magistrala de sistem se compune in mod tipic din 50-100 linii separate. Ele pot fi clasificate in trei grupe functionale:

1. Linii de date: furnizeaza o cale pentru a transporta datele intre componentele sistemului. Largimea magistralei: 8, 16, 32 linii.

2. Linii de adresa: sunt utilizate pentru a indica sursa sau destinatia datelor. Largimea ei determina capacitatea maxima de adresare directa a memoriei. 3. Linii de comanda: sunt utilizate pentru comanda accesului la magistrala, pentru sincronizarea operatiilor si pentru propagarea comenzilor in intregul sistem.

• solutia pentru a obtine magistrale foarte largi: multiplexarea: in loc de a mentine - de exemplu - 16 linii separate de adrese si 16 de date, se poate opta pentru 32 linii comune de adrese si date, multiplexate (la debutul operatiei, liniile magistralei sunt utilizate mai intai pentru adrese; mai tarziu, aceleasi linii vor fi utilizate pentru date).

• pretul utilizarii unei magistrale cu largime redusa este incetinirea vitezei de lucru a sistemului (la citire/scriere, adresa si datele nu pot fi puse pe linii simultan).

Magistralele sistemului

Arbitrarea magistralei

• Dispozitivele legate la o magistrala pot fi de doua feluri:

1. Master: este activ si poate lansa un transfer pe magistrala. 2. Slave: este pasiv si asteapta cereri.

• Dispozitivele pot lucra fie ca master, fie ca slave, in raport de circumstante:

- unitatea centrala este un master tipic.- la un moment dat insa, un coprocesor poate lansa catre UC un transfer - deci UC

devine un slave.

- un dispozitiv de I/E lucreaza in mod normal ca slave, in interactiune cu UC- dar cateva dispozitive pot executa acces direct la memorie, in acest caz accesand

magistrala ca un master.

- memoria lucreaza numai ca slave.

Arbitrarea magistralei

Ce se intampla daca doua sau mai multe dispozitive doresc sa lucreze simultan ca master?

Deoarece numai o unitate poate transmite la un moment dat pe magistrala,

este necesar un arbitraj. • Mecanismul de arbitraj:

- centralizat: exista un singur dispozitiv, arbitrul de magistrala. El determina ce acces va urma.

- descentralizat (distribuit): arbitrul nu mai este prezent. dar sunt necesare mai multe linii de magistrala.

Exemplu: pe magistrala exista atatea linii de cerere, cate dispozitive sunt legate; fiecare dispozitiv urmareste fiecare linie de cerere. Dupa fiecare ciclu, fiecare dispozitiv stie daca el are prioritatea cea mai mare. In caz afirmativ, el ocupa magistrala.

- magistralele PCI si ISA utilizeaza arbitrajul centralizat; -.magistrala SCSI utilizeaza arbitrajul descentralizat;

Sincronizarea magistralei

• Sincronizarea se raporteaza la maniera in care evenimentele sunt coordonate pe magistrala:

1. Sincronizarea sincrona: aparitia evenimentelor pe magistrala este determinata de un orologiu. 2. Sincronizarea asincrona: aparitia evenimentelor pe magistrala urmeaza si depind de aparitia unor evenimente precedente. • Exemple:

- magistralele PCI si ISA utilizeaza sincronizrea sincrona; -.magistrala SCSI utilizeaza sincronizarea asincrona;

Sincronizarea sincrona

• Magistrala include o linie de ceas; toate dispozitivele legate la magistrala pot citi linia de ceas.

• Toate evenimentele pe magistrala incep la debutul ciclului de ceas. • Secventa de magistrala pentru un ordin sincron citire din memorie:

- UC (master) lanseaza un semnal de start pentru a marca prezenta adresei si a parametrilor de comanda pe magistrala: semnalul citire (read) este lansat pe linia de comanda respectiva, iar adresa de memorie este plasata pe liniile de adresa. - dupa o intarziere de doi cili de magistrala, memoria (slave) plaseaza datele pe linii si lanseaza

un semnal acknowledge (cererea a fost achitata) pe linia de comanda respectiva.

Sincronizarea sincrona

• Avantajele sincronizarii sincrone:- simplu de implementat si testat;

• Dezavantajele sincronizarii sincrone:- nu este flexibila:

- timpii de executie ai unei operatii trebuie sa fie multipli ai ciclului de ceas (daca o operatie are nevoie de 3,1 cicli, ea va dura 4 cicli). - frecventa magistralei trebuie sa fie adaptata la dispozitivele mai lente, deci dispozitivele rapide nu pot fi valorificate pe deplin.

Sincronizarea asincrona

- pe magistrala nu exista nici o linie de ceas;- un eveniment este provocat de un alt eveniment anterior si nu de un puls de ceas. Dispozitivul master va astepta exact atat cat este necesar pentru ca dispozitivul slave sa-si termine treaba. - daca un master trebuie sa astepte foarte mult pentru un anumit slava lent, acest lucru nu va influenta in nici un fel timpul de asteptare pentru un alt slave, mai rapid, intr-o operatie urmatoare.

Sincronizarea asincrona

• Secventa de magistrala pentru un ordin asincron de citire din memorie: - dupa ce UC (master) a incarcat liniile de adresa si a lansat semnalul de citire (read), ea va astepta pana ce liniile sunt stabile iar apoi va lansa semnalul MSYN (Master SYNchronization). - cand memoria (slave) primeste MSYN, ea isi efectueaza sarcina cat mai rapid posibil, punand valorile datelor pe liniile de date, apoi lanseaza semnalul SSYN (Slave SYNchronization). - cand master-ul primeste SSYN, se stie ca datele sunt pe linii; atunci se neaga liniile de adrese si MSYN, lansandu-se operatia de citire (read).- cand slave percepe negatia lui MSYN, el stie ca datele au fost citite; atunci se neaga liniile de date si SSYN.

Module de I/E• Modulele de I/E indeplinesc de obicei sarcina controlerului de I/E. Frecvent,

ele sunt produse ca circuite (chipuri) de I/E standardizate.

• Modulul de I/E dispune de o prima interfata cu dispozitivul pe care il comanda si de o a doua cu magistrala sistemului (sau direct la UC si/sau la memorie).

Functiile principale ale unui modul de I/E: - comanda si sincronizarea operatiilor; - comunicarea cu magistrala (sau direct cu UC); - comunicarea cu dispozitivele; - constructia unitatilor de date (buffering-ul datelor);

- detectia erorilor.

• Un posibil exemplu, pentru un transfer de date intre un dispozitiv si UC (pe magistrala): 1. UC interogheaza (pe magistrala) modulul de I/E, relativ la starea (status) dispozitivului. 2. Modulul de I/E trimite (pe magistrala) starea dispozitivului. 3. Daca dispozitivul este OK (ready), UC cere transferul datelor prin intermediul unei comenzi transmisa catre modulul de I/E. 4. Modulul de I/E transmite comenzile adecvate catre dispozitiv si va obtine o unitate de date. 5. Datele sunt transmise (pe magistrala) catre UC.

Module de I/E• Buffering-ul datelor este esential pentru modulele de I/E; el permite sa se faca

transferuri cu memoria la viteza memoriei si nu la viteza dispozitivului de I/E, care este cu mult inferioara. Structura unui modul de I/E:

• Modulele de I/E ascund mai multe detalii de manipulare a unui dispozitiv de catre UC. In consecinta, UC poate vedea dispozitivele ca pe simple operatii:

- modulele sofisticate, numite canale de I/E, dispun de o interfata la nivel elevat cu unitatea centrala; ele sunt utilizate pentru mainfrmames si cateva minicalculatoare; - modulele mai simple, numite controlere de periferic, sunt utilizate pe PC-uri si statii de lucru.

Decodificarea adreselor de I/E

Problema: Cum este ales dispozitivul extern pentru o operatie de I/E ?

Exista doua maniere posibile:

I/E tratate ca memoria. I/E izolate.

I/E tratate ca memoria

• Pentru locatiile de memorie si dispozitivele de I/E exista un singur spatiu de adrese.

• UC trateaza registrele modulelor de I/E (de stare si de date) ca locatii de memorie.

Acelasi set de instructiuni masina este utilizat ca mijloc de a accede la memorie si la dispozitivele de I/E.

I/E tratate ca memoria

• Pe magistrala sunt necesare doua linii: una de citire si alta de scriere. Insasi adresa indica daca este vorba despre o operatie de citire/scriere in memorie sau de o operatie de intrare/iesire pe un anumit dispozitiv.

• Avantaje: - usor de programat: pentru programarea operatiilor de I/E sunt utilizate instructiunile de referinta la memorie, in loc de a utiliza instructiuni de I/E specifice.

• Dezavantaje:- numai o parte din spatiul de adrese este disponibil pentru memorie. Restul este rezervat pentru dispozitivele de I/E.

I/E izolate

• Spatiul de adrese pentru I/E este separat in raport cu spatiul pentru adresele de memorie.

• Pe magistrala sunt linii separate pentru read/write I/E si read/write memory.

I/E izolate

• Tratamentul acceselor la memorie si al operatiilor de I/E sunt efectuate in mod diferit de catre UC. Operatiile de I/E sunt efectuate prin instructiuni specifice:

- cand UC executa o instructiune de acces la memorie, sunt asignate liniile de citire/scriere memorie ale magistralei; - cand UC executa o instructiune de I/E, sunt asignate liniile de citire/scriere de I/E;

In functie de liniile de magistrala asignate, adresa plasata pe liniile de adresa este interpretata ca o adresa de memorie sau ca o adresa de dispozitiv.

• Pentru transferul datelor catre/de la dispozitivele de I/E sunt posibile trei tehnici:

1. I/E programate 2. I/E bazate pe intreruperi 3. Acces direct la memorie

Tratamentul intrarilor/iesirilor

• Unitatea centrala executa o secventa de instructiuni, care reprezinta comenzi directe ale operatiilor de I/E (citire stare dispozitiv, comenzi de citire/scriere etc.).

• Cand UC lanseaza o comanda pentru un modul de I/E, ea trebuie sa astepte pana cand operatia de I/E va fi terminata. Deoarece UC este mai rapida decat dispozitivele, rezulta o pierdere de timp.

I/E programate

I/E bazate pe intreruperi

• Dupa lansarea unei comenzi de I/E, UC nu asteapta pana aceasta operatie se va termina; ea continua o alta activitate utila.

• Cand operatia de I/E a fost terminata, modulul de I/E lanseaza un semnal de intrerupere pe magistrala.

• Dupa receptia semnalului de intrerupere, UC transfera datele spre/din memorie si lanseaza o noua comanda, daca trebuie citite/scrise mai multe date.

• Avantaje: - UC nu asteapta terminarea operatiei de I/E, ea poate efectua o alta activitate utila

• Problema: - UC trebuie sa supravegheze fiecare unitate de date (cuvant), pentru a le deplasa spre/din memorie, si trebuie sa verifice de fiecare data existenta unei comenzi de I/E.

I/E bazate pe intreruperi

• Daca o mare cantitate de date trebuie sa fie deplasata, tehnica nu este totdeauna eficace, deoarece:

- UC trebuie sa transfere separat fiecare unitate de date; - tratamentul intreruperilor consuma de asemenea un anumit timp.

Accesul direct la memorie (DMA)• DMA (Direct Memory Acces) este un modul aditional, plasat pe

magistrala sistemului, care executa transferul datelor pentru toate operatiile de I/E

• UC lanseaza o comanda catre modulul DMA si ii transfera acestuia toate informatiile necesare.

• Modulul DMA efectueaza toate operatiile (are un rol similar cu UC-ul in tehnica I/E programate); transferul datelor intre modulele de I/E si memorie se efectueaza fara a trece prin UC.

• Cand modulul DMA si-a terminat treaba, el lanseaza un semnal de intrerupere catre UC.

• Inaintea inceperii unei operatii, modulul DMA este informat de UC despre:

- tipul operatiei (citire sau scriere); - adresa dispozitivului de I/E implicat; - adresa de start din memorie unde informatia trebuie stocata sau de unde trebuie citita; - numarulcuvintelor care trebuie transferare.

Accesul direct la memorie

• O structura simpla cu modul DMA:

Rezumat• Dispozitivele de intrare/iesire furnizeaza mijloacele pentru stocarea informatiilor si

pentru interactiunea cu calculatorul. Unitatea centrala, memoria si dispozitivele sunt conectate intre ele prin una sau mai multe magistrale de sistem.

• Mai multe magistrale sistem fac sistemul mai rapid si permit conectarea dispozitivelor care lucreaza sub diferite norme de magistrala.

• Chip-ul UC este legat la restul sistemului de calcul prin pini de adrese, de date si de comenzi.

• Magistrala se compune din linii de date, de adrese si de comenzi; liniile de adrese si de date pot fi multiplexate.

• Arbitrajul magistralei evita utilizarea simultana a acestei resurse de catre doi masters. Pot fi utilizate tehnici de arbitraj centralizat sau descentralizat.

• Coordonarea evenimentelor pe magistrala poate fi sincrona sau asincrona. Sincronizarea asincrona este mai eficace, dar mai dificil de implementat.

• Modulele de I/E conecteaza un dispozitiv de I/E la magistrala sistemului. Ele ascund pentru UC detaliile dispozitivelor de I/E.

• Selectia unui dispozitiv de I/E este efectuata prin similitudine cu memoria (memory-mapped) sau prin I/E izolate. Prima tehnica utilizeaza un spatiu de adrese unic pentru memorie si dispozitive I/E. A doua tehnica utilizeaza doua spatii de adrese separate.

• Pentru transferul datelor de I/E pot fi utilizate trei tehnici: I/E programate, I/E bazate pe intreruperi si acces direct la memorie (DMA).

SETUL DE INSTRUCTIUNI

1. Instructiunile masina 2. Tipuri de instructiuni masina 3. Salturi conditionate si neconditionate 4. Instructiuni de salt pentru subprograme 5. Stiva6. Operatii de baza pentru I/E7. Moduri de adresare - alternative8. Prezentarea modurilor de adresare 9. Formatul instructiunilor

Instructiunile masina

• Una din caracteristicile principale ale unei UC este reprezentata de setul de instructiuni propriu - reprezinta colectia de instructiuni masina pe care UC le poate recunoaste si executa.

• O instructiune masina este reprezentata printr-o secventa binara (succesiune de biti). Aceasta trebuie sa defineasca:

- ce trebuie facut (codul operatiei) - cui se aplica operatia (operanzii sursa) - unde se depune rezultatul (operandul destinatie) - cum se continua dupa terminarea operatiei

• Secventa de reprezentare a unei instructiuni masina este divizata in campuri; fiecare camp contine o specificatie de instructiune (cod operatie, operanzi etc.); campurile sunt organizate conform unui format al instructiunii.

• Adresele operanzilor sursa si destinatie, ca si adresa instructiunii urmatoare care trebuie executata, pot fi indicate in mai multe moduri, numite moduri de adresare.

Tipuri de instructiuni masina

• Instructiunile masina sunt de patru tipuri: transfer de date intre memorie si registrii UC; operatii aritmetice si logice; de comanda a programului (salturi); transfer de I/E.

• Aspectele importante legate de procesul de proiectarea al

setului de instructiuni: numarul de adrese; tipuri de operanzi; moduri de adresare; repertoriul de operatii; accesul la registre; formatul instructiunii.

Numarul de adrese intr-o instructiune

• Majoritatea calculatoarelor contemporane au instructiuni cu doua sau trei adrese.

Motivatii: instructiunile cu patru adrese sunt putin judicioase; urmatoarea instructiune care se va

executa este implicit accea care urmeaza in memorie; pentru salt se utilizeaza instructiunile specializate;

instructiunile cu o singura adresa impun utilizarea unui singur registru implicit, pentru toate instructiunile. Solutia este prea restrictiva pentru ca nu permite utilizarea registrilor multipli.

mai putine adrese in instructiune simplifica formatul acesteia, reduce lungimea ei si simplifica hardul UC; in aceasta maniera, instructiunile devin mai primitive.

Numarul de adrese intr-o instructiune

Comanda programului (salturile)

Un exemplu (Motorola 68000):

Saltul conditionat sau neconditionat

• Implicit, urmatoarea instructiune care se va executa este cea care urmeaza imediat celei curente.

• Ordinea de executie a instructiunilor poate fi schimbata cu instructiuni specializate. Efectul final al unei astfel de instructiuni este incarcarea unei noi valori in registrul contor program (PC - program counter):

Salt neconditionat: - - - - - - - - - - - - - BR tinta- - - - - - - - - - - - - - - - - - - - - - - - - -

tinta - - - - - - - - - - - - - - - - - - - - - - - - - -

Saltul conditionat provoaca un salt numai daca este satisfacuta o conditie (aritmetica sau logica) indicata. • salturile conditionale se bazeaza pe informatia stocata in bitii de conditie (condition code flags);

de obicei acesti biti sunt grupati impreuna in registrul de stare al UC (status register).

Bitii de conditie utilizati pentru salt• Cel mai frecvent utilizati biti de conditie sunt:

- N (negativ): este pozitionat pe 1 daca rezultatul este negativ; altfel, ramane 0. - Z (zero): este pozitionat pe 1 daca rezultatul este zero; altfel, ramane 0. - V (depasire): este pozitionat pe 1 daca s-a produs o depasire aritmetica; in caa contrar, ramane 0. - C (transport): este pozitionat pe 1 daca, in timpul unei operatii aritmetice, a aparut transport de pe pozitia bitului cel mai semnificativ (sic!); altfel, ramane 0.

• Exemple de salturi conditionale: BEZ (salt daca egal cu zero), BLZ (salt daca mai mic ca zero) etc.

• Bitii de conditie sunt modificati de anumite instructiuni (de obicei aritmetice sau logice, insa N si Z pot fi de asemenea afectati de instructiuni pentru transfer de date); instructiunile care ii modifica sunt precedente instructiunilor de salt (cele care le verifica valorile).

Instructiunile de salt pentru subprograme

Problemele principale:

- salt catre o procedura (apelul procedurii); - returul din procedura; - transferul parametrilor (intre programul principal si procedura);

Exemplu:

Solutii alternative pentru saltul catre subprograme• Cea mai simpla solutie o reprezinta utilizarea unei instructiuni speciale de salt neconditionat

(numita CALL), care va salva adresa de retur intr-o locatie specifica, de obicei un registru (link registre - LR).

Aceasta solutie simpla este adoptata de exemplu de PowerPC.

• Solutia CALL nu functioneza insa pentru anumite subprograme (numite imbricate sau recursive, adica se apeleaza unele din altele), decat daca adresele de retur sunt salvate de catre programator.

• Pentru a fi corect, exemplul precedent va trebui schimbat:

Solutie alternativa pentru saltul catre subprograme - stiva

• Pentru sustinerea apelurilor de subprograme recursive (care se pot apela pe ele insele) sunt necesare solutii mai complicate.

• Problemele de mai sus pot fi rezolvate mai simplu daca adresa de retur este salvata automat, utilizand o structura de date speciala numita stiva.

Stiva

• Stiva este o lista de elemente informationale, cu restrictia ca aceste elemente pot fi adaugate sau extrase numai pe la una din extremitatile listei (numite inceputul - top - sau sfarsitul - bottom - stivei). Procedura se numeste LIFO (last input, first output)

• plasarea unui nou element in stiva se numeste push; extragerea unui element se numeste pop.

• Anumite calculatoare au o structura tip stiva realizata prin hard: o parte din memoria centrala este controlata ca o stiva si un registru special (Stack Pointer - SP) contine referinta la varful stivei. Operatiile PUSH si POP sunt implementate prin hardware.

Operatii cu stiva

Apelul si returul din subprograme bazate pe stiva

• O instructiune CALL salveaza automat adresa de retur in stiva - inaintea saltului la adresa subprogramului, se executa automat o instructiune PUSH PC.

• Instructiunea RETURN executa salt la adresa salvata automat in stiva.

• Pentium si Motorola 68000 sustin aceasta alternativa.

Exemplu:

Tehnici similare, bazate pe stiva, sunt utilizate si pentru transferul parametrilor.

Operatii de baza pentru intrare/iesire • Pentru a lansa o operatie de I/E, UC transmite o adresa (care indica modulul si

dispozitivul de I/E) si lanseaza o comanda de I/E. • Exista patru tipuri de comenzi de I/E:

- comenzi pentru control (sterge ecran, pozitioneaza hartia etc.); - teste de stare; - comenzi de lectura (citire);

- comenzi de scriere.

Exemplu:

Comunicatia intre UC si un videoterminal utilizeaza un program de comanda pentru I/E. Interfata dispozitivului se compune din: - registrul buffer DATAIN (8 biti), legat la tastatura;- bitul (flag) de sincronizare SIN, asociat cu tastatura; SIN este pozitionat pe 1 daca in DATAIN se gaseste un caracter valid; el este automat trecut in 0 cand continutul lui DATAIN a fost citit. - registrul buffer DATAOUT (8 biti), legat la dispozitivul de afisaj; - bitul (flag) de sincronizare SOUT asociat cu dispozitivul de afisare; SOUT este pozitionat pe 1 daca afisajul este gata de a primi un caracter; el este trecut in 0 automat, atunci cand caracterul a fost transferat in DATAOUT.

Operatii de baza pentru intrare/iesire - exemplu

• SIN, DATAIN, SOUT, DATAOUT sunt adresele registrilor respectiv ai flagurilor dispozitivului . Ele sunt parte a spatiului de adrese utilizat pentru a accesa dispozitivele de I/E; acesta este considerat independent de spatiul de adrese al memoriei (interne).

• Atunci cand sunt utilizate instructiunile speciale de I/E, adresa este considerata ca apartinand unui dispozitiv de I/E si este activata comanda corespunzatoare de acces la dispozitiv pentru magistrala (vezi capitolul respectiv).

Operatii de baza pentru intrare/iesire

In cazul in care adresele de I/E sunt tratate ca adrese de memorie, apar unele particularitati:• Anumite adrese sunt pre-asignate starilor sau registrilor de date ai modulelor sau

dispozitivelor de I/E. • Unitatea centrala trateaza acesti registri asemanator cu locatiile de memorie. UC

utilizeaza aceleasi instructiuni masina pentru a accede la memorie sau la dispozitivele de I/E (vezi capitolul respectiv).

Moduri de adresare

Adresele operanzilor sursa si destinatie, ca si adresa instructiunii urmatoare ce va fi executata, pot fi indicate in mai multe maniere, numite moduri de adresare.

De ce mai multe moduri de adresare?• Diferitele solutii alese pentru a indica adresa operanzilor sau a rezultatelor determina o mai

mare flexibilitate, care simplifica programarea; • Numarul de biti rezervati pentru reprezentarea adresei in cuvantul instructiunii este limitat:

Exemplu: cu o zona de adrese de 8 biti, intr-o instructiune pot fi referite numai 2**8 locatii de memorie. Daca insa, in zona de adrese a instructiunii de mai jos, vom indica in locul adresei propriu-zise un numar de registru care contine adresa operandului, vor putea fi referite 2**16 locatii (considerand ca registrul are 16 biti):

Moduri de adresare - alternative

Moduri de adresare simple:

- necesita campuri de adresa lungi in cuvantul instructiunii; plaja de reprezentare a adreselor care pot fi referite este redusa; - se diminueaza flexibilitatea programarii; - calcululadresei este repid; - complexitatea hard a UC se reduce;

Moduri de adresare sofisticate :

- permite reducerea lungimilor zonelor de adrese in cuvantul instructiunii, fara a reduce eficacitatea plajei de adrese; - ofera flexibilitate in programare; - calculul de adresa poate fi complex; - poate creste complexitatea hard a UC.

Moduri de adresare

• Imediata • Directa • La registru • Indirecta • Cu deplasament • Indexata• Relativa • Cu stiva

Moduri de adresare

Adresarea imediata

ADD R4, #3: efect: R4 - R4+3 Operandul este plasat direct intr-unul din campurile cuvantului instructiunii.

Adresarea directa

ADD R4,X efect: R4 - R4+[x ] Adresa reala a operandului este plasata intr-un camp din cuvantul instructiunii.

Moduri de adresareAdresarea la registru ADD R4, R3: efect: R4 - R4+R3

adresarea la registru este asemanatoare cu adresarea directa, dar zona de adresa se raporteaza la un registru, nu la memoria centrala.

Adresarea indirecta a) Adresarea indirecta la memorie ADD R4, (X): efect: R4 - R4+[[X]]

Cuvantul instructiunii contine adresa unei locatii de memorie care contine adresa reala a operandului.

Prin adresare indirecta, poate fi referit un numar mult mai mare de cuvinte de memorie decat prin adresarea directa: 2 **N > 2 **K (N - lungimea cuvantului de memorie, K - lungimea zonei de adresa in cuvantul instructiunii.

Moduri de adresareb) Adresarea indirecta la registru ADD R4, (R1): efect: R4 - R4+[R1]

Adresarea indirecta la registru este asemanatoare cu adresarea indirecta, dar zona de adresa se raporteaza la un registru, in locul memoriei centrale.

Adresarea indirecta la registru este adesea combinata cu auto-incrementarea sau auto-decrementarea: dupa fiecare executie a unei instructiuni, continutul registrului de adresa este incrementat (decrementat) automat:

ADD R4, (R1)+: efect: R4 - R4+[R1] R1 - R1+1 Exemplu (Motorola 68000):

Moduri de adresareAdresarea cu deplasament ADD R4, R1, X: efect: R4 - R4+[R1+X] Un registru de baza (care poate fi un registru general) contine o adresa reala - adresa de baza; deplasamentul (X) este stocat in cuvantul instructiunii si este considerat ca un supliment (offset) al adresei de baza.

Adresarea indexata ADD R4, X[R1]: efect: R4 - R4+[X+R1] Adresarea indexata seamana cu adresarea cu deplasament si registru de baza. Totusi, se considera o adresare indexata atunci cand campul de adresa din cuvantul instructiunii contine o adresa efectiva, iar registrul de index (special) contine un deplasament.

Moduri de adresare

Exemplu de adresare indexata: • Calculul sumei elementelor dintr-o tabela continand N numere

intregi:

• Indexarea este adeseori combinata cu auto-incrementarea sau auto-decrementarea: dupa fiecare executie a unei instructiuni, continutul registrului de index este incrementat (decrementat) automat:

ADD R4, X[R1]+: effect: R4 - R4+[X+R1] R1 - R1+1

Moduri de adresare

Adresarea combinata: indirecta si indexata

Moduri de adresare

Adresarea relativaEste o varianta a adresarii cu deplasament, dar adresa de baza este plasata implicit in registrul contor de program PC. Cuvantul instructiunii contine un deplasament care poate fi pozitiv sau negativ.

• Adresarea relativa este utilizata de catre instructiunile de salt. Tinta unui salt este de obicei o adresa apropiata de cea a instructiunii care executa saltul, astfel ca sunt necesari doar cativa biti pentru a stoca un deplasament al adresei reale, in raport cu adresa instructiunii de salt.

Adresarea cu stiva Operatiile speciale care lucreaza cu stiva (PUSH, POP, CALL, RETURN) refera implicit varful stivei. Deci, adresa reala este aceea stocata in registrul indicator al stivei (SP).

Formatul instructiunilor

• Formatul instructiunii reprezinta maniera de plasare a campurilor intr-un cuvant al instructiunii si modul in care acestea codifica operatiile si operanzii.

• Alternative in conceptia formatelor de instructiuni: - instructiunile scurte necesita mai putina memorie, dar furnizeaza mai putin biti pentru codificarea codurilor operatiilor si ale adreselor operanzilor. - formatele de instructiuni cu lungimi variabile pot reduce cererea de memorie prin utilizarea eficace a bitilor in cuvantul instructiunii. In acelasi timp, el ridica complexitatea UC si poate provoca scaderea performantei (in particular la prelucrarea pipeline).

Formatul instructiunilor

• Unele coduri de operatii impun implicit anumite moduri de adresare. Alte coduri de operatii permit diferite moduri de adresare pentru operanzi. In acest caz, un anumit numar de biti trebuie sa indice modul real de adresare; pentru moduri de adresare diferite, campul operand este organizat diferit si poate avea lungimi diferite.

• Pentru specificarea registrilor, numarul necesar de biti depinde de numarul registrilor disponibili. De exemplu, pentru 32 registri de uz general sunt necesari 5 biti, pentru 16 registri - numai 4 biti.

• Procesoarele 80x86 et Pentium au formate ale instructiunilor de lungimi variabile (de la 1 la 15 bytes).

• Formatul instructiunilor la PowerPC este de lungime fixa (4 bytes).

Rezumat• Una din caracteristicile principale a unei UC de calculator este setul sau de instructiuni. Instructiunile

sunt reprezentate ca structuri binare, conform unui anumit format al instructiunii. • Instructiunile din set sunt de mai multe tipuri: transfer de date, aritmetice/logice, de comanda a

programului, pentru transfer de I/E. Seturile de instructiuni ale calculatoarelor sunt foarte diferite (numar de adrese, moduri de adresare etc.).

• Pentru comanda programului sunt prevazute instructiuni de salt - conditionat sau neconditionat. Salturile conditionate sunt bazate pe biti (flags) de conditie.

• Apelurile la subprograme sunt efectuate frecvent in timpul executiei programelor. Un apel la subprogram se poate bazat pe hardware (stivele).

• Pentru rezolvarea transferurilor de I/E, pot fi utilizate operatii particulare. Daca accesul la dispozitiv este de tip memory-mapped, pentru I/E sunt utilizate operatii de transfer de date obisnuite.

• Adresele operanzilor si ale instructiunilor pot fi indicate in diferite maniere. Modurile de adresare evoluate ofera o flexibilitate mai mare a programarii si o mai mare accesibilitate la memorie.

• Moduri de adresare: - adresare imediata - directa + adresare la registru - adresare indirecta (cu auto-incrementare si auto-decrementare) - adresare cu deplasament, relativa et indexata (cu auto-incrementare si auto-decrementare) - adresare su stiva • Formatele instructiunilor definesc modul in care sunt organizate campurile in cuvantul

instructiunii si lungimile acestora. Cuvintele instructiunii pot fi de lungimi fixe sau variabile.

TEHNICI PIPELINE (I)

1. Ciclul instructiunii

2. Prelucrarea pipeline a instructiunulor

3. Riscurile (hazarduri) pipeline

4. Hazarduri structurale

5. Hazarduri de date

6. Minimizarea hazardurilor

Ciclul instructiunii

Executia instructiunii prin tehnica pipeline • Executia unei instructiuni este extrem de complexa si comporta mai multe operatii, care sunt

executate succesiv (slide anterior). Aceasta presupune disponibilitatea unei mari cantitati de hardware, dar numai o parte din acest hard functioneaza la un moment dat.

• Pipeline (conducta, banda de asamblare) este o tehnica prin care sunt lansate simultan in executie mai multe instructiuni. Acest lucru se obtine fara un hardware aditional, numai prin punerea la lucru in acelasi timp a unor parti diferite ale hardului, fiecare dintre ele tratand instructiuni diferite.

• Organizarea pipeline a unei unitati centrale este asemanatoare cu o linie de montaj: tratarea unei instructiuni este impartita in mai multe etape (segmente, pasi); pentru fiecare etapa se repartizeaza o fractiune de timp in care sa poata fi executata. Fiecare din aceste etape este un segment al conductei (sau pipe stage).

Segmentele unei pipeline sunt legate succesiv intre ele:

• Timpul necesar pentru a transporta o instructiune de la un segment la altul reprezinta un ciclu masina (ciclu de ceas, clock cycle). Executia unei instructiuni necesita mai multi cicli masina, pana cand aceasta

traverseaza intreaga pipeline.

Accelerarea executiei in pipeline

Exemplu - o pipeline cu doua segmente: FI: fetch (cautarea) instructiunii

EI: executia instructiunii

Daca vom considera ca fiecare instructiune cere un timp de executie Tex, atunci timpul total de executie Tt pentru cele 7 instructiuni, prin tehnica pipeline, este:

Tt = (T ex / 2)*8 = 4*Tex

Accelerarea executiei in pipeline

• Dupa un anumit timp (N-1 cicli), toate cele N segmente pipeline functioneaza: UC pipeline este “plina”. Acum, teoretic, unitatea pipeline furmizeaza paralelismul maximal (cele N instructiuni sunt tratate simultan de cele N segmente pipeline active – in cazul exemplului, N=6).

Exemplu - o pipeline cu sase segmente (N=6):FI: fetch (cautare) instructiune; FO: fetch operand DI: decodificare instructiune; EI: executie instructiuneCO: calculul adresei operand; WO: scriere rezultat

Accelerarea executiei in pipeline

• S-ar parea ca un numar mai mare de segmente in pipeline poate furniza o performanta mai buna. Fals, pentru ca trebuie tinut seama de:

un numar mai mare de etape amplifica procesul de transfer de date intre segmente si

face dificila sincronizarea dintre acestea.

complexitatea unitatii centrale creste odata cu cresterea numarului de segmente pipeline.

este dificil de a construi o pipeline larga si in acelasi timp de mare viteza, din cauza hazardurilor inevitabile.

Exemple:• 80486 si Pentium: o pipeline cu cinci segmente pentru instructiuni cu numere intregi si o pipeline cu

opt segmente pentru instructiunile in virgula flotanta (float point).

• PowerPC: o pipeline cu patru segmente pentru instructiuni cu numere intregi si o alta cu sase segmente pentru instructiunile in virgula flotanta.

Hazarduri in pipeline

• Hazardurile (riscurile) din pipeline sunt acele situatii care impiedică executia urmatoarei instrucțiuni din lanțul de prelucrare în cadrul ciclului său normal de timp. In acest caz, instructiunea va fi blocata (stalled).

• Timpul in care instructiunea este blocata se numeste penalitate si se masoara in cicli masina.

• Cand o instructiune este blocata, toate instructiunile din pipeline situate in aval fata de ea vor fi de asemenea blocate, putand continua numai tratarea instructiunilor din amonte.

• In timpul blocarii, nu va mai fi incarcata in pipeline nici o instructiune noua.

• Hazarduri: 1. Hazarduri structurale2. Hazarduri de date3. Hazarduri de comanda

Hazarduri structurale• Riscurile structurale se produc atunci cand o anumita resursa (memorie, unitate

functionala) este solicitata simultan de mai mult de o instructiune.

• Exemplu:Instructiunea ADD R4, X fetch in etapa FO operandul X din memorie. In timpul

acestui ciclu, memoria nu accepta alte cereri.

• Pentru evitarea hazardurilor structurale, pot fi duplicate anumite resurse.

• Unitatile functionale duplicate (UAL, unitatea in virgula flotanta) se insereaza in pipeline, pentru a trata mai multe instructiuni in acelasi timp.

• O maniera clasica de evitare a hazardurilor de acces la memorie este de a separa memoriile cache de date si de instructiuni.

Hazarduri de date

• Cand avem in pipeline doua instructiuni, I1 si I2, executia lui I2 poate incepe inainte de terminarea lui I1. Daca intr-un anumit segment pipeline, I2 are nevoie de un rezultat produs de I1, dar acest rezultat nu a fost inca produs, apare un hazard de date.

Exemplu:

Inaintea executiei etapei sale FO, instructiunea ADD este blocata pana cand instructiunea MUL va scrie rezultatul in R2.

Penalitatea: 2 cicli !

Evitarea hazardurilor de date• O parte din penalitatea produsa de hazardurile de date poate fi evitata utilizand o tehnica numita

deviere (bypassing, forwarding).

• Rezultatul operatiei din UAL este transmis totdeauna și ca feedback catre intrarea sa. Daca hardul detecteaza ca valoarea necesara pentru operatia curenta este cea produsa de operatia precedenta (dar care inca nu a fost transmisa pe reactie) UAL alege sa expedieze acest rezultat la intrarea sa, in loc sa citeasca valoarea ceruta dintr-un registru sau din memorie.

Dupa etapa EI a instructiunii MUL, rezultatul este disponibil pentru forwarding. Penalitatea este redusa la un ciclu.

Hazarduri de comanda

• Riscurile de comanda sunt produse de instructiunile de salt.

Hazarduri de comanda

• Instructiunile de salt reprezinta o problema importanta pentru asigurarea unui flux optimal de-alungul unei pipeline

• In cazul saltului conditionat, penalitatea apare chiar daca saltul nu a fost efectuat, deoarece trebuie asteptat pana cand conditia de salt va fi disponibila.

• Pentru reducerea penalitatilor de salt, s-au adoptat mai multe solutii (vedem in continuare)

Hazarduri de comanda

TEHNICI PIPELINE (II)

1. Reducerea penalitatilor de salt in pipeline

2. Unitati pentru fetch instructiuni, siruri de asteptare

3. Saltul intarziat

4. Strategii de predictie a salturilor

5. Predictia statica a salturilor

6. Predictia dinamica a salturilor

7. Tabela de istoric al salturilor

Reducerea penalitatilor de salt

• Instructiunile de salt pot afecta serios executia pipeline. Pe de alta parte, operatiile de salt sunt foarte frecvent intalnite in programe.

Statistici: - 20% - 35% din instructiunile executate sunt salturi (conditionale sau nu). - in aproximativ 65% din cazuri saltul se executa efectiv. - salturile conditionate sunt cu mult mai frecvente decat cele neconditionate (cu mai mult de doua ori).

- mai mult de 50% din salturile conditionate sunt efectiv efectuate.

Concluzie: Este foarte important sa se reduca penalitatile provocate de

salturi.

Solutie - executia in avans a fetch-ului instructiunilor• Majoritatea procesoarelor utilizeaza unitati sofisticate pentru executia in avans a fetch-ului

instructiunilor, inainte ca acestea sa fie necesare pentru executie; acestea sunt stocate intr-o coada de asteptare.

• Unitatea de fetch are capacitatea de a recunoaste instructiunile de salt si de a furniza adresele de salt. Astfel, penalitatile produse de salturile neconditionate pot fi radical reduse: unitatea de fetch calculeaza adresa de salt si continua fetch-ul instructiunilor pornind de la aceasta adresa, trimitandu-le apoi in coada de asteptare.

• Prin aceasta tehnica, restul unitatii pipeline obtine si trateaza un sir continuu de instructiuni, fara a pierde din viteza prin blocaje.

• Rata cu care pot fi citite instructiunile (dintr-un modul cache de memorie dedicata) trebuie sa fie suficient de inalta pentru a se evita coada de asteptate vida.

Metoda elimina in totalitate penalitatile de salt neconditionat • In cazul saltului conditionat, penalitatile nu pot fi evitate. Pentru a putea determina

instructiunea urmatoare, trebuie cunoscuta valoarea conditiei de salt, care de obicei depinde de rezultatul instructiunii precedente. Solutii

Solutie - saltul intarziat (branch delay slot)• Iata o secventa pipeline pentru o instructiune de salt conditionat:

• Ideea saltului intarziat este de a lasa UC sa efectueze o activitate utila pe durata celor cativa cicli stall (ca in exemplul de mai sus).

• UC va executa totdeauna instructiunea care urmeaza imediat dupa salt si va schimba decizia numai in cazul in care saltul se executa. In acest fel ordinea de executie este modificata. Instructiunea urmatoare celei de salt se spune ca este in branch delay slot.

Solutie - saltul intarziatDaca programatorul a scris:

• Compilatorul (asamblorul) trebuie sa gaseasca o instructiune care poate fi deplasata de la locul sau original in branch delay slot si care va fi executata independent de rezultatul saltului.

Iata ce produce compilatorul si ce va fi executat in mod real, pentru exemplul de mai sus :

Solutie - saltul intarziat

Solutie - saltul intarziat

• Ce se intampla insa daca nu poate fi gasita de catre compilator o instructiune pentru a fi plasata dupa salt, in branch delay slot?

• In acest caz va fi plasata dupa salt o instructiune NOP (care nu face nimic!). Penalitatea va fi identica cu situatia cand nu este utilizat saltul intarziat.

• Statiscile spun ca pentru 60% - 85% din salturi, compilatoarele sofisticate pot gasi o instructiune pentru branch delay slot.

Solutie - predictia salturilor• In ultimul exemplu, am considerat ca saltul nu va fi executat; in consecinta, se face

fetch-ul instructiunii urmatoare celei de salt. Insa in cazul in care saltul se executa, instructiunea aleasa trebuie abandonata. Ca rezultat, vom avea :

- penalitate 1 ciclu: saltul nu se face (predictie corecta);- penalitate 2 cicli: saltul se face (pedictie incorecta);

• Sa consideram predictia inversa: saltul se face. Pentru aceasta solutie este necesar ca adresa de salt sa fie calculata de unitatea de fetch.

Predictia salturilor• Predictia corecta a saltului este foarte importanta si ea poate produce ameliorari

substantiale ale performantei pipeline.

• Pe baza rezultatelor predictate, instructiunile respective vor fi supuse fetch-ului si - impreuna cu instructiunile urmatoare - vor fi depuse in coada de asteptare (asa cum s-a aratat mai sus).

• Daca, dupa ce conditia de salt a fost calculata, se va confirma ca predictia a fost corecta, executia continua.

• Dimpotriva, daca predictia nu a fost corecta, instructiunile cu fetch-ul efectuat vor fi abandonate si va trebui facut fetch-ul pentru instructiunea corecta.

....................................................................................................................................................................................................................................................................................................

..........

Pentru a profita din plin de predictia salturilor, se poate face nu numai fetch-ul in avans al instructiunilor, ci se poate incepe si executia acestora. Aceasta este tehnica cunoscuta cu numele de executie speculativa.

• Executia speculativa inseamna ca instructiunile sunt executate inainte ca procesorul sa fie sigur ca ele sunt plasate in secventa corecta de executie.

• Daca se va confirma predictia (aceasta va fi corecta), executia continua fara nici o penalitate. Dimpotriva, daca previziunea a fost eronata, instructiunile incepute in avans si toate datele asociate lor vor trebui “aruncate“ si starea precedenta executiei lor va trebui reconstituita.

Predictia statica a saltului

• Strategiile de predictie a salturilor sunt: 1. Predictia statica 2. Predictia dinamica Tehnicile statice de predictie nu iau in considerare istoria executiei programului, pe cand cele dinamice - da.

Variante implementate: • predictie “nu se face niciodata salt” (Motorola 68020); • predictia “totdeauna se face salt”; • predictie in functie de directia saltului (PowerPC 601):

se face salt, pentru salturi inapoi; nu se face salt, pentru salturi inainte.

Predictia dinamica a saltului Tehnicile dinamice de predictie amelioreaza exactitatea predictiei, prin intregistrarea unei istorii a executiei salturilor conditionate.

Schema de predictie cu 1 bit• Este utilizat un bit pentru a inregistra daca ultima executie a avut loc pe o ramura sau nu. Sistemul va

predicta acelasi comportament ca si ultima oara.

• Imperfectie: Cand o ramura se executa aproape intotdeauna, atunci cand nu se va executa, se va face o predictie

inexacta de doua ori, in loc de o data:

- - - - - - - - - - - BOUCLE - - - - - - - - - - -

- - - - - - - - - - - BNZ BOUCLE - - - - - - - - - - -

- dupa ce bucla a fost executata pentru prima oara, se va considera ca BNZ nu se executa. Acum, cand bucla se va executa inca odata, dupa prima iteratie se va face o predictie falsa; predictiile urmatoare sunt OK pana la ultima iteratie, cand va avea loc a doua falsa predictie? In acest caz predictia este mai proasta decat in cazul predictiei statice, care considera ca salturile inapoi sunt totdeauna executate (solutia PowerPC 601).

Predictia dinamica a saltului Schema de predictie cu 2 biti

• cu o combinatie de doi biti, predictiile se pot face in functie de ultimele doua exemple de executie. • Un enunt tipic recomanda ca trebuie sa schimbam predictia numai daca intr-o linie se gasesc doua

predictii incorecte

Tabela de istoric a salturilorInformatia de istoric poate fi utilizata nu numai pentru a predicta rezultatele unui salt

conditionat, dar si pentru a evita recalcularea adresei de salt. Pentru utilizarea ulterioara, adresa de salt poate fi stocata impreuna cu grupul de biti utilizati pentru predictie, intr-o

tabela de istoric a salturilor:

Tabela de istoric a salturilor

• Explicatii la figura precedenta: - adress where to fetch from: daca instructiunea de salt nu este in tabela, se va face fetch pentru instructiunea urmatoare (adresa PC+1). Daca instructiunea de salt este in tabela, se face mai intai o predictie bazata pe bitii de predictie. In functie de rezultatul predictiei, trebuie facut fetch pentru instructiunea urmatoare (adresa PC+1) sau pentru instructiunea care se gaseste la adresa de salt. - update entry: daca instructiunea de salt a fost in tabela, intrarea respectiva trebuie actualizata, pentru a reflecta predictia (corecta sau incorecta).

- add new entry: daca instructiunea de salt nu a fost in tabela, ea va fi adaugata, impreuna cu informatia corespunzatoare, referitoare la adresa de salt si la rezultatele saltului. Dca este necesar, una din intrarile existente ale tabelei va fi stearsa. Sunt utilizati algoritmi de inlocuire asemanatori cu cei utilizati la memoriile cache.

Predictiile obtinute cu aceasta tehnica pot fi corecte in aproape 90% din cazuri ! Pentium si PowerPC 620 utilizeaza executia speculativa cu predictia dinamica a salturilor

bazata pe tabela de istoric.

Rezumat

• Instructiunile sunt executate de UC ca o secventa de etape. Executia instructiunii poate fi accelerata sensibil prin tehnica pipeline.

• O pipeline este organizata ca o succesiune de N segmente. La un moment dat, in interiorul unei pipeline pot fi active N instructiuni.

• Lucrul la viteza ei maximala in pipeline este impiedicat de hazarduri. Hazardurile structurale sunt determinate de conflictele de resurse. Hazardurile de date sunt produse de dependentele de date intre instructiuni. Hazardurile de comanda se produc ca o consecinta a instructiunilor de salt.

• Instructiunile de salt pot afecta radical performanta executiei pipeline. Este foarte important de a reduce penalitatile provocate de salturi.

• Unitatile pentru executia fetch-ului instructiunilor identifica instructiunile de salt si produc adresele de salt.

Rezumat

• Pentru salturile neconditionate, exista posibilitatea de a reduce penalitatea la 0, executand fetch-ul instructiunilor (stocate in cache) la o viteza ridicata si mentinand incarcata coada de asteptare pentru executie a instructiunilor.

• Pentru salturile conditionate, penalitatea 0 nu este posibila, pentru ca trebuie asteptat rezultatul conditiei de salt.

• Saltul intarziat este o tehnica bazata pe compilator, care vizeaza reducerea penalitatii de salt prin transferul unor instructiuni in branch delay slot.

• Reducerea eficace a penalitatii de salt pentru salturile conditionale are nevoie de o strategie inteligenta de predictie a salturilor. Predictia statica a salturilor nu ia in considerare istoricul executiei. Predictia dinamica a unui salt conditionat este bazata pe o tabela de istoric.

• Tabelele de istoric al salturilor sunt folosite pentrua stoca doua informatii: rezultatele salturilor si adresa de salt a instructiunii respective.

CALCULATOARE CU SET REDUS DE INSTRUCTIUNI (RISC)

1.De ce avem nevoie de RISC?

2.Cateva caracteristici tipice ale programelor actuale

3. Caracteristicile principale ale arhitecturilor RISC

4.Sunt intr-adevar mai bune RISC-urile decat CISC-urile?

5. Exemple

Ce este RISC?

• Arhitecturile RISC (Reduced Instruction Set Computer) reprezinta o importanta inovatie in domeniul organizarii unui calculator.

• Arhitectura RISC este o tentativa de a produce mai multa putere pentru UC, simplificand setul de instructiuni al UC.

• Tendinta setului RISC este opusa aceleia a calculatoarelor clasice, cu set complex de instructiuni (Complex Instruction Set Computer - CISC).

Arhitecturile RISC si CISC au fost dezvoltate ca o tentativa de a acoperi decalajul semantic

Decalajul semantic

• Pentru a ameliora eficacitatea programului, au fost dezvoltate noi si puternice limbaje de programare (ADA, C++, Java). Ele furnizeaza: nivel elevat de abstractizare, concizie, putere de calcul.

Prin aceasta evolutie, decalajul semantic se accentueaza!

Decalajul semantic

Problema:

• Cum trebuie compilate si executate eficace noile programe de nivel inalt (high level language - HLL) pe o arhitectura data de procesor ?

Doua raspunsuri posibile:

1. Abordarea CISC: conceptia unor arhitecturi foarte complexe, implicand un mare numar de instructiuni si moduri de adresare; includerea de asemenea a unor instructiuni asemanatoare cu cele HLL.

2. Abordarea RISC: simplificarea setului de instructiuni si adaptarea acestuia la adevaratele cereri ale programelor utilizator.

Evaluarea executiei programelor

Care sunt cerintele reale ale programelor? Ce operatii ocupa majoritatea timpilor de executie ai programelor?

Pentru a determina caracteristicile de executie pentru secventele de instructiuni generate de programele HLL, s-au efectuat anumite studii:

1. Frecventa operatiilor efectuate.

2. Tipurile de operanzi si frecventa lor de utilizare.

3. Ordonantarea executiei (frecventa salturilor, cicluri, apeluri la subprograme).

Evaluarea executiei programelor -frecventa instructiunilor executate• Distributia frecventei de executie a instructiunilor masina :

- transferuri: 33% - salt conditionat: 20% - aritmetice/logice: 16% - altele: intre 0,1% et 10% • Moduri de adresare: marea majoritate a instructiunilor utilizeaza moduri de

adresare simple; adresa poate fi calculata intr-un singur ciclu (la registru, indirect la registru, cu deplasament);

Modurile de adresare complexe (indirect la memorie, indexat + indirect, deplasament + indexat, cu stiva) sunt utilizate numai de ~18% din instructiuni. • Tipurile de operanzi:

- 74 pana la 80% din operanzi sunt valori scalare (numere intregi, reale, caractere etc.) care pot fi depuse in registri;

- - 80% din valorile scalare sunt variabile locale;- restul (20-26%) sunt date structurate (arrays); 90% dintre ele sunt variabile globale;

Concluzie: Majoritatea operanzilor sunt variabile locale de tip scalar, care

pot fi stocate in registri.

Evaluarea executiei programelor - apelurile la proceduri

Au fost facute de asemenea investigatii referitoare la procentajul din timpul total de executie, alocat pentru executia anumitor instructiuni HLL.

• Comparand instructiunile HLL, cel mai mult timp este consumat executand CALL si RETURN.

• In ciuda faptului ca numai 15% din instructiunile HLL executate sunt CALL sau RETURN, ele sunt executate in majoritatea timpului, ca urmare a complexitatii lor.

• CALL si RETURN sunt compilate intr-o secventa relativ lunga de instructiuni masina, cu multe referinte la memorie .

Evaluarea executiei programelor - apelurile la proceduri

Cateva statistici referitoare la subiectul apelurilor la proceduri: - 1,25% dintre procedurile apelate au mai mult de sase parametri. - 6,7% dintre procedurile apelate au mai mult de sase variabile locale. - apelurile imbricate ale procedurilor sunt de obicei scurte si rareori sunt mai multe decat sase.

Evaluarea executiei programelor - concluzii

• Operatiile simple (UAL si transferuri) au o preponderenta

covarsitoare in raport cu operatiile complexe. • Preponderenta modurilor de adresare simple. • O mare frecventa a acceselor la operanzi; in medie, fiecare

instructiune refera 1,9 operanzi. • Majoritatea operanzilor referiti sunt valori scalare (astfel incat ele pot

fi stocate intr-un registru) si sunt fie variabile locale, fie parametri. • Optimizarea mecanismului CALL/RETURN promite mari avantaje

(crescand viteza de executie). Aceste concluzii au constituit punctul de plecare pentru abordarea

conceptului de calculator cu set redus de instructiuni (RISC).

Caracteristicile principale ale arhitecturilor RISC (1) • Setul de instructiuni este limitat si include numai

instructiuni simple. - scopul este de a crea un set de instructiuni care sa se execute rapid; majoritatea

instructiunilor RISC sunt executate intr-un singur ciclu masina (dupa fetch si decodificare).

- executia este de tip pipeline (fara referinta la memorie):

- instructiunile RISC, fiind simple, sunt cablate, in timp ce arhitecturile CISC trebuie sa utilizeze microprogramarea pentru implementarea instructiunilor complexe .

- avand numai instructiuni simple, se obtine reducerea complexitatii unitatii de comanda si a circulatiei datelor; in consecinta, procesorul poate lucra la o frecventa de baza ridicata.

- daca instructiunile sunt simple si cu timpi de executie asemanatori, unitatile pipeline sunt utilizate eficace.

- operatiile complexe pe calculatoarele RISC sunt executate ca o secventa de instructiuni simple RISC. In cazul CISC, ele sunt executate printr-una sau mai multe instructiuni complexe.

Caracteristicile principale ale arhitecturilor RISC (2)

Iata un exemplu. Sa presupunem: - avem un program care executa 80% instructiuni simple si 20% complexe;- pe masina CISC, durata unei instructiuni simple este de 4 cicli, iar cea a unei instructiuni complexe - de 8 cicli; durata unui ciclu este de 100 ns (10 **-7 s); - pe masina RISC, durata unei instructiuni simple este de 1 ciclu; operatiile complexe sunt executate printr-o secventa de instructiuni simple; vom considera in medie 14 cicli pentru o operatie complexa; durata unui ciclu este de 75 ns.

Cat timp va dura un program cu 1 000 000 de instructiuni? Raspuns:CISC: (10 **6 * 0.80*4 + 10 **6 * 0.20*8)*10 **-7 = 0,48 sRISC: (10 **6 *0.80*1 + 10 **6 * 0.20*14)*0.75*10** -7 = 0,27 s

• Operatiile complexe iau mai mult timp pe RISC, dar numarul lor este mic;

• Datorita simplitatii sale, RISC functioneaza la cea mai mica durata a ciclului; cu CISC, instructiunile simple sunt incetinite datorita lungimii lor, circulatiei datelor si a complexitatii comenzilor.

Caracteristicile principale ale arhitecturilor RISC (3) • Arhitectura load-and-store- datele sunt referite in memorie doar prin instructiunile LOAD si STORE.- toate celelalte instructiuni lucreaza numai cu registrele (sunt instructiuni registre - to - registre); - numai cateva instructiuni pentru accesul la memorie au nevoie de mai mult de un ciclu pentru

executie (dupa fetch et decodificare).

Executia pipeline (cu referinta la memorie):

• Instructiunile utilizeaza numai cateva moduri de adresare :- modurile de adresare sunt de obicei direct, la registru, indirect la registru, cu deplasament. • Instructiunile sunt de lungime fixa si de format uniform:

- aceasta face ca incarcarea si decodificarea instructiunilor sa fie simpla si rapida; nu este necesar sa se astepte pana va fi cunoscuta lungimea unei instructiuni, pentru a putea incepe decodificarea urmatoarei; - decodificarea este simplificata deoarece codul operatiei si campurile de adresa sunt situate in aceeasi pozitie pentru toate instructiunile.

Caracteristicile principale ale arhitecturilor RISC (4)

• Este disponibil un mare numar de registre- variabilele si rezultatele intermediare pot fi stocate in registri; se evita astfel transferurile repetate cu memoria.

- toate variabilele locale ale procedurilor si parametrii de transfer pot fi stocati in registri.

Ce se intampla la apelul unei noi proceduri? - in mod normal registrii trebuie salvati in memorie (ei contin valorile variabilelor si parametrii pentru procedura care a facut apelul); la returul in procedura de apel, valorile trebuie restaurate din memorie. Acest lucru ia foarte mult timp. - daca este disponibil un mare numar de registri, cand este apelata o noua procedura, poate fi asignat un nou ansamblu de registri, astfel incat ansamblul de registri asignat apelantului sa ramana intact.

Caracteristicile principale ale arhitecturilor RISC (5)

Este strategia de mai sus realista? - strategia este realista, pentru ca numarul de variabile locale al procedurilor nu este prea mare iar lanturile de apeluri imbricate ale procedurilor este numai in mod exceptional mai mare decat 6.

- daca lantul de apeluri imbricate este prea lung, la un anumit apel nu vor mai fi registre disponibile; in acest caz, variabilele si parametrii locali trebuie sa fie stocati in memorie.

Poate fi plasat un numar mare de registri intr-o arhitectura tipica RISC ? - datorita complexitatii reduse a procesorului, exista suficient spatiu pe chip pentru a plasa un mare numar de registri. De obicei, acest lucru nu este valabil si pentru arhitecturile CISC.

Caracteristicile principale ale arhitecturilor RISC (6)

Problema delayed load :• Instructiunea LOAD (si de asemenea STORE) necesita acces la memorie si executia sa nu

poate fi terminata intr-un singur singur ciclu de ceas. Astfel, in ciclul urmator va incepe tratarea unei noi instructiuni si in UC pipeline apare un hazard, cu penalitate:

Sunt posibile doua solutii : 1. Hard-ul va trebui sa intarzie executia instructiunii urmatoare lui LOAD, daca aceasta instructiune are nevoie de valoarea care trebuie transferata. 2. O solutie mai eficace - delayed load - este bazata pe compilator si are similitudini cu saltul intarziat – branch delayed slot - se va executa o alta instructiune, decat cea urmatoare lui LOAD

Problema delayed load

Cu delayed load, procesorul incepe totdeauna in urmatorul ciclu instructiunea consecutiva lui LOAD. Ramane in responsabilitatea programului (a compilatorului) sa se asigure ca aceasta instructiune nu are nevoie de valoarea incarcata de LOAD.

Ex.: Secventa urmatoare nu este corecta datorita unei situatii delayed load:

Problema delayed load Secventa corecta este urmatoarea (cu introducerea unei alte instructiuni in load delay slot:

Alt ex.: Pentru secventa urmatoare, compilatorul a produs un NOP dupa instructiunea LOAD, deoarece nu a avut nici o instructiune pe care sa o incarce in load delay slot:

Sunt mai bune arhitecturile RISC decat cele CISC?

• Arhitecturile RISC au mai multe avantaje, prezentate in aceasta prelegere.Totusi, este dificil sa dam un raspuns definitiv la intrebare:

Compararea executiilor a aratat ca programele ruleaza intr-

adevar mai rapid pe procesoarele RISC decat pe procesoarele CISC.

Totusi, este dificil sa identificam care caracteristica a unui

procesor produce performanta cea mai ridicata. Unii “fani CISC”

spun ca viteza mai mare a procesoarelor RISC nu este data de

arhitectura. Ea este obtinuta, printre altele, prin tehnologie si

compilatoare mai bune.

Un argument in favoarea lui CISC: setul de instructiuni simplu

RISC are ca rezultat pentru un program compilat un necesar mai mare de memorie decat arhitectura CISC.

Majoritatea procesoarelor curente nu sunt insa arhitecturi tipice RISC sau CISC; ele incearca sa combine avantajele ambelor

variante.

Exemple de procesoareArhitecturi CISC

VAX 11/780 Nr. de instructiuni: 303 Lungimea instructiunii: 2 - 57 Formatul instructiunii: nefixat Moduri de adresare: 22 Nr. registrelor de uz universal: 16

Pentium Nr. de instructiuni : 235 Lungimea instructiunii : 1 - 11 Formatul instructiunii : nefixat Moduri de adresare : 11 Nr. registrelor de uz universal : 8

Arhitecturi RISC Sun Sparc Nr. de instructiuni : 52

Lungimea instructiunii : 4 Formatul instructiunii : fixat Moduri de adresare : 2 Nr. registrelor de uz universal : pana la 520

PowerPC Nr. de instructiuni : 206 Lungimea instructiunii : 4 Formatul instructiunii : nefixat (dar mici diferente) Moduri de adresare : 2 Nr. registrelor de uz universal : 32

Rezumat

• Arhitecturile RISC et CISC incearca, in maniere diferite, sa rezolve aceeasi problema: decalajul semantic.

• CISC utilizeaza maniera traditionala de implementare a instructiunilor din ce in ce mai complexe.

• Arhitectura RISC incearca sa simplifice setul de instructiuni. • Inovatiile in arhitecturile RISC sunt bazate pe o analiza a unui

mare numar de programe utilizate extensiv. • Caracteristicile principale ale arhitecturilor RISC sunt: numarul

redus de instructiuni simple, putine moduri de adresare, arhitectura load-store, instructiunile sunt de format si lungime fixe, este disponibil un mare numar de registre.

• Una din problemele principale ale proiectantilor RISC este sa maximizeze eficacitatea unitatii pipeline.

• Arhitecturile actuale include adesea la un loc dispozitive RISC et CISC.

PROCESOARE SUPERSCALARE SI VLIW

1. Ce este arhitectura superscalara?3. Caracteristicile arhitecturilor superscalare4. Dependente de date5. Politici pentru executia paralela a instructiunilor6. Redenumirea registrilor7. Procesoare VLIW

Ce este arhitectura superscalara

Intr-o arhitectură superscalară mai multe instrucțiuni pot fi inițiate simultan și executate independent.• unitatile pipeline permiteau prelucrarea mai multor instrucțiuni în același timp, dar acestea trebuiau să fie la un moment dat în diferite etape de executie.

• arhitecturile superscalare includ toate caracteristicile de pipelining dar, în plus, pot exista mai multe instrucțiuni care executa simultan aceași etapă în pipeline – exista mai multe pipeline, care lucreaza simultan.

Ce este arhitectura superscalara

Arhitecturi superscalare

•

O arhitectura superscalara consta intr-un numar de pipeline care lucreaza in paralel

Intr-un ciclu de ceas sunt lansate sau terminate mai multe instructiuni, al caror numar depinde, evident, de numarul unitatilor de tratare disponibile.

In exemplul urmator, pot fi executate simultan o instructiune in virgula flotanta si doua cu numere intregi; fiecare unitate de executie este de tip pipeline cu mai multe segmente

Arhitecturi superscalare

Limitari in executia paralela

• Situatiile care impiedica executia in paralel a instructiunilor intr-o arhitectura superscalara sunt foarte asemanatoare cu cele care apar intr-o arhitectura pipeline (vezi hazarduri in pipeline).

• Totusi, consecintele acestor situatii sunt mult mai severe in arhitecturile superscalare fata de unitatile pipeline simple, datorita faptului ca potentialul de paralelism fiind mult mai mare si pierderea de oportunitate este mai mare.

Limitari in executia paralela

Pot aparea trei categorii de limitari: 1. Conflicte de resurse:

- apar in cazul in care doua sau mai multe instructiuni concureaza simultan pentru aceeasi resursa (registru, memorie, unitate functionala) – sunt similare cu hazardurile structurale din pipeline. Prin introducerea in arhitectura superscalara a mai multor unitati pipeline care lucreaza in paralel, se incearca reducerea partiala a acestor conflicte.

2. Dependente de control (procedurale)- prezenta salturilor creaza probleme majore in asigurarea paralelismului optim.

Penalitatile de salt se pot reduce conform celor discutate la arhit. pipeline.- daca instructiunile au lungimi variabile, ele nu pot fi descarcate si tratate in paralel; o

instructiune trebuie sa fie decodificata pentru a o identifica pe urmatoarea si a o descarca (fetch). In consecinta, tehnicile superscalare sunt aplicabile eficient la arhit. RISC, pentru ca aici formatul instructiunilor si lungimea lor sunt fixe.

3. Conflicte de date- sunt rezultatul dependentelor de date aparute intre instructiunile din program.

Datorita faptului ca arhit. superscalare permit o mare libertate privind ordinea executiei instructiunilor, aceste dependente trebuie tratate cu multa atentie.

-

Programarea dinamica a executiei - conceptul out of order

• Arhit. superscalare urmaresc executia a cat mai multor instructiuni in paralel, pentru a exploata la maxim potentialul de paralelism al programului

• O caracteristica a acestor arhit., ce permite cresterea paralelismului tratarii, este programarea dinamica a executiei instructiunilor:- instructiunile sunt reordonate pentru executia dinamica, in paralel si out of order (diferit

fata de ordinea lor initiala din program);- executia out of order consta in tratarea instructiunilor independent de ordinea lor

secventiala din program, avand in vedere numai dependentele de date si disponibilitatea resurselor de tratare

Rezultatul trebuie sa fie identic cu cel produs de executia strict in ordinea secventiala a programului!

Principala problema: dependentele de date

Dependentele de date

• Principiu:

Se lanseaza in executie (paralela) toate instructiunile cuprinse intr-o fereastra de instructiuni, sub rezerva aparitiei constrangerilor produse de dependentele de date si resurse.

• Tipuri de dependente de date:

1. Dependenta de date propriu-zisa

2. Dependente de iesire

3. Antidependente dependente artificiale

Dependentele de date propriu-zise

• Apar atunci cand iesirea unei instructiuni este ceruta ca intrare pentru o instructiune subsecventa:

• Aceste dependente sunt caracteristici intrinseci ale programului utilizator. Ele nu pot fi eliminate de compilator sau prin tehnici hardware.

• Depententele de date trebuie sa fie detectate si tratate:- solutia simpla este blocarea temporara a unitatii de excutie (in ex., sumatorul intra in starea

stall, pana la terminarea inmultirii);- pentru a evita blocarea, trebuie cautata (prin compilator sau hard) o alta instructiune care sa

fie executata pana se finalizeaza instructiunea in cauza (in ex., rezultatul inmultirii).

Dependentele de date de iesire, antidependenta• Dependenta de date de iesire apare atunci cand doua instructiuni scriu in aceeasi locatie.

Daca executia celei de-a doua se termina inaintea primeia, secventa este incorecta:

• Antidependenta apare atunci cand o instructiune foloseste o locatie ca operand, in timp ce o alta urmatoare scrie in aceasta locatie. Daca a doua instructiune se termina in timp ce prima nu s-a finalizat , apare o eroare:

Dependentele de date – natura dependentelor de iesire si a antidependentelor

• Dependentele de iesire si antidependentele nu sunt caracteristici intrinseci ale programului ce se executa. Ele nu sunt dependente de date reale, ci conflicte de stocare.

• Ele sunt pur si simplu consecinte ale manierei in care programatorul sau compilatorul utilizeaza registrele si locatiile de memorie.

• In exemplele anterioare, dependentele apar, in primul caz, pentru ca R4 este utilizat de ambele instructiuni pentru stocarea rezultatului, iar in al doilea, pentru ca R3 este utilizat de a doua instructiune pentru stocarea rezultatului.

• Secventele din exemple pot fi rescrise fara dependente, utilizand registri suplimentari:

Politici pentru executia paralela a instructiunilor (1)• Capacitatea procesorului superscalar de a executa instructiuni in paralel este determinata de:

• numarul si natura unitatilor pipeline paralele (acestea determina numarul si natura instructiunilor care pot fi tratate in acelasi timp)

• mecanismul utilizat de procesor pentru gasirea instructiunilor independente (cele care pot fi executate in paralel)

• Politicile utilizate pentru executia instructiunilor sunt caracterizate prin doi factori:• ordinea in care instructiunile sunt ordonate pentru executie;• ordinea in care instructiunile sunt finalizate (adica in care scriu rezultatele in registre si locatii de memorie).

• Cea mai simpla politica consta in executia si finalizarea instructiunilor in ordinea lor secventiala . Aceasta insa diminueaza sansele de a gasi instructiuni care sa se execute in paralel.

• Pentru a inbunatati paralelismul, procesorul trebuie sa “priveasca inainte” ca sa gaseasca instructiuni independente, ce pot fi executate in paralel. Acestea vor fi executate intr-o ordine diferita decat cea strict secventiala, cu singura restrictie ca rezultatul final trebuie sa fie cel corect!

Politici de executie:

1. In-order issue with in- order completion2. In-order issue with out-of- order completion3. Out-of-order issue with out-of- order completion

Politici pentru executia paralela a instructiunilor (2)Exemplu: consideram o arhitectura superscalara care poate citi si decodifica simultan doua instruct., are 3 unitati functionale care lucreaza in paralel (sumator si multiplicator intregi, unitate virgula flotanta) si poate scrie simultan rezultatele a doua instruct.).

Consideram secventa:

• I1 necesita doua cicluri pentru executie;• I3 si I4 sunt in conflict pentru aceeasi unitate functionala;• I5 depinde de valoarea produsa de I4 (dependenta de date propriu-zisa);• I2, I5 si I6 sunt in conflict pentru aceeasi unitate functionala.

In-order issue with in-order completion (1)• Instructiunile sunt lansate in executie exact in ordinea care corespunde executiei secventiale.

In consecinta:

• o instructiune nu poate fi tratata decat dupa ce a fost tratata cea anterioara;• o instructiune nu poate fi terminata decat dupa ce s-a terminat cea anterioara.

• Pentru garantarea finalizarii in ordine, tratare secventei se blocheaza atunci cand apar conflicte sau atunci cand unitatea cere pentru executie mai mult decat un ciclu de ceas.

In-order issue with in-order completion (2)

• Procesorul detecteaza si rezolva (prin blocare) situatiile de dependenta de date si conflicte de resurse.

• Deoarece instructiunile sunt tratate in ordine stricta, paralelismul rezultant este foarte mult dependent de modul in care programul a fost scris si compilat.

• Exemplu (slide urmator): daca I3 si I6 isi schimba pozitiile, perechile I6-I4 si I5-I3 pot fi executate in paralel

In consecinta, au fost cautate tehnici care sa faca hardul capabil sa detecteze in avans instructiunile executabile in paralel si sa le

ordoneze pentru executie (fara apel la compilator)

In-order issue with in-order completion (3)• Daca compilatorul genereaza secventa modificata de mai jos, I6-I4 si I5-I3 se pot executa in

paralel si secventa necesita numai 6 cicli in loc de 8:

In-order issue with in-order completion (4)

• Procesorul detecteaza numai dependentele reale de date, nu si dependentele de iesire si antidependentele. Niciuna dintre aceste tipuri de dependente nu vor fi violate prin executia in ordine!

• Dependenta de iesire

• Antidependenta

Out-of-order issue with out-of-order completion (1)

• La executia in ordine, nicio instructiune noua nu poate fi lansata, atunci cand procesorul a detectat un conflict si este blocat. Procesorul nu poate explora in avans, pentru a depista noi instructiuni ce pot fi executate in paralel cu cele actuale.

• Executia in afara ordinii incearca sa rezolve problema de mai sus, adaugand grupului de instructiuni care sunt tratate la un moment dat si altele, selectate in avans si in orice ordine, cu singura conditie ca rezultatul programului sa fie cel corect.

Out-of-order issue with out-of-order completion (2)

• Daca vom consideram secventa de instructiuni din slideul anterior: - I6 poate fi acum tratata inaintea lui I5 si in paralel cu I4. seventa se executa in 6

cicli (fata de 8, la executia in ordine)

Out-of-order issue with out-of-order completion (3)

• Aceasta tehnica poate sa rezolve toate cele trei tipuri de dependente, putand fi astfel rezolvate atat

dependente de iesire:

cat si antidependente:

Redenumirea registrilor• Dependentele de iesire si antidependentele pot fi tratate ca si conflicte normale, la fel ca si

dependentele de date.

• Paralelismul poate fi imbunatatit eliminand aceste dependente, care nu sunt dependente de date reale.

Eliminarea celor doua dependente se poate face prin alocarea automata de noi registri pentru stocarea valorilor care pot provoca aceste dependente.

Tehnica se numeste redenumirea registrilor.• Exemple:

• Dependenta de iesire se elimina prin alocarea, de exemplu, a registrului R6 pentru valoarea R2+R5.

• Similar se procedeaza si in antidependenta de mai jos:

Arhitecturi superscalare – comentarii finale

• Procesoarelor superscalare le sunt caracteristice urmatoarele tehnici:- unitati pipeline suplimentare care lucreaza in paralel;- executia instructiunilor altfel decat ordinea secventiala din program a acestora (out-of-

order issue/out-of-order completion);- redenumirea registrilor

Toate tehnicile de mai sus sunt capabile de a spori performanta procesorului

• Experimentele au demonstat ca:• fara utilizarea altor tehnici, simpla adaugare de noi unitati nu este eficienta;• tratarea out-of-order este foarte importanta, pentru ca permite identificarea in avans a instructiunilor

cu executie independenta;• redenumirea registrilor poate creste performanta cu peste 30%; in acest caz penalitatile se

datoreaza numai dependentelor propriu-zise de date (adevarate);• este importanta asigurarea unei capacitati de fetch/decodificare pentru circa 16 istructiuni simultan,

in vederea identificarii celor independente.

Exemple de arhitecturi superscalare• Power PC 604

- sase unitati independente de executie:- unitate de executie salturi- unitate Load/Store- 3 unitati de calcul cu intregi- o unitate vigula flotanta

- tratare in-order• Power PC 620

- suplimentar fata de PC 604, tratare out-of-order• Pentium

- trei unitati de executie independente: - 2 unitati de calcul cu intregi- o unitate virgula flotanta

- tratare in-order, doua instructiuni simultan pe ciclul de ceas• Pentium II-IV

- suplimentar fata de Pentium, tratare out-of-order- cinci instructiuni pot fi tratate intr-un ciclu de ceas

Puncte tari si puncte slabe in arhitecturi superscalare

• Bun:• hardul rezolva totul:

• detecteaza potentialul de paralelism;• incearca sa trateze in paralel cat mai multe instructiuni posibile;• rezolva redenumirea registrilor.

• compatibilitatea binara:• atunci cand sunt adaugate noi unitati functionale intr-o npua versiune arhitecturala (fara a se

modifica setul de instructiuni!), vechile programe pot beneficia si ele de potentialul suplimentar de paralelism

• Rau:• foarte complexe

- este nevoie de mult hard pentru investigarea in avans a instructiunilor in timpul executiei programului si exista limite in aplicarea acestei tehnici.- consumul de energie creste foarte mult

• fereastra de instructiuni este limitata – rezulta limitari in detectarea potentialului de paralelism al instructiunilor.

Procesoarele VLIW - alternativa la superscalare

• Arhitecturile VLIW permit detectarea potentialului de paralelism in timpul compilarii programului:

• dupa ce instructiunea a fost citita (fetch), toate operatiile corespunzatoare sunt tratate

in paralel;• nu mai este necesar hardul suplimentar destinat detectarii paralelismului in timpul

executiei;• este rezolvata problema ferestrei de instructiuni: compilatorul poate analiza intregul

program pentru a detecta operatiile paralele.

Procesoarele VLIW

Detectarea paralelismului si impachetarea operatiilor in instructiuni se face offline, de catre compilator

Procesoarele VLIW

Avantajele si problemele procesoarelor VLIW

Avantaje:- hardware simplificat – numarul unitatilor functionale (FU) poate fi crescut oricat de mult, fara a

mai fi nevoie de hardul sofisticat suplimentar, pentru detectarea paralelismului- compilatoarele performante pot detecta paralelismul pe baza analizei globale a programului –

se elimina problema ferestrei de instructiuni

Probleme:- necesitatea unui mare numar de registre care sa pastreze operanzi si rezultate pentru toate FU

active- capacitate mare de transport intre FU, registre si memorie- magistrala cu banda larga intre memoria cache si unitatea fetch (ex.: o instructiune cu 7

operatii, fiecare pe 24 de biti, rezulta 168 biti/instructiune)- cod de program de mari dimensiuni, in special datorita operatiilor neutilizate (se irosesc biti din

codul instructiunii)- cod binar nereutilizabil – daca in noua versiune de procesor se introduce o FU noua, numarul

operatiilor posibil a fi executate in paralel creste, cuvantul (formatul) instructiunii se schimba si astfel vechiul cod de program nu va mai putea fi executat.

ARHITECTURI PENTRU CALCUL PARALEL

1. De ce calcul paralel2. Programe paralele3. Clasificarea Flynn a arhitecturilor de calculator4. Executia arhitecturilor paralele5. Retele de intercomunicatie6. Masinile celulare7. Multiprocesoare8. Multicomputere9. Procesoare vectoriale10. Extensiile multimedia ale microprocesoarelor

• Nevoia de calcul mai performatLa cresterea randamentului de calcul al procesoarelor moderne contribuie doi

factori principali: 1. Tehnologiile pentru realizarea circuitelor2. Caracteristicile arhitecturale:

- memorii cache de mari dimensiuni- magistrale multiple rapide- prelucrare pipeline- Arhitecturi superscalare (unitati functionale multiple)

• Totusi: • calculatoarele dotate cu UC relativ simple, ca si cele de mai sus, nu sunt frecvent capabile

de a satisface nevoile de executie pentru o serie de aplicatii, ca, de ex.:- analize aerodinamice sau a fluxurilor de curgere a lichidelor; - simularea sistemelor complexe, in fizica, economie, biologie, tehnica; - proiectarea si simularea asistata de calc; - multimédia.

Aplicatiile de mai sus sunt caracterizate printr-un volum foarte mare de calcule numerice si/sau cantitati foarte mari de date de intrare

De ce calcul paralel?

O solutie: calculatoarele paralele

• Solutie pentru nevoia de randament ridicat: arhitecturi in care mai multe UC functioneaza impreuna pentru a rezolva anumite aplicatii.

• Caracteristici principale ale calculatoarelor paralele:

- numarul si complexitatea unitatilor centrale; - disponibilitatile comune (memoria partajata); - topologia de interconectare; - performanta retelei de interconectare; - resursele de I/E.

- altele

Astfel de calculatoare pot fi organizate in trei modalitati (clasificarea Flynn)

Programele paralele (1)

Programele paralele (2)

Programele paralele (3)

Programele paralele (4)

Programele paralele (5)

Programele paralele (6)

Programele paralele (7)

Clasificarea Flynn a arhitecturilor de calculatoare

Clasificarea Flynn este bazata pe natura fluxurilor de instructiuni executate de calculator si a fluxurilor de date care sunt tratate de aceste instructiuni.

Clasificarea Flynn: 1. Flux simplu de instructiuni, flux simplu de date (SISD). 2. Flux simplu de instructiuni, flux multiplu de date (SIMD) 3. Flux multiplu de instructiuni, flux simplu de date (MISD) 4. Flux multiplu de instructiuni, flux multiplu de date (MIMD)

Clasificarea arhitecturala Flynn (2)

Clasificarea arhitecturala Flynn (3)

Clasificarea arhitecturala Flynn (4)

Clasificarea arhitecturala Flynn (5)

Performantele arhitecturilor paralele

Intrebari importante:

• Cum trebuie sa functioneze un calculator paralel pentru a dispune de potentialul sau maxim?

• Ce viteza de executie se poate obtine intr-un calculator paralel,

pentru o aplicatie concreta ? • Cum masuram performanta unui calculator paralel ?

Metrici de executie

• Viteza maximala: volumul maxim de calcul care poate fi teoretic atins, atunci cand toate modulele sunt integral utilizate.

Aceasta valoare nu are semnificatie practica pentru utilizatori, fiind utilizat de producatori pentru a-si face publicitate produselor.

• Sporul de viteza (speedup): masoara castigul obtinut utilizand un anumit calculator paralel pentru executia unui program paralel dat.

• Ts - timpul de executie necesar, utilizand cal mai bun algoritm secvential; • Tp - timpul de executie necesar cu un algoritm paralele.

Metrici de executie

• Eficacitatea: aceasta metrica leaga speedup cu numarul de procesoare utilizate; ea furnizeaza o masura a eficacitatii de care sunt capabile procesoarele .

• S: speedup; • p: numarul de procesoare.

Pentru situatia ideala, in teorie:

Practic, eficacitatea reala cu valoarea 1 nu poate fi atinsa!

Legea lui Amdahl

Fie f partea de calcule care, conform algoritmului, trebuie executate secvential (f intre 0 si 1). Fie p numarul de procesoare.

Legea lui Amdahl (2)

• Legea lui Amdahl: nu se poate obtine un speedup mai mare de 1/f , indiferent de numarul de procesoare. La procesoarele paralele, oricat de mica ar fi partea de calcul secvential, aceasta impune o anumita limitare in speedup

Pentru exploatarea la maxim a numarului mare de procesoare, f trebuie sa fie mic (algoritmul trebuie sa fie puternic paralel).

Alte aspecte care limiteaza speedup

• in afara de secventialitatea intrinseca a anumitor parti ale unui algoritm, exista si alti factori care limiteaza speedup-ul:

- costul comunicatiilor; - echilibrarea sarcinilor pe procesoare; - costul programarii paralele a proceselor de calcul; - operatiile de I/E

• Exista numerosi algoritmi cu un grad ridicat de paralelism; pentru acestia,

valoarea lui f este foarte mica si poate fi ignorata. Ei sunt potriviti pentru sistemele masiv paralele. In aceste situatii, alti factori produc limitari ca, de exemplu, costul comunicatiilor, care poate deveni critic.

Eficacitatea si costurile de comunicatie

Sa consideram un calcul masiv paralel, in asa fel incat f (proportia calculelor secventiale) poate fi neglijat.

Notam cu: fc - costurile generale de comunicatie ale procesorului;Tcalc - timpul in care procesorul executa calcule; Tcomm – timpul in care procesorul este inactiv, datorita comunicatiilor;

• Cu algoritmii avand un grad ridicat de paralelism, calculatoarele masiv paralele, cu cu un mare numar de procesoare, pot fi utilizate eficace daca si fc este mic; asta inseamna ca timpul necesar procesorului pentru comunicatii trebuie sa fie mic, comparabil cu timpul sau util dedicat calculelor.

• Pentru a mentine fc rezonabil mic, numarul de procesoare nu trebuie sa depaseasca o anumita limita superioara .

Reteaua de intercomunicatii

• Reteaua de intercomunicatii (RI) este o componenta cheie a arhitecturii, care are o influenta decisiva asupra executiei si a costurilor globale ale acesteia.

• Traficul in RI se compune din transferul datelor, comenzi si cereri. • Parametrii principali ai RI sunt:

- largimea totala de banda : biti/seconda transferati; - costul.

Reteaua de intercomunicatii (2)

• retelele tip magistrala sunt simple si ieftine. • ele permit o singura comunicatie simpla pe unitatea de timp; largimea de banda este

partajata de toate nodurile. • performanta este relativ slaba. • pentru mentinerea la o anumita performanta, numarul de noduri este limitat (16 - 20).

Reteaua de intercomunicatii (3)

• fiecare nod este legat cu toate celelalte. • comunicatiile pot fi efectuate in paralel intre toate perechile de noduri. • executia e rapida, dar costurile sunt ridicate. • costul creste rapid cu numarul de noduri.

Reteaua de intercomunicatii (4)

• reteaua crossbar este o retea dinamica: topologia de intercomunicare poate fi modificata prin pozitionarea unor comutatoare.

• reteaua este integral conectata: orice nod poate fi direct legat la oricare altul. • sunt necesare mai putine intercomunicatii decat la reteaua statica integral

conectata; totusi, este necesar un mare numar de comutatoare. • un mare numar de comunicatii pot fi executate in paralel (un anumit nod poate

primi sau transmite simultan date).

Reteaua de intercomunicatii (5)

• retelele mash (plasa) sunt mai ieftine decat cele integral conectate si furnizeaza o performanta relativ buna .

• pentru a transmite o informatie intre anumite noduri este necesara o rutare prin noduri intermediare (maximum 2*(n-1) intermediare pentru o plasa cu n x n noduri).

• Sunt posibile racordari pentru buclarea informatiei: ex. intre nodurile 1 si 13, 2 si 14, etc.

• au fost realizate si mash-uri tridimensionale.

Reteaua de intercomunicatii (6)

• cele 2**n noduri ale retelei hypercub sunt aranjate intr-un cub n-dimensional. Fiecare nod este racordat la cele n vecine.

• pentru a transmite o informatie intre noduri, este necesara rutarea prin noduri intermediare (maxim n intermediari).

Calculatoarele SIMD

• Calculatoarele SIMD se numesc in mod obisnuit masini celulare (array processors). • Unitatile paralele (PU) sunt de obicei foarte simple: un ALU care executa sirul de instructiuni lansat de

CU, cateva registre si o memorie locala. • Primul calculator SIMD - ILLIAC IV (anii 70): 64 procesoare relativ puternice relativement puissants, in

retea mash (ca in figura)• Calculatoare comerciale recente:

- CM2 (Connection Machine) fabricat de Thinking Machine Company: 65 536 procesoare foarte simple (legate in hypercube). • masinile celulare sunt puternic specializate pentru probleme numerice cu date care pot fi

exprimate in format matriceal sau vectorial. Fiecare unitate centrala calculeaza un element al rezultatului(ex. de program de la inceputul cursului).

Multiprocesoarele

Calculatoarele MIMD cu memorie partajata se numesc multiprocesoare.

• Unele multiprocesoare nu au niciun fel de memorie partajata. Memoria centrala a sistemului este accesibila in mod egal tuturor procesoarelor. Intreaga memorie este distribuita ca si memorie locala pentru procesoare.

• Totusi, fiecare procesor are acces la memoria locala a celorlalte si este disponibil si un spatiu de adrese fizice global.

• Acest tip de organizare se numeste memorie partajata distribuita.

Multiprocesoarele

• Comunicatia intre procesoare se face prin intermediul memoriei partajate. Daca un procesor schimba o valoare intr-o locatie a acestea, toate celelalte procesoare pot citi aceasta noua valoare.

• Din punct de vedere al programatorului, comunicatia este realizata

prin variabile partajate, adica variabile care pot fi accesate de catre oricare dintre procesele (activitatile) paralelele:

Ex.:- tabela t in slide 5; - matricele a, b,si c in slide 7;

• Conflictele de memorie pot degrada serios performanta multiprocesorului. Este si motivul pentru care aceste arhitecturi nu suporta un numar ridicat de procesoare.

Exemple de multiprocesoare

• IBM System/370 (anii 70): doua UC IBM conectate la memoria partajata. • IBM System370/XA (1981): la memoria partajata pot fi conectate UC multiple. • IBM System/390 (lanii 90): caracteristici asemanatoare cu S370/XA, performanta

ameliorata. Posibilitatea de a lega intre ele mai multe sisteme multiprocesor prin conexiuni rapide pe fibre optice.

• CRAY X-MP (jumatatea anilor 80): patru procesoare vectoriale conectate la o memorie partaja (durata ciclului: 8,5 ns).

• CRAY Y-MP (1988): opt procesoare vectoriale conectate la o memorie partaja; de 3 ori mai puternic decat un à 8 processeurs vectoriels relié à la mémoire partagée; CRAY X-MP (durata ciclului: 4 ns).

• C90 (inceputul anilor 90): dezvoltarea lui CRAY Y-MP; 16 procesoare vectoriale. • CRAY 3 (1993): maxim 16 procesoare vectoriale (durata ciclului 2ns). • Butterfly multiprocesseur systeme, fabricat de BBN Advanced Ordinateurs (1985/87):

maxim 256 procesoare Motorola 68020, conectate impreuna printr-o retea dinamica de comutatie sofisticata; organizare distribuita a memoriei partajate.

• BBN TC2000 (1990): versiunea ameliorata a lui Butterfly , utilizand procesoare Motorola 88100 RISC.

Multicomputerele

Multicomputerele sunt calculatoare MIMD cu un spatiu de adrese distribuit, astfel incat fiecare procesor are propria sa memorie, care nu poate fi accesata de alte procesoare.

Multicomputerele (2)

• Comunicatia intre procesoare se face numai prin passing messages, lansate in reteaua de intercomunicatie.

• Din punct de vedere al programatorului, consecinta este ca nu are disponibila nicio variabila partajata (o variabila poate fi consultata numai de un proces simplu).

• Pentru comunicatia intre procese (activitati paralele) programatorul utilizeaza canale si operatii send/receive (ex. in slide 10).

• Nu exista concurenta intre procesoare pentru memoria partajata. In consecinta, numarul de procesoare nu mai este limitat de conflictele de memorie.

• Viteza retelei de intercomunicatie este un parametru important al executiei globale.

Exemple de multicomputere

• Intel iPSC/2 (1989): 128 UC de tip 80386 conectate printr-un hypercube 7-dimensional (2 **7 = 128).

• Intel Paragon (1991): peste 2000 procesoare de tip i860 (randement ridicat RISC) conectate printr-o retea mash bidimensionala.

• KSR-1 (1992): 1088 procesoare conectate printr-o retea ring (inel); fabricat de Kendal Square Research.

• nCUBE/2S (1992): 8192 procesoare conectate printr-un hypercube 10-dimensional; fabricat de nCUBE.

• Cray T3E MC512 (1995): 512 UC legate printr-un mash tridimensional; fiecare unitate centrala este un DEC Alpha RISC.

• Retele de posturi de lucru: Un grup de posturi de lucru este conectat printr-o retea locala (LAN) si poate fi

angajat pentru un calcul paralel, ca un multicomputer.Performantele sunt de obicei inferioare celor ale multicomputerelor specializate, din

cauza vitezei de comunicatie in LAN. Totusi, aceasta poate fi o solutie ieftina.

Procesoarele vectoriale

• Procesoarele vectoriale includ in setul lor atat instructiuni scalare, cat si instructiuni pentru operatii asupra vectorilor.

• Masinile celulare – SIMD – pot opera asupra vectorilor executand simultan aceeasi

operatie asupra fiecarui element al vectorului. Fiecare element va fi prelucrat de un element de tratament separat.

• Procesoare vectoriale sunt calculatoare cu arhitecturi care dispun

de facilitati de executie a instructiunilor vectoriale, valorificand paralelismul furnizat de de unitatile functionale pipeline.

Procesoarele vectoriale (2)

• Procesoarele vectoriale nu sunt procesoare paralele propriu-zise: ele nu au mai multe UC care sa functioneze in paralel. Ele sunt procesoare SISD care au implementat instructiuni pentru vectori, puse in aplicatie de unitati functionale pipeline.

• Procesoarele vectoriale au de obicei registre de vector, care pot stoca fiecare 64 pana la 128 cuvinte.

• Instructiunile vectoriale permit:

- incarcarea unui vector din memorie in registrul de vector;- stocarea vectorului in memorie; - operatii aritmetice si logice intre vectori; - operatii intre vectori si marimi scalare;

- Altele

• Din punct de vedere al programatorului, acest lucru ii permite sa utilizeze direct in program operatii asupra vectorilor (ex slide 8); compilatorul le va traduce in instructiuni vectoriale la nivel masina.

Procesoarele vectoriale (3)

Unitatea vectoriala

• O unitate vectoriala se compune tipic din:

- unitati functionale pipeline; - registri de vector; • Registrii de vector:

n registri de vector generali Rj; registrul VL al lungimii vectorului; stocheaza lungimea l du vectorilor tratati la

momentul respectiv; registrul masca M; stocheaza un ansamblu de l biti, cate unul pentru fiecare element

din registrul de vector, interpretat ca valori booleeane; instructiunile vectoriale pot fi executate in mod masca, adica elementele registrului de vector care au asociate in M valoarea 0 vor fi ignorate (netratate).

Instructiunile vectoriale

• Executia inmultirii vectorului nu se poate face pana cand nu s-a terminat adunarea vectorului; elementele sumei sunt produse printr-o pipeline sumatoaresi intra intr-o pipeline multiplicatoare; astfel, adunarea si inmultirea sunt executate (partial) in paralel.

Instructiunile vectoriale

Intr-un limbaj asemanator Pascal, cu calcul vectorial:

Un compilator pentru un procesor vectorial produce aceasta secventa:

Extensiile multimedia la microprocesoarele de uz general

• Aplicatiile video si audio solicita frecvent operatii cu date de mici dimensiuni (8 sau 16 bits).

• Aceste operatii valorifica potentialul important de paralelism SIMD (vectorial).

• Noile generatii de microprocesoare pentru uz general au

fost echipate cu instructiuni speciale, pentru exploatarea acestui potential de paralelism.

• Instructiunile specializate pentru multimedia executa calcule vectoriale la nivel de bit, semicuvant sau cuvant.

Extensiile multimedia

• Mai multi constructori au extins setul de instructiuni al procesoarelor pentru a ameliora executia aplicatiilor multimedia:

- MMX pentru Intel x86; - VIS pentru UltraSparc; - MDMX pentru MIPS; - MAX - 2 pentru Hewlett-Packard PA-RISC. • Linia Pentium furnizeaza 57 instructiuni MMX. Ele trateaza

datele in mod SIMD.

Extensiile multimedia

• Ideea fundamentala: executia unor subcuvinte (subword) :• Se foloseste intreaga largime a canalului de date al procesorului (32 sau 64 bits), numai

ca se trateaza date de tip redus (utilizate in tratamentul semnalelor - 8, 12, sau 16 bits).

• Cu un cuvant de 64 bits, sumatoarele pot fi utilizate pentru a efectua in paralel 8 adunari, fiecare pe 8 biti.

• Metoda reprezinta practic un tip de paralelismSIMD, dar practicat la scara redusa.

Extensiile multimedia

• Pentru operatiile multimedia sunt definite trei tipuri de date impachetate: byte impachetat, semicuvant impachetat, cuvant impachetat.

Extensiile multimedia

Un exemplu de aritmetica SIMD cu setul de instructiuni MMX:

Extensiile multimedia

• Cum sa obtinem datele gata pregatite pentru calcul? • Cum sa obtinem rezultatele intr-un format adecvat?

• Solutia: impachetarea si despachetarea datelor

Rezumat

• Nevoile crescande de randament ridicat in prelucrare nu pot fi satisfacute totdeauna de calculatoarele uzuale, dotate cu o singura UC.

• La calculatoarele paralele, mai multe UC functioneaza impreuna pentru a rasounde unei aplicatii date.

• Pentru a utiliza calculatoare paralele, trebuie sa avem disponibile programe paralele.

• Calculatoarele pot fi clasificate pe baza modului de tratare a fluxurilor de instructiuni si de date asociate acestora. Clasificarea Flynn propune SISD, SIMD, MIMD.

• Performanta in executie obtinuta prin utilizarea calculatoarelor paralele depinde nu numai de numarul de procesoare disponibile, ci poate fi limitata de caracteristicile programelor executate.

• Eficacitatea utilizarii unui ordinator paralel este influentata de caracteristici ale programului paralel, ca: gradul de paralelism, intensitatea comunicarii interprocesoare, etc.

Rezumat

• O componenta cheie a unei arhitecturi paralele este reteaua de intercomunicatie.

• Masinile celulare executa aceleasi operatii , ca un ansamblu de unitati de tratare conectate impreuna.Ele sunt specializate pentru probleme numerice exprimate in format matriceal sau vectorial.

• Multiprocesoarele sunt calculatoare MIMD in care toate UC-urile au acces la un spatiu de adrese partajate comune. Numarul de uc este limitat.

• Multicomputerele au un spatiu de adrese distribuit. Comunicatia intre UC se face numai prin lansarea unor mesaje in reteaua de intercomunicatie. Numarul de UC conectate poate fi mare.

• Procesoarele vectoriale sunt de tip SISD si includ in setul lor instructiuni pentru operatii asupra vectorilor. Ele sunt implementate prin unitati functionale pipeline.

• Aplicatiile multimedia solicita un mare potential de paralelism, oferit de SIMD. Setul de instructiuni al micropocesoarelor de uz general moderne (Pentium, UltraSparc) a fost extins pentru a suporta stilul de paralelism SIMD, cu operatii asupra vectorilor scurti.