Obliczenia współbieżne – takie programy, procesy I wątki, które są w trakcie wykonywania w tym samym czasie



Pobieranie 162,69 Kb.
Data12.12.2017
Rozmiar162,69 Kb.

Obliczenia współbieżne – takie programy, procesy i wątki, które są w trakcie wykonywania w tym samym czasie

Obliczenia równoległe – (współbieżność + jednoczesność) – współbieżne, w których poszczególne zadania są wykonywane jednocześnie na wielu rdzeniach jednej lub wielu maszyn Rdzeń = CPU = 1 procesor sekwencyjny (z dokładnością do pewnych

Ograniczeń sekwencyjnych



Obliczenia rozproszone – obliczenia wykonywane z pamięcią lokalną (w systemach), czyli na maszynach wieloprocesorowych z pamięcią lokalną lub w sieciach maszyn (klastrach [komputer tej samej klasy (rodzaju), układ scentralizowany] lub gridach [rożne komputery])

Hiperwątki - W uproszczeniu polega to na tym, że z punktu widzenia programu lub systemu operacyjnego są 2 procesory logiczne. Realizowane jest to poprzez tworzenie dwóch kolejek rozkazów (pochodzących od niezależnych wątków w programie, lub różnych programów) i przełączaniu jednostek wykonawczych między nimi.

Rozszerzenia strumieniowe – Od kilkunastu lat w procesorach ogólnego zastosowania pojawiły się jednostki wykonawcze realizujące w sposób równoległy te same operacje na różnych danych, na ogół zmiennoprzecinkowych, ale o mniejszej precyzji niż podstawowa jednostka wykonawcza zmiennego przecinka. Rozszerzenia te są głównie przeznaczone do szybkiego przetwarzania grafiki oraz multimediów, ale mogą być także wykorzystane do "zwykłych" obliczeń, w tym numerycznych. Oczywiście tam, gdzie wystarczy mniejsza precyzja. Z różnych doświadczeń wynika, że pozwala to na dodatkowe, nawet kilkukrotne przyśpieszenie obliczeń.

Klastry – Klaster to zespół znajdujących się w pobliżu homogenicznych maszyn, najczęściej połączonych szybką, dedykowaną siecią, które są jednolicie zarządzane i mogą być wykorzystywane do wspólnej pracy. "homogeniczne" = oparte na tej samej architekturze procesora, (np. x86, SPARC, PowerPC) i pracujące pod

kontrolą tego samego systemu operacyjnego. - bliskość odnosi się do tego samego lub przyległego pomieszczenia, a najczęściej po prostu oznacza umieszczenie obok siebie na półkach tego samego regału, lub w tej samej szafie



Gridy – Grid (inaczej: metakomputer, komputer globalny) to zbiór luźno powiązanych, rozproszonych geograficznie, heterogenicznych (tzn. składających się z różnych maszyn, pracujących pod kontrolą różnych systemów operacyjnych) zasobów komputerowych.

Konstelacje - zespoły wieloprocesorowych węzłów ze wspólną pamięcią typu SM-MIMD połączone wewnętrzną, szybką siecią: Węzły zawierają na ogół do 16 procesorów połączonych za pomocą sieci z przełącznicą krzyżową. Węzły są natomiast połączone ze sobą tańszą siecią, np. typu Buttery, drzewa, hipersześcianu. Najszybsze obecnie na ±wiecie superkomputery reprezentuj¡ takie właśnie podejście. Tego typu klastry noszą nazwę konstelacji.



Taksonomia Flynna - Bierze się pod uwagę funkcje realizowane przez poszczególne procesory oraz dane, którymi dysponują. Można wyróżnić cztery typy maszyn: 1. SISD (Single Instruction Single Data) - klasyczne i powszechnie używane maszyny sekwencyjne zbudowane według architektury von Neumanna, zawierające jeden procesor i jeden blok pamięci operacyjnej, w której znajduje się program - ciąg instrukcji (a właściwie rozkazów procesora) wykonywanych sekwencyjnie - gdy dany komputer ma kilka procesorów, ale wykorzystywane są one do wykonywania zupełnie niezależnych od siebie programów (np. sesji różnych użytkowników), to możemy go traktować jako zestaw maszyn typu SISD. 2. SIMD (Single Instruction Multiple Data) - Są to maszyny, w których te same operacje wykonywane są jednocześnie na różnych danych; może to być realizowane przez jeden procesor operujący na tablicy danych (komputery wektorowe) albo przez wiele (nawet kilkanaście tysięcy) prostych procesorów wykonujących te same operacje skalarne (tablice procesorów). 3. MISD (Multiple Instruction Single Data) - Do niedawna wydawało się, że maszyny tego typu, wykonujące różne operacje na tych samych danych, s¡ niepraktyczne i jako takie - nie spotykane. Teraz, w obliczu znanych globalnych zagrożeń, które się ujawniły na początku XXI wieku (terroryzm, przestępczość internetowa i tradycyjna o zasięgu globalnym), można sobie wyobrazić komputery deszyfrujące, w których różne algorytmy realizowane na różnych procesorach analizują te same dane. Jeżeli nawet takie maszyny istniej¡, nikt się nimi nie chwali i dlatego ... 4. MIMD (Multiple Instruction Multiple Data). Jest to najważniejszy typ maszyn równoległych; w maszynach takich poszczególne procesory wykonuj¡ różne operacje na różnych danych, jednak stanowiących różne części tego samego zadania obliczeniowego. Maszyny te różnią się przede wszystkim tym, czy korzystaj¡ z jednolitej (globalnej) przestrzeni adresowej czy nie. Inny podział - uzupełniający: Maszyny z pamięcią wspólną, inaczej: współdzieloną, dzieloną, globalną (ang. global, shared memory, w skrócie SM). W maszynach tego typu wszystkie procesory maj¡ tą samą przestrzeń adresową, użytkownik zaś nie musi wiedzieć, gdzie są przechowywane poszczególne struktury danych (obiekty), sięgając do nich zgodnie z regułami zasięgu obowiązującymi w stosowanym przez niego języku programowania. Maszyny z pamięcią lokalną, inaczej rozproszoną (ang. local, distributed memory, w skrócie DM). Do tej klasy należą zarówno maszyny wieloprocesorowe, w których każdy procesor ma swą własną pamięć, jak i sieci komputerowe { w obydwu przypadkach programista dokonuje sam podziału danych. W systemach SIMD jest to prostsze ni» w MIMD i w sieciach, w tych ostatnich bowiem, sięgając do danych innego procesora lokalnego lub organizując wymian¦ danych między komputerami, najczęściej trzeba podać adres explicite.

Elementy równoległości we współczesnych procesorach komputerów osobistych - We współczesnych maszynach tego typu, czyli z jednym rdzeniem, występuje wiele elementów zrównoleglenia, z których najważniejsze to: - przetwarzanie potokowe (ang. pipelining) - Realizacja rozkazu procesora zajmuje przynajmniej kilka taktów, potrzebnych na: pobranie go z pamięci, zdekodowanie, pobranie argumentów dla jednostki wykonawczej (np.: ALU - od ang. Arithmetic Logic Unit - czyli jednostki stałoprzecinkowej, FPU - od ang. Floating Point Unit - jednostki zmiennoprzecinkowej), wykonanie operacji przez jednostką wykonawczą, zapisanie wyników operacji. żeby jednostka wykonawcza nie była bezczynna, kolejne rozkazy s¡ pobierane z pamięci operacyjnej do kolejki (potoku). W trakcie wykonywania operacji przez jednostką wykonawczą są zatem przygotowywane dla niej nowe dane wejściowe z następnych rozkazów i wysyłane wyniki poprzednich. - rozszerzenia strumieniowe - Od kilkunastu lat w procesorach ogólnego zastosowania pojawiły się jednostki wykonawcze realizujące w sposób równoległy te same operacje na różnych danych, na ogół zmiennoprzecinkowych, ale o mniejszej precyzji niż podstawowa jednostka wykonawcza zmiennego przecinka (FPU). Rozszerzenia te są głównie przeznaczone do szybkiego przetwarzania grafiki oraz multimediów, ale mogą być także wykorzystane do "zwykłych" oblicze«, w tym numerycznych. Oczywiście tam, gdzie wystarczy mniejsza precyzja. Z różnych doświadczeń wynika, »e pozwala to na dodatkowe, nawet kilkukrotne przyśpieszenie obliczeń. - hiperwątki (np. w Pentium 4) - W uproszczeniu polega to na tym, »e z punktu widzenia programu lub systemu operacyjnego s¡ 2 procesory logiczne. Realizowane jest to poprzez tworzenie dwóch kolejek rozkazów (pochodzących od niezależnych wątków w programie, lub różnych programów) i przełączaniu jednostek wykonawczych między nimi.

Przełącznice krzyżowe - Zapewnienie każdemu procesorowi takiego samego czasu dostępu do każdego modułu pamięci realizowane jest tylko w systemach z przełącznicą krzyżową (ang. Crossbar switch). Jeżeli założymy, że komputer składa się z p procesorów i p bloków pamięci (najczęściej procesory s¡ sprzedawane w modułach razem z blokami pamięci, które - oczywiście - potem stanowią część pamięci wspólnej), to wymaga to p2 przełączników. Wówczas, gdyby na przykład wszystkie procesory chciały odczytać jednocześnie dane z pamięci operacyjnej, czas wykonania tej instrukcji byłby minimalny { taki jak dla jednego procesora. Jednak to rozwiązanie jest dość drogie, koszt jest rzędu O(p2).

sieci Omega - Rozwiązanie pośrednie polega na zastosowaniu wielostopniowej przełącznicy krzyżowej, w której jeden przełącznik obsługuje kilka wejść i kilka wyjść, np. w przypadku 2x2 przełącznik krzyżowy będzie miał postać:

Każdy pakiet z informacją zawiera pole adresowe, w którym na początku jest zapisany adres d modułu docelowego pamięci reprezentowany bitowo. Działanie przełącznika znajdującego się w i-tej warstwie (stopniu) polega na tym, że wysyła on pakiet wejściowy w górę - w stronę wyjścia "0" - gdy i-ty bit adresu docelowego di jest równy "0", za± w dół - w stronę wyjścia "1" - gdy jest on równy 1.

Parametry opisujące topologie maszyn DM-MIMD - Maszyny te różnią się sposobem połączeń par procesor-pamięć (dalej będziemy dla uproszczenia pisali po prostu o procesorach, pamiętając że w tej klasie maszyn każdemu procesorowi towarzyszy prywatny moduł pamięci), czyli tzw. topologię. Topologie można porównywać biorąc pod uwagę dwa parametry liczbowe: średnica d - jest to największa odległość między procesorami w komputerze, tzn. maksymalna (po parach: procesor nadawca - procesor adresat) liczba kanałów łączących dwa procesory, przez które przechodzi pakiet (komunikat) od procesora „nadawcy" do procesora „adresata", zgodnie z przyjętym algorytmem routingu; zakłada się, że routing jest racjonalny, tzn. zawsze się wybiera najkrótszą drogą między procesorami. przekrój poªówkowy PP (ang. bisection width) { jest to najmniejsza liczba kanałów, po usunięciu których system będzie podzielony na dwie równe części; wielkość ta świadczy o tym, ile komunikatów może być przesyłanych jednocześnie






Definicja drzewa grubego - We współczesnych maszynach jest to łagodzone przez zwiększanie liczby połączeń (oraz przełączników w drzewach dynamicznych) w miarą zbliżania się do korzenia. Taka zmodyfikowana topologia nosi nazwą grubego drzewa (ang. fat tree).

Definicja hipersześcianu – hipersześcian - inaczej hiperkostka (ang. hypercube). Hipersześciany tworzy się w nastapujący sposób: - hipersześcianem wymiaru 0 jest pojedynczy procesor bez etykiety, - hipersześcian wymiaru n tworzy się kopiując dwukrotnie i łącząc parami odpowiadajęce sobie węzły dwóch kopii hipersześcianu wymiaru n-1, a następnie dodając (w sensie konkatenacji) "0" do etykiet procesorów jednej z kopii, a "1" do drugiej.

Maszyny ccNUMA - W przypadku rozwiązania hardware'owego, do przyspieszenia operacji na danych znajdujących się w elementach pamięci innych zespołów służy pamięć typu cache. Musi ona działać tak, by zapewnić spójność danych w całym systemie (ang. Cache coherency). Stąd wzięło się oznaczenie tego rodzaju maszyn wieloprocesorowych - ccNUMA.

Routing kanalikowy - W routingu kanalikowym pakiet jest dzielony na bardzo małe części, tzw. flity (ang. flit, skrót od ow-control digit). Pierwszy flit, tzw. nagłówkowy (ang. header it) „toruje" drogą pozostałym. Oczywiście, odbywa się to według ustalonego wcześniej algorytmu routingu (np. w siatkach 2D, według zasady routingu XY: najpierw ruch w poziomie aż do osiągnięcia odciętej procesora przeznaczenia, potem ruch w pionie w kierunku procesora przeznaczenia"). Jak tylko pierwszy flit – nagłówkowy - zostanie przesłany, to, o ile kanał między procesorami nie jest zajęty, podążają za nim następne.

Na czym polega SSI - Dąży się do tego, by użytkownik miał wrażenie, jakby wszystkie maszyny stanowiły jeden komputer z jednolitym systemem plików, programem szeregującym zadania (ang. scheduler), który kierowałby je do jednostki najmniej obciążonej (ang. load balancing), procesy zaś mogły się komunikować tak, jak procesy jednej maszyny, niezależnie od tego, gdzie zostały uruchomione.

Migracje - W wymienionych systemach występują również migracje procesów, czyli przenoszenie programów w trakcie wykonywania z jednego na drugi, mniej obciążony komputer w klastrze. Dzięki wykorzystywaniu mechanizmu punktów kontrolnych (ang. checkpoints), w których regularnie jest zapisywany stan procesu, po przeniesieniu na inną maszyną, proces jest wznawiany od ostatniego punktu kontrolnego, a nie uruchamiany od początku. Mechanizm ten, poprzez wyrównywanie na bieżąco obciążenia maszyn, znakomicie poprawia wydajność klastra oraz przyśpiesza obliczenia.

Podstawowe narzędzia oprogramowania służące do zrównoleglenia - W środowisku maszyn równoległych będziemy mieli do dyspozycji wszystkie te elementy oprogramowania,które występują na maszynach sekwencyjnych oraz inne, specyficzne dla maszyn równoległych. Wymienimyteraz te które występują we wszystkich środowiskach, niezależnie od rodzaju stosowanej pamięci(wspólna/lokalna): 1. System operacyjny

Oczekujemy od niego efektywnego, dynamicznego uruchamiania oraz przydziału zadań do procesorów,

dobrej skalowalności. 2. Języki wysokiego poziomu – rozszerzenia Chcemy by można w nich było wyrażać równoległość naszego zadania w wygodny - jasny i zwięzły sposób; najłatwiej za pomoc¡ dyrektyw zrównoleglających dodawanych do programów sekwencyjnych, które są na innych maszynach uważane za komentarze (łatwiej przenosić kod) 3. Kompilatory powinny umieć zrównoleglać automatycznie (opcje) w sposób bliski optymalnemu; ponadto muszą rozumieć dyrektywy 4. Biblioteki procedur numerycznych Procedury te same wykorzystuj¡ równoległość, dzięki czemu możemy tworzyć aplikacje równoległe pisząc sekwencyjne programy, które wywołują odpowiednie procedury z biblioteki. 5. Biblioteki procedur do sterowania zadaniami

Jest to narzędzie trudniejsze niż dyrektywy zrównoleglające kompilatorów, ponieważ algorytm obliczeniowy

od początku musi być zakodowany w sposób uwzględniający równoległość. Daje on jednocześnie

dużo większe możliwości efektywnej implementacji algorytmu, poprzez dekompozycję wykorzystującą

jego wewnętrzną strukturę. 6. Mechanizm synchronizacji dynamicznej zadań - bariera

Bariera polega na tym, że przejście do następnego etapu procesu obliczeniowego następuje po zrealizowaniu

przez wszystkie procesory biorące udział w obliczeniach wszystkich instrukcji etapu poprzedniego, tzn. wszystkie zadania muszą dojść do punktu gdzie jest ustawiona, zanim którykolwiek będzie mógł

pójść dalej. 7. Narzędzia do wspomagania programowania, szczególnie graficzne narzędzia do projektowania, uruchamiania (ang. debugging) programów równolegªych. Są to zagadnienia dużo bardziej skomplikowane niż w środowisku sekwencyjnym. Ze względu na losowy przydział zadań do procesorów oraz również losowy czas komunikacji, dwa kolejne uruchomienia programu równoległego dostarczaj¡ różnych wyników pośrednich - za każdym razem jest inna kolejnść, a wersji asynchronicznej również wartość, wyprowadzanych danych. Ponadto instrukcje wyprowadzające wyniki mogą same wpływać na zachowanie programu. 8. Mechanizmy do uruchamiania zadań oraz równomiernego rozkładu obciążenia komputerów w klastrach i gridach (programy szereguj¡ce, ang. schedulers), w tym do migracji działających procesów od punktu ostatniej rejestracji stanu (ang. checkpoint, snapshot) w obrębie klastra oraz ponownego uruchamiania programu w gridzie z którego jakaś jednostka się odłączyła lub utracona została z niż łączność. 9. Mechanizmy zapewnienia bezpieczeństwa w gridach



Definicja wątku - Wątek (ang. thread) jest pojedynczą scieżką sterowania w całym przebiegu programu

Najczęściej jest on instancją procedury obliczeniowej (metody), posiadającą prywatne dane lokalne, mającą dostęp do danych globalnych zgodnie z obowiązującymi w danym języku oraz środowisku regułami zasięgu. W systemie operacyjnym UNIX, zgodnie ze standardem POSIX, każdy wątek dziedziczy przestrzeń adresową procesu który go powołał.



Definicja zamka - Zamek służy do ochrony pewnych fragmentów kodu przed wejściem do nich więcej niż jednego wątku. Taki fragment jest związany najczęściej z korzystaniem z globalnych struktur danych lub urządzeń peryferyjnych. Nazywamy go sekcją krytyczną, a zatem zamek pozwala na kontrolowany (synchronizowany)

dostęp do sekcji krytycznej.



Zamek pisarze-czytelnicy - Jest to specyficzny rodzaj zamka, służący do zamknięcia sekcji krytycznej jedynie wtedy, gdy jeden z wątków zmienia dane globalne. W pozostałych okresach możliwe jest więc jednoczesne czytanie danych przez wiele wątków.

Semafor - Jest to mechanizm niższego poziomu niż zamek, opierający się na operacji inkrementacji i dekrementacji pewnej zmiennej systemowej s. Według definicji klasycznej, semafor s to zmienna całkowita przybierająca jedynie wartości nieujemne. Po nadaniu semaforowi s wartości początkowej operacje na s są wykonywane przez wywołania procedur wait(s) (czekaj) oraz signal(s) (prześlij sygnał).

Komunikacja synchroniczna - Proces wysyłający jest wstrzymywany, dopóki nie będzie gotowy proces odbierający i vice-versa. Następne instrukcje obydwu programów s¡ wykonywane po zakończeniu transmisji. Przykłady: spotkania (ang. rendezvous) w Adzie, rozmowa telefoniczna, wysyłanie faksów.

Komunikacja asynchroniczna - Proces wysyłający wysyła dane, kiedy jest mu to wygodne. Podobnie proces odbierający czyta je, kiedy uważa to za stosowne. W międzyczasie dane s¡ przechowywane w buforach. Przykład: poczta zwykła i elektroniczna, automatyczna sekretarka.

Operacja blokująca - Polega ono na tym, że następna instrukcja w procesie wysyłającym lub odbierającym komunikat będzie wykonana dopiero po zakończeniu operacji wysyłania lub odbierania.

Operacja nieblokująca - W tym przypadku przejście do następnej instrukcji w procesie wysyłającym lub odbierającym następuje zaraz po zainicjowaniu (czyli nie czekając na zakończenie) operacji wysyłania lub odbierania komunikatu.

Demon - (ang. daemon to taki serwer (program który dostarcza serwisu, tzn. udostępnia pewien zasób innym programom pracującym gdzieś w sieci), który jest dostępny cały czas. Uruchamiany jest najczęściej zaraz po włączeniu komputera. Program użytkownika według tej terminologii jest zatem klientem (programem używającym zasobu) demona.

RPC (ogólnie) i jak się zrównolegla aplikacje które z tego mechanizmu  korzystają - Inna metoda realizacji obliczeń w środowiskach z pamięcią lokalną, nie wykorzystująca komunikatów polega na zlecaniu przez jeden procesor innemu wykonania zadania obliczeniowego na dostarczonych danych. Nazywamy ten mechanizm wywołaniem zdalnej procedury (ang. remote procedure call - RPC). Metoda ta, choć może być wykorzystywana na maszynach wieloprocesorowych z pamięcią lokalną, została opracowana z myślą o obliczeniach sieciowych i takim kontekście ją omówimy bliżej. W przypadku gdy aplikacją równoległa tworzymy wykorzystując mechanizm RPC, czyli wywołania zdalnejprocedury, wymiana informacji między komputerami odbywa się za pośrednictwem parametrów tej procedury.Oznacza to, iż odebranie danych wyjściowych od zdalnego serwera następuje dopiero po zakończeniu działaniaprocedury i po powrocie sterowania do programu wywołującego. Powoduje to pewne problemy z uzyskaniemrównoległości obliczeń - nie uzyskamy jej przecież uruchamiając kolejne zdalne procedury sekwencyjnie!Zrównoleglenie można uzyskać na kilka sposobów, z których najprostsze to: 1. Program główny uruchamia zdalne procedury z różnych współbieżnych (niekoniecznie równoległych) wątków. Jeżeli zdalne zadania obliczeniowe muszą wymieniać dane między kolejnymi iteracjami, są one uruchamiane w pętli, w której po wywołaniu zdalnej procedury jest bariera oraz instrukcje przepisania wartości zmiennych wyjściowych z procedury zdalnej do globalnych struktur danych. Potem w każdym wątku następuje odczytanie nowych wartości parametrów wejściowych z globalnych struktur danych i ponowne wywołanie zdalnej procedury, itd. 2. Procedury zdalne są uruchamiane z niezależnych wątków. Zawierają instrukcje wymiany danych za pomocą komunikatów. W przypadku obliczeń synchronicznych są one blokujące lub nieblokujące poprzedzające barierę. 3. Procedury zdalne się uruchamiane sekwencyjnie w sposób nieblokujący. Wymiana danych następuje za pomocą komunikatów.

Podstawowe modele obliczeń równoległych - Najważniejsze modele (architektury systemów oprogramowania) stosowane w obliczeniach równoległych,zarówno na maszynach z pamięcią wspólną, lokalną, jak i w sieciach (klastrach i gridach), to: 1. Równoległość danych (ang. data parallelism) - polega ona na partycji dziedziny i wykonywaniu operacji na jej różnych fragmentach przez różne procesory; jest to software'owa realizacja SIMD 2. Graf zadań (ang. task graph) - cała aplikacja składa się z kilku procesów, które muszą być uruchamiane w odpowiedniej kolejności, zdefiniowanej w pliku znakowym za pomoc¡ specjalnego języka lub bezpośrednio za pomocą interfejsu graficznego. Zadania muszą mieć raczej dużą ziarnistość; jest to często stosowane podejście w gridach (Condor, Globus, UNICORE) 3. Pula/zbiornik/rezerwuar pracy (work pool) - dynamiczna alokacja zadań do procesorów (mogą one tworzyć kolejkę FIFO), zadania muszą się cechować dużym stopniem niezależności/asynchronizmu; uwzględnia się tutaj aktualne obciążenie procesorów (szybszy lub mniej obciążony będzie częściej pobierał zadania); stosowana często w obliczeniach asynchronicznych na maszynach z pamięcią wspólną oraz w klastrach i gridach. 4. Sieć węzłów równouprawnionych (ang. peer-to-peer, P2P)

- poszczególne procesory (komputery) wymieniaj¡ informacje tylko że ze swoimi sąsiadami (określanymi w zależności od zadania); struktura ta nadaje się przede wszystkim do obliczeń asynchronicznych, w tym związanych ze sterowaniem w systemach rozproszonych (np. różnego rodzaju sieciach) 5. Struktura hierarchiczna dla 2 poziomów: Master-Slaves/Master-Workers/farma (ang. farm) W odróżnieniu od systemów równoległego przetwarzania danych (np. baz danych w bankach), gdzie podstawową architekturą systemu oprogramowania jest: "wielu klientów - jeden serwer", w obliczeniach numerycznych stosuje się architekturą odwrotną: "jeden klient - wiele serwerów", Jest to struktura hierarchiczna, w której klient pełni rolę koordynatora, a serwery - jednostek lokalnych. Informacja jest przekazywana w dół (parametry zadań lokalnych, zmienne koordynujące), a po wykonaniu obliczeń przez jednostki lokalne w górę, aby wyznaczyć nowe wartości zmiennych koordynujących, prowadzące do osiągnięcia rozwiązania globalnego dla całego systemu. Model ten dotyczy obliczeń synchronicznych. 6. Producent-konsument, potok (ang. producer-consumer; pipeline) Przepływ informacji jest tutaj jednokierunkowy; żeby wolna jednostka nie wstrzymywała szybkiej, zadania producenta i konsumenta muszą być zrównoważone 7. Struktury hybrydowe mogą być najprzeróżniejsze, np.: potok z wieloma producentami

konsumentami oraz pul¡ pracy, równoległość danych z kolejką FIFO, master/slaves z dynamiczną partycją dziedziny, itp.

Instrukcje Lindy – out(„cube”,4,64) – wrzuca rekord do przestrzeni krotek, eval – tworzy żywą krotkę (zwykle tworzony jest nowy proces), in(„simple”, ?i) – usuwa rekord, rd(„cube”,8,?i) – czyta wartość z przestrzeni krotek


Przestrzeń krotek - Linda to rozszerzenie C/C++ lub Fortranu o kilka prostych instrukcji, służących do zapisywania i pobierania rekordów (tzw. krotek) z globalnej bazy danych (tzw. przestrzeni krotek) oraz tworzenia

nowych procesów (tzw. żywych krotek). Ta globalna baza danych może być rozproszona, to znaczy różne rekordy mogą być przechowywane w pamięciach różnych procesorów, jest ona globalna w tym sensie, że wszystkie jej obiekty s¡ tak samo dostępne dla wszystkich procesów. Wygoda polega na tym, że procesy biorące udział w obliczeniach w łatwy sposób identyfikują rekordy, a mianowicie podając (ustalone wcześniej) wartości pewnych pól. Mogą to być na przykład stringi, konkretne liczby, itp. Dzięki temu możemy traktować Lindę jako narzędzie do emulacji pamięci wspólnej. Zaletą tej wirtualnej pamięci wspólnej w porównaniu ze zwykłą jest to, że programista aplikacji nie musi się obawiać o spójność danych. Sama Linda zapewnia kontrolą dostępu do przestrzeni krotek, a zatem semafory czy zamki nie są potrzebne. Synchronizacja procesów odbywa się w Lindzie również poprzez krotki.



Semantyka instrukcji where - Nadawanie wartości przez maskę (dotyczy całych tablic). Tylko niektóre elementy tablicy otrzymuj¡wartość, w zależności od wyniku operacji logicznej wykonywanej na elementach tablicy:

real, dimension(1:10, 1:20) :: a, bwhere (a < 10)a = sin(a) + belsewhereb = a**2 ! '**' to w Fortranie operator potęgowaniaend where Uwaga! Jeżeli argumentem jakiejś standardowej funkcji matematycznej jest tablica, to funkcja ta jest liczona niezależnie dla wszystkich elementów. Podobnie jest z operatorami, zarówno unarnymi jak i

binarnymi. W szczególności * jest mnożeniem tablic po elementach, czyli dla macierzy real, dimension(1:10, 1:20) :: a, b, c c=a*b

Semantyka instrukcji forall - Modyfikacja tablic w wyniku sprawdzania wartości wyrażenia skalarnego typu logicznego "po elementach" (maski), przy czym: - w odróżnieniu od pętli do kolejność wykonywania instrukcji jest niezdefiniowana - możliwe jest zastosowanie zrównoleglenia; wówczas po każdej instrukcji bloku jest bariera real, dimension(1:10, 1:10) :: a, b ! liczenie odwrotności elementów macierzy przy pominięciu elementów zerowych

forall (i=1:10, j = 1:10, a(i,j) /= 0) b(i,j) = 1./a(i,j) end forall ... end do



Język dyrektyw HPF - jak się realizuje zrównoleglenie - Zadaniem programisty jest podzielenie struktur danych i ewentualnie wskazanie kompilatorowi, które fragmenty kodu (np. pętle) mogą być wykonywane równolegle. Tworzenie aplikacji równoległej realizuje kompilator, który tłumaczy kod ¹ródªowy na program typu SPMD (Single Program Multiple Data),wykonywany przez poszczególne procesory. W programie, występią podstawowe dyrektywy HPF realizujące podział i przydział danych. Są to następujące dyrektywy: - deklaracja n-wymiarowej tablicy procesorów o nazwie nazwa tab proc: !HPF$ PROCESSORS nazwa_tab_proc(p1, p2, ..., pn)

pi oznacza tutaj liczbę procesorów wirtualnych wzdłuż i-tej współrzędnej - rozkład tablic na tablicę procesorów:

!HPF$ DISTRIBUTE lista_tablic ONTO nazwa_tab_proc - wyrównanie tablic tablica1 i tablica2:



!HPF$ ALIGN tablica1 WITH tablica2 Dyrektywa ta służy do wzajemnego ułożenia tablic, tak aby dzieląc między procesory jedną z nich automatycznie uzyskiwać podział i przydział do procesorów części drugiej.

(*,:,BLOCK(m),CYCLIC(m)) a także dyrektywy PROCESSORS - W dyrektywie DISTRIBUTE, dla każdej współrzędnej tablicy możliwe są trzy sposoby rozkładu: 1) * { rzutowanie (nie ma rozkładu), 2) BLOCK(mi) - rozkład blokowy; mi oznacza liczbę elementów w spójnym obszarze, według współrzędnej i (długość "kawałka"), przypisanych do tego samego procesora wirtualnego, musi być spełniony warunek: mi * pi >=ni; domyślnie przyjmuje się mi = ni=pi 3) CYCLIC(mi) - rozkład cykliczny, znaczenie mi takie jak poprzednio; domyślnie przyjmuje się mi = 1.



©operacji.org 2017
wyślij wiadomość

    Strona główna