Primene računara (4. godina/ R smer)

Paralelni algoritmi

1.
Konstruisati EREW algoritam složenosti T(n,n)=O(log n) koji u vektoru A dimenzije n će vrednost A[1] smestiti na preostale lokacije.

 

REŠENJE:

Koristiti se EREW model, te iz lokacije A[1] može u jednom trenutku da čita samo jedan procesor.

Pretpostavimo BSO da je n=2k.
Koristi se metod "dupliranja'':

 

2.
Konstruisati EREW algoritam efikasnosti O(1) čije vreme izvršavanja je O(log n) koji u vektoru A dimenzije n će vrednost A[1] smestiti na preostale lokacije.

 

REŠENJE:

Da bi se poravila efikasnost iz prethodnog zadatka korisiti se Brentova lema.

Brentova lemaAko postoji statički EREW algoritam složenosti T(n,p)=O(t(n)), takav da je ukupan broj koraka (na svim procesorima) s(n), onda postoji statički EREW algoritam složenosti T(n,s(n)/t(n))=O(t(n))

Pretpostavimo BSO da je n=2k i neka je na raspologanju [n/log2n], tj. [2k/k] procesora. Dalje, neka i je takvo da važi 2i-1<2k/k<2i.

Kako je i-1 <k i
kako 2k/2i-1-1=2k-i+1-1 < 2k-1 < 2 log2 n, to je ukupno vreme izvršavanja
i-1 korak + 2k/2i-1-1 koraka
sto je prema vec navedenom manje od log2n + 2log2n =3log2n, tj. vreme izvršavanja je O(log n).

 

3.
Konstruisati EREW algoritam za računar sa zajedničkom memorijom i n procesora koji u vektoru A dimenzije n će na lokaciju A[i] smestiti vrednost A[i]+i, 1 <i <= n.

 

4.
Konstruisati CRCW algoritam za izračunavanje disjunkcije n Bulovih promenljivih za vreme O(1).

 

REŠENJE:

Vrednost operacije disjunkcije nad n Bulovih promenljivih jednaka je maksimumu datih n vrednosti. Time se problem svodi na problem odredjivanje maksimalnog od datih n brojeva.

Koristi se n(n-1)/2 procesora.
Svakom od datih brojeva x[i] pridruzujemo se po jedna (deljena) memorijska lokacija v[i]. Svakom paru {i,j} zadatih brojeva pridruzuje se procesor P[ij].
Najpre se u sve lokacije v[i] upisuje vrednost 1.
U sledećem koraku algoritma, procesor P[ij] poredi elemente x[i] i x[j];
Ako je jedan od njih manji onda u njegovu odgovarajuću lokaciju upisuje se vrednost 0;
ako su x[i] i x[j] jednaki onda ako je i<j onda se 0 upisuje u v[i], a inace se 0 upisuje u v[j].
Nakon toga samo u jednoj od lokacija v[i] ostaje upisana vrednost 1.
Otkrije se kom zadatom elementu je pridružena ta lokacija i taj broj je maksimum zadatih vrednosti.

Vreme izvršavanja algoritma je O(1) i on zahteva O(n2) procesora.

 

5.
Konstruisati CREW algoritam za sortiranje niza različitih brojeva x1, x2, . . . , xn. Vremenska složenost treba da bude O(log n) na paralelnom CREW računaru sa zajedničkom memorijom i dovoljnim brojem procesora.

 

6.
Konstruisati CRCW algoritam za objedinjavanje dva niza brojeva A i B u jedan sortiran niz. Poredak sortiranja je istovetan kod sva tri niza. Vremenska složenost treba da bude O(1). Na raspolaganju je neograničen i memorijski prostor i broj procesora.

 

7.
Pod pretpostavkom da n=2k osoba znaju neke informacije koje žele da razmene među sobom i pod pretpostavkom da u svakom koraku svaka osoba može da komunicira sa tačno jednom osobom i razmeni sve informacije koje poseduje, konstruisati algoritam koji kreira redosled komunikacije tao da nakon log2  n koraka svaka osoba poseduje sve informacije.

 


Jelena Hadži-Purić Primene računara