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 2. koraku učestvuje 2 procesora i oni (pojedinačno) kopiraju elemente niza A[1] A[2] u lokacije A[3] A[4].
. . .
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 (Procesor P_j kopira element sa lokacije j na lokacije j+m*2^i-1, m=1,2,...,2^k/2^i-1-1).

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
i-1 korak + 2^k/2^i-1-1 koraka
sto je prema vec navedenom manje od log₂n + 2log₂n =3log₂n, 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(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 Hadži-Purić

Primene računara