Algoritmi paraleli

Algoritmi paraleli pentru sortare

Algoritmii paraleli sunt opusi algoritmilor seriali deoarece secventele de cod pot

fi executate pe mai multe procesoare si apoi sunt „reunite” pentru a obtine rezultatul

corect. Unii algoritmi sunt usor de împărtit în segmente care să permită procesarea

paralelă. De exemplu, determinarea numerelor prime de la 1 la 10 000, ar putea fi

realizată mult mai repede prin împărtirea intervalului în subintervale de o anumită

lungime (lungimea intervalelor nu trebuie sa fie neapărat egală, unele procesoare pot avea

o putere de calcul mai mare si atunci ele pot procesa un interval mai mare de numere), iar

apoi realizând o listă cu rezultate obtinute de la fiecare procesor în parte. Cei mai multi

algoritmi folositi pentru a calcula numărul PI nu pot fi împărti pentru a fi executati pe mai

multe procesoare. De obicei, se asteaptă rezultatul de la pasul anterior pentru a trece la

următorul pas. Algoritmii paraleli sunt buni deoarece este mult mai avantajos să realizezi

calcule care necesită foarte multe resurse pe mai multe procesoare, decât pe un singur

calculator. Din puncte de vedere tehnologic, este mai greu sa construiesti un computer

care să aiba o putere foarte mare de calcul.

În cele din urmă am prezentat enuntarea problemei de sortare cu următoarele:

· Sortarea este o problemă tipică de procesare date si reprezintă algoritmul prin care

putem rearanja k elemente într-o anumită ordine.

· Există diversi algoritmi de sortare printre care se numară bubble sort, quick sort,

shell sort, selectia minimului, insertiei, interclase, par-impar.

· Fiecare algoritm de sortare se bazează pe o anumită metodă: partitionare(quick

sort), comparare(bubble sort).

· Cu toate ca există numerosi algoritmi de sortare, nu se poate afirma ca unul dintre

ei ar fi cel mai bun.

· Fiecare algoritm are nevoie de un anumit spatiu de memorie, fiecare realizează

sortarea într-un anumit timp.

· Pentru anumiti algoritmi de sortare(bubble sort, insertie, etc) numărul de operatii

necesare depinde de pătratul numărului de elemente ce urmează a fi sortate.

· Pentru algoritmi de sortare mai eficienti(shell sort, quick sort) complexitatea este

determinată astfel:

T ≈ n*log(2)*n

· O accelerare a sortării datelor se poate realiza prin utilizarea mai multor

procesoare.

· Pentru a usura schema de distributie a datelor procesoarele sunt numeroatate

consecutiv.

Bubble Sort

Acest algoritm de sortare se bazează pe compararea si interschimbarea datelor în

cazul în care valorile acestora nu corespund conditiilor de sortare

Operatii de baza comparare-interschimbare

If( A[i] > A[j] );

{

Temp = A[i];

A[i] = A[j];

A[j] = temp;

}

Aplicarea succesivă a acestei operatii permite sortarea datelor. Algoritmul Bubble

sort, pentru a realiza sortarea, compară si interschimbă elementele vecine dintr-o

secventă. După fiecare insertie, o parte din elementele vectorului sunt deja ordonate.

Pentru secventa ( a1, a2, …, an ) algoritmul execută n-1 operatii de comparareinterschimbare:

( a1, a2 ) ,( a2, a3 ) , …, ( a(n-1), an ); ca rezultat după prima insertie, cel

mai mare element este mutat la finalul secventei.

La următoarea insertie ultimul element din secventă este omis, si procedura descrisă

mai sus este aplicată celorlalte n-1 elemente din secventa ( a1, a2, …, a(n-1) ).