Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


SISTEME CU PROCESOARE MULTIPLE

algoritmi



+ Font mai mare | - Font mai mic



SISTEME CU PROCESOARE MULTIPLE


Elemente definitorii (1)

Presupune parcurgerea anterioara a cursurilor ASDN, DCE, AC, AMP, SMP, cunostinte solide de progrmare, cunoasterea limbii engleze



Competente dobandite in urma promovarii:

o        intelegerea functionarii sistemelor care contin procesoare multiple

o        proiectarea de sisteme cu procesoare multiple cu aplicatii real time

o        programarea structurilor cu procesoare multiple

Elemente definitorii (2)

Microprocesorul unic, oricat de puternic, nu poate asigura functionarea in timp real a unor largi clase de aplicatii moderne (e.g. administration, banking, weather prediction, air and ground transport, process modeling and identification etc.)


Rezulta necesitatea utilizarii de sisteme cu procesoare multiple, cu structuri, complexitati si functii adaptate aplicatiilor in cauza


Cunoasterea intima a acestor sisteme confera abilitati de intelegere a integrarii SPM in aplicatii, precum si de proiectare si de programare a SPM


Evaluarea Cunostintelor (1)

Structura cursului:

14 sapt x 4 ore/sapt = 56 ore curs

14 sapt x 2 ore/sapt = 28 ore aplicatii


Metoda de evaluare a cunostintelor: evaluarea continua


Evaluare a activitatii la curs: 1 examen scris (sapt. 8), 1 examen scris+oral (sesiunea de iarna)


Evaluare a activitatii aplicative: 4 teme cu pondere egala:

1 lucrare de cercetare (gen referat) pe o tema legata de materia studiata

1 program de simulare

2 programe de programare paralela.

SPM
Evaluarea Cunostintelor (2)

Baza materiala:

25 PCuri conectate la Internet (ED308) + 12 PCuri conectate la Internet (ED312)


Structura de servere IBM pentru studiul structurilor cu procesoare multiple si programare sub Linux (ED320, ED309)


Materiale elaborate in anii anteriori

Note de curs, difuzate saptamanal, anticipat (7 zile in avans)


Probele de examen:

Saptamana 8:

2 subiecte + 1 problema,

pondere 30 % din nota la examen

conditie de promovare: minimum 5


Sesiunea de iarna:

2 subiecte + 1 problema,

Examen oral, 2 subiecte

pondere 30 % din nota la examen

conditie de promovare: minimum 5


Aplicatii:

Cele 4 teme, notate de la 0 la 10, suma minima pentru promovare 24


Ponderea examenelor: 60% (30% P + 30% F)


Ponderea aplicatiilor: 40% (10% + 10% +10% + 10%)

Principalele capitole ale cursului

Introducere. Clasificari ale arhitecturilor paralele. Evaluarea performantelor si a calitatii.


  1. Procesoare pipeline
    1. Introducere
    2. Structuri
    3. Performante
    4. Tipologie
  2. Pipeline pentru instructiuni
    1. Problematica
    2. Cresterea ratei de transfer
    3. Bottlenecks
    4. Hazard structural
    5. Hazard datorat datelor
    6. Hazard datorat structurii de comanda
  3. Pipeline pentru operatii aritmetice
  4. Controlul si planificarea structurii pipeline
    1. Planificare statica
    2. Planificare dinamica
    3. Utilizarea intarzierilor
  5. Retele de interconectare
    1. Introducere
    2. Topologii statice

i. Magistrala comuna

ii. Linear array

iii. Inel

iv. Arbore binar

v. Fat-tree

vi. Shuffle-exchange

vii. Retea bidimensionala

viii. Hypercurbe

ix. Retea n-dimensionala

x. Cyclic Connected Cube

xi. Dirijare

xii. Latenta

    1. Topologii dinamice

i. Retele fara blocare

ii. Retele cu rearanjare

iii. Retele cu blocare

    1. Decizii privind interconectarea

i. Mod de operare

ii. Metodologie de comutare

iii. Topologia retelei

iv. Strategia de comanda a comutatorului

  1. Multiprocessors & Multicomputers
    1. Introducere
    2. Multiprocesoare

i. Retele de interconectare

ii. Scheme de coerenta cu memorie cache

    1. Specificatie unificatoare pt sisteme multiprocesor
    2. Multicomputers
    3. Multiprocessor sau multicomputer
    4. Multi-multiprocessors
  1. Notiuni de programare paralela si algoritmi paraleli
    1. Introducere
    2. Modele de programare

i. Programare pe multiprocesoare

ii. Programare pe multicomputere

    1. Calcul paralel

i. Partitionare

ii. Alocare, planificare

    1. OpenMP
    2. Structuri de algoritmi

i. Structura sincrona

ii. Structura pipeline

    1. Exemple
  1. Arhitecturi data flow si sistolice
    1. Introducere
    2. Data-flow
    3. Matrice sistolice
  2. Exemple


BIBLIOGRAFIE

Tanenbaum, van Steen: Distributed Systems, 2002

Grama, Gupta, Karypis, Kumar: Introduction to Parallel Computing, 2003

Culler, Pal Singh: Parallel Computer Architecture, 1999

Intel MultiProcessor Specification

OpenMP Application Program Interface

CAPITOLUL 1 - Clasificari arhitecturale


Ce se urmareste in acest capitol:

Trecerea in revista a diverselor clasificari (taxonomii) pentru sisteme cu procesoare multiple

Evidentierea diferentelor intre structurile realizabile practic

Evaluarea posibilelor domenii de aplicatii pentru fiecare structura

Evaluarea performantelor si a calitatii


Introducere

Costul si performantele - cei doi parametri majori de evaluare a arhitecturilor de calcul

Obiectiv : minimizarea raportului cost / performanta


Masurarea performantei:

numarul maxim de operatii/secunda (operatii aritmetice, instructiuni, operatii I/0, etc.)

dimensiunile maxime ale programelor si datelor

comoditatea programarii

consumul de energie electrica

fiabilitatea

disponibilitatea

masa, volum


Introducere - Benchmarks


Benchmarks: pachete de programe standardizate care ruleaza pe masini pentru a le stabili performantele


  1. Kernel benchmarks: fragmente de cod extrase din programe reale, in care fragmentele de cod consuma cea mai mare parte a timpului de executie. Ex. Linpack (solutia sistemelor in mediu Fortran), Lawrence Livermore (24 bucle Fortran obisnuite, 1001 elemente).
  2. Local benchmarks: programe specifice locului (in-site, de firma), in general indisponibile pe scara larga
  3. Partial benchmarks: trace-uri ale programelor
  4. Recursive benchmarks: programe implementand algoritmi recursivi (Turnul din Hanoi, problema celor noua regine)
  5. Unix Utility and Application Benchmarks: larg utilizate in comunitatea Unix. SPEC (System Performance Evaluation Cooperative Effort) consta din 10 scenarii extrase dintr-o varietate de aplicatii stiintifice si ingineresti. Performanta se masoara in SPEC marks.
  6. Synthetic Benchmarks: mici programe special construite pentru evaluare. Nu efectueaza calcule utile, dar aproximeaza, in maniera statistica, caracteristicile medii ale programelor. Exemple tipice: Whetstone, Dhrystone.

Whetstone este utilizat pentru evaluarea abilitatii de a efectua calcule numerice, in esenta aritmetica in virgula mobila

Un mare volum de timp este consumat in bibliotecile matematice.

Foloseste putine variabile locale si multe globale.

9 bucle mici, un mare grad de code locality.


Dhrystone este bazat pe statistici recente, in special din system programming.

Contine relativ putine operatii in aritmetica mobila.

Un mare volum de timp este consumat in functii cu siruri (C - pana la 40%).

Nu contine bucle in programul principal - multe cache miss la procesoarele cu memorie cache mica.

Se manipuleaza putine date globale


  1. Parallel Benchmarks: utilizate la evaluarea arhitecturilor paralele. Recomandare a NIST: secventa de:

Linpack

Whetstone

Dhrystone

Livermore loops

Teste ale Fermi National Accelerator Laboratory

Testele NASA/Ames (12 subrutine Fortran)

Setul de probleme numerice al lui John RICE



Testele lui Raul MENDEZ pentru masini japoneze

Mai multe informatii:

Simpson, D. - The Trouble with Benchmarks, Systems Integration, Aug 1990, 37-45

Weicker, R.P. - An Overview of Common Benchmarks, IEEE Computer, 1990, 23:12, 65-75


Majoritatea imbunatatirilor performantelor se datoreaza progreselor tehnologiei hardware.

Progresul: de la tuburi electronice la VLSI

Trei  valuri  de calculatoare :

o        anii ' 60 : mainframes

o        anii ' 70 : minicomputers

o        anii ' 80 : microcomputers

In general, dezvoltarea software-ului a urmat un traseu independent de tehnologia hardware.

S-a afirmat ca tehnologia semiconductoarelor si-a atins limitele si progresul nu mai este posibil. Afirmatia este falsa.


Cand performanta dorita nu a mai putut fi obtinuta cu tehnologia hardware a momentului, s-a recurs la structuri pipeline si la structuri cu procesoare multiple, fara a se astepta o noua generatie tehnologica.

Prelucrarea paralela este considerata ca al 4-lea val in tehnica de calcul.


Tipuri de sisteme de calcul.

  1. Cu un singur procesor (serial) ;
  2. Structura pipeline ;

  3. Paralel (cu procesoare multiple)

1. serial


2. Pipeline 3. Paralel


De ce sunt necesare structuri puternice de calcul?


Clasificari arhitecturale

Sisteme cu procesor unic

Sisteme cu procesoare multiple

o        Sisteme multiprocesor

o        Sisteme distribuite


Prelucrarea paralela - cale de crestere a performantei. Ea necesita procesoare multiple.


Notiuni

D data stream - flux de date

I instruction stream - flux de instructiuni

S single - unic

M multiple - multiplu


Deci

SISD - Single Instruction Stream, Single Data Stream

SIMD - Single Instruction Stream, Multiple Data Stream

MISD - Multiple Instruction Stream, Single Data Stream

MIMD - Multiple instruction Stream, Multiple Data Stream


Influenta aplicatiei asupra arhitecturii

A - nivelul de paralelism permis de aplicatie

L - nivelul de paralelism permis de limbajul de programare

C - nivelul de paralelism permis de compilator

H - nivelul de paralelism permis de structura hardware


Minimizarea timpului de rulare a aplicatiei necesita :

A ≤ L ≤ C ≤ H


Caracterizarea aplicatiilor

Compuse din taskuri.

In aplicatii cu grad nenul de paralelism unele ruleaza in paralel.

Elemente de caracterizare

o        granularitate

o        grad de paralelism

o        nivelul de paralelism

o        interdependenta datelor (data dependency)


Granularitatea unui task

Dependenta de:

o        R - durata de executie (runtime)

o        C - durata comunicarii

Granularitate grosiera: R > > C

Granularitate fina: R < < C

Granularitate medie: R si C - comparabile


Gradul de paralelism

  • Masura numarului de fire (threads) executate simultan.
  • Nivelul de paralelism:
    • la nivelul procedurii
    • la nivelul taskului
    • la nivelul instructiunii
    • la nivelul operatiei
    • la nivelul microoperatiei (microcode)

Exemplu :

A = B * C + D * E + F * G

  • Gradul de paralelism ≤ 3 (in functie de numarul de procesoare)
  • Adunarile nu se pot face intotdeauna inaintea inmultirilor.
    • Necesitatea conservarii ordinii de obtinere a rezultatelor.
    • Interdependenta datelor (afecteaza si granularitatea ! )



Modele de procese



Taxonomii


Obiectivele clasificarilor :

  • Sa ofere raspunsuri la intrebari privind tipul paralelismului, arhitectura cu cele mai bune perspective de viitor, realizarile la zi privind o anume arhitectura.
  • Sa ofere posibile configuratii ce ar putea fi omise de catre arhitectii de sistem. Sa permita o examinare formala a posibilelor variante de arhitectura.
  • Sa permita construirea de modele utile de evaluare a performantei, evidentiind potentialul unei anumite arhitecturi pentru imbunatatirea performantelor.

Treleaven (1982), Myers (1982), preluate de Milutinovic (1989).

  • Control - driven (Control flow) - Activitatea de prelucrare este dictata de secventa de instructiuni. Datele sunt preluate de procesor cand este nevoie de ele.

RISC

CISC

HLL (high level language)

  • Data - driven (data-flow) - Activitatea de prelucrare dictata de disponibilitatea datelor necesare efectuarii unei instructiuni. Experimentala 
  • Demand - driven (reduction) Executia unei instructiuni este activata atunci cand rezultatul executiei ei este cerut de o instructiune deja activata pentru executie. Experimentala !

Taxonomia Flynn :

  • SISD - sisteme monoprocesor
  • MISD - procesoare pipeline
  • SIMD - array processors
  • MIMD - procesoare multiple

Avantajele MIMD

  • Viteza mare de prelucrare, daca prelucrarea poate fi descompusa in fire paralele, TOATE procesoarele prelucrand simultan
  • Intrucat procesoarele si blocurile de memorie sunt resurse de tip general, defectarea unei unitati se poate compensa prin alocarea sarcinii de prelucrare altei unitati (grad ridicat de Fault Tolerance)
  • Se poate utiliza reconfigurarea dinamica pentru a face fata gradelor variabile de incarcare a procesoarelor

Elemente de considerat in proiectarea MIMD

  • Planificarea procesoarelor: alocarea eficienta a taskurilor la procesoarele din sistem intr-o maniera dinamica, pe durata evolutiei prelucrarii
  • Sincronizarea procesoarelor: prevenirea situatiilor de tentativa simultana de schimb de date intre doua procesoare si respectarea restrictiilor de precedenta in manipularea datelor.
  • Elemente de considerat in proiectarea MIMD (2)
  • Proiectarea retelei de interconectare: retelele de interconectare procesor - memorie si procesor - procesor sunt, probabil, cele mai costisitoare elemente ale sistemului. De aici dedicarea de I/O procesoarelor si NU utilizarea unei retele de interconectare procesor - I/O
  • Overhead: in mod ideal, un sistem cu n procesoare ar trebui sa ofere o viteza de prelucrare (throughput) de n ori mai mare decat un sistem cu un unic procesor. In realitate, consumul suplimentar de resurse (overhead) pentru coordonarea activitatii procesoarelor si solutionarea competitiei pentru resurse comune (memorie, reteaua de interconectare) nu permite atingerea acestui deziderat.
  • Partitionarea: identificarea paralelismului in algoritmii de prelucrare si invocarea prelucrarii concurente nu este o problema triviala

Exemple de sisteme MIMD

  • Carnegie Mellon University: C.mmp, Cm*
  • New York University: Ultracomputer
  • University of Illinois: Cedar
  • BBN Butterfly
  • Alliant FX
  • Thinking Machine Corporation: CM-5
  • Intel: iPSc Series


Structura multiprocesor Structura multicomputer


Structura multi-multiprocesor



Arhitectura dataflow Structura Array Processor


Structura Procesor vectorial Structura Systolic Array




Taxonomia Skillcorn


Skillcorn considera urmatoarele niveluri de modelare a unui sistem de calcul:

  1. Modelul computational: Nivelul cel mai abstract de modelare, in cadrul caruia operatiile primitive sunt cele aritmetice si logice, iar comportamentul computational corect al programului este impus de catre programator. Nivelul nu permite analiza detaliilor structurale ale sistemului.
  2. Modelul masinii abstracte: Evidentiaza primul nivel de implementare a modelului computational. Capteaza esenta unei anumite arhitecturi din modelul computational, fara a distinge diferente tehnologice sau alte detalii de implementare. Este nivelul programatorului de descriere a arhitecturii utilizand registre, ALU, alte resurse ale arhitecturii.
  3. Modelul bazat pe performanta: acest nivel prezinta o viziune structurala a arhitecturii in termenii tranzitiilor de stare ale masinii. Nu se refera doar la tehnologia de realizare a masinii.
  4. Modelul implementarii: acesta reflecta detaliile de implementare in termeni de tehnologie, viteza etc.

Modelul masinii abstracte reprezinta nivelul superior al taxonomiei Skillcorn. Urmatorul nivel se bazeaza pe modelul bazat pe performanta


Skillcorn, D.B.A taxonomy for computer architecture, IEEE Computer 21 (11), 46-57


Taxonomia utilizeaza patru tipuri de unitati functionale in construirea masinii abstracte:

  • Procesorul de instructiuni (IP), unitate functionala care interpreteaza instructiunile (CU)
  • Procesorul de date (DP), unitate care transforma datele prin operatii artimetice si logice (ALU)
  • ierarhie de memorii care stocheaza datele (DM) si instructiunile (IM)
  • Un comutator care ofera interconectivitatea intre unitatile functionale (reteaua de interconectare)

Arhitectura SISD

  • IP - instruction processor
  • IM - instruction memory
  • DP - data processor

- Conexiunile intre unitatile functionale se fac prin comutatoare statice sau dinamice.

- Cele mai simple retele de interconectare - magistralele


Patru tipuri de modele abstracte de comutatoare :

  1. 1-to-1 poate fi uni sau bidirectionala
  2. n-to-n conexiune 1-to-1 multiplicata de n ori
  3. 1-to-n o unitate functionala se conecteaza la toate cele n unitati ale celuilalt set
  4. n-by-n oricare unitate functionala dintr-un set se poate conecta la oricare alta din celalat set

Tipuri de arhitecturi Skillcorn

Cl

IPs

DPs

IP-DP

IP-IM

DP-DM

DP-DP

Name




none

none


none



reduct/data flow

uniprocessor



n

none

none

n-n

none

separate machines



n

none

none

n-n

n x n

loosely coupled

reduct/data flow



n

none

none

n x n

none

tightly coupled

reduct/data flow



n

none

none

n x n

n x n








none

von Neumann

uniprocessor



n

1-n


n-n

none




n

1-n


n-n

n x n

Type 1 array

processor



n

1-n


n x n

none

Type 2 array processor



n

1-n


n x n

n x n



n


1-n

n-n


none



n


1-n

n x n


none



n

n

n-n

n-n

n-n

none

separate von

Neumann uniprocessors


n

n

n-n

n-n

n-n

n x n

loosely coupled

von Neumann


n

n

n-n

n-n

n x n

none

tightly coupled

von Neumann


n

n

n-n

n-n

n x n

n x n



n

n

n-n

n x n

n-n

none



n

n

n-n

n x n

n-n

n x n



n

n

n-n

n x n

n x n

none

Denelcor Heterogeneous

Element Processor


n

n

n-n

n x n

n x n

n x n



n

n

n x n

n-n

n-n

none



n

n

n x n

n-n

n-n

n x n



n

n

n x n

n-n

n x n

none



n

n

n x n

n-n

n x n

n x n



n

n

n x n

n x n

n-n

none



n

n

n x n

n x n

n-n

n x n



n

n

n x n

n x n

n x n

none



n

n

n x n

n x n

n x n

n x n


Clase de arhitecturi

Clasele 1,2,3,4,5 caracterizeaza arhitecturi data flow/reduction.

Clasa 6 se refera la SISD.


Clasele 7,8,9,10 sunt SIMD.

Clasele 11 si 12 califica MISD, chiar daca o asemenea arhitectura este considerata aberanta.

Clasele 13-20 reprezinta structuri conventionale MIMD cu diverse tipuri de retele de interconectare.

Clasele 21-28 sunt clase MIMD neexplorate inca.


Taxonomia Skillcorn o extinde pe cea a lui Flynn, evidentiind mai detaliat diferentele intre diversele tipuri de arhitecturi paralele.

SISD - Reprezentare abstracta


SISD - Structura interna - Procesor IP SISD - Structura interna - Procesor DP

SISD - Struct. interna - Procesor DP - Vers . rapida


SISD - Metode de imbunatatire

Arhitectura SISD se poate imbunatati prin :

Optimizarea digramei de stari in vederea scurtarii timpului de tranzit al jetonului prin retea. Nu produce noi tipuri de arhitectura 

Permisiunea ca mai multe stari sa fie active la un moment dat. Presupune utilizarea de arhitecturi pipeline


Arhitectura SIMD



Toate modelele din desenele ce urmeaza au un singur procesor (IP) de comanda, cu n procesoare artimetice (DP), interconectate prin comutator 1-to-n.



SIMD - Tip 1 SIMD - Tip 2


SIMD - Tip 3



Arhitecturi MIMD

In desene sunt ilustrate doua modele de sistem MIMD :

unul - tightly coupled (cu memorie comuna)

celalalt - loosely coupled (sistem distribuit)


MIMD - Arhitectura "tightly coupled"

In sistemele puternic cuplate ("tightly coupled"), procesoarele se conecteaza la memorii printr-un comutator dinamic arhitectura de acces uniform la memorie (UMA).

Comunicatia si sincronizarea intre procesoare se realizeaza prin zone comune de memorie.




MIMD - Arhitectura "loosely coupled"

In sisteme slab cuplate ("loosely coupled"), fiecare procesor dispune de memorie proprie (private memory).

Comunicatia intre procesoare se face prin mesaje (message passing).

o        arhitectura de acces neuniform la memorie (NUMA).


Exemple : Cm* (Carnegie Mellon University) si iPSc (Intel).





MIMD - Avantaje/Dezavantaje


Avantaj al sistemelor puternic cuplate : comoditate de programare oferita de spatiul comun de adrese

(shared address space).

Avantaj al sistemelor slab cuplate: scalability (posibilitate comoda de expandare)


Arhitecturi cu reducere ("reduction")

Modelul abstract al unei masini tip "reduction" - arhitectura demand driven.

Calculele sunt organizate sub forma unui graf ale carui:

o        nod radacina - este de tip "apply",

o        subarborele din stanga este "description of a function"

o        subarborele din dreapta este "description of the arguments"

Descrierea poate consta in valoarea propriu-zisa sau descrierea modului in care se obtine valoarea.

"Redex" - subarbore in care functia si argumentele sunt deja evaluate.

La executia unui redex valoarea rezultata inlocuieste redex-ul.

In general, la nivelul frunzelui arborelui, sunt disponibile (pentru executie) cateva redex-uri.

o        Pentru evaluarea lor se pot folosi in mod concurent procesoare multiple.

Daca nu exista nici un redex, calculele nu pot incepe.

Intrucat graful redus imbraca atat rolul instructiunilor (in structura), cat si cel al datelor (in continut), nu este necesar procesor IP, iar modelul abstract al masinii este de tipul MIMD puternic cuplat, fara IP si IM.


Exemplu


a = (d + e) + (f * g)

cu d = 1, e = 3, f = 5, d = 7



Nodul x creaza cereri de executie nodurilor 2 si 5. Aceste cereri se propaga in josul arborelui, spre frunze, care propaga rezultatele catre nodurile parinte 2 si 5.

Nodurile 2 si 5 sunt radacinile a doua redex.

Desenul arata starea sistemului dupa executia celor doua redex.



Arhitecturi cu reducere - Exemplu (1)



Arhitecturi cu reducere - Exemplu (2)


Arhitecturi cu reducere - Realizari, Exemple :

1. Newcastle University 2. Cellular Tree Machine (North California State University) 3. Applicative Multiprocessing System (University of Utah).

Arhitecturi Data flow


Arhitectura este de tipul "data driven".

Nu exista un mecanism explicit de secventiere a instructiunilor, iar calculele sunt controlate de disponibilitatea si dependenta datelor.

Modelul de calcul al unei arhitecturi data flow este sub forma unui graf orientat, numit graf data flow


Exemplu

a = (d + e) + (f * g)




Doua tipuri de arhitecturi dataflow Model Dataflow - Tip Dennis

  1. Arhitectura dataflow Manchester: toate datele din memorii sunt vizibile de catre toate DP echivalenta cu arhitectura cu reducere
  2. Modelul MIT (tip Dennis): fiecare procesor dispune de propria memorie. Schimbul de date se face prin mesaje transmise prin reteaua de interconectare.










Taxonomia Duncan


Definitie : Arhitectura paralel - arhitectura care ofera in mod explicit un cadru de nivel inalt pentru dezvoltarea solutiilor de programare paralela prin disponibilitatea de procesoare care coopereaza pentru rezolvarea prin executia concurenta a problemelor.

  • Definitia exclude arhitecturi continand mecanisme cu nivel coborat de paralelism (pipeline pentru instructiuni, unitati functionale multiple, cu CPU si procesoare I/O separate).

Clase

Clasificarea arhitecturilor paralele:

  • Arhitecturi sincrone
  • Arhitecturi MIMD
  • Modele MIMD (MIMD paradigm)

Subclase 

  • Arhitecturi sincrone :
    • Procesoare vectoriale
    • Arhitecturi SIMD
      • Matrice de procesoare
      • Procesoare asociative
    • Matrice sistolice
  • Arhitecturi MIMD
    • Memorie distribuita (cu transmisie de mesaje)
    • Memorie comuna
  • Modele MIMD
    • MIMD/SIMD
    • Dataflow
    • Reduction
    • Waterfront

Procesoare Vectoriale

  • Adecvate pentru calcule cu date structurate ca matrice.
  • n procesoare (sau statii de prelucrare) aranjate in structura pipeline.
  • Fluxul de date (elemente ale unei matrici sau vector) intra in pipeline prin procesorul 1, se deplaseaza din statie in statie si parasesc structura prin procesorul n.
  • Fluxul de date rezultat este stocat in memorie.
  • Unitatea de comanda a masinii are n subunitati, cate una pentru fiecare procesor.
  • Practic, toate arhitecturile utilizeaza pipeline, intr-o masura mai mare sau mai mica. Procesoarele vectoriale contin ALU cu un grad ridicat de pipelining.
  • Procesoarele vectoriale sunt caracterizate de multiple unitati functionale pipeline, care efectueaza operatii aritmetice si logice asupra unor date atat scalare, cat si vectoriale. Ele pot opera concurent. Aceste arhitecturi ofera prelucrare vectoriala paralel, printr-o structura pipeline de unitati functionale.
  • Pot dirija rezultatele de la iesirea unei pipeline la intrarea alteia inlantuire (chaining)
  • Register - based architecture
    • Exemplu : Cray - 1 Fujitsu VP-200
  • Memory - based architecture:
    • Ex.:CDC Cyber 205, Texax Instruments ASC (Advanced Scientific Computer)
  • Cray X-MP, Cray - MP: arhitecturi MIMD cu memorie comuna, cu 4 pana la 16 procesoare


Structura de procesor vectorial Arhitectura vectoriala registru - registru



Procesoare asociative (AM)


  • Procesor asociativ: SIMD avand drept componente principale memorii asociative.
  • AM - utilizate in operatii de cautari rapide.
  • Un model ("pattern") de date, furnizat sistemului, este comparat cu date de memorie. Se intocmeste lista locatiilor care contin modelul.


Procesoare asociative - Model Procesoare asociative - Operare


Procesor asociativ



Arhitecturi sistolice (AS)


  • Solutie pentru probleme in care coexista cerinte de manipulare a unui mare volum de date si cerinte de viteza inalta de prelucrare.
  • AS - structuri multiprocesor pipeline in care datele sunt  pulsate  in maniera ritmica din memorie printr-o retea de procesoare, rezultatele revenind in memorie.
  • Procesoarele sunt interconectate prin retele locale cu structura regulata.
  • In fiecare interval de timp procesoarele executa o secventa scurta si invarianta de instructiuni.
  • Structura "sistolica" evita stocarea intermediara, in memorie, in parcursul datelor de la o treapta de prelucrare la urmatoarea.


Arhitecturi sistolice - Structura Procesoare sistolice - Exemplu

Obiect: calculul produsului A*B





  • Fiecare procesor incepe cu acumulatorul inscris cu 0 si, pe durata fiecarui ciclu, aduna la acumulator produsul celor doua intrari.
  • Dupa 5 cicluri evaluarea produsului este completa.



Procesoare sistolice - Exemplu (2)


Elemente Definitorii

  • Throughput - masura indicand numarul de programe (taskuri) executate de procesor in unitatea de timp.
  • Utilization - fractiunea de timp pe durata careia procesorul este ocupat cu executia programelor. Reprezinta raportul intre timpul de activitate propriu-zisa si cel total intr-o perioada data.
  • Response-time - intervalul scurs intre emiterea unei cereri si executia ei. Se mai numeste turnaround time.
  • Elemente Definitorii (2)
  • Memory bandwidth - numarul de cuvinte de memorie accesate in unitatea de timp.
  • Memory access time - timpul mediu necesar procesorului pentru acces la memorie, exprimat, de regula, in ns.
  • Memory size - capacitatea memoriei exprimata, de regula, in MB.
  • Generality - masura indicand gama de aplicatii a unei arhitecturi

Caz tipic al distributiei instructiunilor


Operatii

Frecventa [%]

CPI

Ponderat

[cycles/instr]

Load and store




Integer add/subtract




Integer multiply/divide




F.P. add




F.P. multiply




Logical




Branch




Compare shift













Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1723
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved