Miliony testów cały szczerbol (rok 2005) 4/5 nie zdało czas napisana: 40 minut nie ma możliwości ściągania z jakichkolwiek źródeł (chyba że ktoś ma ochotę zaliczać ten przedmiot przez najbliższe 4 semestry)

Test 1.

• Pamięci rozproszone, rysunek i opis

• Obliczyć czas z Amdahla, dane T(n,1)=36 ,p=6 , f(n)=10%

• Fifo nie podzielny
  I1 zaczyna
  I2 chce skorzystać jak I1 korzysta
  I3 chce skorzystać z zasobu gdy I1 skończy i I2 korzysta
  I4 chce skorzystać jak I2 i I3 zakończy korzystanie z zasobu

• 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
  
  może były inne znaki (+ , - ,*) ale to nie ma wpływu według mnie

• zależności nie pamiętam

Test 2.

• Schemat producenta i konsumenta- na czym polega, narysować rysunek. Na czym polega synchronizacja i kiedy dochodzi do komunikacji p-k. Napisać producenta w zapisie pascalowym bez semaforów.

• Obliczyć wielkość wektora dla ...................... potokowego dla 6 ...... tak aby wydajność była równa wektorowi o wielkości 16 dla 10 ............ ..

• Zasób niepodzielny, kolejka LIFO. I1, I2, I3, I4 kolejno chcą. I2 chce, jak już I1 skończył, I3 i I4 chcą w trakcie korzystania przez I2.

• Zależności- nie pamiętam

• Zoptymalizować:
  
  do i=1, n-3
  a(i)=b(i)*c(i)+d(i-1)
  if ((a+3)<>0) e(i)=c(i)/d(i)
  b(i)=a(i)*c(i)
  enddo

Test 3.

• Coś o wyznaczaniu ciągu sum. (nie pytajcie o szczegóły)

• Wyznaczyć koszt obliczeń, korzystając z prawa Amdahla.
  p = 9
  T(n,1) = 30s
  f(n) = 25%

• Zasób niepodzielny. Kolejka LIFO. Procesy I1, I2, I3, I4 chcą kolejno skorzystać z zasobu.
  a) procesy I2 i I3 chcą skorzystać z zasobu, gdy korzysta z niego proces I1.
  b) proces I4 chce skorzystać z zasobu, gdy korzysta z niego proces I3.

Test 4.

• Problemy pojawiające przy obliczaniu zadań na jednostce wieloprocesorowej 4. Problem podziału zadania [coś w ten deseń]

• Wyprowadzić wzór na wydajność dla jednostki potokowej, wraz z opisem.

• Semafory, proces I1 dobija się do zasobu, po nim do zasobu ma dostęp I2, I3 chce uzyskać dostęp, gdy I2 korzysta z zasobu. I4 chce uzyskać dostęp, gdy I3 korzysta z zasobu. FIFO

• Opisać zależności w instrukcjach numerowanych od 1 do 6, niestety nie pamiętam treści, było ich około 8 imho. I do tego zrównoleglić się owe pętlę.

Test 5.

• 1. Pamięć wspólna - omówić z uwzględnieniem rysunku poglądowego, wad, zalet takiego systemu oraz wypisać komercyjne komputery posiadające taką strukturę.

• 2. Obliczyć T(n,1) jeśli p=3, T(n,p)=2s i f(n)=0,1

• 3. Semafor, kolejka FIFO, niepodzielny, procesy I1,2,3,4
  - proces 2 wbija się po procesie 1
  - proces 3 wbija się w czasie działania procesu 2
  - proces 4 wbija się po procesie 3

• Zrównoleglij: ten przykład z pi i dwapi
  

Test 6.

• Coś o 4 przykłady o wektorach.. ni cholery nie wiedziałem
  

• Równolegle procki jadą przez 70% czasu, (na 10 proc). ile trzeba procent równoległej pracy by na 4 proc otrzymać taki sam czas?

• Semafor fifo, 3 na raz mogą pracować (podzielny)
  kolejka i1 ,i2, i3, i4
  i2 chce jak i1 wyjdzie
  i3,i4 chcą po wyjściu i1 lecz w trakcie "bycia" i2
  i3 wchodzi po wyjściu i2
  i4 wchodzi po wyjściu i3, oraz zamyka kolejkę

Test 7.

• 4 problemy efektywnego programowania systemów wieloprocesorowych. (w dalszej części tego pytania było cos o rodzajach implementacji w systemach...)

• 2) obliczyć czas z Amdahla, dane T(n,1)=2s ,p=11 , f(n)=30%

• 3) s=1 LIFO chcą skorzystać kolejno procesy I1, I2, I3, I4, przy czym:
  - I2 chce skorzystać jak I1 skończy
  - I3 chce skorzystać jak I2 skończy
  - I4 chce skorzystać w czasie gdy korzysta I3

• było chyba z 6 procesów...

Test 8.

• Problemy efektywnego programowania systemów wieloprocesorowych. (w dalszej części tego pytania było cos o rodzajach implementacji w systemach...)

• Obliczyć koszt obliczeń, jeśli t(n,1)=30 p=8 cześć dająca się zrównoleglić 75% czyli f(n)=25%

• Semafor z kolejka LIFO.
  a)i2 chce skorzystać jak i1 kończy
  b)i3 chce skorzystać jak i2 kończy
  c)i4 chce skorzystać w trakcie korzystania przez i3

• zależności ni ciutka nie pamiętam ale miąłem 6wierszy i wyszło mi tego 12 zależności -masakra

Test 9.

• Hiperszescian i piramida (opisać i dać wzory)

• Prawo amdahla - wyprowadzić i opisać "wniosek z tego wzoru"

• Kolejka lifo(stos) i1,i2,i3,i4.

• Korzysta i2,i3,i4 chce skorzystać podczas korzystania z zasobu przez i1.
  4.
  
  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)
  
  no i jeszcze miąłem w zestawie zależności i typy
  

Test 10.

• Wyprowadź prawo amdahla i podaj istotny wniosek

• Krata (oba rodzaje) i drzewo binarne

• Procesy, fifo, i2 chce jak skończy i1, i3 chce jak skończy i2, i4 chce w trakcie i3

• Zrównoleglij:
  do i=2,n
  a(i+1)=b(i-1)
  b(i)=a(i)*k
  c(i)=b(i)-1
  end do

Test 11.

• Opisz klasyfikacje Flynn'a. Narysuj i opisz SISD

• Kolejka, FIFO, s=1. i1, i2 i i3 próbuje, gdy i1 w użyciu, i4 próbuje, gdy i2 i i3 skoczny.

• la parallela.. Intuicyjnie, bo nie pamiętam jak to szło:
  do i=2,20;
  i(i):=s(i)+c;
  s(i+1)=d*i(i-1);
  h:=c*d;
  end do

Test 12.

• Opisz klasyfikacje Flynn'a. narysuj i opisz SISD.

• Kolejka LIFO, zasób niepodzielny ( s=1).
  i2 gdy i1 używa,
  i3 próbuje gdy i1 zwolni
  i4 próbuje gdy i2 i i3 zwolni.

• Z Amdahla. Czas wykonania na 1 procku T(n,1)=18s. ile będzie trwało obliczenie na 6 prockach jeśli f(n)=10%. ( liczb nie jestem pewien).

• Zależności.. ni cholery nie pamiętam.

• la parallela.. ni cholery nie pamiętam . Krótkie było ale strasznie zakręcone....

Inne lata:

Test 13

1. Scharakteryzować komputery równoległe z równoległym dostępem do pamięci.(inne grupy: z pamięcią wspólną, systemy tj. SISD,SIMD, MISD, MIMD

2.Na podstawie prawa Amodahla oblicz (chyba) czas realizacji zadania na p procesorach, jeśli ilość procesorów to 6, procent czasu wykonania jaki zajmuje cześć sekwencyjna 20%, chyba (czas wykonania 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.

1. 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

Test 14

• 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).

• Omówic (ogólne zasady algorytmu, zastosowanie ciągu n elementów metodą bąbelkowa, w procesorze macierzowym. W jakim stopniu wykorzystanie procesora macierzowego w miejsce konwencjonalnego (sekwencyjnego) wpłynęło na złożoność obliczeniową algorytmu?
  Narysować kolejne kroki sortowania ciągu liczb całkowitych:
  2, 5, 4, 1, -1, -2
  przez 6 połączonych w szereg elementów przetwarzających.

• 
  a) Omówić (ogólnie)zadanie producenta. Zapisać przy użyciu semaforów, procesy producenta i konsumenta.

• 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

Test 15.

• 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 nnymi napisać te wszystkie parametry p,c,d)

• 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)

• 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.

Test 16

1. 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.

2. 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

3. 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

Test 17

1. Problemy z synchronizacją (4). Wypisać oraz objaśnić sposoby zaradzania przy synchronizacji wykonania procesów równoległych.

2. 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.

3. 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).

Test 18 (z rozwiązaniem)

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

Zadania z poprawki rok 2005

Test.1

1. Omowic systemy z pamiecia wspolna, podac komercyjne przyklady zastosowan, schemat, wady i zalety tego typu rozwiazania.
2. Zadanie dotyczace jednostki potokowej, podana dlugosc wektora - 13, czas zegara 13ns, ilosc potokow 8, obliczyc przepustowosc tego typu maszyny.
3. Kolejka FIFO, I1,I2,I3,I4 zasob niepodzielny; I2 chce skorzystac gdy I1 skonczy, I3 chce gdy I2 korzysta, I4 chce gdy I3 skonczy.
4. a) zrownoleglic jesli sie da w oparciu o openMp zadanie z pi i dwapi
b) podac zaleznosci, [moim zdaniem same przeplywu + przeciwzaleznosc imo roz].

Test2.

1. Wymienić 4 problemy występujące przy programowaniu na jednostkach wieloprocesorowych (czy jakoś tak), omówić problem podziału zadań


2. Wyprowadzić wzór dla komputerów wektorowych coś tam z potokami, wiem że trzeba było też podać wzory na czasy i dopiero potem wyprowadzać wzór z potokami (tylko nie pamiętam dokładnie o co chodziło). Opisać


3. FIFO, s=1
I2 chce skorzystać z zasobu jak I1 skorzysta
I3 chce skorzystać z zasobu jak I2 korzysta
I4 chce skorzystać z zasobu jak I3 korzysta

4. Zależności (na bank nie pamiętam czy tak dokładnie było, ale większość się zgadza
):

a(i+1)=b(i)*d(i)
c(i+1)=c(i)*a(i+1)
d(i)=a(i)*c(i+1)
b(i+1)=a(i+1)*c(i)
d(i)=e(i)+d(i)
e(i+1)=abs(f(i+1))

test3.

1. Pamięć wspólna (ang. shared memory)
   
   zalety
   -łatwość programowania
   -łatwość rozbudowy o nowe jednostki funkcyjne
   wady
   -ograniczona przepustowość sieci połączeń
   
   Zazwyczaj 4-8 procesorów
   
   Koszt dostępu do pamięci - stały niezależniony od procesora, jednolity dostęp do pamięci UMA
   SMP-wieloprocesorowość symetryczna
   
   [] [] [] moduły pamięci
   | | |
   ==== sieć połączeń (to jest to tzw. wąskie gardło lol )
   | | |
   [] [] [] procesory
   
   2)
   Dane :
   N - 13
   ts - 13 ns
   p - 8
   W(N,p) = ? MFLOPS
   
   Przepustowość = wydajność/ts (czas)
   a więc
   
   n(N,p)=N/p+N-1=13/8+13-1=13/20 * 1/ts=1/20 {MFLOPS}

Test 4.

INNE:

1. 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.

---