Rezumat: Dezvoltarea de aplicatii paralele sunt principalele etape: descompunere, dependențe informații de identificare între sarcini, subactivități scalarea și echilibrarea încărcării pentru fiecare procesor.
descompunere
Prin descompunere înțelegem împărțirea problemei în părți relativ independente (subtascuri). Descompunerea problemei poate fi realizată în mai multe moduri: prin sarcini, prin date, prin fluxuri de informații.
Descompunerea pe sarcini (descompunerea funcțională) implică atribuirea diferitelor funcții diverselor fluxuri. De exemplu, aplicația care efectuează editarea documentului include următoarele funcții: verificarea ortografiei CheckSpelling. verificați Punctul de control CheckPuncto. Formatarea textului în conformitate cu stilurile de format selectate. calcularea statisticilor privind documentul CalcStat. Salvați modificările fișierului SaveChanges și trimiteți documentul prin e-mailul SendDoc.
Descompunerea funcțională întrerupe activitatea aplicației în sub-sarcini astfel încât fiecare subtasc să fie asociată cu o funcție separată. Dar nu toate operațiunile pot fi efectuate în paralel. De exemplu, salvarea unui document și trimiterea unui document se efectuează numai după ce toate etapele anterioare au fost finalizate. Formatarea și colectarea de statistici poate fi efectuată în paralel, dar numai după terminarea ortografiei și a punctuării.
Descompunerea pe fluxurile de informații alocă sub-sarcini care funcționează cu un singur tip de date. În exemplul examinat, se pot distinge următoarele sub-sarcini:
- Lucrul cu proiectul de document (ortografie și punctuație):
- Lucrul cu documentul corectat (formatarea și colectarea de statistici);
- Lucrul cu documentul finit (salvarea și trimiterea);
Când se descompune prin date, fiecare subtascã funcționeazã cu fragmentul de date, realizând întreaga listã de acțiuni. În acest exemplu, descompunerea datelor poate fi aplicată sarcinilor care pot funcționa cu un fragment al unui document. Astfel, funcțiile CheckSpelling. CheckPuncto. CalcStat. Formatele sunt combinate într-o singură subtasmă, însă sunt create mai multe cazuri ale acestei subtasme, care funcționează în paralel cu fragmente diferite ale documentului. Funcțiile SaveChanges și SendDoc sunt subtascuri separate, deoarece nu pot funcționa cu o parte a documentului.
Descompunere de date
Atunci când se descompune în funcție de fiecare subactivitate efectuează aceleași acțiuni, dar cu date diferite. În multe sarcini de date paralele, există mai multe modalități de separare a datelor. De exemplu, multiplicarea matricei sarcinii permite separarea liniilor - fiecare fir de mânere una sau mai multe linii ale matricei, coloanele - fiecare fir de mânere una sau mai multe coloane, dar, de asemenea, blocurile de dimensiuni predeterminate.
Cele două principii de bază ale separării datelor între sub-sarcini sunt statice și dinamice. Cu descompunerea statică, fragmentele de date sunt atribuite thread-urilor înainte de prelucrare și, de regulă, conțin același număr de elemente pentru fiecare fir. De exemplu, divizarea unei serii de elemente poate fi efectuată pe intervale egale ale unui indice între fluxuri (partiție de interval).
Principalul avantaj al partiționării statice este independența muncii fluxurilor (nu există o problemă de raportare a datelor) și, ca o consecință, nu este nevoie ca instrumentele de sincronizare să acceseze elementele. Eficiența descompunerii statice scade cu complexitatea computațională diferită a prelucrării elementului de date. De exemplu, sarcina de prelucrare a unei procesări i-element poate depinde de indexul elementului.
Diviziunea pe gama duce la dezechilibrul sarcinii diferitelor fluxuri. Dezechilibrul de sarcină reduce eficiența paralelizării. În unele cazuri, descompunerea poate fi îmbunătățită chiar și cu partiționarea statică, atunci când se cunoaște în prealabil ce elemente sunt mai intensive în ceea ce privește forța de muncă și care sunt mai puțin costisitoare. De exemplu, în cazul dependenței complexității computaționale de indicele elementului, aplicarea descompunerii circulară egalizează volumul de lucru al fluxurilor. Primul fir procesează toate elementele simple, al doilea fir procesează toate cele ciudate.
În cazul general, când complexitatea computațională a elementelor de procesare nu este cunoscută în prealabil, balanța încărcării fluxurilor furnizează descompunere dinamică.
Cu descompunere dinamică a fiecărui flux. implicat în prelucrare, accesează blocul de date (porțiunea). După procesarea blocului de date, fluxul este accesat pentru următoarea porțiune. Decompoziția dinamică necesită sincronizarea accesului firului la structura de date. Dimensiunea blocului determină frecvența accesului firului la structură. Unii algoritmi de descompunere dinamică măresc dimensiunea blocului în timpul procesării. Dacă firul procesează rapid elementele, atunci mărimea blocului crește.
Scalarea sub-tastelor
Caracteristica de scalabilitate este utilizarea eficientă a tuturor resurselor de calcul disponibile. O aplicație paralelă trebuie să fie pregătită pentru faptul că mâine va fi rulat pe un sistem cu capacități computaționale mari. Proprietatea de scalabilitate a aplicației este strâns legată de algoritmul ales pentru rezolvarea problemei. Un algoritm este foarte bine paralealizat, dar numai prin două subtascuri, un alt algoritm vă permite să selectați un număr arbitrar de subtascuri.
O condiție esențială pentru scalabilitatea aplicației este posibilitatea de parametrizare a algoritmului în funcție de numărul de procesoare din sistem și în funcție de volumul de lucru curent al sistemului informatic. Această parametrizare permite modificarea numărului de subtascuri alocate în condiții specifice de execuție a algoritmului. Platformele moderne de programare paralelă oferă instrumente pentru echilibrarea încărcării automate (pooling thread).
Problema cursei de date
Problema rasei de date apare în următoarele condiții:
- Fire multiple funcționează cu o resursă partajată.
- Rezultatul final depinde de ordinea execuției secvențelor de comandă ale diferitelor fire.
Pentru a ilustra problema unei rase de date, luați în considerare următorul fragment. Cele două fire afișează valoarea variabilei comune Msg.
Variabila Msg este comună - schimbarea unei variabile într-un fir va fi vizibilă într-un alt fir. În operarea paralelă a fluxurilor, ieșirea este determinată de o secvență specifică de execuție a operatorilor.
Dacă operatorii primului fir sunt executați înainte de operatorii celui de-al doilea fir, adică cu secvența (1) - (2) - (3) - (4), atunci primim:
Dacă operatorii dintr-un fir sunt interveniți de operatorii unui alt fir, de exemplu cu secvența (1) - (3) - (2) - (4), obținem următoarele:
Problema rasei de date apare nu numai atunci când se execută mai mulți operatori, ci și atunci când se execută un singur operator. Luați în considerare următorul caz. Ambele fire efectuează un operator pe o variabilă comună x de tip int:
Acest operator preia următoarele acțiuni:
Atunci când se execută secvențele de comandă ale unui fir pe un dispozitiv executiv, un alt fir poate interfera cu operația. Rezultatul final depinde de ordinea execuției secvențelor de comandă. Dacă firele efectuează secvențial sumarea, obținem rezultatul final: 10. Dacă firele efectuează simultan sumarea, schimbarea timpurie va fi șterse mai târziu:
O altă "capcană" în procesarea cu mai multe fire este lucrarea cu structuri dinamice de date (liste, dicționare). Adăugarea și eliminarea elementelor din structurile de date dinamice se realizează utilizând o metodă:
Implementarea metodelor include mai multe acțiuni. De exemplu, când adăugați un element în listă, trebuie să scrieți elementul la indexul curent (index) și să mutați indexul la următoarea poziție. Pentru implementarea corectă a adăugării unui element printr-un fir, este necesar ca alte fire să aștepte finalizarea manipulărilor cu lista.
Pentru a rezolva problema rasei de date, este necesar să se furnizeze accesul exclusiv la acele secvențe de comandă în care este utilizată resursa partajată. Exclusivitatea reciprocă înseamnă că la fiecare moment într-un singur thread funcționează cu resursa. Alte fire sunt blocate, așteptând ca primul fir să-și finalizeze activitatea. Un fragment al codului la care ar trebui să se ofere acces reciproc exclusiv. se numește secțiunea critică.
Problema unei curse de date nu apare întotdeauna când lucrați cu o variabilă comună. De exemplu, în următorul fragment, două fire efectuează o modificare a variabilei partajate înainte de a termina, iar al treilea fir citește această valoare.
În acest exemplu, al treilea fir din bucla "așteaptă" ca cel puțin un fir să se termine. Problemele datelor de rasă nu apar, în ciuda muncii a trei fire cu o variabilă comună. Ordinea firelor nu afectează rezultatul final. Modificările introduse de fluxuri nu se contrazic reciproc.
Trimiteți-le prietenilor: