EGZAMIN -PRZETWARZANIE ROWNOLEGLE dziene 27.06.03
1. Scharakteryzowac komputery równoległe z równoległym dostępem do pamieci.(inne grupy: z pamięcią wspolna, systemy tj. SISD,SIMD, MISD, MIMD
2.Na podstawie prawa Amodahla oblicz (chyba) czas realizacji zadania na p procesorach jeśli ilość procesorow to 6, procent czasu wykonania jaki zajmuje czesc sekwencyjna 20%, chyba (czas wykonanai zadania równoległego =36s)
3. Opisz operacje na semaforach taka ze do nie podzielnego zasobu dostac się chca procesy I1,I2,I3,I4 W TEN SPOSÓB
- i2 CHCE DOSTAC SIĘ GDY i1 ZAJMUJE ZASOB
-I3 GDY I1 JUŻ SKOŃCZYŁ KORZYSTANIE Z ZASOBU A I2 JEST W TRAKCIE KORZYSTANIA Z ZASOBU
-I4 CHCE DOSTAC SIĘ DO ZASOBU KIEDY I3 I I4 JUŻ sKOŃCZYŁY kORZYSTANIE Korzystanie ZASOBU
4.
Zrównoleglić:
do i=2,n
pi=3.14
dwapi=2*pi
a(i)=dwapi*r(i)*t(i-1)
enddo
b) Zależności:
do i=2,n
S: c(i)=a(i)+d(i-1)
T: a(i)=b(i-1)+1
U: d(i)=c(i)+1
W: b(i)=a(i)+1
X: f(i)=d(i)-(i-1) tu nie jestem na 100% pewna {być może było d(i)+(i-1)}
Y: e(i)=d(i)+f(i-1)
Enddo
były 4 zadania ( od Kamila)
1 producent klient wykład nr 6
2 kolejka fifo lub lifo (dla kilku procesów jakieś semafory?)
3 obliczyć wzrost wydajności z wzoru kogoś na a (alhmana?)
4 zrównoleglić pętle i wypisać problemy do zrównoleglenia
wyjść przepływu itd
pozdrawiam kamil
++++++++++++++
1. Podać ogólne cechy statycznych sieci połączeń miedzy procesorami /elementami przetwórczymi. Podać wzory na parametry sieci o pełnym połączeniu (każdy z każdym).
2.Omówic (ogólne zasady algorytmu, zastosowanie ciągu n elementów metodą bąbelkowa, w procesorze macierzowym. W jakim stopniu wykożystanie procesora macierzowego w miejsce konwencjonalnego (sekwencyjnego) wpłyneło na złożonośc obliczeniową algorytmu?
Narysowac kolejne kroki sortowania ciągu liczb całkowitych:
2, 5, 4, 1, -1, -2
przez 6 połączonych w szereg elementów przetwarzających.
3.
a) Omówić (ogólnie)zadanie producenta. Zapisać przy użyciu semaforów, procesy producenta i konsumenta.
b) 3 miejsca na produkty w magazynie, obecnie magazyn pusty (m=3, p=o) zakładamy, że producent jest "szybki", a konsument "wolny". Przebieg procesu w 2 równoległych kolumnach.
4.
a) Wypisać i sklasyfikować zalezności:
do j=1,m
r(j)=sin(x)
x=p(j)+q(j)
y=p(j)*q(j)
k(j)=cos(y)
end do
b) Zrównoleglic w sposób optymalny
do i=2,n
a(i+1)=b(i-1)
b(i)=a(i)*k
c(i)=b(i)-1
end do
++++++
1.Podać cztery najważniejsze problemy programowania systemów wieloprocesorowych. Omówić języki programowania równoległego.
(inni mieli w tym miejscu pytanie dotyczące statycznych sieci połączeń, mieli właśnie między innymi napisać te wszystkie parametry p,c,d)
2.Miary efektywności obliczeń równoległych. Wypisać wzory i zależności między nimi.
(inni mieli tu chyba zadania z Amdahla, ale na 100% nie jestem pewna)
3.Semafory.Był niepodzielny zasób, stowarzyszony z kolejką LIFO. Cztery procesy.I1,I2,I3,I4.Przy czym I2 i I3 chcą korzystać w momencie, gdy I1 już korzysta, zaś I4 chce skorzystać w momencie, gdy I2 korzysta.
(w inni mieli podobnie tylko zmienił np. kolejkę)
4.a)Zrównoleglenie(nie było szans spisać)
b)Wypisać zależności. W sumie dosyć prosty przykład, podobny do tego, który robiłam wczoraj było właśnie S,T,U,W, ale tez nie dałam rady spisać jak to dokładnie wyglądało.
+++++
Zad 1
Zapisać we wspólnym porządku chronologicznym kolejne fazy współbieżnych procesów podając zachodzące w nich następującej sytuacji :
Z niepodzielnego zasobu , chronionego semaforem s , z którym jest stowarzyszona kolejka typu LIFO (stos) chcą skorzystać procesy L1 , L2 , L3 , L4 , przy czym L2 , L3 , L4 chcą skorzystać z zasobu w trakcie korzystania z niego przez proces L1 .
Odp :
Semafor binarny, początkowa wartość s=1
L1: czy s=0 ? Nie ;
L1: zajmuje zasób ;
.
.
L2: czy s=0 ? Tak;
Stan [L2] := zawieszony ;
L2 zostaje umieszczone na stosie ;
L3: czy s=0 ? Tak;
Stan [L3] := zawieszony ;
L3 zostaje umieszczone na stosie ;
L4: czy s=0 ? Tak;
Stan [L4] := zawieszony ;
L4 zostaje umieszczone na stosie ;
L1: s:=s+1=0+1=1;
Czy są procesy zawieszone na stosie ? Tak;
Stan [L4] := aktywny ;
L4: s:=s-1=1-1=0;
L4: zajmuje zasób ;
.
.
L4: s:=s+1=0+1=1;
Czy są procesy zawieszone na stosie ? Tak;
Stan [L3] := aktywny ;
L3: s:=s-1=1-1=0;
L3: zajmuje zasób ;
.
.
L3:s:=s+1=0+1=1;
Czy są procesy zawieszone na stosie ? Tak;
Stan [L2] := aktywny ;
L2: s:=s-1=1-1=0;
L2: zajmuje zasób ;
.
.
L2:s:=s+1=0+1=1;
Czy są procesy zawieszone na stosie ? Nie;
Zad 2
a)Dokonać przekształceń prowadzących do zrównoleglenia ( o ile jest to możliwe) poniższej pętli w sposób optymalny , z wykorzystaniem dyrektywy 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)=a(i)*c(i+1) b(i+1)=e(i)+f(i)
|
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) end do ! $omp parallel do do i=1 , n-1 d(i)=a(i)*c(i+1) end do ! $omp end parallel do
|
b) wypisz wszystkie występujące w poniższej pętli zależności danych podając ich typy I rodzaje :
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
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 3
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)]
Stad η(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
+++++++++
Oto pytania jakie miałem na zaliczeniu z Przetwarzania równoległego i rozproszonego...
1. Podać ogólne cechy statycznych sieci połączeń miedzy procesorami /elementami przetwórczymi. Podać wzory na parametry sieci o pełnym połączeniu (każdy z każdym).
2.Omówic (ogólne zasady algorytmu, zastosowanie ciągu n elementów metodą bąbelkowa, w procesorze macierzowym. W jakim stopniu wykożystanie procesora macierzowego w miejsce konwencjonalnego (sekwencyjnego) wpłyneło na złożonośc obliczeniową algorytmu? Narysowac kolejne kroki sortowania ciągu liczb całkowitych: 2, 5, 4, 1, -1, -2 przez 6 połączonych w szereg elementów przetwarzających.
3. a) Omówić (ogólnie)zadanie producenta. Zapisać przy użyciu semaforów, procesy producenta i konsumenta. b) 3 miejsca na produkty w magazynie, obecnie magazyn pusty (m=3, p=o) zakładamy, że producent jest "szybki", a konsument "wolny". Przebieg procesu w 2 równoległych kolumnach.
4. a) Wypisać i sklasyfikować zalezności: do j=1,m r(j)=sin(x) x=p(j)+q(j) y=p(j)*q(j) k(j)=cos(y) end do b) Zrównoleglic w sposób optymalny do i=2,n a(i+1)=b(i-1) b(i)=a(i)*k c(i)=b(i)-1 end do
Podaj cechy sieci statycznych , scharakteryzuj parametry z nimi związane; opisz sieć o pełnym połączeniu (i narysuj) ; podaj wzory na parametry dla tej sieci i je wyprowadź (podobno na dziennych były wyprowadzenia u nas na zaocznych nie było, co nie przeszkodziło Panu w zadaniu tego pytania).
Opisz i narysuj i wyprowadź wzory (znowu - nie wystarczy napisać tych wzorów) dla sortowania bąbelkowego bąbelkowego trybie sekwencyjnym i równoległym)
Zadanie o producencie i konsumencie - opisz , narysuj ;
Do tego zrób przykład dla m=3, zakładając, że Producent pracuje dużo szybciej niż konsument. (znowu - Tomek Wechterowicz na głos pytał na ostatnim wykładzie czy będzie takie zadanie - i facet głośno i wyrażnie powiedział - NIE - bo nie zdążyliśmy omówić ) - no ale ja musiałam wiedzieć jak je zrobić.
4 a) wypisz zależności
nie pamiętam
b) zrównoleglij
do i=2, n
a(i+1)=b(i-1)+ c(i)
a(i)=b(i)*k
a(i)=b(i) +c(i)
enddo.
+++++
Pytania spisane po egzaminie z przetwarzania równoległego
Scharakteryzuj i opisz sieć dynamiczna ( jednostopniową)
Inna grupa
1a. Scharakteryzuj i opisz sieć z rozproszona pamięcią
1b. Wyznacz ciąg sumy macierzy dla 8 procesorów 0-7, wykaż różnice między
komputerami sekwencyjnymi i równoległymi.
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 20%
P =6
20% czasu równoległego
Inna grupa
P =5
50% czasu równoległego
2a. Na podstawie prawa Amdahla wyznacz koszt obliczeń dla 6 procesorów przy 60% równoległych
Niepodzielny zasób , kolejka FIFO, 4 procesy ( L1, L2, L3, L4 ) chcą skorzystać.
Przy czym
L1 - korzysta
L2 - w trakcie gdy L1
L3 - w trakcie L2 po zakończeniu L1
L4 - po zakończeniu L2 i L3
++++++
Pytania z egzaminu przetwarzania równoległego - grupa Tomka Wiśniewskiego
krata i drzewo binarne, omówić i wzory
wyprowadzenie wzoru i omówienie alhambra ( czy jak go tam)
semafory zadanie na 4 semaforach
no i zrównoleglenie i wypisanie zależności
++++
Podaj cechy sieci statycznych , scharakteryzuj parametry z nimi związane; opisz sieć o pełnym połączeniu (i narysuj) ; podaj wzory na parametry dla tej sieci i je wyprowadź (podobno na dziennych były wyprowadzenia u nas na zaocznych nie było, co nie przeszkodziło Panu w zadaniu tego pytania).
Jesli chodzi o wzory to wystarczylo wyprowadzic tak:
d=1 - bezapelacyjne, poprostu logiczne
c=n-1 - rowniez logiczne
natomiast p=(n*(n-1))/2 i to jest tez logiczne ale liczy sie to z dwumianu newtona
(2) | to jest jeden nawias.
(n) |
Opisz i narysuj i wyprowadź wzory (znowu - nie wystarczy napisać tych wzorów) dla sortowania bąbelkowego bąbelkowego trybie sekwencyjnym i równoległym)
to bylo ale bez wzorow. byl za to przyklad zeby posortowac jakis ciag znakow.
Zadanie o producencie i konsumencie - opisz , narysuj ;
Jesli chodzi o opis to dotyczyl on nie zadania a samego problemu - czyli jaki jest algorytm na producenta i konsumenta, podac ten algorytm z semaforami czyli z P(m), V(p) - dla producenta ; i P(p) i V(m) - dla konsumenta.
Do tego zrób przykład dla m=3 (m - miejsce w magazynie) , zakładając, że Producent pracuje dużo szybciej niż konsument. (co oznacza ze producent wyprodukuje tyle ze zajmie caly magazyn zanim konsument skonsumuje pierwszy produkt) No i zadanie nalezy przerwac gdy konsument zacznie korzystac z drugiego produktu.
no ale ja musiałam wiedzieć jak je zrobić (proste i logiczne, jak sie rozumie zagadnienie to nawet Justyna sobie poradzi :) )
odpowiedz nastepna strona. (kurde, ja tez musialem to wiedziec)
m=3, p=0
Producent Konsument
wytwarza produkt (wp) czeka
m=2 |
składa produkt (sp) |
p=1 |
aktywuje konsumenta---------------------| {koniec czekania}
wp p=0
m=1 bierze produkt (bp)
sp m=2
p=1 |
wp |
m=1 | {korzysta z produktu}
sp |
p=2 |
wp |
m=0 |
sp |
p=3 |
wp |
czeka {kończy korzystanie}
| p=2
| bp
| m=1
| {koniec czekania}------------------------aktywuje producenta
m=0 |
zp | {korzysta z produktu}
p=3
i tak dalej - ale trzeba przerwac gdy konsument zaczyna korzystac z produktu drugiego, dlatego juz przerwalismy.
4 a) wypisz zależności
do j=2, m
s1: a(j)=sin(x)
s2: x=b(j)+c(j)
s3: y=b(j)*c(j)
s4: p(j)=cos(y)
enddo.
źródło |
ujście |
zmienna |
typ |
rodzaj |
s1 |
s2 |
x |
przeciw zależność |
wewnątrz iteracyjna |
s3 |
s4 |
y |
przepływu |
wewnątrz iteracyjna |
s2 |
s2 |
x |
wyjść |
między iteracyjna |
s2 |
s1 |
x |
przepływu |
między iteracyjna |
s3 |
s3 |
y |
wyjść |
między iteracyjna |
s4 |
s3 |
y |
przeciw zależność |
między iteracyjna |
b) byl posrany nie dalem rady zrobic i nie pamietam tresci.
+++++
Problemy z synchronizacją (4). Wypisać oraz objaśnić sposoby zaradzania przy synchronizacji wykonania procesów równoległych.
Obliczyć koszt zrównoleglenia wykonania procesów przy 6 procesorach jeżeli funkcja f(n)=40% a czas wykonania zadania na 1 procesorze wynosi 10s.
Mamy niepodzielny zasób o kolejce typu LIFO. Z zasobu chcą kolejno skorzystać I1, I2, I3 i I4. Jeżeli:
- I2 i I3 chcą skorzystać z zasobu w momencie gdy I1 skończył korzystanie
I4 chce korzystać z zasobu w momencie gdy I3 korzysta z zasobu.
4. Wypisz zależności oraz ich typy w podanej pętli ( niestety nie pamiętam tego fragmentu programu).
made by:j.fryca@wp.pl