Zestaw 1

1. Załóżmy, że sieć poniżej jest modelem pewnego przedsięwzięcia. Który wierzchołek może opisywać zdarzenie początkowe?

2. 1 – bo nie dochodzą do tego wierzchołka żadne łuki; jest to jedyny taki wierzchołek

3. 2

4. 5

5. 7

6. Sieć poniżej jest modelem pewnego przedsięwzięcia. Czasy realizacji wszystkich czynności wynoszą 1. Jaki jest luz czasowy zdarzenia 5?

1. 0

2. 1

3. 2

4. 3

5. Jeżeli algorytm o złożoności O(n⁴) w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N to jeżeli prędkość procesora wzrośnie 1000-krotnie wówczas w tym samym czasie rozwiążemy problem o rozmiarze:

6. 10 n

7. 5,62 n * (wykład 1, strona 7 - sposób) => 1000^(1/4)

8. 250 n

9. 3,98n

10. Jeżeli algorytm sekwencyjny w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N, to jeżeli dysponować będziemy p=10 procesorami (przy założeniu braku opóźnień komunikacyjnych i połączeniach między procesorami typy każdy z każdym) to w czasie 1h rozwiążemy problem o rozmiarze:

11. >=10N

12. = 10N

13. <=10N

14. chuj wie

15. Jeżeli czas działania algorytmu sekwencyjnego wynosi 3 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna, wynosi 2, to górne ograniczenie na czas działania alg. równoległego reprezentowanego przez pewien AGS i wykorzystującego p=3 procesory będzie:

16. <=2

17. <=5

18. <=4

19. <=3

20. Jeżeli czas działania algorytmu sekwencyjnego wynosi 7 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 3, to dolne ograniczenie na czas działania alg równoległego reprezentowanego przez pewien AGS i wykorzystującego p=2 procesory będzie:

21. >=3

22. >=7

23. >=2

24. >=1

25. Załóżmy, że graf z zadania 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi optymalna liczba procesorów p* dla tego AGS:

26. 3

27. 2

28. 1

29. 6

30. Najkrótsza droga dla sieci z zadania 1 z wierzchołka nr 1 do wierzchołka nr 5 ma długość:

31. 9

32. 12

33. 14

34. 23

35. Załóżmy, że graf z zad 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi długość harmonogramu przy założeniu, że liczba procesorów p=3:

36. 3

37. 6

38. 5

39. 7

40. Jeżeli czas działania algorytmu sekwencyjnego wynosi 5 oraz czas działania algorytmu równoległego (reprezentowanego przez pewien AGS) przy p=3 procesorach wynosi 3 to dolne ograniczenie na czas działania alg równoległego przy dostatecznie dużej liczbie procesorów będzie:

41. >=2

42. >=1

43. >=3

44. >=5

45. W praktyce efektywność algorytmu równoległego wykorzystującego p procesorów jest:

46. Zawsze <=1

47. Zawsze należy do przedziału [0, 1]

48. Zawsze jest >1

49. Może być >1

50. Który z wymienionych elementów stanowi podstawową zaletę obliczeń asynchronicznych:

51. znaczna redukcja czasu obliczeń (wykład 3 str. 8)

52. mniejsza częstotliwość przesyłania danych między procesorami

53. łatwość w określeniu zbieżności algorytmu

54. szybsza komunikacja między procesorami

55. Długość harmonogramu wyznaczanego dla grafu AGS jest w szeregowaniu zadań nazywana:

56. całkowitym czasem zakończenia zadania

57. max opóźnieniem

58. max spóźnieniem

59. długością uszeregowania

60. Mamy listę 5-ciu zadań o czasach wykonywania odpowiednio: 5,4,7,3,2. Długość uszeregowania tych zadań na p=2 procesorach według zasady LPT wynosi:

61. 11

62. 13

63. 12

64. 10

65. Algorytm Hu służy do szeregowania:

66. zadań niepodzielnych, niezależnych na procesorach identycznych

67. zadań niepodzielnych, niezależnych na procesorach dowolnych

68. zadań niepodzielnych, zależnych na procesorach identycznych

69. zadań niepodzielnych, zależnych na procesorach dowolnych

ZESTAW 3

1. Załóżmy, że sieć poniżej jest modelem pewnego przedsięwzięcia. Który wierzchołek może opisywać zdarzenie początkowe?

1. 1 – bo nie dochodzą do tego wierzchołka żadne łuki; jest to jedyny taki wierzchołek

2. 2

3. 5

4. 7

5. Sieć poniżej jest modelem pewnego przedsięwzięcia. Czasy realizacji wszystkich czynności wynoszą? Jaki jest luz czasowy zdarzenia?

1. 2

2. 3

3. 4

4. 1

5. Jeżeli algorytm o złożoności O(n²) w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N to jeżeli prędkość procesora wzrośnie 1000-krotnie wówczas w tym samym czasie rozwiążemy problem o rozmiarze:

6. 500 n

7. 31,62 n

8. 10.0 n

9. 1000 n

10. Jeżeli algorytm sekwencyjny w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N, to jeżeli dysponować będziemy p=5 procesorami (przy założeniu braku opóźnień komunikacyjnych i połączeniach między procesorami typy każdy z każdym) to w czasie 1h rozwiążemy problem o rozmiarze:

11. >=5N

12. = 5N

13. <=5N

14. chuj wie

15. Jeżeli czas działania algorytmu sekwencyjnego wynosi 7 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna, wynosi 2, to górne ograniczenie na czas działania alg. równoległego reprezentowanego przez pewien AGS i wykorzystującego p=3 procesory będzie:

16. <=4

17. <5

18. <4

19. <=5

20. Jeżeli czas działania algorytmu sekwencyjnego wynosi 11 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 5, to dolne ograniczenie na czas działania alg równoległego reprezentowanego przez pewien AGS i wykorzystującego p=3 procesory będzie:

21. >=3

22. >=11

23. >=5

24. >=2

25. Załóżmy, że graf z zadania 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi optymalna liczba procesorów p* dla tego AGS:

26. 3

27. 2

28. 1

29. 4

30. Najkrótsza droga dla sieci z zadania 1 z wierzchołka nr 1 do wierzchołka nr 4 ma długość:

31. 13

32. 12

33. 14

34. 23

35. Załóżmy, że graf z zad 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi długość harmonogramu przy założeniu, że liczba procesorów p=1:

36. 8 (podobno ok)

37. 6

38. 5

39. 7

40. Jeżeli czas działania algorytmu sekwencyjnego wynosi 8 oraz czas działania algorytmu równoległego (reprezentowanego przez pewien AGS) przy p=3 procesorach wynosi 4 to dolne ograniczenie na czas działania alg równoległego przy dostatecznie dużej liczbie procesorów będzie

41. >2

42. >1

43. >=2

44. >=3

45. W praktyce efektywność algorytmu równoległego wykorzystującego p procesorów jest:

46. Zawsze <=1

47. Zawsze należy do przedziału [0,1]

48. Zawsze jest >1

49. Może być >1

50. Który z wymienionych elementów stanowi podstawową zaletę obliczeń synchronicznych:

51. Mała częstotliwość przesyłania danych między procesorami

52. Znaczna redukcja czasu obliczeń

53. Małe opóźnienia w realizacji operacji

54. Szybsza komunikacja między procesorami

55. Długość harmonogramu wyznaczanego dla grafu AGS jest w szeregowaniu zadań nazywana:

56. całkowitym czasem zakończenia zadania

57. max opóźnieniem

58. max spóźnieniem

59. długością uszeregowania

60. Mamy listę 5-ciu zadań o czasach wykonywania odpowiednio: 5,4,7,3,2. Długość uszeregowania tych zadań na p=2 procesorach według zasady LPT wynosi:

61. 12

62. 11

63. 13

64. 21

65. Algorytm Hu służy do szeregowania:

66. zadań podzielnych, zależnych na procesorach identycznych

67. zadań podzielnych, zależnych na procesorach dowolnych

68. zadań niepodzielnych, zależnych na procesorach identycznych

69. zadań niepodzielnych, zależnych na procesorach dowolnych

ZESTAW 4

1. Załóżmy, że sieć poniżej jest modelem pewnego przedsięwzięcia. Jaki jest najwcześniejszy termin realizacji przedsięwzięcia (zdarzeniem końcowym jest zdarzenie nr 5):

1. 23

2. 17

3. 14

4. 18

5. Sieć poniżej jest modelem pewnego przedsięwzięcia. Czasy realizacji wszystkich czynności wynoszą 1. Jaki jest najpóźniejszy dopuszczalny termin rozpoczęcia czynności J:

1. 2

2. 3

3. 4

4. 1

5. W praktyce przyspieszenie algorytmu równoległego wykorzystującego p procesorów jest:

6. zawsze należy do przedziału [1,p]

7. zawsze jest <= 1

8. może być <=1

9. może być >=p

10. Załóżmy, że graf z zad 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi długość harmonogramu przy założeniu że liczba procesorów p=2?

11. 4

12. 6

13. 5

14. 7

15. Załóżmy, że graf z zad 2 reprezentuje AGS pewnego problemu obliczeniowego w którym pominięto wierzchołki wejściowe. Ile wynosi optymalna długość harmonogramu dla tego AGS?

16. 5

17. 4

18. 6

19. 1

20. Jeżeli czas działania algorytmu sekwencyjnego wynosi 10 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 4, to dolne ograniczenie na czas działania alg równoległego reprezentowanego przez pewien AGS i wykorzystującego p=5 procesory będzie:

21. >=3

22. <=10

23. >=5

24. >=4

25. Jeżeli czas działania algorytmu sekwencyjnego wynosi 5 oraz czas działania algorytmu równoległego przy założeniu, że dostatecznie duża liczba procesorów jest dostępna wynosi 3, to przyspieszenie algorytmu równoległego z dowolna liczbą procesorów:

26. <=0.6

27. <=1.67

28. >=0.6

29. >=2

30. Najkrótsza droga dla sieci z zadania 1 z wierzchołka nr 1 do wierzchołka nr 5 ma długość:

31. 14 (1->7->8->3->5)

32. 17

33. 23

34. 13

35. Jeżeli algorytm sekwencyjny w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N, to jeżeli dysponować będziemy p=11 procesorami (przy założeniu braku opóźnień komunikacyjnych i połączeniach między procesorami typu każdy z każdym) to w czasie 1h rozwiążemy problem o rozmiarze:

36. >=11N

37. = 11N

38. <=11N

39. chuj wie

40. Jeżeli algorytm o złożoności O(n^(1/8)) w ciągu 1h jest w stanie rozwiązać problem o rozmiarze N, to jeżeli prędkość procesorów wzrośnie 10-krotnie wówczas w tym samym czasie rozwiążemy problem o  rozmiarze:

41. 10 N

42. N

43. 100N

44. 1000N

45. 100 000 000N

46. Efektywność algorytmu równoległego reprezentowanego przez AGS z zadania 2 (w którym pominięto wierzchołki wejściowe) dla p=4 procesorów jest:

47. 0.5

48. 0.8

49. 0.4

50. 0.2

51. Mamy listę 5-ciu zadań o czasach wykonywania odpowiednio: 8, 4, 7, 3, 2. Długość uszeregowania tych zadań na p=2 procesorach według zasady LPT wynosi:

52. 13

53. 11

54. 12

55. 10

56. Algorytm wyznaczania ścieżki krytycznej służy do szeregowania:

57. zadań niezależnych, niepodzielnych w systemach jednoprocesorowych

58. zadań niezależnych, podzielnych w systemach jednoprocesorowych

59. zadań zależnych, niepodzielnych w systemach bezprocesorowych

60. zadań zależnych, podzielnych w systemach bezprocesorowych.

61. Który z wymienionych elementów stanowi podstawową wadę obliczeń synchronicznych:

62. duża częstotliwość przesyłania danych między procesorami

63. znaczne wydłużenie czasu obliczeń

64. trudność w określeniu zbieżności algorytmu

65. wolniejsza komunikacja między procesorami (?)

66. Przyspieszenie algorytmu równoległego reprezentowanego przez AGS z zadania 2, w którym pominięto wierzchołki wejściowe, dla p=2 procesorów jest równe:

67. 2.0

68. 0.8

69. 1.2

70. 1.6

Przykładowe pytania testowe

1. Wartość efektywności algorytmu równoległego:

1. zawsze jest >=1;

2. zawsze jest <=1;

3. nie musi być >=1;

4. nie musi być <=1;

5. Harmonogramowanie według reguły SPT oraz LPT:

6. gwarantuje otrzymanie tej samej postaci harmonogramu, ale inną długośćharmonogramu;

7. gwarantuje otrzymanie tej samej postaci harmonogramu oraz tą samą długośćharmonogramu;

8. nie gwarantuje otrzymanie tej samej postaci harmonogramu, ale tą samą długośćharmonogramu;

9. nie gwarantuje otrzymanie tej samej postaci harmonogramu, ani tej samej długościharmonogramu;

10. Podstawową wadą obliczeń asynchronicznych jest:

11. wydłużenie czasu obliczeń w stosunku do obliczeń synchronicznych;

12. duża intensywność przesyłania danych między procesorami;

13. zwiększenie rozmiaru danych do obliczeń;

14. zmniejszenie dokładności otrzymanych rozwiązań;

Część Nowaka

Grupa 1

1. Różnice między modelem „stacja robocza = serwer” (NOW – Network of Workstation) a modelem „pula procesorów”.

   Model puli procesorów składa się z wielu jednostek centralnych w jednej szafie (polegający na wydzieleniu w systemie zbioru procesorów nie będących własnością żadnego konkretnego użytkownika, wydzierżawianych z puli poszczególnym procesom na czas ich obliczeń). Użytkownicy mają szybkie terminale graficzne. Model stacji roboczych składa się z wielu stacji roboczych połączonych siecią LAN.

Podstawowa wada systemów NOW to niespójność systemu, tzn. każdy węzeł jest widziany jako niezależny system, co utrudnia wykorzystanie jako środowiska do uruchamiania zadań równoległych.

1. Wytłumacz działanie ssi w klastrze obliczeniowym.

   Systemy SSI (Single System Image) zarządzają zasobami w klastrze, tworząc wspólny obszar udostępniania zasobów, tj. dysk, pamięć, procesy. W ten sposób aplikacja działająca w klastrze nie widzi odrębnych węzłów klastra, ale jedną wspólną przestrzeń pamięci RAM, jeden system plików, jeden obszar adresacji zadań. Uproszcza to znacznie użytkowanie klastra.

2. Opisać sposób rozpraszania obliczeń w pvm.

PVM jest narzędziem służącym głównie do pośrednictwa w wymianie informacji pomiędzy procesami uruchomionymi na oddzielnych maszynach oraz do zarządzania nimi za pośrednictwem konsoli pvm. Z punktu widzenia obecnej definicji maszyny wirtualnej, pvm w sumie nie zasługuje na swoją nazwę, powinien się bardziej nazywać "zarządca procesów zrównoleglonych", jednakże historia pvm sięga dawnych czasów, kiedy to nazewnictwo było nieco inaczej rozumiane.

W dużym uproszczeniu PVM pozwala na "połączenie" większej ilości komputerów w jeden. Odbywa się to na zasadzie dołączania kolejnych hostów (komputerów), na których został zainstalowany i skonfigurowany pvm. Podłączanie hosta jest w uproszczeniu procedurą połączenia przez rsh, uruchomieniu demona pvm i dostarczenia mu informacji o tym, kto jest jego "rodzicem" oraz o parametrach istniejącej sieci.

W momencie, kiedy cała "maszyna wirtualna" już jest skonfigurowana, rola pvm sprowadza się do stanowienia pomostu wymiany informacji pomiędzy procesami, które się w pvm "zarejestrują", oraz umożliwienia administrowania stanem zarejestrowanych w pvm procesów.

http://eti.agh.edu.pl/skiai/lab/scenariusz-MPI.pdf

Grupa 2

1. Różnica między now i pulą procesorów.

   jw.

2. Realizowanie obliczeń równoległych w mpi.

   MPI – standard przesyłania komunikatów miedzy procesami.

   Zasadą działania środowiska MPI jest podział programu na tzw. komunikatory. Są to podstawowe jednostki funkcjonalne, między którymi wymieniane są dane i przesyłane są komunikaty.

   Standard ten pozwala na zdefiniowanie dwóch podstawowych struktur procesów w obrębie jednego komunikatora. Pierwsza z nich to topologia kartezjańska, w której procesy ułożone są w macierz niekoniecznie dwuwymiarową.

   bardziej ogólna topologia - topologia grafu - działa na podobnej zasadzie, ale dla struktury grafu.

   http://eti.agh.edu.pl/skiai/lab/scenariusz-MPI.pdf

3. Pytanie z ssi. (konkretnie jakie nie wiem, pewnie opisać)

   jw.

26. Czym różni się system rozproszony budowany wg modelu stacji roboczych od modelu puli procesorów?

System rozproszony realizujący model puli procesorów zawiera system usług dla stacji roboczej, do którego dołączono jedną lub więcej pul procesorów. Pula procesorów składa się ze zbioru tanich komputerów, z których każdy zawiera m.in. procesor, pamięć i interfejs sieciowy. Każdy procesor puli ma niezależne połączenie z siecią (podobnie jak stacje robocze i serwery), a ich architektura nie musi być jednolita.

Z punktu widzenia użytkownika model puli procesorów różni się od modelu usług dla stacji roboczej tym, że użytkownik może wykonywać pożyteczne prace za pomocą słabo wyposażonego w sprzęt komputera albo nawet sieciowego terminalu. Stacja robocza lub terminal użytkownika po prostu zapewnia dostęp do zasobów obliczeniowych systemu. Zadanie obliczeniowe może być wykonywane częściowo lub w całości przez pulę procesorów. Jeśli użytkownik zapoczątkuje więcej niż jedno zadanie lub zadanie wytwarza podzadania, to procesory puli mogą być przydzielone każdemu z nich i wszystkie zadania mogą wykonywać się równolegle. Procesory puli są przydzielane dynamicznie na podstawie bieżącego obciążenia obliczeniami i obciążenia pamięci oraz wymagań pamięciowych programu. Przykładem systemu realizującego model puli procesorów może być system Amoeba.

Druga modyfikacja polega na programowym rozszerzeniu modelu usług dla stacji roboczej, umożliwiającym przydzielenie zadań bezczynnym lub słabo wykorzystywanym stacjom roboczym jako płynnej puli dodatkowych komputerów, które mogą być używane podobnie jak pula procesorów w modelu puli procesorów. W każdej chwili, a zwłaszcza nocą, znaczna część stacji roboczych w sieci może pozostawać bezczynna lub tylko lekko obciążona pracami w rodzaju redagowania dokumentów. Takie stacje robocze mają zapas mocy obliczeniowej i mogą być używane do wykonywania zadań dla użytkowników zarejestrowanych na innych stacjach i których zadania wymagają więcej mocy obliczeniowej niż może im zapewnić jedna stacja robocza. Przykładem może być system Sprite - przeznaczony dla systemów rozproszonych, który umożliwia użytkownikom wykonywanie poszczególnych poleceń na bezczynnych lub nie w pełni wykorzystanych stacjach roboczych. Docelowa stacja jest wybierana przeźroczyście przez system. System Sprite uwzględnia możliwość migracji procesów, czyli przemieszczania wykonywanego programu z jednej maszyny do drugiej. Oznacza to, że w razie zarejestrowania się użytkownika na danej stacji lub gdy stacja ta zacznie być intensywniej wykorzystywana, gościnnie wykonywany program może powędrować bezpiecznie z powrotem do innej lub swojej maszyny, gdzie może być dalej wykonywany.