Przetwarzanie równoległe i rozproszone (sem.IV) - przykładowe zadania egzaminacyjne
Zad. Zapisać, w postaci tabelki, kolejne fazy współbieżnych procesów, dla następującej sytuacji:
Z podzielnego zasobu, z którego mogą jednocześnie korzystać maksymalnie 3 procesy, i który jest chroniony semaforem s, z którym jest stowarzyszona kolejka typu FIFO, chcą korzystać kolejno procesy I1, I2, I3 i I4, przy czym
procesy I2, I3 i I4 chcą skorzystać z zasobu przed zwolnieniem go przez proces I1,
procesy I1 i I2 zwalniają zasób w kolejności: I2, I1,
proces I3 zwalnia zasób jako ostatni z procesów,
proces I4 zwalnia zasób po zwolnieniu go przez proces I1.
Procesy |
s |
Zmiany w tablicy stan |
... |
3 |
… |
I1 sprawdza s; zajmuje zasób I2 sprawdza s; zajmuje zasób I3 sprawdza s; zajmuje zasób I4 sprawdza s I2 zwalnia zasób I4 zajmuje zasób I1 zwalnia zasób I4 zwalnia zasób I3 zwalnia zasób |
2 1 0 0 1 0 1 2 3 |
− − − I4: zawieszony I4: aktywny − − − −
|
Zad. Wypisać wszystkie występujące w poniższej pętli zależności danych, podając ich typ i rodzaj.
do i = 2,n
S: e(i) = c(i+1)
T: c(i) = a(i) + b(i-1)
U: b(i) = c(i) + 2.0
W: a(i) = b(i)
end do
Odp.
S —> T przeciwzależność, międzyiteracyjna
T —> U zależność przepływu, wewnątrziteracyjna
T —> W przeciwzależność, wewnątrziteracyjna
U —> T zależność przepływu, międzyiteracyjna
U —> W zależność przepływu, wewnątrziteracyjna
Zad. Korzystając z prawa Amdahla, podać wydajność obliczeń równoległych na 6 procesorach dla programu, którego część, dająca się zrównoleglić, wynosi 80 %.
Odp. Z definicji: η(n,p) = S(n,p) / p
Prawo Amdahla: S(n,p) = p / [1+(p-1)f(n)]
Stąd: η(n,p) = 1 / [1+(p-1)f(n)]
Dane: p = 6
f(n) = 1 - 80%/100% = 0,2
Po podstawieniu: η(n,6) = 1 / (1+5*0,2) = 1/2 = 0,5
----
Zad. Dokonać przekształceń prowadzących do zrównoleglenia (o ile jest ono możliwe) poniższej pętli, w sposób optymalny, z wykorzystaniem dyrektyw systemu OpenMP.
do i = 1,n-3
e(i) = d(i) * b(i) + d(i-1)
f(i) = e(i+2) + c(i)/d(i-1)
c(i) = e(i) + f(i)
end do
Rozwiązanie. Przeszkodę w bezpośrednim zrównolegleniu stanowi międzyiteracyjna przeciwzależność z instrukcji drugiej do pierwszej. Zrównoleglenia można dokonać zamieniając miejscami instrukcję pierwszą i drugą (co jest dopuszczalne ze względu na brak między tymi instrukcjami zależności wewnątrziteracyjnych), aby źródło zależności znalazło się leksykalnie przed ujściem, a następnie wykonując podział pętli, aby źródło i ujście znalazły się w oddzielnych pętlach. Obie otrzymane w ten sposób pętle można zrównoleglić, gdyż brak w każdej z nich zależności międzyiteracyjnych:
!$omp parallel do
do i = 1,n-3
f(i) = e(i+2) + c(i)/d(i-1)
end do
!$omp end parallel do
!$omp parallel do
do i = 1,n-3
e(i) = d(i) * b(i) + d(i-1)
c(i) = e(i) + f(i)
end do
!$omp end parallel do
Zad. Dokonać przekształceń prowadzących do zrównoleglenia (o ile jest ono możliwe) poniższej pętli, w sposób optymalny, z wykorzystaniem dyrektyw systemu OpenMP.
do i = 1,n-1
a(i+1) = d(i) * b(i)
c(i+1) = c(i) * a(i+1)
d(i) = a(i) * c(i+1)
b(i+1) = e(i) + f(i)
end do
Odp.
!$omp parallel do
do i = 1,n-1
b(i+1) = e(i) + f(i)
end do
!$omp end parallel do
!$omp parallel do
do i = 1,n-1
a(i+1) = d(i) * b(i)
end do
!$omp end parallel do
do i = 1,n-1
c(i+1) = c(i) * a(i+1) !rekurencja liniowa - nie wolno zrównoleglać!
end do
!$omp parallel do
do i = 1,n-1
d(i) = a(i) * c(i+1)
end do
!$omp end parallel do
Zad. Wypisać wszystkie występujące w poniższej pętli zależności danych, podając ich typ i rodzaj.
do i = 2,n−1
do j = 2,n−1
S: a(i,j) = c(i+1,j−1) + b(i−1,j)
T: c(i−1,j+1) = a(i,j−1) + b(i,j)
U: b(i,j+1) = c(i−1,j) + b(i−1,j+1) − a(i,j)
end do
end do
Odp.
S —> T przeciwzależność, międzyiteracyjna (tablica c)
S —> T zależność przepływu, międzyiteracyjna (tablica a)
S —> U zależność przepływu, wewnątrziteracyjna (tablica a)
T —> U zależność przepływu, międzyiteracyjna (tablica c)
U —> S zależność przepływu, międzyiteracyjna (tablica b)
U —> T zależność przepływu, międzyiteracyjna (tablica b)
U —> U zależność przepływu, międzyiteracyjna (tablica b)
Zad. Obliczyć przepustowość jednostki potokowej o 6 stopniach i czasie cyklu zegara 5 ns w trakcie przetwarzania wektora o długości 5.
Odp. W(N,p) = N / [(p+N-1)ts]
Dane: p = 6
ts = 5 ns
N = 5
Po podstawieniu: W(N,p) = 5 / (10 * 5 ns) = 1 / (10 * 10-9 s) = 100 * 106 1/s =
= 100 Mflops
-------------