Systemy czasu rzeczywistego (QNX)
III rok informatyki studia MUZ

 rok akademicki 2006/2007 semestr zimow

Zadanie 3.

1. Treść

W procesie konstruowania równoległych (lub współbieżnych) aplikacji dla wielu algorytmów numerycznych (nawet typowych) jest zadanie komunikacji, tzw. zadanie "pełnej wymiany". Szczególnie ważnej jest przy tworzeniu aplikacji realizujących iteracyjne rozwiązywanie równań liniowych, programowania liniowego itp.
    Zadanie "pełnej wymiany" sprowadza się do konieczności utworzenia na pewnym etapie algorytmu w każdym węźle pełnej kopii wyników obliczeń - obliczeń wykonanych przez wszystkie wykorzystywane w systemie procesory (lub procesy). Przy czym węzeł rozumiemy jako węzeł systemu równoległego lub - w przypadku programowania współbieżnego - jako proces.
    Zadanie "pełnej wymiany" może w wielu przypadkach okazać się wąskim gardłem, i negatywnie wpływać na efektywność (rozumianą jako czas) realizacji całego algorytmu. Jest to szczególnie istotne w przypadku realizacji obliczeń w systemach klastrowych, w kórych to właśnie zadania komunikacyjne są bardzo czasochłonne. Przez odpowiednią organizację algorytmu realizującego omawiane zadanie można jednak znacznie obniżyć liczbę komunikatów koniecznych do przesłania.

Celem ćwiczenia jest zaprojektowanie, oprogramowanie i wszechstronne przetestowanie trzech typowych sposobów rozwiązania problemu "pełnej wymiany":
1. Komunikacja każdy-do-każdego.
2. Komunikacja typu master-slave.
3. Komunikacja pierścieniowa.

Zakładamy, że liczba procesorów (procesów) wykorzystywanych do obliczeń wynosi P, natomiast pełna ilość przetwarzanych przez te procesy danych wynosi n. Średnia ilość danych przetwarzanych przez każdy z procesorów (procesów) wynosi n/P. W zadaniu należy rozważyć wszystkie możliwe warianty rozdziału zadań: zarówno przypadek, kiedy n jest podzielne przez P i wszystkie procesory realizują tyle samo zadań (w szczególności gdy n=P), oraz przypadek, kiedy n nie jest podzielne przez P, i w takim przypadku cześć procesorów będzie wykonywała o jedno zadanie więcej.

1a. Komunikacja każdy do każdego.
Każdy z procesorów (procesów) przesyła wyliczone wyniki zadań do pozostałych procesów (procesorów) - czyli realizuje P-1 komunikatów, oraz odbiera po jednym komunikacie od każdego pozostałego procesora (procesu) - czyli również realizowane jest P-1 komunikatów.
    Jak łatwo policzyć, zadanie wymaga przesłania pomiędzy wszytkimi procesorami P(P-1) komunikatów (P procesów, każdy przesyła P-1 komunikatów). Zadanie to ma kwadratową złożoność obliczeniową i może bardzo długo obciążać system, szczególnie kiedy liczba procesorów będzie duża.
    Liczba wszystkich przesyłanych w systemie danych będzie wynosiła średnio P(P-1)(n/P), co wskazuje na konieczność (P-1)-krotnego przesyłania wszystkich danych.

1b. Komunikacja typu master-slave.
Każdy z procesorów (procesów) przesyła obliczone przez siebie wyniki obliczeń (wyniki z obliczania owych b danych, jakie przypadają na każdy proces) do jednego, wybranego w systemie procesora (procesu), nazywanego master. Co w sumie daje P-1 komunikatów do przesłania. następnie master odsyła do pozostałych procesorów (procesów) pełny zestaw danych. Każdy taki zestaw danych zawiera n lub n(n-1) danych (bo albo wszystko wysyłamy - i wtedy n danych, albo nie wysyłamy tych danych, które dany proces i tak posiada - czyli jego własnych - i wtedy mamy n-1 danych do przesłania). Owe dane są przesyłane w P-1 komunikatach.
    W sumie zadanie wymaga przesłania pomiędzy wszystkimi procesorami (procesami) (P-1) + (P-1) komunikatów, czyli 2(P-1), czyli znacznie mniej niż w omawianej uprzednio metodzie. Można zauważyć, że jest to zadanie komunikacyjne o złożoności liniowej. Liczba wszystkich danych będzie z kolei wynosiła średnio (P-1)(n/P) + (P-1)n, czyli n(P-1)( (P+1)/P), co z kolei nieznacznie bardziej (bo (P+1)P - krotnie) obciąża system w porównianiu z pierwszą metodą. Uwaga! Zwiększenie tego obciążenia malej wraz ze wzrostem P!

1c. Komunikacja pierścieniowa.
Zakładamy, że wszystkie procesory są połączone ze sobą tworząc wirtualną topologię typu pierścień:
...-1-2-3-4-...-(P-1)-P-1-2...
Każdy z procesorów (o numerze oznaczonym np. przez i, gdzie i=1,2,...,P) przesyła wyniki zadań, które obliczył (wyliczył z danych n/P) do procesora (procesu) następnego w łańcuchu - czyli takiego o numerze i+1. Jednocześnie otrzymuje analogiczny komunikat od procesora i-1. Dane otrzymane od poprzedzającego procesora (procesu) każdy z procesorów przekazuje do następnego procesora w łańcuchu.
    Taki cykl wymiany powtarza się P-1-krotnie. Po wykonaniu tych działań, każdy z procesorów będzie dysponował pełną kopią danych. Zadanie wymaga przesłania pomiędzy wszystkimi procesorami P(P-1) komunikatów, przy czym komunikaty te mogą być (przynajmniej w pewnym zakresie) wykonywane równolegle. Należy zbadać zagadnienie równoległego przesyłania komunikatów.
    Liczba wszystkich danych przesłanych w systemie będzie wynosiła średnio n(P-1), przy czym dane te mogą być przesyłane równolegle - przynajmniej w pewnym zakresie.


W ćwiczeniu należy przebadać i porównać wszystkie przedstawione algorytmy pełnej wymiany dla algorytmu obliczeniowego wybranego przez prowadzącego zajęcia. W obliczeniach należy uwzględnić cztery procesory, oraz różne ilości przesyłanych danych n (rozumiane w bardzo szerokim zakresie). Decydującym kryterium oceny badanych rozwiązań jest zmierzony czas realizacji, dlatego bardzo istotne są:
- odpowiedni sposób pomiaru,
- odpowiednia synchronizacja czasu realizacji.

2. Zasady

Zadania wykonujecie Państwo w grupach 4-o osobowych.

3. Materiały pomocnicze (przykładowe programy)
Materiały z programowania w QNX-ie dostępne są na poprzednich stronach - przesyłanie komunikatów.
  

(wyk. A.Zatwarnicka)

prof. J. Sadecki