[ vlaiv @ 25.07.2007. 14:46 ] @
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. |