przyklady na egzamin, szkola, przetwarzanie rownolegle i rozproszone - Prof Szczerbinski


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

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)t­s]

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

-------------



Wyszukiwarka

Podobne podstrony:
[ tycjan ] - PRIR zadania, szkola, przetwarzanie rownolegle i rozproszone - Prof Szczerbinski
Wyk ad 8 sciaga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
[tomko] Progr Rozpr Pytania egzaminacyjne, przetwarzanie rownolegle i rozproszone - Szczerbinski
Wyk ad 1 sciaga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
Wyk ad 4 sciĄga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
Wyk ad 5 sciĄga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
Wyk ad 6 sciĄga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
Wyk ad 2 sciaga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
Wyk ad 9 sciaga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
Wyk ad 3 sciĄga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
Wyk ad 7 sciaga, Studia - Automatyka, Przetwarzanie równoległe i rozproszone, egzamin, ściąga
PAL EC przyklad na egzamin
Przetwarzanie Równoległe i Rozproszczone Szczerbińskiego, wykład 3, SIEĆ PRZETASOWANA (perfect shuff
wyklad 4, przetwarzanie rownolegle i rozproszone - Szczerbinski

więcej podobnych podstron