plik

8.10.2013

QQS

PRiR

Wykład 1

Kontakt:



plazek@pk.edu.pl



WFMiI, Instytut Teleinformatyki, pokój nr 103 (Huston)

Zasady zaliczenia:



Ocena



Egzamin (50%)



Laboratoria (25%)



Projekt (25%)



aby przystąpić do egzaminu, trzeba zaliczyć:

- laboratoria
- projekt



egzamin będzie mieć formę pytanie-odpowiedź



Laboratoria

- Będziemy programować w 3 środowiskach: OpenMP, MPI, CUDA

W sali 112 będziemy oprogramowywać karty graficzne; każda architektura karty graficznej ma
określone współczynniki mówiące o tym, co na takiej karcie możemy zrobić – konieczność
konfiguracji takiej karty przed użyciem

Plan wykładu:



Zagadnienia podstawowe



Środowiska sprzętowe



Narzędzia oprogramowania



Metody obliczeniowe

Literatura:



Praca zbiorowa pod red. A. Karbowskiego i E. Niewiadomskiej-Szynkiewicz, „ Programowanie
równoległe i rozproszone”, Oficyna Wydawnicza PW, 2009.



V.Kumar, A.Grama, A.Gupta, G.Karypis, „Introduction to parallel computing”, Addison-Wesley,
2003



I.Foster, „Designing and building parallel programs”



A.Tanenbaum „Rozproszone systemy operacyjne”, PWN, 1997



Colouris G., Dollimore J. i Kindberg T, „Systemy rozproszone. Podstawy i projektowanie”, WNT,
1998.

Uzyskanie sensownych wyników umożliwia nieobciążona maszyna – inaczej mamy zafałszowane.

Taksonomia Flynna



Klasyfikacja architektur komputerowych



Opiera się na liczbie przetwarzanych strumieni danych i rozkazów



4 grupy: SISD, SIMD, MISD i MIMD

Postęp technologiczny



Lata 1945-85 erą nowoczesnych komputerów;

- duże rozmiary i wysoka cena
- działały niezależnie – brak sposobów połączenia



Od połowy lat 80-tych:
- Postęp w technologii komputerowej

+ opracowanie mikroprocesorów o dużej mocy obliczeniowej (taniały)
+ wynalezienie szybkich sieci komputerowych

o sieci LAN (ang. Local Area Network)
o sieci WAN (ang. Wide Area Network)

- Postęp w dziedzinie oprogramowania
- Zapotrzebowanie na rozwiązywanie dużych zadań obliczeniowych

Wraz z rozpowszechnieniem się sieci protokół TCP/IP stał się darmowy; wzrastało zapotrzebowanie
na moc obliczeniową – np. liczenie współczynników macierzy zawierającej współczynniki fizyczne

Definicja systemu rozproszonego:



Są różne definicje



Nas będzie interesować definicja Tanenbauma, która mówi, że:



Aspekty:

- Sprzęt – maszyny są autonomiczne
- Oprogramowanie – wrażenie pojedynczego systemu

Pojawia się pytanie – czy komputer stworzony z wielu procesorów (tzw. „wieloprocesor”) jest
maszyną autonomiczną – według Tanenbauma tworzą się tak systemy rozproszone (procesory,
pamięć rozproszona w kilku modułach); zakładamy, że system wieloprocesorowy jest rozproszony

Zalety systemów rozproszonych
+  Ekonomia – lepszy współczynnik cena/wydajność, dzielenie zasobów
+  Szybkość – większa moc obliczeniowa
+  Możliwość rozwiązywania dużych zagadnień
+  Niezawodność
+  Stopniowe rozszerzanie

Program rozproszony kojarzy nam się z przyspieszeniem obliczeń, aczkolwiek bardziej prawidłowym
pojęciem będzie tutaj DEKOMPOZYCJA ZADANIA – czyli podział zadania na podzadania (zadanie,
które przykładowo nie mogło się zmieścić w pamięci teraz może, bo do danej kostki dociera tylko jego
część) – umożliwia zatem rozwiązanie zadania nie-do-rozwiązania na pojedynczej maszynie. Tak
naprawdę nie jest ważne, czy szybko obliczymy tego typu zadanie, ale liczy się końcowy wynik.

Niezawodność takiego systemu wprowadzona jest poprzez redundancję (powielania); stopniowe
rozszerzanie systemu wiąże się z jego rozbudową

System rozproszony - układ niezależnych komputerów, sprawiający wrażenie bycia pojedynczym
komputerem.

Wady systemów rozproszonych
-  Oprogramowanie
-  Sieć
-  Bezpieczeństwo

Oprogramowanie jest stale rozwijane, aplikacje najczęściej o charakterze sieciowym

Z siecią związane jest „wąskie gardło” – przepustowość; problem polega na tym, że nieraz komputery
mają większą moc od sieci, ale ta sieć je spowalnia; pewna analogia z procesorami – niby mogą liczyć
więcej, ale spowalnia je magistrala.

Dane przesyłane są w sposób niebezpieczny

GRID – system do obliczeń, sprawia wrażenie jednej całości, a tak naprawdę stworzony jest z
połączonych komputerów. W momencie, kiedy uruchamiamy jakąś aplikację na nim, to on decyduje,
gdzie zostanie ona uruchomiona; userowi to obojętne, bo widzi cały system jako 1 całość (tzw.
„przezroczystość”); ważne są kwestie bezpieczeństwa (w każdym kraju to trochę inaczej wygląda,
stąd nieraz są problemy ze stworzeniem międzynarodowych systemów).

Własności systemów rozproszonych



dzielenie zasobów



otwartość



współbieżność



skalowalność



tolerowanie uszkodzeń



przezroczystość

Dzielenie zasobów



urządzenia sprzętowe

- (drukarki, specjalizowane komputery, szybkie pamięci, itp.)



dzielenie danych
-  zespoły projektowe
-  zastosowania komercyjne (system kupna biletów samolotowych)
-  zdalne nauczanie (np. e-learning)

Otwartość



Możliwość dodawania nowych usług dzielenia zasobów bez naruszania lub podwajania usług
istniejących.
-  na poziomie sprzętu (dodawanie urządzeń zewnętrznych)
-  na poziomie oprogramowania (wprowadzanie nowych usług, umożliwiających programom

użytkowym dzielenie zasobów)

dodanie nowej funkcji nie jest kosztowne – w końcu głównym elementem systemów operacyjnych jest
OTWARTOŚĆ – reakcja systemu na zmiany

Współbieżność



Jeśli w 1 komputerze istnieje wiele procesów, to mówimy, że są one wykonywane współbieżnie
(równolegle).



Współbieżny dostęp do wspólnie wykorzystywanych zasobów i ich aktualizacje muszą być
synchronizowane.

Procesy współbieżne dzielą zasób między sobą – np. gdy mamy 1 procesor i 5 procesów, to one dzielą
go między sobą; w procesach równoległych mielibyśmy 3 procesy i 3 procesory; inna sytuacja – mamy
3 procesy i 1 procesor- i wtedy też możemy mieć system równoległy, pod warunkiem, że każdy z
procesów będzie wykorzystywać inny zasób, np. 1 czyta, 2-gi pisze itd.; w równoległości każdy proces
korzysta z jakichś zasobów

Najprostszym mechanizmem umożliwiającym współpracę jest semafor – pewien mechanizm
występujący tam, gdzie między procesami jest walka o zasób

Skalowalność



Powiększenie skali systemu i oprogramowania użytkowego nie powinno pociągać za sobą
konieczności wykonywania w nich zmian.



Musi to być system otwarty

Tolerowanie uszkodzeń



redundancja sprzętowa (użycie nadmiarowych składowych)



odtwarzanie programowe (zaprojektowanie programów do usuwania skutków uszkodzeń)

W 1-wszym przypadku, gdy 1 procesor się zepsuje, to Iny przejmuje jego robotę (ten drugi mógł
wcześniej równolegle z nim pracować, lub uruchomić się tylko w momencie awarii); przy
programowym odtwarzaniu, SO go odczytuje i naprawia, co przejawia się spowolnieniem pracy SO

Przezroczystość



Ukrywanie przed użytkownikiem rozproszenia zasobów



Rodzaje przezroczystości w systemie rozproszonym:

- Biuro Międzynarodowych Standardów (ang. ISO - International Standards Organization)

wyróżnia 8 form przezroczystości:

+  Dostępu
+  Położenia
+  Współbieżności
+  Zwielokrotniania
+  Awarii
+  Wędrówki
+  Wydajności
+  skalowania

Przezroczystość dostępu



oznacza ujednolicenie metod dostępu do lokalnych i odległych danych i ukrywanie różnic w ich
reprezentacji



w systemie rozproszonym będą to dane ukryte; nas nie interesuje, czy odwołujemy się do
zmiennej lokalnej, czy nie

Przezroczystość położenia



umożliwia dostęp do zasobu bez znajomości jego lokalizacji (przez nazwę)

Przezroczystość współbieżności



możliwość współbieżnego przetwarzania nie powodująca powstawania niespójności w systemie

[E] Przezroczystość zwielokrotniania



pozwala na użycie wielu kopii zasobu w celu zwiększenia niezawodności i wydajności systemu
bez wiedzy użytkowników



np. mamy jakąś rozproszoną bazę, userzy z niej korzystają; w pewnym momencie odwołania
zaczynają być tak duże, że baza „sama” decyduje, do której ze składowych baz dać ruch –
zdolność zwielokrotniania (i usuwania ewentualnego nadmiaru baz)

Przezroczystość awarii



ukrywanie uszkodzeń poszczególnych komponentów systemu rozproszonego

Przezroczystość wędrówki



umożliwia przenoszenie zasobów pomiędzy serwerami bez zmiany sposobu odwoływania się do
nich

Przezroczystość wydajności



umożliwia rekonfigurowania systemu w celu poprawy działania przy zmianie obciążenia

Przezroczystość skalowania



umożliwia rozszerzenie skali systemu bez zmiany jego struktury lub algorytmów użytkowych

Zastosowanie systemów rozproszonych



Zastosowania komercyjne (banki, linie lotnicze, supermarkety)



Zastosowania sieci rozległych (Internet: poczta elektroniczna, przeglądarki)



Dostęp do informacji multimedialnej i zastosowania konferencyjne (komputerowo wspomagane
nauczanie, wideokonferencje)



Obliczenia wielkiej skali



Modelowanie zmian klimatu



Badanie własności związków chemicznych



Badania w medycynie i genetyce



Zadania biologii molekularnej



Modelowanie przepływów turbulentnych



Obliczenia w fizyce, astronomii

15.10.2013

QQS

PRiR

Wykład 2

Architektura maszyn równoległych

Dzisiejszy wykład będzie dotyczył klasyfikacji systemów komputerowych, a w szczególności tych
równoległych. Część wiadomości powtórzy się z materiałem z „architektury komputerów” z I stopnia.

Klasyfikacja systemów komputerowych
Taksonomia Flynna (1972, najczęstsza)

Podstawą tej klasyfikacji jest:



liczba strumieni instrukcji (instruction stream)



liczba strumieni danych (data stream) (na 1 grupie danych lub kilku)

Liczba strumieni



pojedyncze (single)



wielokrotne (multiple)

Taksonomia Flynna:



SISD (single instruction stream - single data stream)



SIMD (single instruction stream - multiple data stream)



MISD (multiple instruction stream - single data stream)



MIMD (multiple instruction stream - multiple data stream)

SISD



klasyczne komputery 1-procesorowe, w których rozkazy wykonywane są w sposób sekwencyjny
(jeden po drugim)



wydajność podaje się w:

- MIPS (milions of instructions per second)

- MHz (Megahertz; częstotliwość taktowania zegara)

- w tych maszynach ewolucja

Ewolucja komputerów sekwencyjnych
Początkowo pamięć była powiązana w pojedynczy, ciągły fizycznie i adresowo moduł pamięci (jej
cena była bardzo wysoka i mało co dało się tam zapisać):

Aplikacje uruchamiane na komputerze rozbijały się zawsze o pamięć (przy każdym algorytmie trzeba
było robić analizę złożoności pamięciowej).

Z czasem jednak wymyślono, że rozbijając pamięć jednolitą adresowo na moduły uzyska się większe
przyspieszenie – powstaje procesor, który kontaktuje się z pamięcią rozbitą na kilka modułów
(jednoczesne odwołanie do kilku modułów pamięci):

Procesor i pamięć współpracują – procesor pobiera elementy z pamięci operacyjnej do swoich
rejestrów, wymaga to jednak ciągłego przepływu informacji (ograniczenie systemu). Z czasem jednak
wymyślono pamięć podręczną (cache), przechowującą ostatnie elementy kodu i umiejscowioną w
pobliżu procesora (pobieranie słowa stało się szybsze niż z PAO):

Z czasem cache tez urósł – efektem stało się przyspieszenie obliczeń.

Dalszą modyfikacją było wyspecjalizowanie procesorów (na rysunku widać kilka procesorów):

Kiedyś do procesorów dodawano koprocesory - procesory zoptymalizowane do obliczeń
zmiennoprzecinkowych; takie wyspecjalizowanie się koprocesora wiązało się z tym, iż arytmetyka na
liczbach zmiennopozycyjnych jest bardzo złożona (postać wykładnicza, mantysa, cecha itd.) i te
operacje są wielopoziomowe (trzeba wiele rozkazów wykonać, żeby rozwiązać działanie); teraz
procesory mają część odpowiedzialną za operacje zmiennoprzecinkowe i część za inne – pozwoliło to
osiągnąć dodatkowe przyspieszenie.
Obecnie zamiast maszyn 1-perocesorowych, mamy wielordzeniowe.

SIMD



możliwość wykonywania pojedynczej instrukcji na wielu danych



wszystkie procesory wykonują tą samą instrukcję



łatwość w programowaniu (program nie odbiega od klasycznego sekwencyjnego, jedynie
zrównolegleniu podlegają fragmenty kodu; zrównoleglenie automatycznie przez kompilator)



wady:

- przeznaczenie specjalistyczne (ośrodki naukowe, na zamówienie)
- nie do wszystkich algorytmów



miarą wydajności tych systemów jest MFLOPS (millions of floating point operations per second –
miliony operacji zmiennoprzecinkowych na sekundę); umożliwia liczenie mocy maszyny



najczęściej - komputery i maszyny wektorowe - dla obliczeń na macierzach (w kilku taktach
wykonujemy 1 instrukcje; dodawanie 2 wektorów, inkrementacja na każdym elemencie - ta sama
operacja)

W SIMD mamy procesory połączone siecią:

Procesory te korzystają z pamięci - wykonują tą samą instrukcję, ale na innych danych.

w SIMD możemy wyróżnić grupę maszyn, rozumianych trochę inaczej, niż maszyny macierzowe:



parallel SIMD model:

- w tej architekturze dodawaniem każdej dwójki wektorów zajmuje się 1 procesor:

(na rysunku są 4 procesory, każdy dodaje 2 elementy wektora)

- przykłady: Connection Machine CM-2, Maspar MP-1, MP-2



vector SIMD model:

- zrównoleglenie operacji zmiennoprzecinkowych

- żeby np. dodać 2 liczby zmiennoprzecinkowe, trzeba przeprowadzać przesuwanie po

przecinku, znormalizować, dodać mantysę i ponownie znormalizować wynik; pojawia się
pytanie - czy każda para liczb musi być liczona w ten sam sposób? W vector SIMD, jak w 1-
dnej parze liczb zrównoleglę wykładnik, to w 2 grupie będzie przesuniecie przecinka itd. –
umożliwia to ciągłe wykorzystywanie pracy procesorów;

- dana operacja rozbita na jeszcze drobniejsze elementy (rozkazy), które wykonujemy

równolegle)

- przykłady: Cray 1, NEC SX-2, Fujitsu VP, Hitachi S820

MISD



maszyny te nie są spotykane („czystych” MISD nie ma)



w niektórych książkach wymienia się architektury MISD, jednakże Tanenbaum uważa takie
podejście za naciągane (MISD podawane tylko, żeby była ciągłość w klasyfikacji)



wiele instrukcji pracuje na tych samych danych - nic z tego nie wynika

MIMD



mówi o maszynach równoległych (z punktu widzenia PRiR najważniejsza)



każdy procesor wykonuje swój strumień instrukcji na własnym strumieniu danych



wielokrotny strumień instrukcji i danych



najobszerniejsza klasa współczesnych komputerów

Wady:
-  trudny do programowania (trudniejsze niż maszyny macierzowe)
-  ciężko zapewnić równomierne obciążenie procesorów (loadbalancing - zrównoważenie)

W komputerach macierzowych jednostki przetwarzające były bardziej prymitywne, natomiast w
MIMD jednostki przetwarzające są klasy pojedynczego procesora. Jednostki te współpracują ze sobą
poprzez sieć połączeń:

typowy model:

(mamy 4 procesory, każdy realizuje jakiś fragment kodu)

Przykłady:
- IBM klaster RS6000, Cray2, IBM SP1, IBM SP2

Architektury pamięci

Flynn na tym zakończył klasyfikację systemów komputerowych, od tego czasu wiele się jednak
zmieniło - MIMD tak się rozrosło, że pojawiła się potrzeba jego ponownej klasyfikacji - dokonali tego
inni (nie Flynn).

Klasyfikacja ta:



opiera się na architekturze pamięci (pamięć operacyjna, pamięć RAM - klucz do dodatkowej
klasyfikacji maszyn).



to, jak postrzegamy pamięć wiąże się ze sposobem odwołania procesora do niej



sposób komunikowania się procesorów zależy od architektury pamięci -> narzucanie pisania kodu
równoległego

Organizacja przestrzeni adresowej



przestrzeń adresowa wygląda tak, ze pamięć składa sie z komórek pamięci (odpowiednik adresu);
jeśli mamy wiele procesorów, to możemy mieć podział ze względu na rodzaj adresowania
przestrzeni pamięci – pamięć wspólną lub rozproszoną.

Pamięć wspólna

Pamięć rozproszona



inne nazwy: pamięć globalna/shared memory (SM)



procesory mają dostęp do 1 pamięci



jednolity sposób adresowania dla wszystkich procesorów (przy
odwołaniu się do komórki o danym adresie jest w
rzeczywistości odwołaniem do tej samej komórki)



komunikacja poprzez wstawianie i pobieranie wartości z danej
komórki (np. zmiana wartości zmiennej)



inne nazwy: lokalna/distributed memory (DM)



pamięć rozproszona (adresowo, nie fizycznie) - nie mamy
jednolitej pamięci adresowej, tylko rozproszoną



każdy procesor dysponuje fragmentem pamięci (każdy
fragment jest adresowany osobno); jeżeli wszystkie
procesory odwołają się do komórki o adresie 100, to każdy
odwoła się do innych danych (lokalna przestrzeń
adresowa)



wiele procesorów pracuje niezależnie, dzieląc tą samą pamięć



W danej chwili tylko jeden procesor może korzystać z pamięci
(konieczne są mechanizmy synchronizacji; mechanizmy te
powinny wystąpić zawsze, gdy w maszynie występuje jakiś
pojedynczy zasób, który może być wykorzystywany przez
wiele procesów; procesory nie mogą jednocześnie coś na
pamięci dzielonej zapisywać, inkrementować etc.)



Wiele procesorów pracuje niezależnie i każdy korzysta ze
swojej własnej (lokalnej) pamięci



Dane są dzielone poprzez przesyłanie komunikatów siecią
(brak mechanizmu pamięci wspólnej do komunikacji, tylko
wysyłanie przez sieć; zagrożenie –
uszkadzanie/zagubienie/przechwycenie pakietów itd.)

+  Prosty sposób efektywnego wykorzystania maszyny
+  Szybkie dzielenie danych między procesami
+  Proste programowanie (szybka wymiana danych)

+ Pamięć jest skalowalna przez liczbę procesorów

- Przy dużej liczbie procesorów możliwe opóźnienia (mamy

więcej odwołań i czekamy dłużej)

- Użytkownik jest odpowiedzialny za przesyłanie i

odbieranie informacji (musi dokonać jawnego przesłania
informacji; potrzebny jest bufor do wysłania/odebrania)

- W celu zredukowania opóźnień dane muszą wcześniej

zostać rozesłane do poszczególnych pamięci lokalnych

Ponieważ pamięć wspólna umożliwia łatwe programowanie, natomiast pamięć rozproszona - dużą
skalowalność, dalszy rozwój architektur poszedł w takim kierunku, aby z pamięci rozproszonej zrobić
pamięć wspólną – w ten sposób powstała WIRTUALNA PAMIĘĆ WSPÓLNA.

Wirtualna pamięć wspólna



Pamięć ta wykorzystuje zalety pamięci wspólnej i rozproszonej, „pamięć wspólna z rozproszonej”



używa się jej w klastrach;



mamy maszyny rozdzielne, które mają pamięć lokalną, ale budujemy programową nakładkę,
która postrzega pamięci lokalne jako 1 pamięć adresową - przeadresowane; np. mając 4 pamięci
lokalne, adresowane od 0 do 200 po użyciu nakładki nowe numerowanie przyjmie postać od 0 do
800 (mimo, że fizycznie leży w rożnych miejscach)

Klasyfikacja komputerów MIMD

Klasyfikacja ta wynika z różnorodności przestrzeni adresowych i pamięci RAM. W jej ramach istnieje
podział na WIELOPROCESORY i MULTIKOMPUTERY

Wieloprocesory

(ang. multiprocessors)

Multikomputery

(ang. multicomputers)



komputery wyposażone we wspólną pamięć (shared
memory; wiele procesorów dzieli tą samą przestrzeń
adresową)



jedna wirtualna przestrzeń adresowa współdzielona
przez wszystkie procesory (fizycznie te pamięci są różne)



procesory komunikują się ze sobą poprzez pamięć



Komputery bez pamięci wspólnej



Łatwo się buduje



Skalowalne rozwiązanie



Trudne programowanie (komunikacja poprzez
przesyłanie komunikatów, problem gubionych
komunikatów, buforowania, zakładania blokad itd.)



Np. Cray Y-MP, Convex C-2, Cray C-90



Np. nCUBE Hypercube, Intel Hypercube, TMC CM-5, IBM
SP1, SP2; Intel Paragon

Dość ciekawym przykładem klasyfikacji komputerów MIMD jest klaster.

Klaster:



Zaliczany często do multikomputerów (klaster tworzą komputery poukrywane w szufladach;
niezależne stacje robocze)



Ponieważ szuflady tworzą 1 duże pudło, może to sugerować wieloprocesor



Procesory leżą blisko siebie, ale pamięć ma architekturę pamięci lokalnej



Tutaj zaczęto stosować wirtualną pamięć wspólną



Różnice między klastrem, a zespołem połączonych stacji roboczych:

- Klastry wykorzystuje się do rozwiązania 1 zadania, często kolejki do niego (osoba, która z

niego korzysta ma wyłączność)

- Przy połączonych stacjach roboczych w jednej chwili korzysta z nich dużo ludzi (SO sam

wybiera, na ilu komputerach uruchomić zadanie – kieruje się optymalizacją)



Zespół stacji roboczych – podobnie jak klaster - tworzą środowisko pamięci wirtualnej;

Sieci połączeń



W komputerze mamy sieć połączeń (kontaktowanie się procesora z pamięcią), która powoduje
największe obciążenie w systemie komputerowym. Wieloprocesory i multikomputery można
podzielić na podstawie architektury tej sieci, na szynowe i przełączane.

Rodzaje:



Szynowa (ang. bus)



Przełączana (ang. switch)

Typowe architektury wieloprocesorów:

(P – procesor, M – moduł pamięci)

Rozwój biegł od architektury (a) do (c).

Architektura (a)

Architektura (b):

Architektura (c):



Architektura ta składała się z jednostek
przetwarzających (procesory i moduły
pamięci)



Duża liczba procesorów wymagała dużej
pamięci; pamięć rozproszona i
podzielona na wiele modułów



Procesory sięgają do pamięci poprzez
sieć połączeń; muszą znać numer
komórki, do której chcą się odnieść



Złożona sieć połączeń (każde odwołanie
do procesora do pamięci uaktywnia sieć
połączeń; sieć połączeń – wąskie gardło)



Każdy procesor wzbogacony w
dodatkową pamięć cache (tam
przechowywane były instrukcje
zdalnego programu)



Gdy procesor potrzebował
następnej strony pamięci –
pobierał ją z modułu do cache
(cache nie zawsze starczało);
obciążenie magistrali



Każdy procesor posiada swój
moduł pamięci oraz cache



Program ląduje do cache, a
jak się nie zmieści to do
lokalnego modułu pamięci
(na ogół nie wychodzi poza tą
pamięć, tylko czasami
pobiera z innego fragmentu)



Odciążenie magistrali

[E] architektury z pamięcią wspólna

UMA

(ang. Uniform Memory Access)

NUMA

(ang. NonUniform Memory Access)



identyczny czas dostępu do
każdego słowa maszynowego



czas dostępu do słowa w pamięci lokalnej jest krótszy niż do słowa w innych
pamięciach (nierównomierny czas dostępu do słowa)



najczęstszy



Częstym błędem przy omawianiu nierównomiernego czasu dostępu do słowa w NUMA jest
wskazanie, że czas ten jest szybszy przy cache niż w module pamięci operacyjnej (tak jest w każdej
architekturze); rozwiązaniem jest architektura (c) i że w NUMA procesor ma mniejszy czas dostępu
do swojej lokalnej pamięci, niż do innej pamięci (np. innego procesora).

Czas dostępu zależy od fizycznego położenia pamięci (pamięć zdekomponowana - do jednych
procesor odwołuje się szybciej, a do innych wolniej)

W kartach graficznych mamy małe procesory – w nie dołączamy lokalną; inny czas dostępu do
pamięci lokalnej i bloku.

pamięć podręczna



przechowuje ostatnio używane słowa (zakładając, że mamy sekwencyjny program składający się z
listy instrukcji, to duża szansa, że program wyląduje w cache)



przy odpowiednio dużej pamięci podręcznej wysoki współczynnik trafienia (współczynnik ten
określa, ile razy potrzebna strona znalazła się w pamięci; wyrażamy za pomocą
prawdopodobieństwa – jeśli wyniesie np. 90% to znaczy, że trafiliśmy w cache; procesor sięga
najpierw do cache, ale jak tam nie ma to z PAO i ładuje dane do cache i do siebie)



problem spójności pamięci (cache coherence)

- w systemie mamy wiele procesorów, każdy z nich ma swój cache (fragment pamięci wspólnej,

ale może też to być ta sama PAO); dopóki procesor tylko czyta z cache to problemu nie ma –
gorzej, jak próbujemy coś zapisać (np. jak 1 procesor zmienia zmienną we fragmencie pamięci,
a w 99 innych cache’ach jest inna wartość – niespójność pamięci, trzeba z tym walczyć np. za
pomocą algorytmów)

- rodzaje:

o pamięć przepisywalna
o pamięć podglądająca

Pamięć przepisywalna

Pamięć podglądająca



algorytm



działa tak, że jak proces zmienia coś w
cache, to przepisuje się tą poprawkę do
wszystkich kopii tego fragmentu



SO musi zapamiętać miejsce
przechowywania adresu pamięci i
informuje procesory o tym



Przy dużej liczbie procesorów dane
musiałyby być uaktualniane przez
maszyny; w rzeczywistości mamy ileś tam
poprawek i co jakiś czas robimy
aktualizację



Przy aktualizacji jakiegoś cache’a SO zapamiętuje dany fragment
pamięci jako stronę brudną; inne procesory przy odwołaniu się do
niej dostają zwrotną informację, że jest brudna i dopiero wtedy
następuje aktualizacja



Aktualizacja następuje tylko, gdy chcemy odczytać aktualną wartość



Nazwa bierze się stąd, że każdy cache podgląda, czy strona, którą
ma, nie jest brudna (wymaga to rozbudowanego systemu
wieloprocesorowych SO – system musi scalić, dbać o spójność
pamięci, kontrolować, w jakim cache umieszczone są konkretne
fragmenty PAO - za pomocą tysięcy tablic - i robić aktualizacje)



CC-Numa – maszyny, które uaktualniają powyższe tablice

CC-NUMA
(Cache Conherency NUMA)

COMA
(Cache Only Memory Access)



komputery NUMA z uzgadnianiem zawartości pamięci
podręcznej wszystkich lub części procesorów



architektura wieloprocesorowa o mechanizmie
uzgadniania cache'a;



różny czas dostępu do pamięci



każdy procesor ma własną pamięć podręczną, nie ma
pamięci lokalnej (cache bardzo rozbudowany)



nie podbiły świata

Wielkość pamięci podręcznej, a spójność
- pamięć podręczna ma określoną wielkość (jest mała, gdyż inaczej byłyby problemy ze spójnością

pamięci – większa kolizja)

pamięć spójna, a wspólna

wieloprocesory szynowe
Początkowe architektury na szynach robione były tak, że nie było cache – mieliśmy same procesory.
Taki układ powodował jednak, że tworzyło się wąskie gardło do szyny (zapychanie danych).

Z czasem do każdego procesora dodano pamięć cache, odciążając szynę:

Obecnie stosuje się wieloprocesowy na switchach:

Schemat (a)

Schemat (b)



procesor odwołuje się do konkretnego modułu tak, że
zamyka się konkretne przełączniki



wady:

- drogie rozwiązanie
- dla 4 procesorów i 4 modułów pamięci potrzeba aż 16

przełączników



układ zrobiony na 4 przełącznikach (architektura
butterfly)

Wieloprocesory - podsumowanie



w systemie z pojedynczą szyną, szyna jest potencjalnym wąskim gardłem (nie można dołączać
dużej liczby procesorów)



w systemie z przełącznikami można dodawać wiele procesorów, ale system jest złożony, wolny i
kosztowny,



zaleta - programowanie jest proste: dostęp do wspólnej pamięci (ale wymagane programowe
mechanizmy synchronizacji procesów dostania się do wspólnej pamięci)

Multikomputery



Distributed-memory architecture – poprzez różną pamięć



Message-passing architecture – przesyłanie komunikatów

Typowa architektura rozproszona



Procesory są ze sobą połączone poprzez sieć połączeń



Każdy procesor ma swoją własną pamięć



Procesory mogą się ze sobą komunikować poprzez przesyłanie komunikatów

multikomputer szynowy



Procesory z własną pamięcią lokalną



Sieć = wąskie gardło (ale mniejsza niż w wieloprocesorze, bo mniejsza komunikacja)



Najpopularniejsze topologie:

- Krata
- hiperkostka (1024 procesorów, a nawet 16384 procesorów)

krata

hiperkostka

(kwadraty – procesory,

między nimi sieci połączeń)

(wierzchołki – procesory, po bokach połączenia)

Układ 2 cube’ów



w tej architekturze
stworzono całe biblioteki
oprogramowania
(umożliwiają tworzenie
oprogramowania za
pomocą loadbalancingu)



optymalne, ale
specyficzne połączenia



najbardziej popularna



hipercube – układ kostek



każdy procesor ma charakterystyczny numer



najczęstszy układ 2 cubów, ważny jest układ połączeń (górny z górnym dolny z dolnym
– jak na rysunku); każdy taki układ składa się z 16 procesorów; mamy szyny główne, do
których dołączone są chipy (tworzy to multikomputer; przy 10 chipach mamy 160
procesorów, wszystkie specyficznie połączone); każdy z wierzchołków ma pamięć
lokalną;



optymalne oprogramowanie wymaga, aby każdy procesor musiał komunikować się z
sąsiadem (wymaga to olbrzymich bibliotek numerycznych – wywołanie danego
programu, napisane pod daną architekturę)

wniosek - programowanie równolegle zależy od architektury komputerów.

22.10.2013

QQS

PRiR

Wykład 3

Inna klasyfikacja systemów równoległych MIMD i modeli

programowania

tu pojawia się pojęcie węzła.

Węzeł



system składający się z jednego lub więcej procesorów mających dostęp do pamięci lokalnej.
(wspólnej; elementy przetwarzające, pogrupowane w zbiory procesorów)



Węzły mogą być połączone siecią tworząc klastry komputerów i porozumiewać się między sobą
poprzez przesyłanie komunikatów (w praktyce na wieloprocesorze mamy pamięć wspólną,
dzieloną na poszczególne węzły)



Tworzy się je, żeby systemy były otwarte – gotowe do skalowania

Architektury MIMD



w tej klasyfikacji podzielone są one według 2 kryteriów : na ilość węzłów i liczbę procesorów w
węźle



podział na 4 grupy systemów:

SNSP



komputer o pojedynczym węźle z pojedynczym procesorem (przetwarzającym kod sekwencyjnie)



typowe rozróżnienia między pamięci lokalne

SNMP



1 węzeł wieloprocesorowy (maszyny wielordzeniowe - 1 węzeł i kilka rdzeni, wszystkie pracujące na 1 pamięci
lokalnej - shared memory; zwykła maszyna z wieloma procesorami);



Procesory są ściśle połączone



dostęp do jednolicie adresowanej pamięci RAM

MNSP



wiele węzłów z pojedynczymi procesorami



jeśli każdy węzeł oznacza pamięć lokalną, to pod te architektury wrzucamy zespół stacji roboczych (osobne
komputery posiadające niezależne pamięci połączone siecią; oparte o distributed memory (pamięć
rozproszona, przesyłanie komunikatów)



luźne powiązanie procesorów



CPU tworzą oddzielne węzły, każdy węzeł ma pamięć lokalną (architektura węzłowa)



np. sala laboratoryjna - dajemy oprogramowanie żeby całość postrzegało jako maszynę wirtualną (każdy
procesor ma oddzielnie adresowaną pamięć lokalną)

MNMP



kombinacja pamięci wspólnej w obrębie węzła i między węzłami



kombinacja luźno połączonych pamięci rozproszonych



najdroższe, "superkomputery"



architektura wielowęzłowa, każdy węzeł ma wspólną pamięć - dla grupy procesorów



zaleta: łatwe rozbudowanie systemu o dodatkowe procesory z pamięcią wspólną



Powyższe pamięci są lokalne, ale każda z nich adresowana jest oddzielnie



Węzły komunikują się ze sobą poprzez przesyłanie komunikatów



Jeśli te pamięci są wspólne dla poszczególnych węzłów, ale równocześnie tworzą 1 pamięć dla
całej maszyny (nie ma komórki o powtarzalnym adresie), wówczas węzły mogą komunikować się
poprzez pamięć (sieć; wszystko zależy od adresowania pamięci)

Sposoby programowania

Do tej części wykładu omówiliśmy sam hardware; teraz na niego nakładamy środowisko
programowania równoległego

SNSP



dla węzłów z pojedynczym procesorem mamy wątki, gdzie – w zależności od budowy programu - mogą
pracować współbieżnie, multitasking; jednakże wtedy nie ma równoległości

SNMP



ładnie pracuje pamięć dzielona



dobre dla OpenMP (środowiska zrównoleglenia elementów potrzebujących dzielenia zmiennych)



w OpenMP można zrównoleglić pętle (siła tego rodzaju programowania, ale też ograniczenie, bo całość musi
działać w obrębie pamięci wspólnej), ale też elementy kodu źródłowego (dyrektywy, każdy wykona się na
innym procesorze); można mieć wiele multitasków



dataparallelizm – zrównoleglenie na poziomie danych; wykonujemy to samo, ale na różnych danych



możliwość przyporządkowania różnych instrukcji do różnych procesorów



musi być 1 proces, który się zrównolegli (nie kilka)

MNSP



wiele węzłów 1 procesorowych (np. zespół stacji roboczych)



równolegle możemy liczyć, mając środowisko PVM czy MPI (MPI standardem w programowaniu z
przesyłaniem komunikatów)

MNMP



najdroższe rozwiązanie



budowa węzłowa z wieloma procesorami



mieliśmy wiele procesorów w węźle, działających na swojej lokalnej pamięci wspólnej (szybkość -> łatwość
programowania)



message passing między węzłami (komunikaty), ale związane z nimi pewne zagrożenia (np. opóźnienia;
rozwiązanie – nakładka, zastępująca lokalne adresowanie i umożliwiająca widzenie całości jako jednolicie
adresowanej shared memory); VIRTUAL SHARED MEMORY (pamięć dzielona WIRTUALNA) - w rzeczywistości
oddzielne pamięci w każdym węźle, ale programowo postrzegane jako 1

Ważne paradygmaty:

Model wątkowy



uaktywniane są poszczególne wątki



praca wielowątkowa - wątki pracują współbieżnie; uruchamiamy 1, potem 2



każdy ma stosy, rozkazy - ale jak mamy 1 procesor, to one wykonują się na 1 procesorze;
współbieżnie



wiele wątków z danego procesu może być aktywnych



HPF - hyper-fortran, popularny wśród inżynierów

- Powstał przed C; jak C przyszedł, to zastanawiano się, czy Fortran przetrwa; ale zaczęto

rozwijać stary fortran, powstaje wersja równoległa fortranu;

-  masa bibliotek z rożnych dziedzin technicznych;
-  nadal się dużo pisze i korzysta z gotowych bibliotek
-  SUB – podprogram (w C void), FNC – funkcja (w C funkcja określonego typu),



wymagają struktury 1-wezlowej z wieloma prockami

Paradygmat
pamięci dzielonej



pamięć wspólna – odwołanie się do poszczególnych komórek pamięci



sposób komunikacji między sobą



przykładowa architektura – SMP (Symmetric Multi Processing):

Paradygmat
przesyłu
komunikatów
(Message passing)



mamy osobne pamięci lokalne, i sieć



Message passing wymaga zdefiniowana procesu przesyłu informacji (bufor, do którego dajemy
wartość; sender i receiver - jak 1 send to drugi receive)



musimy wiedzieć, co wysyłamy; musi być zgodność typów (sugeruje nam, co ile bajtów musimy
odcinać ten ciąg bitów);



wymaga protokołu żeby przesyłanie było prawidłowe (protokół 7 warstw modelu OSI)



architektura pamięci rozproszonej:

Virtual/distributad
shared memory



modne



zlikwidowano proces przesyłu informacji (brak bufora, protokołu przesłania)



komunikacja poprzez zmianę wartości w komórce (1 CPU wylicza zmienną i wstawia ją do pamięci
- ta pamięć może być w tym fragmencie, którą ma, ale może to też być w każdym innym, bo
widziana jako wirtualna); z tych zmiennych korzystają wątki



w OpenMP mamy prywatyzowanie zmiennych (po rozbiciu pętli każdy wątek ma
sprywatyzowane), ale nie ma stricte paczki do przesyłu;

Techniki dekompozycji

Aby dokonać zrównoleglenia systemu, należy dokonać jego dekompozycji na prostsze podsystemy
(obliczamy coś równolegle i dekomponujemy na mniejsze elementy).

Techniki dekompozycji:

Geometryczna



Najczęściej spotykana w programach symulujących zachowanie się systemów fizycznych (np. materiał
z jakiego wykonano samolot; symulacje umożliwiają zmierzenie wydajności systemu)



Obszar obliczeniowy dzielony jest na mniejsze podobszary. W każdym podobszarze wykonywane są
te same obliczenia dla różnych danych.



Pozwala nie tylko przyspieszyć obliczenia, ale także daje możliwość rozwiązania dużych zadań.



nazwa wzięła się stąd, że obszary przedstawiamy w 2D (podział na trójkąty) lub 3D (czworościany i
sześciany);



inne się na niej opierają



w większości przypadków prowadzi do rozwiązania układu równań dla danego obszaru
(dekompozycja umożliwia podział olbrzymich równań na mniejsze równania):

Iteracyjna



Wykorzystuje fakt istnienia pętli w programach sekwencyjnych.



Jest najbardziej efektywna w przypadku, gdy liczba pętli iteracyjnych jest znacznie większa niż liczba
dostępnych procesorów.



Jest preferowana na komputerach z pamięcią rozproszoną.



Np. fortran (mamy taski – watki, pamięć wspólna - tablica A)

Rekurencyjna



Zaczyna się od podzielenia oryginalnego problemu na dwa lub więcej podproblemów, a następnie
współbieżnego ich rozwiązania.



Przykład: algorytm szybkiego sortowania

Spekulatywna



W celu znalezienia rozwiązania wykorzystujemy N metod, które liczone są równolegle. Wybierany
jest proces, który pierwszy obliczy prawidłowe rozwiązanie.



Wybieramy 1 proces, pozostałe N-1 jest odrzucanych.



zastosowanie - tam gdzie zależy nam na jakości

Rozproszona



Rozwiązywany problem jest dzielony na fragmenty. Liczba fragmentów musi być dużo większa niż
liczba procesorów.



Każdemu procesorowi przydziela się pewną liczbę tych fragmentów



[E] Problem: granulacja obliczeń

- mała granulacja
- duża granulacja - zmniejszenie obciążenia magistrali komunikacyjnej

Mała granulacja

Duża granulacja



właściwe równoważenie obciążenia



działa tak, że coś liczymy i od razu
wysyłamy (magistrala obciążona, ale
program świetle zrównoleglony)



zmniejszenie obciążenia magistrali
komunikacyjnej



liczymy coś długo i dopiero potem
wysyłamy

funkcjonalna



Polega na przyporządkowaniu każdej funkcji programu (wydzieleniu jego części)

wyspecjalizowanemu procesorowi, który będzie wykonywał obliczenia najskuteczniej i równolegle z
innymi procesorami (funkcjami).

Istnieją różne sposoby dekompozycji danych



W wieloprocesorze wektor dzielimy na tyle, ile mamy procesorów (np. jak wektor ma 100
elementów, a my mamy 4 procesory, to każdy z nich otrzyma po 25; można też przydzielać
cyklicznie, np. 1 element do 1 procesora, 2 do 2, … 4 do 4, 5-ty do 1-ego etc.)



macierze można dzielić wierszami/kolumnami/ na bloki; jak za duży błąd, to dzielimy w
elemencie



podział zależy od fizycznego przechowywania danych (SEM – dostarczanie określonej liczby
bajtów pod wskazany adres; w RAM inaczej; w C jedna po drugiej)



Ważna optymalizacja

Strategie podziału mesh’a



Nałożenie siatki na badany obiekt

- Im mniejsza, tym dokładniejsza (tam, gdzie są mniejsze oczka, tam cos się dzieje)
- Podział obszaru na podobszary (różne algorytmy; obszary te na siebie nachodzą, musimy

wiedzieć, co na złączeniu)

- Na granicy obszarów 1 element wspólny (by lepiej wyliczyć)



Inna metoda – program sumujący warunki i sprawdzający wytrzymałość



W wyborze kryterium dobrego podziału:

- ważny jest load balancing (podział równomierny; każdy procek liczy podobną paczkę danych)
- by każdy podobszar miał tyle samo elementów (trójkątów; im ich więcej, tym więcej

komunikacji)

- kryterium dające jak najmniejszy transfer (komunikacja) na granicy obszarów (jak najmniej

elementów wspólnych)

- wniosek - bardzo indywidualna rzecz zależna od problemu, nie ma 1 metody



Np. w MESie liczymy elementy dla każdego trójkąta – na podstawie tych obliczeń tworzona jest
macierz globalna;

algorytm postępującego frontu - pobieramy do obszaru elementy, potem koniec i następny
greedy algorytm (podział wertykalny); jeśli weźmiemy 8 Procków to normalnie mamy 2500 przesłań,
teraz tylko 800

29.10.2013

QQS

PRiR

Wykład 4

Obliczenia równoległe

Przetwarzanie sekwencyjne



Przetwarzanie rozumiane w sposób tradycyjny



Program uruchamiany na pojedynczym komputerze posiadającym jeden procesor



Kolejne instrukcje programu wykonywane sekwencyjnie (jedna po drugiej)



Tylko jedna instrukcja może być wykonywana w danym czasie

Przetwarzanie równoległe



Jednoczesne wykorzystanie zwielokrotnionych zasobów obliczeniowych w celu rozwiązania
danego problemu



Uruchomienie programu na wielu procesorach



Problem dzielimy na niezależne części, które mogą być wykonywane równocześnie



Każda część składa się z ciągu instrukcji



Instrukcje z każdej części są wykonywane jednocześnie na różnych procesorach

Zasoby obliczeniowe może tworzyć:



pojedynczy komputer z wieloma procesorami (architektura wieloprocesorów)



wiele komputerów połączonych siecią (zespół stacji roboczych; klastry – niezależność procesów)



kombinacja obu

Dlaczego obliczenia równoległe?



Oszczędność czasu



rozwiązywanie dużych problemów



umożliwienie równoczesnych obliczeń (czasami wymagana/deklarowana)



udostępnienie zasobów rozproszonych w sieci

też jako optymalizacja niektórych zasobów; maszyny z szybkimi procesorami muszą być intensywnie
eksploatowane, udostępniane w sieci (za to się płaci)

inne pojęcia, stosowane obok równoległości, i pokrywające się z nią
obliczenia:

współbieżne szersze od równoległości
równoległe

równolegle są współbieżne (ale nie odwrotnie)

rozproszone



dość intuicyjne pojecie



generalnie o obliczeniach rozproszonych mówimy przy przesyłaniu komunikatów;



też dotyczące maszyn zlokalizowanych w 1 miejscu, gdzie są też inne zasoby, np. pamięci;



bardzo szerokie pojęcie



wymagają dekompozycji czegoś, np. danych, obliczeń etc.

Równoległość a współbieżność



Akcje współbieżne mogą być wykonywane faktycznie jednocześnie lub też (pod kontrolą systemu
operacyjnego z podziałem czasu) fragment po fragmencie naprzemiennie z akcjami innego
procesu. Opisując wykonanie pewnego procesu używamy następującej terminologii:

Wykonanie
sekwencyjne



Poszczególne akcje procesu są wykonywane jedna po drugiej



Dokładniej: kolejna akcja rozpoczyna się po całkowitym zakończeniu poprzedniej.

Wykonanie
równoległe



Kilka akcji (procesów) jest wykonywanych w tym samym czasie



"prawdziwa" współbieżność, możliwa do uzyskania na komputerze z wieloma procesorami



Możemy mówić o równoległości nawet wtedy, gdy mamy tylko 1 zasób obliczeniowy – jeśli mamy 1
procesor i wiele procesów, to nie zawsze będą wykonywać się współbieżnie, bo może być
równoległość; warunek: kilka procesów z rożnych zasobów korzysta, np. pierwszy liczy, a drugi coś
wczytuje

Wykonanie
w przeplocie



Choć jednocześnie odbywa się wykonanie tylko jednej akcji, to jednak jest wiele czynności
rozpoczętych i wykonywanych na zmianę krótkimi fragmentami



1 procesor, wiele procesów – procesor udostępniany naprzemiennie

Wykonanie
współbieżne



Kolejna akcja rozpoczyna się przed zakończeniem poprzedniej.



nie mówimy nic na temat tego, czy akcje te są wykonywane w tym samym czasie czy też w
przeplocie.



wykonanie współbieżne jest abstrakcją równoległości i zawiera w sobie zarówno wykonanie
równoległe jak i wykonanie w przeplocie (typowe wykonywanie obliczeń na 1 procesorze, kiedy to
mamy wiele procesów);



systemy z podziałem czasu

- systemy, w których czas procesora dzielony jest na kwanty ( przypisywane poszczególnym

procesom; kolejna akcja rozpoczyna sie przed zakończeniem poprzedniej - dlatego pojecie
szersze od równoległości, bo nie mówimy czy w przeplocie, czy równolegle; współbieżność
szerokim pojęciem, równoległość zawęża)

Metaprzetwarzanie



Narzędzie informatyki zapewniające użytkownikowi przeźroczysty dostęp do różnorodnych usług
komputerowych (użytkownik przestaje odczuwać gdzie i co się znajduje).



Należą do nich takie usługi jak:
- duża moc obliczeniowa (dużo procesorów)
- usługi graficzne, multimedialne i wizualizacji naukowej (działy potrzebne dużej liczbie

zasobów związanych z pamięcią, procesorem czy wielkością RAM)

- usługi archiwizacji bardzo dużych zbiorów (ważnym atrybutem – pojemność dyskowa)

Zrównoleglenie obliczeń



W nowoczesnych systemach komputerowych zrównoleglenie obliczeń (w programie) może
zachodzić na różnych poziomach:

-  poziomie prac,
-  poziomie zadań,
-  poziomie instrukcji i rozkazów.

Zrównoleglenie
obliczeń na poziomie
prac



Równoczesne wykonywanie wielu niezależnych programów (praca = program)

- System jednoprocesorowy - podział czasu procesora (obliczenia współbieżne –

przydział kwantu czasu)

- System wieloprocesorowy - przydzielenie każdemu procesorowi innego programu

(równoległość, a nie współbieżność)



System operacyjny decyduje o zrównolegleniu procesów i przydziale ich procesorowi. W
tym celu korzysta z kolejki zadań do wykonania (FIFO, ale też kolejka priorytetowa). Na
pracę SO może jednak wpłynąć administrator (może zmienić kolejność w FIFO, zmienić
priorytet zadania itd.), zwykły użytkownik nie ma takich praw.

Zrównoleglenie
obliczeń na poziomie
zadań



W programie wydziela się niezależne zadania (ang. task), które wykonywane są
równolegle

Macrotasking

Microtasking



równoległość na poziomie funkcji



zadaniami są wydzielone
fragmenty programu, najczęściej
w formie procedur



równoległość na poziomie danych



zadaniami są niezależne iteracje
pętli programowych (np.
OpenMP)



Zadanie = program lub jego element



Rozbicie programu na elementy wykonujące przypomina robicie programu na wątki,
aczkolwiek mogą tu być procesy niezależne

Zrównoleglenie
obliczeń na poziomie
instrukcji i rozkazów



Polega na równoległym wykonywaniu niezależnych instrukcji programu (niezależnych
rozkazów w ramach instrukcji); np. jak dam do 1 rejestru jakąś wartość „a”, do 2-ego „b”,
to przy wykonaniu dodawania suma ląduje w rejestrze C



zrównoleglić możemy operacje pobierania danych;



przyspieszenie obliczeń - uzyskanie lepszej wydajności



Poziom praktycznie niedostępny dla programisty, ponieważ równoległość jest realizowana
sprzętowo (w samej maszynie jednoprocesorowej jest dużo elementów równoległości)

Zrównoleglenie
obliczeń



Z przedstawionej klasyfikacji wynika, że:
- im niższy poziom, tym większa rola mechanizmów sprzętowych,
- im wyższy poziom, tym istotniejsze stają się mechanizmy programowe.



Programista dokonuje zrównoleglenia obliczeń na poziomie zadań

Modele (paradygmaty) obliczeniowe



Wyróżniamy dwa podstawowe modele programowania równoległego:
- model z wymianą komunikatów z zaimplementowaną równoległością na poziomie funkcji,
- model wirtualnej pamięci wspólnej dla zaimplementowania równoległości na poziomie

danych

Model z wymianą

komunikatów

(message-passing

paradigm,

explicit parallel

programming)



dla explicit parallel programming trzeba podać konkretną nazwę zmiennej, adres odbiorcy



najdroższe rozwiązanie



wykorzystuje popularne środowiska obliczeń, np.

- Parallel Virtual Machine (PVM - parallel virtual machine)
- Message Passing Interface (MPI - message passing interface) – na poziomie funkcji



Odrębne procesy współpracują ze sobą w celu rozwiązania danego problemu. Współpraca
ta polega na wymianie danych między procesami realizowanej w oparciu o przesyłanie
komunikatów

(zwykle mamy 1 program podzielony na wątki, tu mamy 1 proces uruchamiający inne
procesy, żeby rozwiązać różne problemy, p. najczęstszy - master-slave; uruchamiamy
mastera - program główny, który wywołuje procesy slavey; slave się wykonuje, po czym
zwraca informacje do mastera; master zbiera dane i kończy (PVM); w MPI piszemy 1
program dla wszystkich procesów, tylko tam rozróżnienie ze względu na numer (0- master,
inny - slave); wiele procesów rozwiązujących dane zadanie)



Rodzaje komunikatów:

jeden-jeden



wymiana komunikatu między procesem wysyłającym i
odbierającym



mamy konkretny proces, który wysyła dane i 1, który
przejmuje



określone adresy

jeden-wielu
(ang. broadcast)



jeden proces rozsyła ten sam komunikat do wielu innych
procesów

wielu-jeden
(ang. reduction)



wiele procesów wysyła komunikat do jednego wybranego
procesu



korzystamy, gdy np. w obliczeniach poszczególne procesy liczą
pewien błąd, ale działanie podejmowane dopiero, gdy wyliczy
się globalny błąd



Do przesłania dowolnego komunikatu system musi posiadać informacje:
- gdzie znajdują się dane do wysłania (określane poprzez nazwę zmiennej w to miejsce,

np. nazwa tablicy - adres zerowego elementu)

-  jaki jest ich typ i rozmiar
-  do którego procesu będzie wysłany
-  gdzie będą przechowane otrzymane dane

typ decyduje o ilości bajtów; w przypadku tablicy ważne jest określenie, jakiego typu są
elementy tablicy i ile tych elementów jest; określenie typu jest ważne, bo przy przesłaniu
komunikatów możemy załadować do bufora wartości różnych typów (ciąg 0 i 1 tak naprawdę);
wysyłając taką paczkę informujemy odbiorcę o tym, jak powinien je odczytać, żeby wiedzieć,
co tak naprawdę otrzyma; jeśli wie, że to np. integer, to ta wartość zapisana będzie na 8
bajtach – odczytuje więc te pierwsze 8 bajtów i je przechowuje; typ zmiennej przy wczytaniu
musi się zgadzam w tym przy wysłaniu; w rożnych architekturach ten sam typ może być różnie
reprezentowany

jak zmienić liczbę z 6 bajtów na 8? za pomocą protokółu – explicite programming model (nie
ważne, jak reprezentowane są dane- ważne tylko, by była poprawna; czasami jednak jak
wyślemy wartość rzeczywistą i zmniejszamy bajty, to tracimy na wartości - nie jest oczywiste
że otrzymamy to samo); jak wysyłamy wiadomość, to musimy podać adres odbiorcy
(zazwyczaj nazwami symbolicznymi ale bez tych całych dokładnych nazw); mechanizm
przekładający nazwę odbiorcy na nazwę IP; w MPI posługujemy się numerami procesów,
powiązanych już z adresami IP (wygodne rozwiązanie dla użytkownika - cały mechanizm
przesyłu informacji jest zautomatyzowany i z dala od usera; user tylko podaje adresata)



Model z wymianą komunikatów powinien:
-  zapewnić równoważenie obciążenia pomiędzy procesorami,
-  zminimalizować ilość przesyłanych informacji,
-  zminimalizować czas wykonania całego zadania.

Równoważenie obciążenia między procesorami - chodzi o to, żeby każdy procesor pracował ze
swoją max wydajnością; procesory nie musza otrzymywać takiej samej porcji danych do
zrównoważenia, bo możemy mieć słabszy komputer; model z wymianą komunikatów powinien
zapewnić przydzielenie każdemu procesorowi obliczeń proporcjonalnych do jego wydajności -
wtedy zachowany load balancing; trudne, bo nie ma algorytmu jak zrobić taki podział (my

mamy tylko numer procesora, nie ma jakiegoś współczynnika określającego jego wydajność -
robimy trochę intuicyjnie

w dekompozycji geometrycznej - był MES, i tam loadbalancing poległaby na daniu każdemu
procesorowi tyle samo elementów skończonych (trójkąty);
załóżmy ze mamy procki o takiej samej wydajności - wtedy uproszczona sprawa, bo mamy
obszar obliczeniowy zdyskretyzowany na te trójkąty; robimy dekompozycje, dajemy model z
przesyłem komunikatów, a każda maszyna coś otrzymuje, liczy i zwraca jakieś wyniki; liczymy
też błąd - określamy czy duży, czy nie;

metody adaptacyjne (bardziej zaawansowane) - stwierdza się, w których elementach duży
błąd - jeśli tak, to dzielimy; jak dany trójkąt ma duży błąd, to dzielimy go na 4 mniejsze, ale to
zaburza load balancing (w praktyce podział następuje nawet 500-600 razy); przy błędach
zwiększa sie dysproporcja w loadbalancingu; zwykle robi sie tak, ze po 200-300 iteracji robi się
jeszcze raz dekompozycje (bo nie opłaca się brnąć dalej); jest grupa algorytmów dbających o
loadbalancing czy spójność cache

badanie czasu przy programach z przesyłaniem - musimy zainicjować bufor, ładujemy go i
potem SMP; inicjalizacja bufora najkosztowniejsza; kosztowne wielokrotne wysyłanie -
program w MPI ma zminimalizować liczbę przesłań - wysłanie naraz 100 czy 200 kb danych nie
jest tak kosztowne, jak osobne; czasem lepiej wysłać więcej, ale też my musimy wiedzieć, czy
dana zmienna jest potrzebna czy nie - być może lepiej opóźnić przesłanie i wysłać mniej
komunikatów



Zastosowanie:
- sieci stacji roboczych (homogeniczny i heterogeniczny)
- klastry

- komputer wieloprocesorowy



najbardziej optymalne, MPI uruchomimy na każdym środowisku

Model z równoległością
danych
(data-parallel
programming,
implicit parallel
programming,
data parallelism)



posługuje się językiem programowania wysokiego poziomu



większość współczesnych kompilatorów wyposażona jest w możliwość obliczeń w tym
modelu

- High Performance Fortran (HPF), pFortran, PC
- środowisko OpenMP



Zastosowanie:

- Komputer wieloprocesorowy

wymaga maszyn z pamięcią wspólną, jednolite adresowanie; nie pójdzie na multikomputerze;
nie można rozdzielić pętli na kilka procesów; proces może być uruchomiony w 1 przestrzeni
adresowej na 1 maszynie

Model hybrydowy



Równoczesne zastosowanie modelu z przesyłem komunikatów i z równoległością na
poziomie danych



Zastosowanie:
- sieci komputerów wieloprocesorowych
- Komputery wieloprocesorowe o budowie węzłowej

mamy model z przesyłem komunikatów (dla kilku węzłów); na poziomie 1 węzła - zrównoleglenie na
poziomie danych; w sieci - tworzymy MPI, każdy procesor dostaje inny proces i w obrębie procesu -
zrównoleglenie na poziomie danych
- budowa węzłowa - alternatywa; jeśli mamy wieloprocsor, który ma węzły z pamięcią globalna dla
węzła, to miedzy węzłami stosujemy model przesyłu komunikacji

5.11.2013

QQS

PRiR

Wykład 5

Efektywność obliczeń równoległych

Ocena jakości zrównoleglenia

Najczęściej spotykane:



przyspieszenie (ang. speed-up)



efektywność (ang. efficiency)

ogólna zasada – jeśli jakaś angielska ma odpowiednik polski, to piszemy ją po polsku …

Przyspieszenie

Rodzaj

przyspieszenia

wzór

opis

absolutne

- czas wykonania „najlepszego” sekwencyjnego algorytmu

- czas wykonania programu równoległego na p procesorach



trzeba rozróżnić program na wykonany sekwencyjnie i równolegle; to są często 2
różne algorytmy (różnica nie tkwi we wprowadzeniu dyrektyw, jak w OpenMP);
program równoległy jest bardziej rozbudowany, ma inne zmienne



liczenie najlepszego sekwencyjnego algorytmu programu – tu nie chodzi o zmianę
algorytmu w sekwencyjnym (w sekwencyjnym i równoległym algorytmy muszą być
takie same), ale o hermetyczność środowiska; w przypadku OpenMP liczymy na
identycznych węzłach roboczych (zrównoleglenie na wątki), wieloprocesor o
identycznych procesorach; może być jednak sytuacja, w której maszyna ma procesory
o różnych mocach obliczeniowych – czas najlepszego sekwencyjnego liczymy na
najlepszym procesorze wieloprocesora lub najlepszej maszynie

względne

– czas wykonania programu równoległego na 1 procesorze

- czas wykonania programu równoległego na p procesorach



w równoległości wykorzystujemy identyczny algorytm, jak w przypadku algorytmu
sekwencyjnego, ale zrównoleglamy go; czasami jednak mogą pojawić się problemy i
wtedy piszemy kod równoległy od początku; jeśli chcielibyśmy obliczyć wówczas
przyspieszenie absolutne, to pojawia się problem, bo nie mamy kodu sekwencyjnego
(zmiennej potrzebnej – wyliczamy ją na podstawie ilości procesorów)



program działa na n procesorach, ale jest w stanie prowadzić obliczenia dla n=1



najczęściej dla MES najpierw dyskretyzuje się obszary (podział obszaru na p
procesorów, ale gdy p=1 to nie dzielimy – problem, bo dane muszą się zmieścić)



przyspieszenie względne – wykorzystywane, gdy nie mamy implementacji
sekwencyjnej



najwygodniejsze, bo stosujemy ten sam algorytm



Przyspieszenie:



W idealnej sytuacji wartość przyspieszenia powinna być równa p.



W praktyce zrównolegleniu ulega nie cały program, a tylko wybrane jego elementy.

Warto jednak zauważyć, że każdy program równoległy ma w sobie jakiś procent programu
sekwencyjnego, którego nie da się zrównoleglić

Wykres przyspieszenia będzie mieć następującą postać:

W programie równoległym jakaś określona liczba procesorów współpracuje ze sobą celem
rozwiązania jakiegoś zadania. Większa liczba procesorów wymaga jednak przesyłu większej
komunikacji; powyżej jakiegoś p ta komunikacja zaczyna przeważać i procesory nie mogą w pełni
wykorzystać swojej mocy obliczeniowej – pojawiają się opóźnienia wynikające z komunikatów (mpi)
czy przeciążania magistrali w wieloprocesorze.

Czas wykonania programu na p procesorach:

gdzie:

- czas wykonania programu na p procesorach

- czas wykonania części sekwencyjnej

- czas wykonania części równoległej algorytmu

p - liczba procesorów

Z zależności wynika, że czas równoległego wykonania zadania nie będzie nigdy krótszy, niż czas
wykonania części sekwencyjnej programu, niezależnie od użytej liczby procesorów.

Prawo Amdahla [E]



Potencjalne możliwe przyśpieszenie S algorytmu jest równe:

Jeśli czas wykonania programu wynosi 1, a udział części nierównoległej na F, to czas wykonania
programu równoległego to część sekwencyjna + równoległa na p procesorach; zwiększając ilość
procesorów uzyskujemy niby większe przyspieszenie, ale przy nieskończenie wielu procesorach
przyspieszenie przyjmie wartość 1/F



Prawo Amdahla: przy użyciu dowolnej liczby procesorów, obliczeń nie da się przyśpieszyć
(zrównoleglić) bardziej, niż odwrotność części sekwencyjnej w programie (1/F)











T - czas wykonania algorytmu
F - udział części nierównoległej



Jeśli znamy % części sekwencyjnej i równoległej w kodzie, wówczas możemy narysować
hipotetyczny wykres przyspieszenia (chodzi o wartość, której przyspieszenie nigdy nie przekroczy)

[E] Przykład:



Załóżmy, że program na jednym procesorze liczy się 20 godzin



Część sekwencyjna stanowi 5% tzn. liczy się 1 godzinę



Część równoległa stanowi 95% tzn. liczy się 19 godzin



Maksymalne przyspieszenie na p procesorach wynosi:

A z prawa Amdahla wyjdzie nam, że:

(na egzaminie mamy jakiś problem, gdzie określona jest część sekwencyjna i równoległa i trzeba
narysować wykres)

Odczyt parametrów na podstawie wykresu - przykład:

Weźmy 2-gą od góry linię. Część równoległa wynosi tu 90%, a to oznacza, że część sekwencyjna
wynosi 100% - 90% = 10%, co daje nam wartość 0,1. Odwrotnością tej liczby jest 10.

Na podstawie proporcji (części sekwencyjnej i równoległej w programie) możemy obliczyć granice
przyspieszenia, poza które nie wyjdzie (prawo Amdahla).

John L.Gustafson



Pokazał, że w przypadku równoczesnego zwiększania rozmiaru zadania i liczby procesorów prawo
Amdahla nie obowiązuje (obliczenia olbrzymiej skali).



Wyprowadził wzór na obliczanie przyspieszenia oddzielnie dla algorytmów o stałym i
skalowalnym rozmiarze.



Przyjmuje wartości z przedziału [0,1]



stosunek przyspieszenia do liczby procesorów







100





dla p procesorów optymalne przyspieszenie wyniesie p, czyli efektywność byłaby optymalna dla p/p
czyli 1 (efektywność to ułamek);

Przyspieszenie superliniowe



Gdy jego wartość przekracza p



Wartość efektywności przekracza 1



Zachodzi dla pewnych klas zagadnień realizowanych równolegle lub wtedy, gdy w wyniku
dekompozycji zadania poszczególne części mieszczą się w całości w pamięci podręcznej
procesorów.

Początkowo sądzono, że przyspieszenie superliniowe jest wbrew logice, ale okazało się to prawdziwe.
Przyspieszenie przekraczające liczbę p wiąże się z pamięcią – jeśli przed dekompozycją zadania nie
mieszczą się w cache (sytuacja dla 1 procesora), wówczas bierzemy poszczególne strony i
umieszczamy je w cache (wymiana stron pamięci); dekompozycja polega na zmniejszeniu
potrzebnych porcji, dostarczanych do procesora – dzięki temu nie ma wymiany z pamięcią RAM,a
wszystko, co potrzebne znajduje się w cache. Liczba procesorów p określa podział na dekompozycji.

Generalnie, jak podzielone zadanie zmieści się w cache procesorów, wówczas możemy uzyskać
przyspieszenie ponadliniowe.

wykresy z superkomputerów

Obrazek przedstawia fragment skali logarytmicznej, na której widać zachwiania. Obliczenia
wykonane były na klastrze składającym się z węzłów 8-procesorowych – dla obliczeń wewnątrz węzła
zachowywał się jak wieloprocesor, widoczne było przyspieszenie; przy dodaniu 9-ego procesora (a
więc 1-ego z innego węzła) tworzy się nam powoli multikomputer (przesyłanie komunikatów w sieci
zewnętrznej – spowolnienie przyspieszenia); dopiero dodanie kolejnych procesorów z kolejnego węzła
przyspieszało przyspieszenie; duża zależność od zastosowanej architektury.

W przypadku MES-a na skrzydle samolotu PVM (przesyłanie komunikatów) było bardziej opłacalne od
OpenMP:

w OpenMP można zrównoleglić tylko małe fragmenty kodu – stąd słabsze przyspieszenie; oczywiście
wszystko zależy od obliczanego zadania i OpenMP może nieraz dawać lepsze rezultaty

Rozbicie na wątki w architekturze wieloprocesorowej:



Dla programu sekwencyjnego mamy 1 wątek, najwięcej liczy funkcja main (suma wywołań
poszczególnych funkcji; wątek liczył całość w ciągu 50 sekund)



Przy zrównolegleniu w OpenMP na 7 wątków: mamy 1 wątek główny aż do rozbicia pętli na
poszczególne wątki, potem znów część sekwencyjna itd.; dekompozycja pętli wiąże się z rozbiciem
tylko niektórych funkcji (6 wątków robiło swoje obliczenia w ciągu 5 sekund każdy, 7-dmy
„główny” liczył całość w ciągu 20)

wykresy przyspieszenia daje się w programach równoległych, ale pojawia się problem, gdyż maszyna
nie może być obciążona (musimy mieć ją na wyłączność; superkomputery umożliwiają pracę wielu
użytkowników jednocześnie; jeśli maszyna ma system kolejkowy, to on udostępnia nam takich
zasobów o jakie prosimy, czyli np. jak mamy kod openmp i chcemy policzyć wszystko na 7
procesorach, to system kolejkowy nie uruchomi go dopóki na wyłączność nie odstaniemy 7 wątków);

Załóżmy, że mamy wieloprocesowy (po 8 procesorów każdy) połączone magistralą; przy programie
tworzącym 12 wątków system kolejkowy najprawdopodobniej da nam 8 procesorów z 1 węzła i 4 z
innego; mam na wyłączność 12 procesorów, ale muszą się między sobą komunikować;

W rzeczywistości też nie wiemy, jak system przydzieli nam węzły (system nie wyłączy zadań, które
liczy 10 godzin; czasami da nam po 1 procesorze z węzła - najmniej optymalna sytuacja); najlepiej jak
nasze programy uruchamiamy na kastrach (bo są dedykowane na zadanie)

12.11.2013

QQS

PRiR

Wykład 6

Programowanie maszyn klasy HP-UX Systems

Model pamięci wspólnej

Do tej pory powiedzieliśmy wszystko odnośnie sprzętu oraz programowania równoległego
(wyróżniamy tu 2 modele: z przesyłaniem komunikatów (MPI, PVN) oraz na poziomie danych -
OpenMP, dyrektywy kompilatora). Teraz skupimy się na programowaniu komputerów z pamięcią
wspólną na przykładzie maszyn HP-owskich (zrównoleglenie za pomocą dyrektyw kompilatora –
przypomina nieco OpenMP; dyrektywy dostarczone z kompilatorem; OpenMP dostarcza dodatkowo
środowisko funkcji bibliotecznych).

Lokacje kompilerów HP:

Kompilator

opis

lokacja

f90

Fortran90

/opt/fortran90/bin/f90

ANSI C

/opt/ansic/bin/c89

aC++

ANSI C++

/opt/aCC/bin/aCC

W kodzie źródłowym programu mogą pojawić się dyrektywy (C,C++) lub pragmy (Fortran 90);
najczęściej używane dla tych 2 kompilatorów

dyrektywy przyjmują postać:

Fortran90

#pragma _CNX <dyrektywa>

C$DIR <dyrektywa>

Teraz, żeby te dyrektywy były rozpoznawane przez kompilator, kod źródłowy kompilujemy z
odpowiednią opcją (domyślnie ustawiony jest najniższy poziom opcji kompilatora, wtedy dyrektywy
traktowane są jako komentarz).

Poziom
optymalizacji

właściwości

Korzyść

+o0

(domyślny)



Występuje na poziomie instrukcji maszyny



Stała składnia



Dostosowanie danych do naturalnych granic



Częściowa ocena warunków testowych



Rejestry (prosta alokacja)

Najszybsza kompilacja

+o1

(zawiera
wszystko z
+o1)



Występuje na poziomie bloków



Optymalizacja gałęzi



Eliminacja martwego kodu



Planista instrukcji



Optymalizacje wizjera (peephole)

Tworzy szybsze programy od +o0 i jest szybciej
się kompiluje od +o2

+o2 (-o)

(zawiera +o0
i +o1)



Występuje na poziomie procedur



Eliminacja powszechnych wyrażeń regularnych



Zaawansowana stała składnia i propagacja



Pętla – niezmienność ruchu kodu



może tworzyć szybciej run-time code niż
+o1, jeśli pętle używamy rozlegle



Run-time dla zmiennoprzecinkowych,
zorientowanych na pętle aplikacji może być



Rozwijanie pętli



Rejestry (globalna alokacja)



Ponowne nawiązanie łączności z rejestrami



Programowanie potokowe



optymalizacja przechowywania/zapisu



obniżenie siły indukcji



zmienne i stałe



eliminacja nieużywanych zmiennych



np. cc +o2 plik.c

zredukowany nawet do 90%



SO i interaktywne aplikacje używające
zoptymalizowanych bibliotek systemowych
mogą osiągać 30-50% dodatkowej poprawy

+o3

(zawiera
wszystkie
wcześniejsze)



Występuje na poziomie pliku



Klonowanie w obszarze pojedynczego źródła
pliku



Lokalizacja danych



Automatyczne i określone dyrektywami
zrównoleglenie pętli



Dyrektywy określają zrównoleglenie
regionu/zadań



Inline w obrębie pojedynczego pliku źródłowego



Pętle: blokada/podział pętli …



Równoległość, redukcja



Dostępna opcja +Oparallel



Np. cc +o3 +Oparallel plik.c



Tworzy szybszy kod Run-Time niż +o2 na
kodzie często używającym małych funkcji
lub rozległych pętli



Linkuje się szybciej niż +o4

+o4

(zawiera
wszystkie
wcześniejsze,
ale nie
dostępne w
fortranie 90)



Występuje na przecięciu poziomu modułu i
wykonuje się w czasie linkowania



Klonowanie wzdłuż wielu kodów źródłowych



Optymalizacja globalnych/statycznych
zmiennych



Inline wzdłuż wielu kodów źródłowych



Dostępna opcja +Oparallel



Tworzy szybszy kod run-time niż gdyby przy
+o3 użyto globalnych zmiennych lub gdy
wywołania procedury będą inlined przez
moduły



Z powyższej tabelki trzeba wiedzieć tylko kilka rzeczy:

- poziom wyższy bierze pod uwagę poziom niższy + wprowadza swoje dodatkowe możliwości;
- nas interesuje poziom +o3 (określone są tu dyrektywy zrównoleglające +Oparallel – możemy

zrównoleglić zadania i pętle; są jednak pewne rozróżnienia: prefer paralel i loop paralel – 2
dyrektywy umożliwiające zrównoleglenie pętli; +Oparallel – opcja domyślna); poniżej +o3 nie
działają opcje do zrównoleglenia

- poziom optymalizacji kompilatora podajemy przy jego wywołaniu
- cc +o3 +Oparallel plik.c - zrównoleglenie musimy wymusić odpowiednią opcją kompilatora,

żeby miało ono miejsce, bo nawet jak nadpiszemy dyrketywy to może się nie uruchomić;

opcja +Oparallel



kompilator wyszukuje pętle do zrównoleglenia



wyszukuje i uwzględnia dyrektywy/pragmy z kodu źródłowego

ta opcja kompilacji wyszukuje pętle do zrównoleglenia (poziom automatycznego zrównoleglenia) i
bada czy należy zrównoleglić czy nie; bierze też pod uwagę dyrektywy, które user wpisuje do kodu
źródłowego

opcja +Oautopar



+Oautopar – default (domyślnie kompilator zbada kod pod względem zrównoleglenia)



automatyczne zrównoleglenie



+Onoautopar - kompilator zrównolegla tylko fragmenty kodu poprzedzone dyrektywami lub

pragmami typu:

- loop_parallel
- prefer_parallel



autopar daje możliwość uruchomienia kodu zrównoleglenia tylko tam gdzie chcemy;



wszystkie superkomputery maja to; możemy albo automatycznie zrównoleglić albo dać
kompilatorowi do zrównoleglenia;

Zrównoleglenie pętli



automatyczne zrównoleglenie następuje po użyciu odpowiedniej opcji kompilacji; kompilator
sam decyduje, które pętle mogą zostać poprawnie zrównoleglone (prywatne zmienne pętli)



zrównoleglenie wymuszone przez programistę (w OpenMP my wymuszamy, które zmienne mają
być prywatne, a które nie)

automatyczne zrównoleglenie wcale nie jest takie super; twórcy oprogramowania chcą, aby
automatyczne zrównoleglenie zastąpiło pracę usera; w rzeczywistości jednak, jak uruchomimy taki
większy program i damy opcje automatycznego zrównoleglenia, to nasz kod, który jest objectem
wzrasta do wielkich rozmiarów, kompilator analizuje każdą możliwą pętlę do zrównoleglenia (w 99%
decyduje, że nie można jej zrównoleglić, nie ma zatem pewności, że kod będzie działać poprawnie).

Weźmy poniższy program jako przykład:

Zakładamy, że program zrównoleglimy automatycznie. Przy inicjalizacji zmiennych program zadziała,
ale każdą inną pętlę, wykorzystującą operacje I/O kompilator odrzuci (nie można zrównoleglić
automatycznie)

Automatyczne zrównoleglenie pętli
Pętle muszą spełniać następujące warunki:



Nie zawierają zależności przenoszonych przez iteracje (z wyjątkiem operacji redukcji)



W czasie wykonywania, przed wejściem do pętli, mają określoną liczbę wykonywanych iteracji



Nie zawierają operacji we/wy



Nie zawierają wywołań procedur i funkcji

trzeba być pewnym, że wykonanie lokalnie dla rożnych funkcji przejdzie poprawnie, ale
automatycznie kompilator takich pętli nigdy nie zrównolegli



Przed pętlą nie wystąpiła dyrektywa lub pragma no_parallel - możemy automatyczne
zrównoleglenie, ale zaznaczamy sobie pętle których nie chcemy zrównoleglić (noparallel)

Przykład (program napisany w Fortranie)



Załóżmy, że mamy dostępnych 8 procesorów, dla których tworzymy 8 wątków (numeracja 0-7)



Przedstawiony podział - default



Program jest następujący:

for(i =0; i<n; i++)

w[i] = 0;

for(i...)

a[i] = 2*a[i+3]+2;

PROGRAM PARAXPL

....
DO I = 1,1024

A(I) = B(I) + C(I)

....
ENDDO



Wówczas 0-owy dostanie iteracje <1,128>, 1-wszy <129,256> , … , 7-my <897, 1024>

Zrównoleglenie pętli



W czasie tworzenia wątków kompilator prywatyzuje pewne zmienne, tworząc ich kopie dla
każdego wątku.



Liczba iteracji wykonywanych przez każdy wątek to całk. liczba iteracji / liczba wątków

automatyczne zrównoleglenie pętli [E]



Kompilator rozpoznaje i zrównolegla pętle, w których występuje specjalny rodzaj zależności
zwany redukcją (dotyczy wszystkich kompilatorów)

Przykład redukcji - sumowanie elementów tablicy :

załóżmy, że program wykonujemy na kilku wątkach; redukcja polega na tym, że liczymy sumę dla
kilku elementów, a na końcu tworzymy sumę ze wszystkich sum; każdy watek wie, że musi
sprywatyzować zmienną sumy - po odejściu każdy ma inną wartość i na końcu sumujemy; redukcja
ma to do siebie, że sama to zrobi, nie trzeba mu przypominać

dyrektywy kompilatora loop_parallel i prefer_parallel
#pragma _CNX
prefer_parallel



preferowane zrównoleglenie pętli



kompilator zrównolegla pętlę o ile da się to zrobić, prywatyzuje zmienne



inaczej mówiąc – my prosimy kompilator, żeby zrównoleglił pętlęi jeśli to tylko
możliwe, to ją zrównolegla (prywatyzuje zmienne);



nie ma 100% gwarancji, że pętla będzie zrównoleglona

#pragma _CNX
loop_parallel



wymuszone zrównoleglenie pętli, kompilator nie sprawdza zależności danych
wewnątrz pętli, nie prywatyzuje zmiennych. Programista musi sam
sprywatyzować dane wykorzystując do tego celu dyrektywę:
#pragma _CNX loop_private(lista obiektów)



użyteczna przy zrównolegleniu pętli zawierających wywołanie funkcji, np.
C$DIR LOOP_PARALLEL
DO I=1, N
X(I)=FUNC(I)
ENDDO



musimy sprawdzić, czy nie ma zależności iteracyjnych; jeśli wiemy, że zależności
nie ma, to możemy to zrobić, ale trzeba uważać żeby było dobrze

różnica miedzy nimi jest taka, ze jak można automatycznie zrównoleglić pętle to wtedy kompilator
bierze na siebie wszystko co jest z tym związane;

Język

Forma

Fortran

C$DIR PREFER_PARALLEL[(attribute-list)]

C$DIR LOOP_PARALLEL[(attribute-list)]

#pragma_CNX prefer_parallel[(attribute-list)]

#pragma_CNX loop_parallel(Ivar = indar, [attribute-list])

suma=0;
for(i=0;i<100;i++)

suma=suma+a[i];

Argument chunk_size = n
Iteration distribution using Chuck_size = 1

Dla 4 procesorów i 8 wątków:

CPU0

CPU1

CPU2

CPU3

iteracje

…

domyślnie ilość iteracji dzielona przez liczbę wątków, jednak możemy wymusić inną wartość

Chuck_size = 5 i 40 wąków:

CPU0

CPU1

CPU2

CPU3

iteracje

1,2,3,4,5

6,7,8,9,10

11,12,13,14,15 16,17,18,19,20

21,22,23,24,25 26,27,28,29,30 31,32,33,34,35 36,37,38,39,40

Przykład:

Wówczas przy pracy na 8 wątkach pierwszy dostanie 1-4, drugi 5-8 etc.; gdy dojdzie do ostatniego, to
pierwszy znów otrzymuje i tak, aż zostaną rozdzielone wszystkie iteracje

argument max_threads = m



m liczba całkowita



zrównoleglenie pętli na nie więcej niż m wątków

przy wywołaniu programu można ustawiać maks. liczbę wątków; zrównoleglenie pętli na nie więcej
niż n wątków – problem, bo działając na maszynie wielodostępnej, posiadającej dużą liczbę
użytkowników SO musi decydować o przyznaniu odpowiedniego procesora (optymalna praca); można
się zorientować, które procesory liczą, ale może się okazać, że wszystkie obliczane będą tylko na 1
procesorze - bo jak SO miał kolejkę zadań pochodzących od wielu użytkowników, to SO może
stwierdzić, że bardziej optymalnie dla systemu będzie przekazanie pojedynczego procesora – w
efekcie otrzymujemy bzdurne czasy, bo to nie równoległość, tylko współbieżność (jeżeli interesują nas
wykresy przyspieszenia, to musimy sprawdzać czy mamy wykonanie równolegle, a nie współbieżnie)

przy min_threads - nie wiadomo na ilu (minimum); jeśli określimy minimalną i maksymalną liczbę
wątków liczących program, wówczas program powinien wykonać się równolegle na zdefiniowanej
przez nas liczbie procesorów.

sekcja krytyczna
język

Forma

Fortran

C$DIR CRITICAL_SECTION[(gate)]

C$DIR END_CRITICAL_SECTION

#pragma _CNX critical_section [(gate)]

#pragma _CNX end_critical_section

C$DIR PREFER_PARALLEL(CHUNK_SIZE=4)

DO I=1, 100

A(I) = B(I) + C(I)

ENDDO

19.11.2013

QQS

PRiR

Wykład 7

Narzędzia do tworzenia programów rozproszonych

(RPC, RMI, CORBA)

Do tej pory mówiliśmy o rożnych środowiskach programowania równoległego: przesyłania
komunikatów (wiele procesów komunikujących się, np. MPI, PVC) oraz pamięci wspólnej
(przetwarzanie oparte na przetwarzaniu różnych danych w te same ciągi kroków, np. OpenMP, które
jest podobne do dyrektyw kompilatorów - można zrównoleglić różne ciągi instrukcji); procesy -
pamięć rozproszona, watki - pamięć wspólna; oprócz tego inne mechanizmy umożliwiające
zrównoleglenie naszego programu - dochodzą biblioteki numeryczne (wywołujemy procedurę, która
juz jest zrównoleglona)

pewne narzędzia do programowania rozproszonego:



RPC - zdalne wywołanie procedury



RMI – Java



CORBA

Aspekty obiektowego programowania rozproszonego:



Standaryzacja.



Współdziałanie (ang. interoperability) modułów programowych różnych producentów, na
różnych maszynach, przez różne media komunikacyjne.



Wielokrotne wykorzystanie (ang. reusability) modułów programowych.

struktura oprogramowania rozproszonego



Aplikacje działające w środowisku rozproszonym mogą być napisane w różnych językach
programowania.



Interfejs do operacji zdalnych jest definiowany w specyficznym języku narzędzia programowania
rozproszonego.



Interfejs służy do wygenerowania zestawu procedur w konkretnym języku programowania

Moduły mogą być jednak zapisane w różnych językach – pytanie, czy można stworzyć standard do
tworzenia informacji?

Jakie modele możemy wyróżnić?

model
klient-

serwer



Część procedur będzie wykonywana przez klienta czyli program korzystający z operacji w komputerze
odległym

- są to tzw. namiastki (stubs) operacji wykonywanych przez serwer.



Część procedur będzie wykonywana przez serwer tj. program świadczący usługę wykonania operacji.



Część procedur będzie wykorzystywanych przez oba programy.



Model ten jest najczęściej spotykany

Namiastki



Procedury stub mają prawie dokładnie taką samą liczbę i typy parametrów jak w deklaracji interfejsu, ale
służą wyłącznie do przekazania argumentów wywołania do serwera, a następnie odebranie wyników
zdalnej procedury tam wykonanej.



Kod odpowiedzialny za organizację i konwersję przekazywanych danych (marshalling code) jest
generowany automatycznie.



W skrócie – są to procedury odpowiedzialne za organizację i konwersję przekazywanych danych;
generują automatycznie kod wykonywalny; problem – przekazanie parametrów przez zdalną procedurę

Ograniczenia przesyłania parametrów



Przesyłanie tablic wymaga każdorazowo podania ich rozmiaru.



Przesyłanie wskaźników i referencji nie ma sensu:

- różne przestrzenie adresowe serwera i klienta.



Przesyłanie deskryptorów plików, uchwytów okien nie ma sensu:

- obiekty te mają charakter lokalny.

Powyższy problem związany jest z parametrami – bo jeśli przesyłamy tablice jako parametr, to oprócz
typu tej tablicy trzeba zdefiniować jej długość; trudność z przesyłaniem wskaźników i referencji (nie
ma sensu); to się bierze stąd, że adresowanie u klienta i serwera jest oddzielne

RPC
(Remote
Procedure
Call)



RPC jest protokołem, który pozwala wywoływać programowi działającemu na jednym komputerze,
procedury znajdujące się na innym komputerze, w innej przestrzeni adresowej w sposób
zapewniający osiągnięcie jak największej PRZEŹROCZYSTOŚCI wywołań w stosunku do wywołań
procedur lokalnych.

- w przypadku MPI uaktywniamy oddzielne procesy (w środowisku klient-serwer 1 proces

uruchamia inny)

- w RPC mamy 1 przezroczysty program
- kod takiego programu jest prosty (pisanie procedury z odpowiednią ilością parametrów);

użytkownik pisze program normalnie

- trudność – program wykonywany jest nie na maszynie, która go wywołuje, ale na innej maszynie

w innej przestrzeni adresowej; potrzeba funkcji, które rozwiążą problem interfejsu – namiastki
(oprogramowanie dbające o to, by przesłać wszystkie potrzebne informacje - głównie parametry
przesyłania funkcji)



Mechanizm RPC został opracowany przez firmę Sun; obecnie znormalizowany przez ISO/IEC.



Powszechnie stosowany w systemach Unix różnych producentów.



Wspólny sposób reprezentacji podstawowych typów danych – eXternal Data Representation.

External Data Representation



Ujednolica reprezentację danych w transmisjach sieciowych miedzy różnymi komputerami o
odmiennych architekturach.



RPC zawiera funkcje służące do kodowania i dekodowania typów prostych, łańcuchów znaków, tablic,
unii i wskaźników języka C w standardzie XDR.



Dane są zapisywane/odczytywane z potoku XDR tj. strumienia bajtów.

przesyłanie informacji to tak naprawdę ciąg 0 i 1; jeśli mamy maszyny heterogeniczne to dane
reprezentacje określonych typów danych muszą być rozpoznawane, bo jeśli typ na 1 maszynie ma 8
bajtów, a na innej 6, to jak to jest przekładane z 1 maszyny do innej decyduje protokół (zaczęło to
funkcjonować przy przesyłaniu danych)

ograniczenia RPC



Nie przystosowany do programowania obiektowego (CORBA i RMI są).



Zdalna procedura przyjmuje tylko jeden argument (może on być strukturą).



Wszelkie zmiany dokonane przez procedurę w obrębie jej argumentu pozostają lokalne i nie są
przekazywane z powrotem do klienta.



Do klienta przekazywany jest wynik procedury jako dowolny typ XDR – np. także struktura.

Ogólna realizacja



Serwer przez cały czas nasłuchuje czy ktoś się z nim nie łączy;



Klient wywołując zdalnie procedurę znajdującą się na serwerze łączy się z serwerem przez sieć
komputerową;



Klient wysyła argumenty potrzebne do wykonania procedury;



Serwer realizuję odpowiednią procedurę i wysyła jej wynik (w przypadku niepowodzenia kod błędu).

To ma sens, gdy procedura jest odpowiednio złożona i serwer może ją odpowiednio zrealizować

Wywołanie zdalnej procedury

klient wysyła zdalną procedurę; serwer nasłuchuje i jak wyłapie to realizuje dane zadanie - wykonuje tą
procedurę i zwraca klientowi wynik; wywołanie synchroniczne (klient czeka, aż serwer go obsłuży)

Pieniek (Stumb, łącznik)



Zapewnia przezroczystość zdalnego wywołania;



Pieniek klienta dostarcza lokalnie interfejsu zdalnej procedury;



Przetwarza wywołanie oraz wynik na wiadomość sieciową;



Ich kod generowany jest automatycznie.

Schemat komunikacji:

mamy klienta i serwer; musza być filtry XDR; mamy procedurę klienta, która ma pewien łącznik, za
pomocą którego następuje przesłanie do serwera; na serwerze dane są interpretowane (szuka żądania
wykonania procedury, obsługuje je i wysyła do klienta)

Identyfikacja procedur:
W RPC procedura identyfikowana czterema wartościami:



adres IP serwera;



numer usługi RPC;



numer wersji usługi;



numer procedury w ramach usługi.

Portmapper (nie trzeba tego umieć)



Stały i znany numer portu - 111;



Odwzorowuje numery usług RPC na numery portów i nazwy protokołów transportowych poprzez
które można się dostać do serwera zdalnej procedury.

Poziomy szczegółowości wywołania



Poziom najwyższy – maksimum przezroczystości (wywołanie funkcji zdalnej praktycznie tak jak
lokalnej);



Poziom najniższy - możliwość dokładnej kontroli parametrów komunikacji (wykorzystywany protokół ,
czasy opóźnień itp.).

RMI
(Remote
Method
Invocation)



Mechanizm RMI jest częścią języka Java opracowanego przez firmę Sun (Java Development Kit).



Umożliwia wywoływanie metod obiektów istniejących w maszynie wirtualnej Javy przez obiekty
znajdujące się w innej maszynie wirtualnej – komunikacja via protokół TCP.



Obiekty zdalne jak i lokalne są identyfikowane standardowo, przez referencje.

Ograniczenia:
-  Problemy rozproszonego bezpieczeństwa danych, synchronizacji, odśmiecania pamięci.
-  Możliwe jest tylko wykonywanie metod zdalnego obiektu, a nie dostęp do jego pól (zmiennych).
-  Metody RMI muszą być zadeklarowane w interfejsie rozszerzającym interfejs (extends)

java.rmi.Remote - wygenerowane zostaną odpowiednie procedury (marshalling code).

- Java jest językiem interpretowanym i aplikacje działają wolniej niż ich odpowiedniki skompilowane do

kodu maszynowego.

- Java ma duże wymagania sprzętowe.
- Java wywołuje obiekty z Javy (teraz najnowsze wersje Javy umożliwiają odtwarzanie kodów z innych

języków)

CORBA
(Common
ORB
Architecture)



ORB – Object Request Broker (pośrednik podczas wywoływania procedury – część kodu na maszynei
zdalnej)



Standard komunikacji aplikacji w środowisku rozproszonym realizowanej za pośrednictwem
wspólnego brokera ORB.



Opracowany przez Object Management Group:

http://www.omg.org/

Interfejs CORBA:



Moduły programowe komunikują się z innymi za pośrednictwem własnych brokerów.



Wszyscy brokerzy komunikują się ze sobą w jednakowy sposób (common).



Moduł poznaje charakterystykę interfejsu innego modułu:
- poprzez dynamiczne pobranie definicji interfejsu ze standardowego serwisu: katalogu interfejsów

(interface repository),

- poprzez statyczne wprowadzenie do własnego kodu definicji wymaganych interfejsów



Umożliwia komunikowanie się modułów w różnych językach programowania



Umożliwia komunikowanie się modułów działających w maszynach o różnych architekturach



W tym celu CORBA wprowadza własny język do definiowania interfejsów IDL (ang. Interface Definition
Language)

Interface Definition Language



IDL – uniwersalny język opisu interfejsu.



Definicje interfejsów są niezależne od języków programowania używanych do stworzenia modułów.



Odpowiednie narzędzia przekształcają definicje sformułowane w języku IDL na ich odpowiedniki w
danym języku - m. in. C,C++, Smalltalk, Ada, Cobol, Java.

Własności IDL:



Język IDL umożliwia definiowanie:
- modułów zawierających deklaracje typów, stałych, wyjątków, interfejsów oraz definicje innych

modułów.



Deklaracje interfejsów mogą zawierać:
- deklaracje typów, stałych i wyjątków,
- deklaracje atrybutów i operacji.



Możliwe jest wielobazowe dziedziczenie między interfejsami.

Definicje operacji



Przypominają deklaracje funkcji w języku C.



Każdy z parametrów jest poprzedzony obowiązkowym atrybutem, określającym kierunek przepływu
danych:

-  in – parametr wejściowy (dane przesyłane od klienta do serwera),
-  out – parametr wyjściowy(od serwera do klienta),
-   inout – parametr wejściowy i wyjściowy (dane przesyłane w obu kierunkach).



Listę zgłaszanych wyjątków, poprzedzoną dyrektywą raises, umieszcza się w nawiasach okrągłych za
listą argumentów.

Operacje asynchroniczne



Standardowo CORBA wykonuje operacje synchronicznie tj. blokuje klienta do czasu otrzymania
wyników.



Definicja operacji, która ma być wykonywana asynchronicznie, musi być poprzedzona dyrektywą
oneway:

- nie może ona mieć parametrów z atrybutami out, inout ani zgłaszać wyjątków,
- deklaracja zwracanego typu musi być void.

Technologia
RMI-IIOP



Umożliwia współpracę i pozwala na jednoczesne wykorzystanie w jednym programie Java platform
RMI i CORBA. Dzięki temu klient wykorzystujący RMI-IIOP (RMI Internet Inter-ORB Protocol), może
wywoływać metody zarówno obiektów RMI, jak i obiektów CORBA, a ponadto klient CORBA może
wywoływać metody obiektu, którego używa serwer.

Cechy wspólne RPC, RMI, CORBA:



Umożliwienie komunikowania się modułów oprogramowania (typowe programowanie
rozproszone - bo na rożnych maszynach)



zapewnienie im odpowiedniego poziomu zabezpieczeń w sieci (w programowaniu rozproszonym
największym zagrożeniem jest korzystanie z ogólnodostępnych protokołów, na których zawsze
istnieje niebezpieczeństwo związane ze zwykłym przesyłaniem informacji w sieci)

Porównania:

Podejście

obiektowe



RPC – w znikomym stopniu; docelowym językiem implementacji jest C



RMI – pełne; argumenty i rezultaty mogą być przekazywane albo przez wartość albo przez
referencję



CORBA – pełne; można decydować, które parametry są wejściowe, a które wyjściowe; operacje
mogą zgłaszać wyjątki (od momentu powstania miała możliwość wykonywania w środowisku
rozproszonym modułów różnych języków)

Łatwość

programowania



RPC – wymagana znajomość języka C oraz podstaw zagadnień dotyczących komunikacji poprzez
IP. Konieczność zapoznania się z językiem RPC (ale w sumie najprostsze)



RMI – wymagana znajomość Javy w stopniu zaawansowanym



CORBA – w celu zdefiniowania interfejsu wymagana znajomość IDL, a implementacji – języka
docelowego

Rozpowszechnie

nie



RPC – powszechny; może być traktowany jak część systemu operacyjnego



RMI – szybko się upowszechnia; rozwój nie jest równomierny dla wszystkich platform;
dokumentacja dostępna



CORBA – mało powszechna; mało literatury

RMI staje się popularne, bo Java działa w mobilnych aplikacjach, aczkolwiek najczęściej RPC

[E] Na koniec:



na egzaminie coś było o RPC, RMI i CORBIE, ale nie musimy ich znać – wystarczy umieć
podstawowe informacje (zalety/wady, z jakimi językami wiązać)

26.11.2013

QQS

PRiR

Wykład 8

Systemy klastrowe

Historia superkomputerów



wrzesień 1964 - amerykańska firma Control Data Corporation zaprezentowała skonstruowany
przez Seymona i Thorntona komputer CDC-6600.
- W maszynie tej po raz pierwszy wykorzystano pamięć hierarchiczną, którą wciąż się stosuje

(fizycznie pamięć rozproszona i tam wielopoziomowe pamięci podręczne, kilka poziomów
cache itd.)



Następcą był komputer, CDC-7600 (również autorstwa Craya)
- Po raz 1 zastosowano tu przetwarzanie potokowe



Kolejnym, ale tym razem o architekturze bardziej zbliżonej do naszych komputerów był Cray 1
(Cray odszedł z CDC i założył własną firmę)

Cray-1

- komputer 1-procesorowy, zdolny do wykonywania rozkazów wektorowych w sposób potokowy (pipelining)
- wydajność 160 megaflopsów
- procesor w superkompie cray-1 zawierał 12 potokowych modułów wykonawczych
- nowatorska koncepcja - łańcuchowanie potoków
(...)

Cray X-MP
(multiple
processor)

- firma Cray Research
- zwielokrotniono liczbę procesorów wektorowych i wykorzystano wspólną pamięć dla wszystkich jednostek
PAO
- w najsilniejszej konfiguracji komputer składał sie z 4 jednostek centralnych, które mogły się komunikować
zarówno przez PAO, jak i za pośrednictwem wyspecjalizowanego układu synchronizującego prace
- rozwiązanie, zastosowane w tej maszynie: przetwarzanie symetryczne SMP (symmetric multiprocessing),
które jest z powodzeniem stosowane do dziś m.in. w najnowszych wielordzeniowych procesorach intel core
duo 2 i AMD Athlon

sposobem na ograniczenie kosztów budowy i eksploatacji superkomputera była idea połączenia
standardowych komponentów (np. PC) za pomocą gigabitowego Ethernetu i wykorzystanie ich
jednocześnie do realizacji zaawansowanych obliczeń.

ludzie zastanawiali się, jak wykorzystać słabsze maszyny, żeby zrobić superkomputer; te zwykłe
maszyny PC trzeba połączyć standardowymi liniami (ethernert) i stworzyć takie środowisko
oprogramowania, żeby ta grupa maszyn mogła być wykorzystana do obliczenia 10-tnego problemu.
Tak powstałe grupy komputerów, z zewnątrz widziane jako 1 system, nazwano klastrami, a
poszczególne komputery – węzłami.

Aby uzyskać dużą niezawodność, każdy węzeł wyposażono w specjalne mechanizmy do wykrywania
innego węzła (żeby wiedział, z którym współpracuje, a z którym nie) i żeby mógł przejąć jego zadania,
a także przyłączanie do/odłączanie od węzłów kastra. Oczywiście była to struktura dynamiczna –
węzeł nie tylko sprawdzał, czy nastąpiła awaria, ale umożliwiał też odłączenie/przyłączanie bez
wprowadzania zmian w systemie

ORGANIZACJA PAMIĘCI

Architektura

opis

UMA



jednolity czas dostępu do pamięci



mało wydajne (konflikty wynikające z równoczesnego korzystania z 1-kowego obszaru pamięci przez
wiele jednostek przetwarzających - zbyt duże opóźnienia)

NUMA



każdemu węzłowi przydzielamy oddzielne obszary pamięci, tak aby każdy węzeł miał do swojej
dyspozycji pamięć



pamięć lokalna



nadal jednak brak spójności pamięci

cc-NUMA



dodatkowe mechanizmy spójności pamięci dla NUMA



wszystkie cache obserwowane przez specjalne oprogramowanie



równolegle komputery COMA – tylko na cacheach, ale też architektura CMP

Znacznie efektywniejsze okazało się zastosowanie w systemach SMP wspólnej dla wszystkich
procesorów pamięci cache trzeciego poziomu.

Coraz częstsza technika - architektura CMP (Cellular multiprocessing); pomimo tych innowacji,
zbytnie obciążenie magistrali systemowej jest nadal podstawowym problemem ograniczającym
skalowalność takich systemów.

systemy MPP
- składają się z dużej liczby jednocześnie przetwarzających PE (Processing element)
- w rzeczywistości maszyna MPP jest zbiorem niezależnych procesorów, dysponujących własną PAO;
na 1 komputerze może być kilkaset czy kilka tys. procesorów, umożliwiających budowę
superkomputerów o wydajności większej niż SMP
(...)

System klastrowy (cluster system)



jest systemem rozproszonym



zawiera zbiór połączonych ze sobą siecią samodzielnych komputerów - niezależne jednostki
obliczeniowe systemu (tzw. węzły) posiadają swój własny SO oraz nie dzielą żadnych
komponentów sprzętowych, nie wykorzystują też do komunikacji niestandardowych rozwiązań,
takich jak np. pamięci dzielonej, lecz komunikują się za pośrednictwem zwyklej sieci lokalnej
(klaster nie musi, ale może być zamknięty w 1 obudowie)

generalnie węzły są łączone albo w technologii shared everything - jak w SMP, albo shared
nothing - podobnie jak w MPP; kastry wykorzystują więc z 1 i 2 architektury: wieloprocesorów i
multikomputerów



stanowi jednolity zasób (dla klientów systemów) - klaster składa się z wielu niezależnych
komputerów (równorzędnych), ale musi stanowić dla klienta spójną całość, jednolity zasób
(odpowiednie oprogramowanie)

różnica miedzy klastrem, a systemami SMP

KLASTER

SMP

SKALOWALNOŚĆ



dodając nowy węzeł klastra dodajemy cały
komputer z podsystemami we/wy, pamięcią itd.



łatwiejsze od SMP



nie wymaga zmian w systemie



znaczna rozbudowa wymaga zmian w
innych elementach systemu

AWARIA WĘZŁA



nie przerywa pracy klastra



unieruchamia cały system

LICENCJA NA

OPROGRAMOWANIE



konieczność wykupienia tylu licencji, z ilu węzłów
składa się klaster



SMP jest systemem widocznym z
poziomu SO jako 1 komputer = 1
licencja

różnice w stosunku do typowych systemów rozproszonych

KLASTER

SYSTEM ROZPROSZONY

ANONIMOWOŚĆ
WĘZŁÓW



W klastrach dąży się do anonimowości węzłów



Każdy element systemu rozproszonego
jest rozróżnialny

HIERARCHICZNOŚĆ
WĘZŁÓW



brak



często spotykana w systemach
pracujących z wykorzystaniem
paradygmatu klient/serwer (zadania są
rozdzielane pomiędzy maszynami
poprzez wyspecjalizowaną maszynę)

cechy charakteryzujące systemy klastrowe



skalowalność - zdolność do szybkiej i niezawodnej rozbudowy dla systemu



dostępność - odporność systemu na awarie



otwartość - podatność na rozszerzenia, możliwość rozbudowy systemu zarówno pod względem
sprzętowym, jak i oprogramowania



przezroczystość - wrażenie pracy na 1, zintegrowanym systemie

klasyfikacja klastrów
istnieje wiele sposobów klasyfikacji klastrowa. Najbardziej przejrzystą jest klasyfikacja oparta na roli,
jaką mają odgrywać klastry w zadanym środowisku informatycznym. Wyróżniamy:



klastry wysokiej wydajności (wykorzystywane w nauce)



klastry równoważące obciążenie



wysokiej niezawodności

klastry

wysokiej

wydajności



obliczeniowe/do przetwarzania równoległego



znacznie poprawienie wydajności aplikacji dzięki uruchomieniu ich na wielu jednostkach
przetwarzających



wykorzystują biblioteki wysokiego poziomu tworzące środowiska programowania
równoległego, takie jak MPI lub nieco starsze PVM



równoważenie obciążenia najczęściej jest w gestii samej aplikacji - user pisząc kod musi
zadbać o odpowiednie rozłożenie obciążenia na poszczególne jednostki w celu
optymalnego przyśpieszenia obliczeń (loadbalancing)



np. tani klaster obliczeniowy - typu Beowulf // to najczęściej zbudowany ze zwykłych PC-
tów połączonych Ethernetem; 1 z komputerów pełni rolę stacji sterującej i serwera
plików, pozostałe wyposażono jedynie w procesor , RAM, interfejs sieciowy; pozbawione
dysku, monitora i klawiatury



komputery z takiego klastra pracują pod Linuxem

klastry

równoważące

obciążenie



dla utrzymania bardzo obciążonych usług sieciowych (serwery WWW itd.) lub realizacji
prostych zadań obliczeniowych



klastry tego typu implementuje sie w przypadku, gdy bardziej istotny jest czas reakcji
usługi na żądanie klienta (implementowane gdzie istotny czas reakcji)

wysokiej

niezawodności

(pracy

awaryjnej)



ich celem nie jest zwiększenie wydajności serwerów, ale wyeliminowanie tzw.
pojedynczego punktu awarii



ich działanie polega na rozłożeniu w przypadku wystąpienia awarii 1 z serwerów, jego
zadań na pozostałe serwery w sposób przezroczysty dla userów; ponadto w przypadku
uszkodzenia sieci oprogramowanie przełącza węzły w tryb sieci zapasowych



wykorzystywane w systemach o znaczeniu krytycznym, gdzie usługi świadczone są ciągle
bez przerw (wojsko, reaktory atomowe)

klastry komputerowe na świecie i w Polsce



od wielu lat na liście top500 królują 2 architektury: klastry i komputery masowo równolegle (MPP
= Massively Parallel Processors); przed 2003 rządził MPP, potem klastry (architektura o
największej mocy); w 2013 na liście top500 proporcje wyglądały następująco - Klaster 83% (417),
83 MPP (17%);



najszybszym superkomputerem jest chiński superkomputer Tianhe-2 zaprojektowany w
Narodowym Uniwersytecie Technologii Obronnych, a zainstalowany w Narodowym Centrum
Superkomputerowym w Guanghou. Jego moc obliczeniowa to: 33,86 petaflipsa (biliard operacji
zmiennoprzecinkowych ...)



w Polsce mamy 3 komputery z tej listy: z Akademickiego Centrum Komputerowego, Cyfronet
AGH (113), IMBM Blue Gene z Uniwersytetu Warszawskiego (170)

Zeus - (AGH, teraz 113); ma kilka części, np. na karty graficzne; kilka tesli, do współpracy z wieloma
procesorami CPU, procesory korzystają z wielu kart graficznych; zrównoleglenie obliczeń

obliczenia heterogeniczne - rożne modele; mieliśmy 2 paradygmaty MPI (komunikaty, dedykowany
na procesy - maszyny o lokalnej pamięci) czy OpenPM (dane z pamięcią wspólną; standard dla
kompilatorów zrównoleglających) i GPU (OpenCl - środowisko standaryzujące dla kard graficznych);
obecnie łączy się te modele programowania i tworzy kilka warstw; MPI - programowanie klastrów
(osobne pamięci lokalne).

3.12.2013

QQS

PRiR

Wykład 9

GRID czy CLOUD?

GRIDy i CLOUDy można spotkać w przedsiębiorstwach

GRID



rodzaj rozproszonego computingu (do zadania używamy zasobów zlokalizowanych w rożnych
miejscach i połączonych siecią)



organizuje przetwarzanie danych, zarówno zasoby, jak i userów, lecz nie zarządza nimi centralnie.
Zasoby należą do rożnych właścicieli.

w GRIDzie panuje stała temperatura, stale przepływa powietrze, zachowana jest odpowiednia
wilgotność; superkomputery używają dużo energii; wszystkie centra prowadza monitoring
wykorzystania tego sprzętu, obciążenia procesorów, ich wykorzystania itd.; GRID wykorzystuje
istniejące już zasoby komputerowe, znajdujące się na różnych kontynentach, brak jednak centrum
administracyjnego

pierwszy historyczny przykład GRIDu:
SETI@HOME



każdy komputer podłączony do Internetu może zainstalować oprogramowanie do analizy danych
z radioteleskopu San Mateo CA



Niebo podzielone jest na małe obszary i każdy komputer dostaje kawałek do przeanalizowania w
czasie, gdy jest nieobciążony (zasada screen-savera)



obecnie SETI@home ma 5.5 mln uczestników

przydzielając komputer do obliczeń jego właściciel nie ma gwarancji, że obliczenia nie zostaną w
połowie wyłączone, jedyną gwarancją są wyniki

Dostęp do GRIDu
Trzeba skutecznie rozpoznać użytkownika i dać mu bezpieczny dostęp do zasobów obliczeniowych



Certyfikaty użytkowników (w formacie X.509) umożliwiają autentykację (sprawdzenie
tożsamości) użytkownika.



Autoryzacja na zasoby udzielana w ramach wirtualnych organizacji przez serwisy Virtual
Organization Membership Service (VOMS; organizacja naukowa, z której korzystają biedne kraje).

Trochę statystyki - Enabling Grids for E-science:



54 kraje, 267 węzłów sieciowych



114 000 CPU dostępnych 24/7



20 PB pamięci dyskowej + tape MS



200 wirtualnych organizacji



16 000 użytkowników



150 000 zadań/dzień



15 obszarów tematycznych aplikacji

usery wypełniają kwestionariusz, gdzie podają wymagania aplikacji, jaką chcą uruchomić
(oprogramowanie, biblioteki itd.); potem system GRIDowy analizuje/wybiera ośrodek, gdzie
uruchomienie będzie jak najoptymalniejsze; oprócz tego można liczyć równoległe zadania; system
powinien być przezroczysty - nie ważne, gdzie uruchomi się program, ważny jest wynik

czym jest chmura?
- chmura obliczeniowa (cloud) to coraz modniejszy model przetwarzania, oparty na użytkowaniu

usług dostępnych przez zewnętrzne organizacje (funkcjonalność = usługa); pojęcie związane z
WIRTUALIZACJA; nowy model dostarczania i korzystania z zasobów informatycznych, takich jak
zasoby obliczeniowe (serwerowe), magazynowanie danych, przepustowość sieci, a nawet
aplikacje. Model cechuje się takimi funkcjami, jak samoobsługa na żądanie, duża elastyczność,
implementacja puli zasobów i szeroka weryfikacja usług (pay-as-you-use) i szeroki dostep do
sieci.

...model przetwarzania oparty na użytkowaniu usług dostarczonych przez zewnętrzne organizacje.
Funkcjonalność jest tu rozumiana jako usługa (dająca wartość dodaną użytkownikowi) oferowana
przez dane oprogramowanie (oraz konieczną infrastrukturę). Oznacza to eliminację konieczności
zakupu licencji czy konieczności instalowania i administracji oprogramowaniem. Konsument płaci za
użytkowanie określonej usługi, np. za możliwość korzystania z arkusza kalkulacyjnego. Nie zakupuje
sprzętu ani oprogramowania. Termin „cloud computing” związany jest z pojęciem WIRTUALIZACJI.
Model „cloud computing” historycznie wiąże się z przetwarzaniem w sieci GRID, gdzie wiele
systemów udostępnia usługi korzystając z podłączonych zasobów, z tą różnicą, że w „Cloud
computing” mamy do czynienia z podążaniem zasobów za potrzebami usługobiorcy.

Wikipedia

...nowy model dostarczania i korzystania z zasobów informatycznych, takich jak zasoby obliczeniowe
(serwerowe), magazynowanie danych, przepustowość sieci, a nawet aplikacje. Model cechuje się
takimi funkcjami, jak samoobsługa na żądanie, duża elastyczność, taryfikacja usług (pay-as-you-use),
implementacja puli zasobów i szeroki dostęp do sieci.

NIST (National Institute of Standards and Technology).

Wirtualizacja elastyczne dostosowanie możliwości infrastruktury do potrzeb klientów, co w praktyce
przekłada się na konieczność zwirtualizowania posiadanych zasobów.

GRID a CLOUD
- GRID - ci co maja zasoby i płacą za nie, "oddają" nadmiarowe GRIDy; wykorzystanie czegoś w

CLOUDzie – właściciel chmury kombinuje, na czym można by zarobić (sprzedawanie różnych
usług); dochodzi też kwestia licencji na oprogramowanie – korzystamy z oprogramowania, czyichś
zasobów, a ten ktoś dba o licencję i musi inwestować;

wirtualizacja

- elastyczne dostosowanie infrastruktury do potrzeb klientów, co w praktyce przekłada się na

konieczność zwirtualizowania posiadanych zasobów.

GRID vs CLOUD

GRID

CLOUD



Provider: nauka



Technologia open source



Użytkownik wpływa na infrastrukturę i dostosowuje do
specyficznych zadań



Złożony – do używania wymagana wstępna wiedza



Niepewna jakość usług



Możliwość tworzenia własnych, specyficznych serwisów



Bezpieczeństwo danych: repliki w różnych miejscach



Łatwe współdzielenie danych



Provider: komercja



Technologia proprietary



Użytkownik dzierżawi dostęp do zdefiniowanej
infrastruktury



Prosty w użyciu od „poziomu zero”



Komercyjnie gwarantowana jakość



Brak wysoko-specjalizowanych serwisów aplikacyjnych



Bezpieczeństwo danych: specjalna usługa



Współdzielenie po wykupie dostępu

początek cloudu - obliczenia naukowe, a teraz komercja nawet na najprostszych aplikacjach

OBLICZENIA GPU

procesory CPU



zwiększenie mocy obliczeniowej poprzez zwiększenie częstotliwości taktowania (lata 80-te 1MHz:
obecnie 1-4 GHz) - koszty + bariera technologiczna



procesory wielordzeniowe (pierwsze w 2005 roku) oraz płyty główne wieloprocesorowe

ponieważ procesory przegrzewały się, zaczęto robić procesory wielordzeniowe; równocześnie do
rozwoju CPU mamy rozwój procesorów GPU (graficznych); CPU = Central Procesing Unit, GPU -
Graphical Processing Unit

procesory GPU



zapotrzebowanie na nowy typ procesora graficznego

- koniec lat 80-ych - systemy operacyjne z graficznym interfejsem użytkownika np. Microsoft

Windows

- popularyzacja grafiki trójwymiarowej (m.in. programy dla rządu i wojska, wizualizacje

techniczne, gry …)



układy graficzne funkcjonowały początkowo na zasadzie potoków przetwarzania graficznego o
sztywno ustalonych funkcjach. W przeciągu lat stawały się one coraz bardziej programowalne, co
doprowadziło w efekcie do wprowadzenia pierwszego układu

Procesory Graficzne Odciążyły CPU - programiści zaczęli używać grafiki do liczenia innych rzeczy, niż
tylko grafika, jednak pojawiło się ograniczenie - trzeba operować na bibliotekach graficznych -
programista wykonujący inne obliczenia, niż graficzne musiał używać bibliotek graficznych; aby
dostać się do pamięci procesora graficznego, musiał poznać języki cieniowania (grafika); niestety
wymagania te znacznie zredukowały liczbę programistów.

GPGPU



w okresie 1999-2000 z aplikacji wykorzystujących GPU zaczęli korzystać przede wszystkim
informatycy , ale też badacze różnych dziedzin (obrazowania medycznego i elektormagnertyzmu
…)



GPGPU = obliczenia ogólnego przeznaczenia na układach GPU

Jack Dongarra:
"GPU wyewoluowały do poziomu, na którym wiele poziomów aplikacji implementuje się z łatwością
- programy są szybsze, niż na procesorach wielordzeniowych; w przyszłości będzie się stosować
systemy hybrydowe – procesory wielordzeniowe będą współpracować z graficznymi "

połączenie wielu rdzeni (procesorów wielordzeniowych) z tysiącem procesorów graficznych (proste
jednostki przetwarzające) daje potężną moc obliczeniową

historia GPU



listopad 2006 - firma ATI stworzyła CTM (Close To Metal - elementy kart graficznych,
umożliwiające obliczenia na kartach graficznych)



grudzień 2007 - rozbudowano projekt i powstał CTM (ATI STREAM); konkurencja – Nvidia



8800GTX - pierwszy procesor w architekturze CUDA (Compute Unified Device Architecture) od
NViDii - nowa, bardziej przyjazna architektura pod obliczenia, która jednak nadal wymagała
bibliotek graficznych do programowania - dlatego też NVidia wymyśliła mechanizm, polegający
na dodaniu paru elementów do języka C; w efekcie, w lutym 2007 powstało CUDA C (kompilator
języka C z rozszerzeniami, które pozwoliły programować na CUDA;

ATI i NVIDIA pracowały równocześnie nad tymi procesorami graficznymi; NVidia miała jednak
lepsza reklamę - teraz podaje sie głównie CUDA

Ponieważ kopiowanie z CPU do GPU wiąże się z największym obciążeniem, zunifikowano pamięć,
dzięki czemu już nie trzeba było kopiować danych.

Najpierw powstawały różne kompilatory, potem zdecydowano się na standard:



grupa Kronos (zrzeszająca twórców kart graficznych) stworzyła standard OpenCL; w 2008 roku
wersja 1.0 (zrobiły to AMD i NVidia)



OpenCL – stworzone, aby uniezależnić programowanie kart graficznych od producenta (czerwiec
2008); OpenCL nigdy nie będzie szybszy od NVidii

NVidia i AMD - dwaj najbardziej znaczący producenci kart graficznych

porównanie mocy CPU i GPU:
-  Możliwość obliczeń kilkaset razy szybszych, niż na CPU
-  Odciążenie procesora do zadań obliczeniowych
-  Wysoka skalowalność – można dokładać karty i łączyć je za pomocą CrossFireX (ATI) lub SLI

(NVidia)

Wady:



Na GPU nie można przeprowadzać skomplikowanych obliczeń/ ifów; kod sekwencyjny spowalnia
obliczenia



Mniejszy cache niż w CPU



Uboższe możliwości synchronizacji



Nieliniowy wzrost wydajności (im więcej procesorów strumieniowych, tym większy koszt
współpracy między nimi)



Możliwość wykorzystania tylko przy obliczeniach dających się łatwo zrównoleglić



Błędy zaokrąglenia

10.12.2013

QQS

PRiR

Wykład 10

Message Passing Interface (MPI)

Message passing interface:



standard przesyłania komunikatów między procesami programów równoległych



biblioteka do przesyłania komunikatów (komunikacja między komputerami)



przesyłanie komunikatów miedzy PROCESAMI



rok 1994 - pierwsza implementacja



uruchamia się w C lub Fortranie



program składa się z niezależnych procesów, działających na rożnych danych (MIMD)



każdy procesor ma własną przestrzeń adresową, ale pamięć wspólna przyspiesza



realizuje model przetwarzania współbieżnego MIMD ( Multiple Instruction Multiple Data), a
dokładniej SPMD (Single Program Multiple Data - ten sam kod źródłowy wykonuje się
jednocześnie na kilku maszynach i procesy mogą przetwarzać równocześnie różne fragmenty
danych, wymieniając informacje przy użyciu komunikatów) – wiąże się z tym możliwość
współbieżnych obliczeń wykonywanych na maszynach o zupełnie różnych architekturach (np.
Linux-x86 oraz Solaris-Sparc) czy rezygnacja z koncepcji pamięci dzielonej i wynikające z tego
ogólne uproszczenie programowania.



Realizując ten model, MPI umożliwia:

- Wymianę komunikatów między procesami (Główny nacisk jest położony na wymianę

danych, ale możliwe jest również wysyłanie komunikatów kontrolnych, czy synchronizacja
procesów)

- Uzyskiwanie informacji o środowisku (Typowy przykład to ilość aktywnych proces[-ów/-

orów], czy numer aktualnego procesu)

- Kontrolę nad systemem (Inicjalizacja/kończenie programu, kontrola poprawności

przesyłanych komunikatów itp.)



Wszystkie te rzeczy są realizowane przy minimalnym stopniu skomplikowania kodu źródłowego

[E] MPI a OpenMP?

OpenMP

MPI



realizacja na
wątkach



wątki danego
procesu
współpracują w
ramach pętli i
wykonują ten
proces



Pracuje tylko na
pamięci wspólnej



realizacja na procesach



stosuje sie przy wykonywaniu obliczeń na kilku maszynach o osobnych przestrzeniach
maszynowych (procesy; każdy proces = nowa przestrzeń adresowa)



może pracować na pamięci wspólnej i rozproszonej (ale i tak mamy procesy; jak MPI
uruchomię na wieloprocesorze, to pomimo pamięci wspólnej procesy nie będą mieć do
siebie dostępu)

W przypadku uruchomienia MPI na wieloprocesorze procesy co prawda nie mają do
siebie dostępu, ale zyskujemy na szybkości transferu (pamięć wspólna); w przypadku
pracy w sieci stacji roboczych (pamięć rozproszona) są duże narzuty komunikacyjne i
możemy nie otrzymać przyspieszenia.



identyfikowanie procesów przez numer w grupie (zakres od 0 do n-1; domyślnie zerowy
proces jest masterem (głównym))

Główna różnica między wątkiem, a procesem – praca na różnych przestrzeniach adresowych

Czas w MPI należy mierzyć od rozpoczęcia MPI (przed wysłaniem danych do liczenia) do momentu,
kiedy wszystkie dane zostaną rozesłane (inaczej możemy nie otrzymać przyspieszenia – dla małych
zadań koszta często przewyższają komunikaty). Na wieloprocesorze uzyskujemy dobre
przyspieszenie.

wszystko na 1 wspólnej pamięci, udostępnianie adresu - jeśli sie przemieszcza, to w obrębie 1 pamięci;

Ciekawostka: openmp i mpi były kiedyś płatne, obecnie są standardami
w UNIX public domain, windowsa kupujemy

Zalety MPI

Wady MPI

+ przenośność
+ możliwość zastosowania na wieloprocesorach i heterogenicznych sieciach

stacji roboczych (MPI się dostosowuje, głównie dzięki bibliotekom; działa
to podobnie jak przesyłanie wiadomości w sieci – czyli nie jest zależne od
architektury komputera)

+ poszczególne procesy mogą być wielowątkowe (w szczególności MPI

nadaje się do zrównoleglenia wielopoziomowego – możemy wysyłać
komunikaty/procesy i w ramach procesu tworzyć drugi poziom
zrównoleglenia np. OpenMP; MPI umożliwia komunikację maszyn, a na
każdej maszynie działa proces)

+  dobra efektywność w systemach wieloprocesorowych
+  dobra dokumentacja
+  bogata biblioteka funkcji
+  posiada status public domain
+  przyjął się jako standard

- statyczna konfiguracja jednostek

przetwarzania

- statyczna struktura procesów w trakcie

realizacji programu

- brak wielowątkowości (w PVN można

uaktywnić dowolną liczbę procesów, w
MPI w MPI mamy ustaloną na
początku liczbę procesów
wykonujących zadanie; nowsze wersje
mogą je dynamicznie tworzyć – wtedy
mamy tak zwaną „maszynę wirtualną”
(tworzenie w trakcie działania
programu); w PVN początkowo tworzy
się maszynę wirtualną)

Zaawansowana komunikacja
Główną zaletą MPI przy bardziej złożonych schematach wymiany danych jest ukrywanie przed
programistą szczegółów implementacyjnych oraz możliwość optymalizacji ścieżki przepływu
danych. Wyobraźmy sobie przykładowo, że mamy 8 procesów i pierwszy z nich ma przekazać pewną
porcję danych wszystkim pozostałym (broadcast).

Przypadki BROADCASTu:



sytuacja nieoptymalna (złożoność czasowa procesu przesyłania jest zależna
liniowo od liczby procesów biorących udział w tej operacji)



1 proces wysyła do pozostałych komunikat (komunikat wysłany jest do specjalnej
kolejki, wraz z odpowiednimi adresami; procesy uruchamiamy na rożnych
komputerach)



przesyłanie danych dwukrotnie krótsze, niż poprzednio



dzielimy listę do rozesłania na pół, następnie przesyłamy dane do 2 połówek; na
końcu przesyłane są one poszczególnym procesom (ten, który już je odebrał,
przesyła dalej)



najbardziej optymalny schemat broadcastu danych w obrębie grupy procesów



pierwszy proces wysyła dane do każdej 2-jki (taka kombinacja); proces po
otrzymaniu danych wysyła je do sąsiada

Cechy:



Przezroczystość przesyłania komunikatów – w MPI decyzje (dotyczące wyboru dróg przesyłania
danych) są ukryte przed programistą - może on po prostu założyć, że dane "kiedyś" i "jakoś"
dotrą na miejsce przeznaczenia, a "kiedy" i "jak" - decyduje system i stara się to zrobić w sposób
optymalny.



Wszystkie te rozważania można również przeprowadzić w odwrotną stronę - dla agregacji danych
z kilku procesorów. MPI definiuje zbiór funkcji służących do zbierania danych z kilku procesów.
Typowy przykład to obliczanie sumy elementów wektora na podstawie zbioru sum częściowych
(lub np. wyszukiwanie maksymalnego elementu).



w MPI jest warstwa odpowiedzialna za routing - MPI sam dba o to, aby przesyłanie komunikatów
było jak najbardziej optymalne (sieciowe operacje, które wykonują się bez naszego udziału)

Ważniejsze funkcje MPI

Inicjalizacja/zamykanie programu

nazwa

opis

int MPI_Init(int *argc, char ***argv);



inicjalizuje środowisko wykonywania programu, m.in. tworzy domyślny
komunikator MPI_COMM_WORLD. Dopiero od momentu wywołania
MPI_Init można używać pozostałych funkcji MPI (tu też zaczynamy mierzyć
czas).

int MPI_Finalize();



Funkcja zwalnia zasoby używane przez MPI (zamyka wszystkie procesy) i
przygotowuje system do zamknięcia



Tuż przed tą funkcją wyłączamy stoper

int MPI_Comm_rank(MPI_Comm
comm, int *rank);



Funkcja pobiera numer aktualnego procesu (w obrębie komunikatora comm)
i umieszcza go w zmiennej rank.

int MPI_Comm_size(MPI_Comm
comm, int *size);



pobiera ilość procesów (w obrębie komunikatora comm i umieszcza ją w
zmiennej size)

Przesyłanie informacji
nazwa

opis

int MPI_Send(void *msg, int
count, MPI_Datatype
datatype, int dest, int tag,
MPI_Comm comm);



Funkcja wysyła komunikat typu datatype do procesu numer dest oznaczony znacznikiem
tag w obrębie komunikatora comm.

zmienna

Opis

datatype



Typ komunikatu (każdy ma określoną liczbę bajtów)



Możliwe predefiniowane typy (p. MPI_INT, MPI_FLOAT,
MPI_DOUBLE, MPI_CHAR) lub zdefiniowane przez usera

dest



Określa odbiorcę komunikatu



jeśli uruchomimy 10 komputerów i na nich maszynę wirtualną, to
środowisko samo pamięta numery ich IP (my posługujemy się
numerem procesów, a środowisko przerabia je na IP)

Tag



Liczba w zakresie [0..MPI_TAG_UB]



określa dodatkowy typ komunikatu wykorzystywany przy
selektywnym odbiorze funkcją MPI_Recv



możliwość odbioru wybranych komunikatów

Komunikator
comm



połączenie numeru procesu z jego adresem IP

int MPI_Recv(void *msg, int



Funkcja odczytuje z kolejki komunikatora comm (z ewentualnym blokowaniem do czasu

count, MPI_Datatype
datatype, int source, int tag,
MPI_Comm comm,
MPI_Status *status);

nadejścia) pierwszy komunikat od procesu source oznaczony znacznikiem tag typu
datatype.



Wynik umieszczany jest w buforze msg a status operacji w zmiennej status.



Musi posiadać informację, od kogo pochodzi wiadomość; jeżeli proces ustawi
source==MPI_ANY_SOURCE, to odczytany będzie pierwszy komunikat od dowolnego
procesu. Podobnie, dla tag==MPI_ANY_TAG nie będzie sprawdzany znacznik typu
wiadomości.

zmienna

Opis

status



Bufor stanu, stworzony przez programistę



Dla C pojedynczy element składa się z MPI_SOURCE,
MPI_TAG oraz MPI_STATUS



tablica status określa nam źródło i typ każdego komunikatu z
osobna



pewność poprawnego przesłania informacji

Int
MPI_Get_count(MPI_Status
*status, MPI_Datatype
datatype, int *count);



umożliwia pobranie ilości odebranych komunikatów na podstawie zmiennej stanu



szukaną ilość umieszcza w zmiennej count

Rozsyłanie danych

nazwa

opis

int MPI_Bcast(

void *msg, int count,

MPI_Datatype datatype, int root, MPI_Comm

comm

);



Funkcja rozsyła komunikat do wszystkich procesów w obrębie komunikatora
comm poczynając od procesu root. Pozostałe argumenty - podobnie jak w
MPI_Send().



nie trzeba w pętli wywoływać wielokrotnie send; 1 komenda umożliwia
przesłanie informacji do całej grupy procesów (poczynając od procesu root,
pozostałe argumenty MPI_send() - czyli root przesyła też sam do siebie)

int MPI_Reduce(

void *operand, void *result,

int count, MPI_Datatype datatype, MPI_Op op, int

root, MPI_Comm comm

);



pozwala np. wykonać sumowanie wszystkich częściowych wyników
otrzymanych w procesach i umieszczenie wyniku w zmiennej



„wszyscy do 1”

zmienna

Opis

root



wskazuje, dla którego procesu wynik ma być
umieszczony w zmiennej result



operator, np. MPI_MAX, MPI_MIN, MPI_SUM



można też tworzyć własne operatory



przykład:

MPI_Reduce(&suma_cz, *&suma,1,MPI_FLOAT, MPI_SUM, 0,MPI_COMM_WORLD);

int MPI_Allreduce(

void *operand, void

*result, int count, MPI_Datatype datatype, MPI_Op

op, MPI_Comm comm

);



funkcja podobna do poprzedniej (z tym, że po jej wykonaniu wynik agregacji z
użyciem operatora op znajduje się w zmiennej result we wszystkich
procesach)

int MPI_Scatter(

void *send_buf, int

send_count, MPI_Datatype send_type, void
*recv_buf, int recv_count, MPI_Datatype recv_type,

int root, MPI_Comm comm

);



Funkcja rozproszenia ("scatter") danych między procesami



proces root rozsyła zawartość send_buff między wszystkie procesy. Jest ona
dzielona na p segmentów, każdy składający się z send_count elementów.
Pierwszy segment trafia do procesu 0, drugi do procesu 1 itp.



argumenty, których nazwy zaczynają się na Send mają znaczenie tylko dla

procesu który jest nadawcą.

int MPI_Gather(

void *send_buf, int

send_count, MPI_Datatype send_type, void
*recv_buf, int recv_count, MPI_Datatype recv_type,

int root, MPI_Comm comm

);



Każdy proces w grupie comm wysyła zawartość send_buff do procesu root.
Ten proces układa przysłane dane w recv_buff w kolejności numerów
procesów.



Wysyła częściową strukturę z procesorów i łączy w 1

int MPI_Allgather(

void *send_buf, int

send_count, MPI_Datatype send_type, void
*recv_buf, int recv_count, MPI_Datatype recv_type,

MPI_Comm comm

);



Funkcja ta jest analogiczna do MPI_Gather (jednakże jej wynik jest
umieszczany w recv_buff każdego procesu)



Można tą funkcję traktować jako ciąg kolejnych wywołań MPI_Gather
każdorazowo z innym numerem procesu root

synchronizacja

nazwa

opis

int MPI_Barrier(MPI_Comm comm);



Wywołanie tej funkcji w pewnym miejscu programu powoduje jego czekanie,
aż wszystkie pozostałe jego instancje dojdą do tego miejsca i dopiero potem
ruszy dalej.



gdy mamy wiele procesów, to czasami nam zależy, żeby następną instrukcję
wykonać dopiero, gdy wszystkie procesy skończą dany element; w tym celu
używamy bariery, czyli pewnej przeszkody zatrzymującej procesy

Zasada budowy programu w MPI



wykorzystujemy 1 program dla wszystkich procesów i tylko to, co idzie na danym procesie zależy
od tego czy wprowadzimy ify (sprawdza, czy slave, czy master)

w PVM nie mamy 1 programu, ale mamy program mastera i slave'a; wewnątrz mastera jest
wywołanie PVM_Spawn (nazwa exe-ka); spawn powoduje, że program zaczyna działać na slavie
(master go aktywuje).

maszyna wirtualna musi mieć zapisaną konfigurację; każda maszyna musi mieć uruchomionego
demona