Lygiagrečiojo burbuliuko algoritmo realizacija ir tyrimas

Šiame darbe aptarsime ir ištirsime lygegretujį burbuliuko algoritmą ir jo modifikaciją. Tyrimą atliksime VGTU lygegrečiųjų skaičiavimų laboratorijos kompiuteriais.
2. Realizacija
Vienas iš duomenų rūšiavimo metodu yra burbuliuko algoritmas. Algoritmas vyskta taip, turima n duomenų seką, kurios elementus galime palyginti ir išrušiuoti didėjimo tvarka. Tada poromis tikrinamo visi elementai iš eilės. Jei pirmas elementas yra didesnis už antrą, tai jie sukeičiami vietomis. Tada tikrinamas antras elementas su trečiu, po to trečias su ketvirtu ir taip iki sekos galo. Per vieną ciklą didžiausias elementas patenka į sekos galą, todėl antrą kartą kartojant ciką, nereikia tikrinti paskutinio elemento todėl seka sutrumpėja iki n – 1. Taip yra sutaupomos tikrinimo operacijos, kas ir pagreitina rūšiavima nuo paprasto brutalios jėgos rūšiavimo algoritmo (kur yra tikrinama kiekvienas elementas su kiekvienu). Taip pat galima pastebėti, kad dažniausiai seka tampa išrūšiuota algoritmui nealikus visų ciklų.
2.1. Lygiagretusis burbuliuko algoritmas
Lygiagretujį burbuliuko algoritmą sudarysime naudodami duomenų lygiagretumo modelį. Visus duomenų aibės elementus dalijame į p blokų skaičių, t.y. tiek kiek yra procesorių. Tada i-ajam procesoriui tenka m=n/p elementų. Mūsų atveju elementų dalybos likutį priskiriame paskutiniam procesoriui. Skaičiavimo algoritmas:
p = dirbančių procesorių kiekis
n = duomenų kiekis
myid = mano procesoriaus ID
s = n/p*myid;
f = (n/p*(myid+1))-1;
if (myid==p-1)
{ f += n % p; };
k = n – 1;
while ( k >= s ) {
pivot = 0;
if (k0)
sort_su_kaimynu(xs,myid-1);
j = s – 1;
kl = min(k, f-1);
for (i=s; i xi+1) {
j = i;
swap(xi, xi+1);
};
if (pivot==1) {
k=j-1;
} else {
sort_su_kaimynu(xf, myid+1);
get(k) from myid-1;
};
if (myid != p-1)
send(k) for myid-1;
};
Aptarsime svarbiausias lygegrečiojo burbuliuko algoritmo detales. Kadangi algoritmo eilinio ciklo vykdymas yra nuoseklus, tai skaičiavimų pradžia vyksta konvejeriniu būdu. Pirmasis procesorius atlieka pirmojo ciklo užduotis, pasikeičia pasienio aibės elementais suantruoju procesoriumi ir užbaigia pirmąjį ciklą. Tada jis pradeda vykdyti antrojo ciklo skaičiavimus ir vėl kartoja skaičiavimo ir duomenų pasikeitimo žingsnius. Toks algoritmas vykdomas tol kol surūšiuojami visi elementai, kurie buvo saugomi kituose procesoriuose. Paskui pirmasis...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!