Przetwarzanie Równoległe Projekt 1 Opis problemu



Pobieranie 77.06 Kb.
Data28.04.2016
Rozmiar77.06 Kb.
Tomasz Stróżyk 80150

Kamil Piska 80125



Przetwarzanie Równoległe

Projekt 1



Opis problemu:

Zbadanie architektury systemu przetwarzającego w postaci pierścienia dwukierunkowego (niesymetrycznego) z 8 węzłami (problem nr 4).


1. Testowanie prędkości łącz oraz czasu przetwarzania transputerów.
1.1. Test prędkości łączy.
W systemie transputerów wyróżniamy dwa rodzaje łącze: poziome oraz pionowe. W celu zbadania przepustowości obu rodzajów przesyłaliśmy różne ilości danych (konkretnie liczb typu Integer) do dwóch sąsiednich transputerów głównego procesora(T0). Wyniki przedstawiono w tabelach poniżej (w kolumnach kolejno liczba danych, czas przesyłania):




10

47




100

249




500

1150




1000

2274




5000

11274




10000

22524
























































10

68

100

446

500

2125

1000

4226

5000

21026

10000

42026

Łącze poziome łącze pionowe


Wykorzystując funkcję REGLINP programu Excel, wykorzystującą metodę najmniejszych kwadratów, wyznaczyliśmy czasy komunikacji S oraz C dla obu łącz.
Łącze poziome: Łącze pionowe

S = 11,88 S = 12,4

C = 2,253 C = 4,2

1.2. Test prędkości przetwarzania transputerów.
Zadanie jednorodne wykorzystane do wyznaczenia parametrów polegało na pomnożeniu każdej liczby przez dziesięć (poprzez dziesięciokrotne dodawanie) i zsumowaniu wszystkich otrzymanych liczb. W celu przeprowadzenia pomiarów prędkości przetwarzania transputerów, użyliśmy dwóch z nich. TR0 (wypisywał zmierzone czasy) i TR1 (dokonywał obliczeń i przesyłał zmierzone czasy do TR0). Zakres ilości liczb na których wykonywano obliczenia ustalono na od 100 do 1000. Analogicznie do punktu wyżej, za pomocą funkcji REGLINP w programie Excel wyznaczono parametr A = 25,4328.

2. Opis modelu systemu.
Nasz system transputerów wygląda następująco:


Transputer inicjalizujący to TR0.
2.1. Podejście sekwencyjne.
W podejściu sekwensyjnym trzeba pamiętać, że jeden transputer nie może równocześnie wykonywać obliczeń oraz przesyłać danych. Celem optymalizacji tego podejścia jest minimalizacja casu najdłużej pracującego transputera.
Trzeba jednak zauważyć, że dane z pierwszego (TR0) tranpustera można rozprowadzić po innych w tej architekturze na 4 sposoby:


  1. najpierw TR0 wysyła dane do TR1, potem do TR3, a dane do TR8 trafiają z TR5

  2. najpierw TR0 wysyła dane do TR1, potem do TR3, a dane do TR8 trafiają z TR7

  3. najpierw TR0 wysyła dane do TR3, potem do TR1, a dane do TR8 trafiają z TR7

  4. najpierw TR0 wysyła dane do TR3, potem do TR1, a dane do TR8 trafiają z TR5

Różne podejścia do sposobu przesłania danych wpływają na wynik rozwiązania modelu matematycznego, zatem wskazane jest sprawdzenie wszystkich czterech wyżej wymienionych kombinacji w celu wyznaczenia najbardziej optymalnego.


Przykładowo transputer 2 może rozpocząć obliczenia po otrzymaniu paczki z TR1 oraz po wysłanu swojej do TR5, co możemy opisać wzorem (dla pierwszego opisanego przypadku):
T2 = S1x01 + C1 (a1 + a2 + a5 + a8) + S1 x1 + C1 (a2 + a5 + a8) + S2 x2 + C2(a5 + a8) + A a2
2.2. Podejście równoległe z przesłaniem jednej paczki do obliczenia.
W przeciwieństwie do przetwarzania sekwencyjnego, tu może wystąpić równocześnie przetwarzanie oraz przesyłanie na jednym transputerze. Oczywiście zanim transputer zacznie przetwarzanie, musi poczekać na odbiór swojej paczki, ale zaraz po otrzymaniu i wydzieleniu części dla sąsiada może równocześnie wykonywać oba zadania.
Przykładowo transputer 2 może rozpocząć obliczenia po otrzymaniu danych od transputera nr

1:

T2 = S1 x01+ C1 (a1 + a2 + a5 + a8) + S1 x1+ C1 (a2 + a5 + a8) + A a2


2.3. Podejście równoległe z dwukrotnym przesłaniem paczek do obliczenia.
To podejście charakteryzuje się tym, że każdy z transputerów (oczywiście po za inicjującym) dostaje dwie paczki danych do obliczenia. Tego typu rozwiązanie ma tę dobrą cechę, że transputer otrzymawszy pierwszą paczkę może nie tylko przesyłać dane dalej, ale również odbierać kolejną paczkę, co zwiększa współbieżność.
W tym wypadku trzeba zwrócić uwagę na to, że rozpoczęcie obliczeń danych z drugiej paczki, może się rozpocząc dopiero po skończeniu obliczeń danych z pierwszej paczki oraz po otrzymaniu drugiej paczki. Oba te logiczne fakty trzeba odnotować w modelu matematycznym tego problemu.
Przykładowo dla transputera nr 2:
T2 > T22 +A a22

T22 > S1 x011 + C1 (a11 + a21 + a51 + a81) + S1 x11+ C1 (a21 + a51 + a81) + A a21



T22 > S1 x011 + C1 (a11 + a21 + a51 + a81) + S2 x031+ C2 (a31 + a61 + a71) + S x012+ C1 (a12 + a22 + a52 + a82) + S1 x12 + C1 (a22 + a52 + a82)
Wszystkie modele wraz z wynikami w załączniku.
3. Opis wyników optymalizacji dla badanych modeli.
3.1. Podejście nr 1 (sekwencyjne)
Rozważono 4 modele komunikacji, opisane powyżej, oto wyniki optymalizacji dla V=1000, gdzie ai – ilosc danych przetwarzanych na i-tym transputerze.


wersja

T

a0

a1

a2

a3

a5

a6

a7

a8

V

1

6368.586

149

170

133

114

113

104

104

113

1000

2

6432.127

148

180

155

106

155

90

83

83

1000

3

6803.473

159

134

104

151

89

138

136

89

1000

4

6908.742

161

139

119

141

119

123

116

82

1000

Jak widać, najkorzystniejszy jest pierwszy model (najpierw przesyła dane łączem szybkim do T1, a do T8 dane trafiają z T5).


Posiadając te informacje, dla następnych podejść optymalizacji nie musimy porównywać 4 różnych możliwości komunikacji, wiemy że optymalna jest wersja pierwsza, dlatego na niej będziemy się opierać w kolejnych podejściach.
W wyniku optymalizacji widzimy, że najwięcej danych do przetwarzania dostał transputer nr 1. Dzieje się tak, ponieważ to on pierwszy zacznie wykonywać obliczenia (TR0 musi jeszcze przesłać dane do TR3, a że przesyła po łączu pionowym, to komunikacja będzie trwałą dłużej). Transputery 3,6,7 otrzymują mniej danych niż 2,5,8 ponieważ przesyłają dane przeważnie wolnymi łączami, a dodatkowo, TR0 wysyła dane w tę strone dopiero po wysłaniu do TR 2,5,8. Transputery przedostatni i ostatni po obu stronach mają taką samą ilość danych do przetworzenia, ponieważ równocześnie zaczną liczyć.

3.2. Podejście nr 2 (równoległe z przesłaniem jednej paczki do obliczenia.).

T

5391.754

a0

212

a1

167

a2

137

a3

119

a5

105

a6

89

a7

82

a8

89

V

1000

W tym podejściu najwięcej danych do przetwarzania ma TR 0. Jest to spowodowane tym , że równocześnie zaczyna przesyłanie danych do innych transputerów oraz liczyć swoje dane. Dane są przesyłane równocześnie z przetwarzaniem, więc kolejny, który zacznie przetwarzać jest TR1, następnie TR2, ponieważ przesyłanie odbywa się po szybkim łączu. Analogicznie do poprzedniego podpunktu, transputery 2,5,8 dostają więcej danych niż 3,6,7. Ostatnie w łańcuchach tranpustery (7,8) mają mniej danych do przetworzenia od przedostatnich (5,6), ponieważ zaczynają przetwarzać o przesłanie później od przedostatnich. Jak na dłoni widać również, że czas przetwarzania w tym podejściu jest krótszy niż w poprzednim podejściu.


3.3. Podejście nr 3 (równoległe z dwukrotnym przesłaniem paczek do obliczenia).

T

4312.335

a0

169

a11

53

a12

96

a21

55

a22

79

a31

54

a32

69

a51

54

a52

61

a61

53

a62

52

a71

52

a72

47

a81

56

a82

50

V

1000
Ten model jest zdecydowanie najszybszy. Nie ma tu tak dużych dysproporcji w ilości danych przetwarzanych na konkretnych transputerach jak poprzednio, ale podobnie, najwięcej danych otrzymuje TR0. Warto również zwrócić uwagę na to, że pierwsze paczki przesyłane do kolejnych transputerów są rozmiarowo bardzo do siebie zbliżone.


4. Opis aplikacji testowej.
Schemat połączeń transputerów został zaprezentowany wyżej. Schemat ten gwarantuje maksymalne wykorzystanie dostępnych łączy szybszych – poziomych.
Poniżej zaprezenotwany jest schemat procesów:

Procesy proci, odpowiadają za komunikacją między transputerami oraz za pomiary czasów, dlatego mają przydzielony priorytet wysoki. Natomiast procesy calci wykonują obliczenia i mają priorytet niski. Proces proc i przesyła calc i wskaźnik na tablicę danych, a po wykonaniu obliczeń zwraca obliczoną wartość przesyłając ją do procesu proc.
Procesy zostały przydzielone do transputerów w następujący sposób


TR0

proc1

TR1

proc2

TR2

proc4

TR3

proc3

TR5

proc6

TR6

proc5

TR7

proc7

TR8

proc8

5. Opis wyników obliczeń.


Kierunek

Czas

01

1145

03

2375

1

768

3

758

2

854

6

207

5

402




Nr

Rozmiar

Czas zakończenia

Czas obliczeń

0

212

5816

5816

1

167

5600

4455

3

119

5620

3245

2

137

5570

3657

6

89

5566

2433

5

105

5575

2808

7

82

5523

2183

8

89

5536

2367

Według modelu wszystkie procesy powinny zakończyć się w ciągu 5392, więc otrzymane wyniki nie różnią się bardzo od tych z modelu. Różnice mogą wynikać z błędów pomiarowych, możliwego przełączania kontekstu bądź zaokrągleń. Jednak różnice pomiędzy otrzymanymi wartościami nie są znaczne osiągają zaledwie kilka procent.



Podsumowanie

Tym co najlepiej zobrazuje przewagę równoległości nad sekwencyjnością będzie wykres przedstawiający czas potrzebny do wyliczenia 1000 elementów w zależności od zastosowanego podejścia.




Jak widzimy, wydajność architektury złożonej z kilku procesorów bije na głowę rozwiązanie jednoprocesorowe. Oczywiście wydajność ta będzie większa dla odpowiednio dużej liczby danych i dla rozsądnych kosztów przesłania danych.


©absta.pl 2016
wyślij wiadomość

    Strona główna