1. Motivaţia
Calculul rezultat direct din definiţie
Yüklə 232,21 Kb.
|
- Bu səhifədəki naviqasiya:
- Metoda coeficient-vector
- Metoda listelor de vectori
- Metoda naivă
- Algoritmul lui Strassen A fost dedus de către Volker Strassen
- Algoritmul „celui mai mic exponent cunoscut” A fost prezentat de către Don Coppersmith şi Shmuel Winograd
- Evaluarea „doar local” pe un singur procesor
- Evaluarea „doar local” pe 2 procesoare
- Evaluarea „doar la distanţă” pe 2 calculatoare
Calculul rezultat direct din definiţie: 
Fig. 5.1 Figura de mai sus arată cum se va calcula elementul (1,2) si (3,3) al matrici rezultante AB daca A este o matrice cu 4 linii si 2 coloane si B este o matrice cu 2 linii si 3 coloane. Elementele din fiecare matrice sunt grupate in direcţia săgeţilor. Fiecare pereche este înmulţită element cu element, si produsul fiecărei înmulţiri este sumat. Poziţia acestui nou element calculat corespunde liniei si coloanei ce fac parte din pereche: 
Un exemplu simplist al acestei metode este adus mai jos :
Produsul matriceal poate fi efectuat si utilizând o altă metodă. Această metodă constă in sumarea vectorilor împreună după ce aceştia au fost înmulţiţi cu diferiţi coeficienţi. Dacă A şi B sunt matrici date de:
atunci:
Exemplul de mai sus, insă, utilizând această metoda devine: 
Liniile matrici din stânga reprezintă coeficienţii pe când matricea din dreapta e considerată o listă de vectori. Ecuaţia poate fi simplificată şi mai mult: 
Termenii acestei sume sunt matricele ce au aceeaşi formă, fiecare descriind efectul unei coloane din A şi al unei linii din B ca rezultat. Coloanele lui A pot fi văzute ca un sistem de coordonate al transformării. Fie un vector x, avem:  , unde  sunt coordonatele de-a lungul axei  .
Termenii Acelaşi exemplu rescris devine:
Vectorii 
Produsul matricial poate fi văzut şi ca un produs scalar intre vectorii coloana şi vectorii linie. Fie matricile A si B date de:  ,
unde 
Produsul matricial nu este comutativ ceea ce înseamnă că 5.3 Algoritmii produsului matricial Mai jos sunt prezentaţi toţi algoritmii ce pot fi utilizaţi pentru calculul produsului matricial:
Acest algoritm presupune utilizarea modelului matematic reprezentat mai sus pentru a calcula matricea rezultantă. Complexitatea operaţiei de produs a doua matrici poate fi naiv determinat ca fiind
A fost dedus de către Volker Strassen în 1969, numit adesea si „produs matriceal rapid”, se bazează pe o metoda ingenioasă de înmulţire al matricilor de dimensiuni Aplicând acest calcul intr-un mod recursiv vom obţine un algoritm cu complexitatea Este nevoie de 8 înmulţiri pentru a calcula Urmează partea importantă al algoritmului. Sunt definite matrici noi:
Matricile  ,  ,
 , 
Iterăm acest proces de divizare n ori până când sub-matricile degenerează în numere. Practic, însă, acestui algoritm ii lipseşte stabilitatea numerica si este extrem de complicat si pentru a fi utilizat in aplicaţii.
A fost prezentat de către Don Coppersmith şi Shmuel Winograd in 1990 are o complexitate asimptotică de Deoarece orice algoritm utilizat pentru a calcula produsul a două matrici de dimensiuni Prezenta lucrare descrie utilizarea algoritmului „naiv” ce presupune complexitatea
Pentru a înţelege această decizie mai bine trebuie înţeles termenul de „problemă natural paralelizabilă”. Acest termen a fost conceput pentru prima dată când a apărut nevoia distribuţiei calculelor pe mai multe unităţi de procesare. O problemă „natural paralelizabilă” este un care poate fi împărţită un sub-probleme ce pot fi evaluate complet separat pe diferite unităţi de calcul. Datele de intrare evaluate pe o unitate de calcul nu vor influenţa în nici un caz evaluarea datelor pe alte unităţi de procesare. 
Fig. 5.2 Figura de mai sus denotă faptul că spaţiul datelor de intrare poate fi fracturat în mai multe seturi şi acestea evaluate independent, rezultatul fiind construit în paralel de toate unităţile de procesare.
Evaluarea fiecărui element din matricea rezultantă AB în paralel este elementul cheie în aplicarea calculului distribuit. În esenţă este utilizată această formulă de calcul:
Unde grupele
Mai jos este expus codul propriu-zis ce va fi distribuit pe unităţile de calcul:
După cum se poate observa această metodă acceptă un set de intrare ce conţine următorii parametri importanţi:
6. Rezultate şi testare 6.1. Analiza performanţelor Un ultim aspect important al acestei lucrări este de a demostra capabilităţile sistemului într-un set de teste. Se va putea observa, deci, circumstanţele în care randamentul acestuia este maxim şi în ce cazuri este minim. Se urmăreşte efectuarea unui număr de teste utilizând diferite configurări al algoritmului selectat (Produsul Matricial) şi compararea acestora într-un mod obiectiv. Trebuie de specificat că deşi timpul total de execuţie poate fi mai mare, acesta se datorează unor procese interne ce nu ar trebui calculate, din această cauza se cronometrează doar intervalul de timp de când sunt declarate primele rezultate până când este declarat sfârşitul execuţiei.
Acest set de teste vor utiliza doar LocalMachineRunner ce face parte din client. Nu se va distribui calculul pe alte calculatoare. De asemenea doar un singur miez va fi utilizat pentru evaluarea datelor. Nu este necesară echilibrarea încărcării. - Sunt date matricile A cu 20 linii şi 40 coloane, matricea B cu 40 linii şi 30 de coloane.
- Sunt date matricile A cu 200 linii şi 400 coloane, matricea B cu 400 linii şi 300 de coloane.
Acest set de teste vor utiliza doar LocalMachineRunner ce face parte din client. Nu se va distribui calculul pe alte calculatoare. De asemenea doua miezuri vor fi utilizate pentru evaluarea datelor. Echilibrarea se face utilizând FairLoadBalancer. - Sunt date matricile A cu 20 linii şi 40 coloane, matricea B cu 40 linii şi 30 de coloane.
- Sunt date matricile A cu 200 linii şi 400 coloane, matricea B cu 400 linii şi 300 de coloane.
Se observă doar mici schimbări între cele moduri de testare. Acest lucru se datorează faptului că deşi algoritmul este executat pe 2 procesoare, acestea deja sunt utilizate de către alte fire de execuţie ceea ce face ca metoda evaluării locale să nu fie cea mai optimă soluţie.
Acest set de teste vor utiliza doar două calculatoare pe unităţi de execuţie Echilibrarea se face utilizând PredictiveLoadBalancer. - Sunt date matricile A cu 20 linii şi 40 coloane, matricea B cu 40 linii şi 30 de coloane.
- Sunt date matricile A cu 200 linii şi 400 coloane, matricea B cu 400 linii şi 300 de coloane.
În cazul distribuţiei calculelor pe mai multe calculatoare vitezele de calcul vor varia mult în dependenţă de calitatea conexiunilor, mărimea cozii şi mulţi alţi factori. Acest lucru face imposibilă o testare obiectivă al acestui mod. 6.2. Posibilitatea extinderii ulterioare Deşi framework-ul DCalc pare destul de bine realizat pentru grupul său de probleme rezolvabile există totuşi o mulţime de puncte care pot fi ajustate şi extinse, sau chiar implementate:
7. Bibliografie 1. Mitică Craus - Proiectarea algoritmilor, Editura Gheorghe Asachi, Iaşi, 2002 2. Mitică Craus, C. Amarandei, B. Romanescu - Algoritmi şi limbaje pentru calcul distribuit - Îndrumar de laborator 3. . Florin Leon, Mihai Horia Zaharia - Ingineria programării, Politehnium, Iaşi, 2005 4. Jeffrey Richter - Applied Microsoft .NET Framework Programming 5. M.H. Zaharia, Sisteme Paralele si distribuite, Ed. Gh. Asachi, 2003 6. http://www.w3.org/Protocols/, „HTTP - Hypertext Transfer Protocol” 7. http://msdn.microsoft.com, „MSDN” 8. http://en.wikipedia.org/ Yüklə 232,21 Kb. Dostları ilə paylaş:
|
,
sunt la fel ca 
cu diferenţa că 
conţine coordonata i pentru fiecare coloana din B. 
şi 
au fost transformaţi în 
si 
in paralel. Aceştia pot fi transformaţi unul câte unul utilizând aceiaşi paşi:
este vectorul linie al 
, 
este vectorul linie al tuturor elementelor de forma 
etc., si 
este vectorul coloana al tuturor elementelor de forma 
, 
este vectorul coloana al tuturor elementelor de forma 
etc. Rezultatul poate fi scris ca:
, exceptând câteva cazuri speciale. Este uşor de înţeles de ce: nu poate fi aşteptat acelaşi rezultat atunci când proporţiile vectorilor sunt diferite. Este de asemenea uşor de înţeles de ce ordinea factorilor determina rezultatul atât timp cât numărul coloanelor in matricea proporţiilor trebuie sa fie egal cu numărul liniilor în matricea vectorilor: trebuie ambele să reprezinte acelaşi număr de vectori. Deşi produsul matricial nu este comutativ, determinaţii AB şi BA sunt întotdeauna egali (data A si B sunt matrici pătrate de aceleaşi dimensiuni). Produsul matricial este comutativ când ambele matrici sunt diagonale şi de aceleaşi dimensiuni.
. Acest algoritm, deşi cel mai lent este utilizat pe larg din motivul că este simplu de implementat si prezintă un înalt grad de stabilitate numerică.
care necesită doar 7 înmulţiri în loc de 8. 
.
unde 
, liniile şi coloanele lipsă vor fi umplute cu zerouri. În continuare matricile A, B si C vor fi partiţionate în matrici bloc de dimensiuni egale:
,
, 
. Atunci:
ca şi in cazul algoritmului standard.
,
,
,
sunt utilizate pentru a exprima matricile 
. Datorita definiţiei matricilor 
. Este asemănător cu algoritmul lui Strassen: un mod ingenios de înmulţire a 
matrici cu mai puţin de 
operaţii de înmulţire. Această tehnică este la fel aplicată recursiv. La fel ca şi algoritmul lui Strassen acesta nu se aplica des: numai in cazurile in care matricile ce trebuie înmulţite sunt prea mari pentru a fi evaluate pe un calculator contemporan.
trebuie sa înmulţească 
valori, este definită o asimptotă inferioara de 
operaţii.
, 
… 
sunt evaluate in paralel pe toate unităţile de calcul. In practică acest lucru înseamnă că pentru 2 matrici: X cu 200 coloane şi 200 
elemente ce vor fi calculate in paralel. Deci numărul total de seturi ce vor fi ditribuite este egal cu „Numărul de linii din matricea A” înmulţit cu „Numărul de coloane din matricea B”.