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=2^k.
Koristi se metod "dupliranja'':

u prvom koraku jedan procesor kopira A[1] u A[2];
. . .
u i-tom koraku učestvuje 2^i-1 procesora i oni (pojedinačno) kopiraju elemente niza A[1..2^i-1] u lokacije A[2^i-1+1..2ⁱ. Takvih koraka ima ukupno k, te vreme izvršavanja algoritma je O(log n).

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=2^k i neka je na raspologanju [n/log₂n], tj. [2^k/k] procesora. Dalje, neka i je takvo da važi 2^i-1<2^k/k<2ⁱ.

Za i-1 korak se kopira A[1] na lokacije od 1..2^i-1 (predstavljenim algoritmom).
Dalje, svaki od tih 2^i-1 elemenata se paraleleno kopira uz 2^i-1 procesora 2^k/2^i-1-1 puta.

Kako je i-1 <k i kako 2^k/2^i-1-1=2^k-i+1-1 < 2k-1 < 2 log₂ n, to je ukupno vreme izvršavanja manje od 3log₂n, tj. 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(n²) procesora.

5.
Konstruisati CREW algoritam za sortiranje niza različitih brojeva x₁, x₂, . . . , x_n. 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=2^k 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 log₂ n koraka svaka osoba poseduje sve informacije.

Jelena Grmuša

Primene računara