Treść zadania laboratoryjnego z przedmiotu „Obliczenia równoległe”

1. Zapoznać się z oprogramowaniem „Symulator obliczeń równoległych” umieszczonym we wskazanym przez prowadzącego katalogu; 2. Dla zagadnień algebraicznych podanych w tabeli zaproponować schemat obliczeń równoległych (AGS, harmonogram) dla różnej liczby procesorów (przyjąć kilka wartości tak, aby można było narysować wykres tej zależności) oraz a) oszacować teoretyczną złożoność obliczeniową problemu, jako funkcję rozmiaru zadania i liczby procesorów przyjmując, że procesory połączone są w sieci „każdy-z-każdym”, opóźnienia przesyłu danych między procesorami są zerowe oraz opóźnienia przesyłu danych wewnątrz każdego procesora są zerowe; b) wykonać punkt a) przy założeniu, że procesory połączone są w sieci „każdy-z-każdym”, opóźnienia przesyłu danych między procesorami są równe 2 oraz opóźnienia przesyłu danych wewnątrz każdego procesora są równe 1; c) przeprowadzić symulację obliczeń równoległych dla każdej z trzech wartości liczby procesorów (mniejszej od rozmiaru zadania, równej rozmiarowi zadania i większej od rozmiaru zadania) przyjmując łącznie następujące dane: i. dla każdej liczby procesorów przyjąć, że procesory są jednorodne (pierwszy przypadek) i niejednorodne (każdy kolejny procesor jest dwa razy szybszy od poprzedniego) oraz ii. przyjąć, że wszystkie wymagane do realizacji zadania operacje są jednorodne (pierwszy przypadek) i niejednorodne (szybkość operacji ustalić według uznania); iii. sprawdzić dla dowolnych czterech algorytmów wyznaczania harmonogramu oraz dwa sposoby przydziału procesora do zadań; d) porównać wyniki uzyskane punktach a), b) i c) w zależności od przyjętej liczby procesorów, dokonać wyliczenia przyspieszenia, efektywności algorytmu dla każdej z badanych wartości liczby procesorów, odczytać wartość długości harmonogramu. Ponadto wyliczyć wartości charakterystyk: T∞, Tp, D, p* dla każdej z badanych wartości liczby procesorów; e) wykonać sprawozdanie. Wyniki przedstawić w postaci graficznej (te, które są możliwe do takiej prezentacji), przedstawić wnioski ustosunkowując się do każdego z punktów zadania.

Jeżeli nie podano innych zagadnień algebraicznych, to obowiązującymi są podane w tabeli.

Nr

Opis problemu

Nr studenta

problemu

w dzienniku

1

Sortowanie przez proste

1, 11

wstawianie

2 Sortowanie

połówkowe 2,

12

3 Sortowanie

bąbelkowe 3,

13

4 Sortowanie

drzewiaste

4, 14

(heapsort)

5 Mnożenie dwóch macierzy

5, 15

n na n

6

Dodawanie dwóch macierzy

6, 16

7

Obliczanie macierzy odwrotnej

7, 17

8

obliczanie histogramu

8, 18

9

Przeszukiwanie grafu w głąb 9,

19

10

Przeszukiwanie grafu wszerz

10, 20

1