Zad 1

Korzystając z prawa Amdahla, podać wydajność obliczeń równoległych na 6 procesów dla programu, którego część, dająca się zrównoleglić wynosi 80%.

Odp.

Z definicji η (n,p)=S(n,p)/p p - liczba procesów

p.Amdahala: 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,p)=1 / (1+5 * 0,2) = 1 / 2 = 0,5

Zad 2

Zapisać we wspólnym porządku chronologicznym, kolejne fazy współbieżnych procesów, podając wszystkie zachodzące w ich trakcie operacje, dla następującej sytuacji:

Z niepodzielnego zasobu chronionego semaforem, z którym jest stworzona kolejka typów LIFO (stos), chcą korzystać kolejno procesy 11, 12, 13, 14, przy czym procesy 12, 13, 14 chcą skorzystać z zasobu w trakcie korzystania z niego przez proces 11.

Odp.

1: czy s=0 ? Nie;

S=s-1=1-1=0;

Zajmuje zasób

…………………………………

.

.

.

2: czy s=0 ? Tak;

Stan[12] := zawieszony;

12 zostaje umieszczony na stosie;

.

.

.

3: czy 3=0 ? Tak;

Stan[13]:=zawieszony;

13 zostaje umieszczony na stosie;

.

.

.

4: czy s=0? Tak;

Stan[14]:=zawieszony;

14 zostaje umieszczone na stosie;

11: s=s+1=0+1=1;

Czy to są procesy zawieszone na stosie ? Tak;

Stan[14]:=aktywny

.

.

.

14: s=s-1=1-1=0;

14 zajmuje zasób;

.

.

.

S:=s+1=0+1=1;

Czy są to procesy zawieszone na stosie? Tak;

Stan[13]:= aktywny;

.

.

.

13:s:=s-1=1=1=0;

13 zajmuje zasób;

.

.

.

s:=s+1=0+1=1;

czy są procesy zawieszone na stosie? Tak;

stan[12]:= aktywny;

.

.

.

12: s:=s-1=1-1=0;

12 zajmuje zasób;

.

.

.

S:=s+1=0+1=1;

Czy są procesy zawieszone na stosie? Nie;

Zad 3

a) Dokonać przekształceń prowadzących do zrównoleglenia (o ile jest możliwe) poniższej pętli w sposób optymalny, z wykorzystaniem ……….. systemu Open MP.

do i=1, n-1

a(i+1)=d(i) * b(i)

c(i+1)=c(i) * a(i+1)

d(i+1)=a(i) * c(i+1)

b(i+1)=e(i) * f(i)

enddo

Od.:.

!$omp parallel do

do i=1,n-1

b(i+1)=e(i)+f(i)

enddo

!$ omp end parallel do

!$ parallel do

do i=1,n-1

a(a+1)=d(i)*b(i)

enddo

!$ omp end parallel

do i=1,n-1

c(i+1)=c(i)*a(i+1)

end do

!$ omp parallel

do i=1,n-1

d(i)=a(i)*c(i+1)

end do

!$ omp end parallel

b) Wypisać wszystkie występujące w poniższej pętli zależności danych, podając ich typy 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

2

---