1 PRAM

2 EREW CREW ERCW CRCW

3 SYNCHRONIZACJA I STEROWANIEprocesy są ściśle zsynchronizowane testowanie warunków zakończenia pętli - za pomocą sieci sterującej lub jednoczesnego zapisu do pamięci

4 USTALANIE PORZĄDKU ELEMENTÓW NA LIŚCIEMetoda przeskakiwania (podwajania) : DANE : n elementowa lista rekordów (pola : klucz, d, next) WYNIK : d[i] = odległość elementu o kluczu=i od końca listy L 0 jeśli next[i] = NIL d[i] : = d[next[i]] jeśli next[i] <>NIL

5 Procedure LIST-RANK (L); { dla EREW }begin for każdy proces i in parallel do if next[i] = NIL then d[i] := 0 else d[i] := 1; while istnieje element i w L taki, że next[i] <> NIL do for każdy proces i in parallel do if next[i] <> NIL then d[i] := d[i] + d[next[i]]; next[i] := next[next[i]]; end; T(n) = O(lg n)

6 OBLICZENIA PREFIKSOWE NA LIŚCIEDANE: n, X = (x1, x2, ... xn ), n  1,  - binarny, łączny operator WYNIK: Y = (y1, y2, ... , yn ) x jeśli k = 1 yk = yk-1  xk jeśli k > 1 OZNACZENIA : [i,j] = xi xi+1 ... xj

7 T(n) = O(lg n) Procedure LIST-PREFIX (L); { dla EREW }{(x1, x2, ... xn ) umieszczone w liście L (xi, yi, next) } begin for każdy proces i in parallel do y[i] : = x[i]; while istnieje element i w L taki, że next[i] <> NIL do if next[i] <> NIL then y[next[i]] := y[i]  y[next[i]] next[i] := next[next[i]]; end; T(n) = O(lg n)

8 PROBLEM MAKSIMUM DANE: n > 0 , x1, ... , xn, xi  R; WYNIK : max = maximum {x1, ... , xn, xi  R} 0 , x1, ... , xn, xi  R; WYNIK : max = maximum {x1, ...", "description": ", xn, xi  R} .", "width": "800" } 9 FAST-MAX (X); { dla CRCW z jednolitym zapisem }{ wykorzystuje n2 procesów } begin for i : =0 to n-1 in parallel do m[i] := TRUE; for i := 0 to n-1, for j := 0 to n-1 in parallel do {proces dla pary (i,j) !} if X[i] < X[j] then m[i] = FALSE; { wiele procesów może pisać ale wszystkie zapisują tę samą wartość - FALSE } for i := 0 to n-1 in parallel do if m[i] = TRUE then max := X[i] { wiele procesów może pisać ale wszystkie zapisują tę samą wartość – max } return max end; T(n) = O(1) { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/56843/1/images/9/FAST-MAX+%28X%29%3B+%7B+dla+CRCW+z+jednolitym+zapisem+%7D.jpg", "name": "FAST-MAX (X); { dla CRCW z jednolitym zapisem }", "description": "{ wykorzystuje n2 procesów } begin. for i : =0 to n-1 in parallel do. m[i] := TRUE; for i := 0 to n-1, for j := 0 to n-1 in parallel do {proces dla pary (i,j) !} if X[i] < X[j] then m[i] = FALSE; { wiele procesów może pisać ale. wszystkie zapisują tę samą wartość - FALSE } for i := 0 to n-1 in parallel do. if m[i] = TRUE. then max := X[i] { wiele procesów może pisać ale. wszystkie zapisują tę samą wartość – max } return max. end; T(n) = O(1)", "width": "800" } 10 5 6 9 2 m F T X[j} X[i] { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/56843/1/images/10/5+6+9+2+m+F+T+X%5Bj%7D+X%5Bi%5D.jpg", "name": "5 6 9 2 m F T X[j} X[i]", "description": "5 6 9 2 m F T X[j} X[i]", "width": "800" } 11 FIND-ROOTS(F) begin for każdy procesor i in parallel do if parent[i] = NIL then root[i] := i; while istnieje węzeł i taki, że parent[i] <> NIL do for każdy procesor i in parallel do if parent[i] <>NIL then root[i] := root[parent[i]]; parent[i] := parent[parent[i]]; end;

9 FAST-MAX (X); { dla CRCW z jednolitym zapisem }{ wykorzystuje n2 procesów } begin for i : =0 to n-1 in parallel do m[i] := TRUE; for i := 0 to n-1, for j := 0 to n-1 in parallel do {proces dla pary (i,j) !} if X[i] < X[j] then m[i] = FALSE; { wiele procesów może pisać ale wszystkie zapisują tę samą wartość - FALSE } for i := 0 to n-1 in parallel do if m[i] = TRUE then max := X[i] { wiele procesów może pisać ale wszystkie zapisują tę samą wartość – max } return max end; T(n) = O(1)

10 5 6 9 2 m F T X[j} X[i]

11 FIND-ROOTS(F) begin for każdy procesor i in parallel do if parent[i] = NIL then root[i] := i; while istnieje węzeł i taki, że parent[i] <> NIL do for każdy procesor i in parallel do if parent[i] <>NIL then root[i] := root[parent[i]]; parent[i] := parent[parent[i]]; end;