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'':
- 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 2i-1 procesora
i oni (pojedinačno) kopiraju elemente niza
A[1..2i-1] u lokacije A[2i-1+1..2i].
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=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.
- Za i-1 korak se kopira A[1] na lokacije od 1..2i-1 (predstavljenim algoritmom).
- Dalje, svaki od tih 2i-1 elemenata se paraleleno kopira uz
2i-1 procesora 2k/2i-1-1 puta
(Procesor Pj kopira element sa lokacije j na lokacije j+m*2i-1, m=1,2,...,2k/2i-1-1).
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.