Sieci obliczeniowe - algorytmy równoległe - współczesne superkomputery
Sieci obliczeniowe - komputery i algorytmy równoległe.
Myśląc o superkomputerach mamy na myśli dedykowane wieloprocesorowe stacje robocze, które osiągają wielką moc obliczeniową w oparciu o innowacyjne koncepcje związane z modelem oprogramowania, architekturą oraz najnowsze rozwiązania techniczne z dziedziny techniki cyfrowej. Na przestrzeni lat to podejście uległo przeobrażeniu a dzisiejsze superkomputery są oparte o tak zwane systemy klastrowe.
"Komputer równoległy - klaster - układ niezależnych jednostek obliczeniowych połączonych siecią komunikacyjną.Zwykle każda jednostka posiada niezależną pamięć (Jedna jednostka moze zawierać kilka procesorów ze wspólną pamięcią)."
Możliwości
Takie podejście jest bardzo elastyczne - w odróżnieniu do tradycyjnego superkomputera można zbudować klaster składający się z komputerów o różnej ilości pamięci i szybkości, tak, aby każda jednostka dała swój wkład obliczeniowy do ogólnej mocy obliczeniowej. Przy rozwiązaniach klastrowych pojawiaja się problemy w dziedzinie zarządania pracą takich jednostek.Skupienie dużej liczby jednocześnie pracujących CPU pociąga za sobą podstawowy problem, jakim jest maksymalne wykorzystanie tak zgromadzonej mocy obliczeniowej. W celu jej wykorzystania potrzebne jest posługiwanie się odpowiednimi algorytmami kierującymi pracą takiego klastra, oraz nowe podejście do programowania takich systemów (programowanie równoległe).Programiści musza dzielić obliczenia tak, aby wykonywały się one w równolegle komunikujących się ze sobą węzłach klastra w jak najszybszym czasie.Podział obliczeń stanowi najtrudniejszy i najważniejszy element projektowania programów, tutaj najbardziej uwidacznia się jakość zastosowanych rozwiązań pod względem ich wydajności.Wciąż jednak synchronizacja i spójne działanie wielu sprzężonych jednostek w sposób bardzo efektywny jest problemem otwartym i nieposiadającym jednoznacznego rozwiązania.
Model komputera równoległego
Aby analizować algorytmy równoległe należy ustalić odpowiedni model obliczeń równoległych. Przyjmiemy model maszyny o dostępie swobodnym oznczany jako PRAM - Parallel Random Access Machine. Wiele algorytmów równoległych dla tablic, list, drzew i grafów daje sie łatwo wyrazić w modelu PRAM. Dla tradycyjnego superkomputera (Rys 1) model PRAM składa sie z pewnej liczby identycznych procesorów sekwencyjnych, które mają dostęp do wspólnej pamięci globalnej, wszystkie procesory mogą jednocześnie odczytywać z pamięci globalnej lub do niej zapisywac.Procesory mogą również wykonaywać równolegle różnorodne operacje arytmetyczne i logiczne.Komunikacje pomiędzy procesorami i pamięcią zapewniają bardzo szybkie magistrale synchronizujące i przesyłające dane.
_Rys 1.Schemat organizacji superkomputera _
W przypadku klastra nie istnieją bezpośrednie magistrale między procesorami i pamięcią, a ich rolę
przejmuje interfejs sieciowy, łączący komputery w węzłach klastra.Za pamięc takiej jednostki uważamy
abstrakcyjną pamięć globalną, która składa sie z pamięci komputerów w węzłach (Rys 2).
_Rys 2.Schemat organizacji klastra _
Przy łączeniu poszczególnych węzłów w sieć, znaczenia nabiera topologia jaką tworzymy oraz rodzaj interfejsu sieciowego. Prosta sieć lokalna zastępowana jest skomplikowanym grafem połączeń, a popularne i niedrogie interfejsy sieciowe złożonymi układami, maksymalizującymi wykorzystanie lokalnej magistrali urządzeń i prędkość przekazywania komunikatów. Wszystko po to, by uzyskać jak największą wydajność, zbliżoną do wydajności magistral superkomputerów. Budowa klastra o takich parametrach jest procesem złożonym i wymaga podobnego podejścia jak budowa klasycznych superkomputerów. Jedną z najbardziej powszechnych topologii połączeń jest topologia Fat-Tree, przedstawiona na rys. 3. Przy pomocy kółek zostały zaznaczone przełączniki sieciowe, natomiast komputery symbolizowane są przez prostokąty. W przedstawionym grafie każda para komputerów może komunikować się niezależnie w dowolnym momencie czasowym (zawsze istnieje wolna ścieżka pomiędzy dwoma komputerami, które nie biorą udziału w komunikacji). W związku z tym opóźnienie przy przekazywaniu komunikatów jest zawsze minimalne.
Rys 3.Topologia typu Fat-Tree (Rysunek z „Overview of Recent Supercomputers 2003”, Aad J. van der Steen, Jack J. Dongarra).
Podstawowym założeniem jakie przyjmuje się przy badaniu wydajności algorytmów w modelu PRAM - jest, że czas działania może być mierzony liczbą równoległych dostępów do pamięci, wykonywanych podczas działania algorytmu.To założenie jest prostym uogólnieniem założenia dla zwykłej sekwencyjnej maszyny, o dostępie swobodnym w której czas działania, mierzony liczbą dostępów do pamięci jest asymptotycznie taki sam jak czas działania mierzony jakąkolwiek inną miarą. Tak przyjęte założenie ma swoje rzeczywiste wytłumaczenie - komputery równoległe są zazwyczaj wyposażone w sieć komunikacyjną umożliwiającą realizację abstrakcyjnej pamięci globalnej.Odczytywanie lub zapisywanie danych za pomocą takiej sieci, zachodzi relatywnie wolniej w porównaniu z operacjami arytmetycznymi, logicznymi wykonywanymi przez procesory.
- Zliczanie równoległych dostępów do pamięci w algorytmach równoległych daje dobrą ocenę ich względnej wydajności.
- Czas działania algorytmu równoległego zależy od liczby procesorów na których ten algorytm jest wykonywany oraz od rozmiaru danych wejściowych.
Dostępy do pamięci.
Mówimy, że algorytm dla maszyny PRAM jest algorytmem z jednoczesnym odczytem (CR - conncurent-read), jeśli podczas jego wykonania, wiele procesorów moze czytać jednocześnie z tej samej komórki wspólnej pamięci.Algorytmem z wyłącznym odczytem (ER - exlusive-read), nazywamy algorytm dla maszyny PRAM, w którym nigdy dwa procesory nie mogą jednocześnie czytać z tej samej komórki pamięci. Podobne rozróżnienie wprowadzono w przypadku jednoczesnego zapisu do wspólnej pamięci, dzieląc algorytmy na maszyny PRAM na te z jednoczesnym zapisem (CW - conncurent-write) i te z wyłącznym zapisem(EW- exclusive write).Najpopularniejszymi typami algorytmów są:
- EREW - algorytmy z wyłącznym oczytem i wyłącznym zapisem
- CRCW - algorytmy z jednoczesnym odczytem i jednoczesnym zapisem
Przykład algorytmu równoległego- ustalanie porządku obiektów na liście
Listy na maszynie PRAM można pamiętać tak samo, jak pamięta się listy na maszynie RAM. Jednakże aby operować równolegle na obiektach listy, wygodnie jest związać z każdym obiektem odpowiedzialny za ten obiekt procesor. Załóżmy że jest danych tyle procesorów, ile jest obiektów na liście, oraż że i-ty procesor jest odpowiedzialny za i-ty obiekt. Procesory odpowiedzialne za i-te obiekty mogą operować na nich w stałym czasie. Przypuśćmy, że jest dana n-obiektowa lista L i chcemy dla każdego obiektu listy L obliczyć jego odległość do końca tej listy.Badziej formalnie, jeśli next[] jest wskaźnikiem do następnego obiektu na liście, to chcemy dla każdego obiektu i policzyć wartość d_ taką że:
Jedno z rozwiązań tego problemu polega na przekazywaniu odległości w tył, poczynając od końca listy.Ta metoda ma liniowy czas wykonania, ponieważ k-ty obiekt od końca listy musi czekać, aż zostaną policzone odległości dla wszystkich k-1 obiektów występujących za nim na liście.To rozwiązanie jest w istocie sekwencyjne.
Na Rys. 4. widać jak algorytm LIST-RANK oblicza odległości.Każda częsć rysunku obrazuje stan listy przed wykonaniem jednej iteracji pętli while z wierszy 5-9.
Podsumowanie
Obecnie technologia dostępna dla zwykłego użytkownika dorównuje profesjonalnym rozwiązaniom opartym o drogiej technologii i najnowszych rozwiązaniach z dziedziny oprogramowania. Doskonałym przykładem jest tutaj system operacyjny Linux, który dzięki posiadaniu odpowiednich funkcji jądra systemu pozwala w oparciu o standardowe rozwiązania sprzętowe utworzyć klaster obliczeniowy dużej mocy. Wraz z rozwojem Internetu pojawił się nowy typ przetwarzania danych w oparciu o bardzo rozproszone węzły klastra, jaki stanowi Internet, brak odpowiedniej topologii dyskwalifikuje takie rozwiązania w zastosowaniach profesjonalnych, ale łączna moc obliczeniowa uzyskana z takiego rozwiązania może być znacząca. Jeden z pierwszych programów przetwarzania rozproszonego związanego z szukaniem cywilizacji pozaziemskich SETI oparty jest o ten właśnie model.
Ciekawe linki do publikacji związanych z klastrami obliczeniowymi i linux z funkcjami klastra.
- Klater obliczeniowy TASKU - http://www.task.gda.pl/kdm/holk/
- Linux i funkcje klastra - http://www.klastry.org.pl/technologie.html
- Projekt KLinux - http://athena.wmid.amu.edu.pl
- Przetwarzanie rozproszone - http://www.chip.pl/arts/archiwum/n/articlear_84013.html
Artykuł napisany w oparciu o materiały dostępne w Internecie oraz literatutę informatyczną.
Aby dodawać komentarze musisz być zalogowany!