Paralelizacija poznatih algoritama - teorijsko razmatranje
Sve je popularnija tema paralelnog procesiranja i u tom
svetlu mi je palo na pamet da pokrenem jednu diskusiju,
vise kao mentalnu vezbu, takoreci razgibavanje mozga, vezano
za paralelizaciju poznatih algoritama.
U velikom broju prakticnih primena, ovo nece postici velik
napredak u performansama programa (pre ce to uciniti dodela
razlicitih poslova razlicitim procesorima) ali mislim da je
tema interesantna zbog razvijanja odredjenog nacina razmisljanja
prilikom programiranja za vise procesora.
Poceo bih sa recimo algoritmima za sortiranje.
Kod problema sortiranja vidim dva potencijalna resenja,
oba zahtevaju dodatni korak koji se izvrsava na jednom
procesoru a u zavisnosti od pristupa radi se o predprocesiranju
odnosno postprocesiranju zadatog skupa ulaznih podataka.
1. Predprocesiranje
Ideja dolazi od poznatog quick sort algoritma koji deli
niz brojeva (u prvoj iteraciji rekurzije) na dva podskupa,
"gornji" i "donji", smestajuci sve vrednosti vece od zadate
referentne vrednosti u "gornji" podskup, odnosno sve manje
vrednosti od referentne u "donji" podskup.
Pod pretpostavkom da postoji n procesora koji ce obavljati
sortiranje, potrebno je podeliti ulazni skup na n podskupova
koji ce biti ograniceni sa n-1 (Rx) referentnih vrednosti i u odgovarajuce
podskupove staviti one ulazne podatke k takve da su
Za grupu 1 k<R1
Za grupu y (y>1,y<n) k>Ry-1 i k<Ry (Ry-1<k<Ry)
Za grupu n k>Rn
Nakon toga se grupi dodeli odgovarajuci procesor i sortiranje se vrsi
implementacijom bilo kog od poznatih sort algoritama.
Nakon zavrsetka rada svih procesora niz je sortiran
Prednosti pristupa:
Sortiranje se vrsi "inplace" i jedino je potrebno alocirati memoriju
za cuvanje granicnih index-a
Problemi kod ovog pristupa:
Da bi algoritam optimalno funkcionisao, treba odrediti granicne vrednosti
Rx tako da broj elemenata po grupama bude sto vise ujednacen (u slucaju
sistema sa procesorima iste snage) odnosno da bude proporcionalan procesorskoj
snazi kako bi se obezbedilo da procesori zavrse sortiranje u sto pribliznije
istom vremenu.
2. Postprocesiranje
Ideja dolazi od poznatog merge sortiranja.
Ulazni niz se u startu deli na grupe prema broju procesora (i/ili procesorskoj
snazi) i svaki procesor vrsi sortiranje na svojoj grupi podataka ili podnizu.
Sortiranje se vrsi bilo kojim od poznatih sort algoritama.
Nakon zavrsetka sortiranja, pristupa se merge sort fazi pojedinacnih podnizova
Prednost pristupa:
Izuzetno lako se odredjuje pripadnost grupama (nema potrebe za utvrdjivanjem
granicnih vrednosti kako bi grupe bile balansirane)
Problemi pristupa:
Mislim da je izuzetno komplikovano (da budem iskren nisam puno razmisljao o tome,
pa ako nije tako neka me neko ispravi) implementirati inplace merge u finalnom
koraku u slucaju da je broj procesora veci od 2. Ovo se naravno moze zaobici
dodatnom alokacijom memorije, odnosno odstupanjem od inplace principa.
 |  |
 |
