Beowulf HOWTO

Autor: Jacek Radajewski i Douglas Eadline
v1.1.1, 22 październik 1998
Wersja polska: Adam Byrtek alpha@irc.pl
v1.0, lipiec 1999

Ten dokument jest wprowadzeniem do architektury superkomputerów Beowulf i dostarcza podstawowych informacji na temat programowania równoległego, wraz z odnośnikami do bardziej szczegółowych dokumentów oraz stron WWW.

1. Wstęp

1.1 Zastrzeżenie

Nie ponosimy żadnej odpowiedzialności za jakiekolwiek błędne informacje zawarte w tym dokumencie, ani za uszkodzenia które mogą one spowodować.

1.2 Prawa autorskie

Copyright © 1997 - 1998 Jacek Radajewski and Douglas Eadline. Udzielono zezwolenia na dystrybucję i modyfikowanie tego dokumentu zgodnie z licencją GNU General Public Licence.

1.3 Informacje o dokumencie

Jacek Radajewski rozpoczął pracę nad tym dokumentem w październiku 1997, niedługo potem dołączył do niego Douglas Eadline. W przeciągu kilku miesięcy dokument Beowulf HOWTO znacznie się rozrósł, i w sierpniu 1998 został podzielony na trzy dokumenty: Beowulf HOWTO, Beowulf Architecture Design HOWTO, oraz Beowulf Installation and Administration HOWTO. Wersja 1.0.0 Beowulf HOWTO została wydana w ramach Linux Documentation Project (Projektu Dokumentacji Linuxa) 11 października 1998. Mamy nadzieję, że to jedynie początek tego, co stanie się wkrótce Beowulf Documentation Project (Projektem Dokumentacji Beowulfa).

1.4 Informacje o autorach

1.5 Podziękowania

Pisanie Beowulf HOWTO było długim procesem, zakończonym dzięki wielu osobom. Chciałem podziękować następującym ludziom za pomoc i wkład w ten dokument.

2. Wstęp

Jako że wydajność sprzętu komputerowego i sieciowego wciąż rośnie, a jego ceny spadają, bardziej praktyczne niż kupowanie bardzo kosztownego superkomputera staje się budowanie równoległych systemów obliczeniowych ze składników dostępnych w każdym sklepie. W rzeczywistości wskaźnik wydajności do ceny maszyny typu Beowulf jest od trzech do dziesięciu razy wyższy niż tradycyjnych superkomputerów. Architektura Beowulf jest łatwo skalowalna, łatwa w budowie i płaci się jedynie za sprzęt, jako że większość oprogramowania jest darmowa.

2.1 Kto powinien czytać ten dokument?

To HOWTO jest zaprojektowane dla osoby mającej przynajmniej podstawowe doświadczenie z systemem operacyjnym Linux. Znajomość technologii Beowulf czy rozumienie bardziej złożonych koncepcji związanych z systemami operacyjnymi i sieciami nie jest konieczne, ale podstawowa wiedza o przetwarzaniu równoległym będzie przydatna (w końcu musisz mieć jakiś powód, czytając ten dokument). To HOWTO nie odpowie na wszystkie możliwe pytania na temat Beowulf'a, ale być może da ci pomysły i poprowadzi we właściwym kierunku. Celem tego dokumentu jest udzielenie podstawowych informacji, oraz odnośników do bardziej zaawansowanych dokumentów.

2.2 Czym jest Beowulf?

Famed was this Beowulf: far flew the boast of him, son of Scyld, in the Scandian lands. So becomes it a youth to quit him well with his father's friends, by fee and gift, that to aid him, aged, in after days, come warriors willing, should war draw nigh, liegemen loyal: by lauded deeds shall an earl have honor in every clan. Beowulf to najstarszy zachowany poemat epicki w języku angielskim. Jest to opowieść o bohaterze dysponującym wielką siłą i odwagą, który pokonał potwora zwanego Grendel. Patrz do działu Historia aby dowiedzieć się więcej o walecznym Beowulf'ie.

Prawdopodobnie istnieje co najmniej tyle definicji Beowulf'a, ile ludzi którzy budowali lub korzystali z architektury superkomputera Beowulf. Niektórzy twierdzą że system może zostać nazwany Beowulf tylko jeśli został zbudowany tak samo, jak oryginalna maszyna NASA. Inni zmierzają do drugiej skranności, nazywając imieniem Beowulf każdy system stacji roboczych wykonujących kod równoległy. Moja definicja Beowulf'a mieści się mniej więcej pośrodku, i jest oparta na wielu opiniach z listy dyskusyjnej Beowulf'a:

Beowulf to wielo-komputerowa architektura która może zostać użyta do obliczeń równoległych. Jest to system, który na ogól składa się z jednego węzłą-serwera i jednego lub więcej węzła-klienta połączonego przez Ethernet lub jakąś inną sieć. Jest to system zbudowany w oparciu o powszechnie dostępne komponenty sprzętowe, jak każdy PC zdolny do uruchomienia Linuxa, standardowe karty Ethernet i switch'e. Nie zawiera żadnych unikalnych komponentów sprzętowych i jest łatwy w tworzeniu. Beowulf korzysta również ze zwykłego oprogramowania, jak system operacyjny Linux, Parallel Virtual Machine (PVM) oraz Message Passing Interface (MPI). Węzeł-serwer kontroluje cały klaster i udostępnia pliki klientom. Pełni on także funkcję konsoli klastra i jest jego bramą do zewnętrznego świata. Duże maszyny Beowulf mogą posiadać więcej niż jeden węzeł-serwer, oraz inne węzły stworzone dla specyficznych zadań, na przykład konsole lub stacje monitorujące. W większości przypadków węzły-klienci w systemie Beowulf są głupie, im głupsze tym lepiej. Węzły są konfigurowane i kontrolowane przez węzeł-serwer, i robią tylko to, co kazano im robić. W konfiguracji bezdyskowej klienci nie znają nawet swojego adresu IP lub nazwy, dopóki serwer im ich nie poda. Jedną z podstawowych różnic pomiędzy Beowulf'em a architekturą Cluster of Workstations (COW) jest to, że Beowulf zachowuje się bardziej jak jedna maszyna, niż wiele stacji roboczych. W większości przypadków węzły-klienci nie posiadają klawiatur czy monitorów, a dostęp do nich jest możliwy jedynie przez odległe logowanie bądz opcjonalny terminal szeregowy. Wezły Beowulf można sobie wyobrazić jako pakiej CPU + pamięć, który może zostać podłączony do klastra, tak jak CPU czy moduł pamięci może zostać dołączony do płyty głównej.

Beowulf to nie żaden specjalny pakiet oprogramowania, nowa topologia sieci czy nowa nakładka na jądro. Beowulf to technologia łączenia komputerów Linux aby utworzyć równoległy, wirtualny superkomputer. Chociaż istnieje wiele pakietów oprogramowania, takich jak modyfikacje jądra, biblioteki PVM i MPI, narzędzia konfiguracyjne, które przyspieszają architekturę Beowulf, ułatwiają konfigurację i zwiększają użyteczność, jednak możliwe jest zbudowanie maszyny Beowulf wykorzystując standardową dystrybucję Linux, bez żadnego dodatkowego oprogramowania. Jeśli masz przynajmniej dwa usieciowione komputery Linux które dzielą przynajmniej katalog /home poprzez NFS, i ufają sobie nawzajem na tyle, aby uruchomić odległą powłokę (rsh), możesz się upierać że dysponujesz prostą, dwu-węzłową maszyną Beowulf.

2.3 Klasyfikacja

Systemy Beowulf za konstruowane z różnorodnych części. W celu zwiększenia możliowści obliczeniowych czasami korzysta cię z pewnych niedostępnych powszechnie komponentów (tzn. produkowanych przez pojedynczego producenta). W celu odróżnienia osiągów różnych typów systemów, i ułatwienia dyskusji na ich temat, proponujemy następującą klasyfikację:

BEOWULF KLASY I:

Maszyna tej klasy jest zbudowana wyłącznie z powszechnie dostępnych komponentów. W celu sprawdzenia powszechności elementów przeprowadzmy test przy użyciu "Computer Shopper" (calowej grubości miesięcznika/katalogu systemów PC i komponentów). Test ten wygląda następująco:

Beowulf KLASY I to maszyna, która może zostać skonstruowana z części znalezionych przynajmiej w 3 krajowych/ogólnoświatowych katalogach reklamowych.

Zalety systemów KLASY I to:

Wady systemów KLASY I to:

BEOWULF KLASY II

Beowulf KLASY II to po prostu każda maszyna która nie przejdzie testu z użyciem "Computer Shopper". To nie jest coś złego, jest to jedynie klasyfikacja maszyny.

Zalety systemów KLASY II to:

Wady systemów KLASY II to:

Żadna KLASA nie jest lepsza niż inna. Wszystko zależy wyłącznie do potrzeb i możliwości finansowych. Ta klasyfikacja została utworzona jedynie w celu ułatwienia i większej zwięzłości dyskusji na temat systemów Beowulf. Dział "Projektowanie systemu" może pomóc ustalić, który typ systemu pardziej pasuje do twoich potrzeb.

3. Ogólny opis architektury

3.1 Jak to wygląda?

Myślę, że najlepszym sposobem opisu architektury superkomputera Beowulf jest użycie przykładu, który jest bardzo podobny do prawdziwego Beowulf'a, ale znany większości administratorów systemu. Przykład najbliższy Beowulf'owi to laboratorium komputerów Unix z serwerem i klientami. Aby być bardziej szczegółowym użyję jako przykładu laboratorium komputerów DEC Alpha na Katedrze Nauk Komputerowych, USQ. Serwer nazywa się beldin, a klienci nazywają się scilab01, scilab02, aż do scilab20. Wszyscy klienci mają zainstalowaną lokalną kopię systemu operacyjnego Digital Unix 4.0, ale korzystają z katalogów użytkownika (/home) oraz /usr/local serwera poprzez NFS (Network File System). Każdy klient posiada wpis dla serwera i wszystkich pozostałych klientów w swoim pliku /etc/hosts.equiv, więc wszyscy klienci mogą uruchomić rsh na każdym innym. Serwer jest jednocześnie serwerem NIS dla całego laboratorium, więc informacje księgowania są identyczne dla wszystkich maszyn. Osoba może siedzieć przed konsolą scilab02, zalogować się i pracować w tym samym środowisku, w jakim pracowała by gdyby zalogowała się z serwera bądz z scilab15. Spowodowane jest to tym, że system operacyjny na wszystkich komputerach jest zainstalowany i skonfigurowany w ten sam sposób, a katalogi użytkownika /home i /usr/local mieszczą się fizycznie na serwerze, i są udostępniane przez NFS. Więcej informacji o NIS i NFS znajdziesz w dokumentach HOWTO NIS oraz NFS.

3.2 Jak wykorzystać pozostałe węzły?

Gdy mamy już jakieś pojęcie o architekturze systemu, możemy spojrzeć jak wykorzystać dostępne cykle CPU maszyn w laboratorium komputerowym. Każda osoba może zalogować się na dowolnej maszynie, i uruchomić program i swoim katalogu domowym, ale może także wykonać to zadanie na innej maszynie wywołując po prostu odległą powłokę. Przykładowo załóżmy że chcemy obliczyć sumę pierwiastków kwadratowych wszystkich liczb całkowitych od 1 do 10 włącznie. Piszemy prosty program nazwany sigmasqrt (patrz kod źródłowy), który wykonuje oblicznia. Aby obliczyć sumę pierwiastków kwadratowych liczb od 1 do 10 wykonujemy: 

[jacek@beldin sigmasqrt]$ time ./sigmasqrt 1 10
22.468278

real    0m0.029s
user    0m0.001s
sys     0m0.024s
Komenda time pozwala nam śledzić upływ czasu podczas wykonywania zadania. Jak widać, ten przykład zajął jedynie mały ułamek sekundy (0.029s), ale co będzie jeśli spróbujemy dodać pierwiastki kwadratowe liczb od 1 do 1000000000? Spróbujmy, ponownie obliczając upływ czasu. 

[jacek@beldin sigmasqrt]$ time ./sigmasqrt 1 1000000000
21081851083600.559000

real    16m45.937s
user    16m43.527s
sys     0m0.108s

Tym razem wykonianie programu trwało znacznie dłużej. Oczywistym pytaniem jest co możemy zrobić aby przyspieszyć wykonanie programu? Jak możemy zmienić sposób wykonania zadania aby zmniejszyć upływ czasu? Oczywistą odpowiedzią jest rozbicie zadania na wiele pod-zadań równoległych na wszystkich komputerach. Możemy rozbić jedno duże zadanie dodawania na 20 części, obliczając jeden zakres pierwiastków kwadratowych i dodając je na każdym węźle. Gdy wszystkie węzły zakończą obliczenia i zwrócą rezultaty, 20 liczb powinno zostać dodanych do siebie aby otrzymać końcowy wynik. 

[jacek@beldin sigmasqrt]$ mkfifo output
[jacek@beldin sigmasqrt]$ ./prun.sh & time cat output | ./sum
[1] 5085
21081851083600.941000
[1]+  Done                    ./prun.sh

real    0m58.539s
user    0m0.061s
sys     0m0.206s

Tym razem zajęło to około 58.5s. Jest to czas od rozpoczęcia zadania do zakończenia go przez wszystkie węzły i zwrócenia rezultatu przez potok. Ten czas nie zawiera końcowego dodania 20 liczb, ale to jedynie mały ułamek sekundy, który może zostać zignorowany. Zauważamy że nastąpiła znaczna poprawa przy równoległym wykonaniu zadania. Równoległe zadanie wykonało się ponad 17 razy szybciej, co jest bardzo dobrym wynikiem przy 20-krotnym zwiększeniu ilości CPU. Powyższy przykład ma na celu zilustrowanie najprostszej metody zmiany zwykłego kodu na równoległy. W praktyce takie proste przypadki są niezwykle rzadkie, i różne techniki (takie jak API PVM i PMI) są wykorzystywane do osiągnięcia równoległości.

3.3 Czym Beowulf różni się od COW?

Laboratorium komputerowe opisane powyżej jest doskonałym przykładem klastra stacji roboczych (COW). Tak więc co jest szczególnego w Beowulf'ie, i w jaki sposób różni się on od COW? Prawdą jest, że nie jest to wielka różnica, ale Beowulf posiada kilka unikalnych cech. Po pierwsze, w większości przypadków węzły-klienci klastra Beowulf nie posiadają klawiatury, myszy, karty graficznej czy monitora. Dostęp do węzłów-klientów odbywa się poprzez odległe połączenia z węzła-serwera, dedykowanego węzła-konsoli lub konsoli szeregowej. Jako że węzły-klienci nie muszą mieć dostępu do maszyn spoza klastra, ani maszyny spoza klastra nie muszą mieć bezpośredniego dostępu do węzłów-klientów, powszechnie stosowaną praktyką jest nadawanie węzłom-klientom prywatnych adresów IP, z prywatnych zakresów takich jak 10.0.0.0/8 czy 192.168.0.0/16 (RFC 1918 http://www.alternic.net/rfcs/1900/rfc1918.txt.html). Na ogół jedyną maszyną podłączoną do świata zewnętrznego za pomocą drugiej karty sieciowej jest węzeł-serwer. Najczęściej korzysta się z systemu poprzez bezpośredni dostęp do konsoli serwera, lub poprzez telnet czy odległe logowanie na serwer z odległej stacji roboczej. Na serwerze użytkownicy mogą edytować i kompilować swój kod, a także uruchamiać procesy na wszystkich węzłach w klastrze. W większości przypadków systemy COW są używane do obliczeń równoległych w nocy i w weekendy, gdy użytkownicy nie korzystają ze swoich stacji roboczych do pracy, wykorzystując w ten sposób z niepotrzebne cykle procesora. Z kolei maszyna Beowulf jest maszyną dedykowaną do przetwarzania równoległego, i zoptymalizowaną w tym celu. Beowulf zapewnia także większy współczynnik ceny do wydajności, jako że jest zbudowany z ogólnie dostępnych komponentów i korzysta na ogół z darmowego oprogramowania. Beowulf ma także więcej cech pojedynczego systemu, które pomagają użytkownikom dostrzegać klaster Beowulf jako pojedynczą obliczeniową stację roboczą.

4. Planowanie systemu

Przed zakupem sprzętu dobrym pomysłem może okazać się przemyślenie planu gotowego systemu. Przy tworzeniu systemu Beowulf należy wziąść pod uwagę przede wszystkim dwie główne kwestie sprzętowe: typ komputerów/węzłów których masz zamiar użyć, oraz sposób ich połączenia. Istnieje jedna kwestia programowa, która może wpłynąć na decyzję w sprawie sprzętu: biblioteka komunikacyjna lub API. Bardziej szczegółowe rozważania na temat sprzętu i oprogramowania znajdują się w innym miejscu tego dokumentu.

Mimo że wybór nie jest zbyt wielki, istnieją jednak pewne istotne decyzje które muszą zostać podjęte przy konstruowaniu systemu Beowulf. Jako że dziedzina wiedzy (bądź sztuka) "przetwarzanie równoległe" posiada wiele możliwych interpretacji, poniżej zamieszczone wprowadzenie do niej. Jeśli nie jesteś zainteresowany takim materiałem wprowadzającym, możesz pominąć tą sekcję, jednak zaleca się, abyś przeczytał sekcję Suitability zanim podejmiesz ostateczne decyzje sprzętowe.

4.1 Krótkie wprowadzenie do przetwarzania równoległego.

Ta sekcja stanowi wprowadzenie do koncepcji przetwarzania równoległego. NIE jest to wyczerpujący materiał, jest to jedynie krótki opis spraw, które mogą być istotne dla projektanta i użytkownika Beowulf'a.

Podczas projektowania i budowania Beowulf'a, wiele z opisanych poniżej zagadnień może okazać się istotnych dla twoich decyzji. Ze względu na szczególne cechy komponentów superkomputera Beowulf, należy uważnie zastanowić się nad wieloma aspektami, dopóki jeszcze zależą one od ciebie. Wcale nie jest tak trudno zrozumieć podstawowe zagadnienia związane z przetwarzaniem równoległym. W rzeczywistości gdy już zrozumie się te zagadnienia, oczekiwania okażą się bardziej rzeczywiste i sukces będzie bardziej prawdopodobny. W przeciwieństwie do "świata sekwencyjnego", gdzie szybkość procesora jest najważniejszym aspektem, szybkość procesora w "świecie równoległym" jest tylko jednym z wielu aspektów wpływających na ogólną wydajność i efektywność systemu.

4.2 Metody przetwarzania równoległego

Przetwarzanie równoległe może zostać osiągnięte w różny sposób. Z perspektywy użytkownika istotne jest rozpatrzenie zalet i wad każdej metody. Poniższe działy próbują dostarczyć informacji na temat metod przetwarzania równoległego i stwierdzają, czy maszyna Beowulf podpada pod tę kategorię.

Po co więcej niż jeden procesor?

Odpowiedź na to pytanie jest bardzo istotna. Korzystanie z 8 procesorów aby uruchomić twój ulubiony edytor tekstów to lekka przesada. A co z serwerem www, bazą danych, programem renderującym? Może więcej CPU pomoże. A co ze złożoną symulacją, kodem dynamiki cieczy czy aplikacją górniczą? Dodatkowe CPU na pewno pomogą w tych przypadkach. Faktem jest że architektury wieloprocesorowe są wykorzystywane do rozwiązywania coraz większej liczby problemów.

Najczęściej następnym pytaniem jest: "Dlaczego potrzebuję dwóch czy czterech CPU? Po prostu poczekam na turbo-hiper układ 986." Istnieje kilka powodów:

  1. Podczas korzystania z wielozadaniowych systemów operacyjnych można robić więcej niż jedną rzecz w tym samym czasie. Jest to naturalna "równoległość", która może być łatwo wykorzystana przez więcej niż jeden tani CPU.
  2. Szybkość procesorów podwaja się co każde 18 miesięcy, ale co z prędkością pamięci i dysku twardego? Niestety te szybkości nie rosną tak szybko, jak szybkość CPU. Pamiętaj, że większość aplikacji wymaga dostępu do pamięci i twardego dysku. Wykonywanie zadań równolegle jest sposobem obejścia tych ograniczeń.
  3. Badania wskazują, że szybkość procesorów przestanie rosnąć dwukrotnie co 18 miesięcy po roku 2005. Istnieją pewne bardzo poważne przeszkody które należy pokonać aby utrzymać ten wskaźnik.
  4. Zależnie od aplikacji, przetważanie równoległe może przyspieszyć działanie od 2 do 500 razy (w pewnych przypadkach nawet więcej). Taka wydajność nie jest dostępna przy użyciu pojedynczego procesora. Nawet superkomputery, które kiedyś korzystały z bardzo szybkiego, specjalnego procesora teraz są budowane z wielu ogólnodostępnych CPU.

Jeśli do rozwiązania złożonego problemu potrzebujesz szybkości, przetwarzanie równoległe jest warte rozważenia. Ponieważ przetwarzanie równoległe może zostać zaimplementowane na różne sposoby, rozwiązanie problemu wymaga podjęcia pewnych bardzo ważnych decyzji. Te decyzje mogą drastycznie wpłynąć na przenośność, wydajność i koszt systemu.

Zanim dojdziemy do spraw technicznych, spójrzmy na realny problem dla przetważania równoległego, korzystając z przykładu który dobrze znamy -- oczekiwania w długich kolejkach w sklepie.

Sklep z przetwarzaniem równoległym

Rozważmy wielki sklep z ośmioma kasami zgrupowanymi razem na przedzie sklepu. Załóżmy że każda kasa/każdy kasjer jest CPU, a każdy klient jest programem komputerowym. Wielkość zamówienia każdego klienta jest rozmiarem programu komputerowego (ilością pracy). Te analogie mogą zostać wykorzystane do zilustrowania pojęć przetwarzania równoległego.

Jednozadaniowy system operacyjny

Tylko jedna kasa jest otwarta, i musi obsłużyć każdego klienta pojedynczo.

Przykład: MS-DOS

Wielozadaniowy system operacyjny

Otwarta jest jedna kasa, ale teraz przetwarzany jest tylko fragment zamówienia klienta, a następnie obsługiwany jest fragment zamówienia klienta następnego. Każdemu wydaje się, że wszyscy są obsługiwani jednocześnie, ale jeśli nie ma nikogo innego w kolejce klient zostanie obsłużony szybciej.

Przykład: UNIX, NT korzystający z jednego CPU

Wielozadaniowe systemy operacyjne z wieloma CPU

Teraz sklep dysponuje wieloma kasami. Każde zamówienie może zostać przetworzone przez odrębną kasę i kolejka może zostać obsłużona szybciej. Nazywane jest to SMP -- Symmetric Multi-processing. Mimo że istnieje wiele kas, to jeśli jesteś sam w kolejce, nie zostaniesz obsłużony szybciej, niż gdyby istniała tylko jedna kasa.

Przykład: UNIX oraz NT z wieloma CPU

Wątki w wielozadaniowym systemie operacyjnym z wieloma CPU

Jeśli podzielisz produkty w zamówieniu, być może zdołasz szybciej przejść przez kolejkę korzystając z kilku kas jednocześnie. Najpierw musimy założyć, że posiadasz dużą ilość towaru, ponieważ czas poświęcony na rozbijanie zamówienia musi zwrócić się przez korzystanie z wielu kas. Teoretycznie powinieneś przejść kolejkę n-razy szybciej niż poprzednio, gdzie `n' to ilość kas. Gdy kasjer musi podsumować zamówienie, może wymienić informację i komunikować się z wszystkimi innymi `lokalnymi' kasami. Kasy mogą nawet `zaglądać' do innych kas aby uzyskać informację, która przyspieszy ich pracę. Istnieje jednak limit ilości kas w jednym sklepie, aby praca przebiegała efektywnie.

Prawo Amdala także ogranicza prędkość programu do prędkości jego najwolniejszego, sekwencyjnego fragmentu.

Przykład: UNIX lub NT z wielona CPU na jednej płycie głównej uruchamiające programy wielo-wątkowe.

Wysyłanie komunikatów w wielozadaniowych systemach z wieloma CPU

Aby zwiększyć wydajność, sklep dodaje 8 kas na tyłach sklepu. Jako że nowe kasy są daleko od kas z przodu, kasjerzy muszą przekazywać sobie sumy cząstkowe przez telefon. Ta odległość zwiększa nieco opóźnienie w komunikacji między kasjerami, ale jeśli uda się zminimalizować komunikację, to wszystko jest w porządku. Jeśli masz naprawdę wielkie zamówienie, wymagające wszystkich kas jednocześnie, to przed obliczeniem zysków czasowych należy rozważyć opóźnienia komunikacji. W pewnych przypadkach sklep może posiadać pojedyncze kasy (lub zgrupowania kas) rozmieszczone na terenie całego sklepu -- każda kasa (lub zgrupowanie) musi komunikować się przez telefon. Jako że każdy kasjer może rozmawiać z dowolnym innym, nie jest istotne gdzie oni się znajdują.

Przykład: Jedna lub więcej kopii UNIX lub NT z wieloma CPU na tej samej lub innej płycie głównej, porozumiewających się poprzez komunikaty.

Powyższe scenariusze, mimo że niedokładne, są dobym przykładem ograniczeń nakładanych na system równoległy. W przeciwieństwie do pojedynczego CPU (lub kasy) komunikacja jest istotna.

4.3 Architektury przetwarzania równoległego

Popularne metody i architektury przetwarzania równoległego są zaprezentowane poniżej. Mimo że opis ten nie jest pod żadnym względem wyczerpujący, jest jednak wystarczający do zrozumienia podstaw projektu Beowulf.

Architektury sprzętowe

Istnieją dwa podstawowe sposoby łączenia sprzętu:

  1. Maszyny z pamięcią lokalną, komunikujące się przez komunikaty (klastry Beowulf)
  2. Maszyny z pamięcią dzieloną, komunikujące się przez pamięć (maszyny SMP)

Typowy Beowulf to zbiór jednoprocesorowych maszyn połączonych przez szybką sieć Ethernet, a więc jest systemem z własną pamięcią. System SMP to maszyna z pamięcią dzieloną, która może zostać wykorzystana do przetwarzania równoległego -- aplikacje równoległe komunikują się przez pamięć dzieloną. Tak jak w przykładzie sklepu, maszyny z pamięcią lokalną (pojedyncze kasy) są skalowalne do dużej liczby CPU, gdy liczba CPU maszyn z pamięcią dzieloną jest ograniczona przez pamięć.

Jest jednak możliwe połączenie wielu maszyn z pamięcią dzieloną aby utworzyć "hybrydową" maszynę z pamięcią dzieloną. Te hybrydowe maszyny wyglądają dla użytkownika jak pojedyncze, duże maszyny SMP i często zwane są maszynami NUMA (non uniform memory access -- nietypowy dostęp do pamięci), ponieważ globalna pamięć widoczna dla programisty i dzielona przez wszystkie CPU może być ukrywana. Jednak na pewnym poziomie maszyna NUMA musi przekazywać wiadomości pomiędzy lokalnymi obszarami pamięci dzielonej.

Możliwe jest także podłączenie maszyn SMP jako lokalnych węzłów obliczeniowych. Typowe płyty główne KLASY I mają 2 lub 4 procesory, jest to sposób zredukowania kosztów. Wewnętrzny scheluder Linuxa określa, w jaki sposób te CPU są dzielone. W tym przypadku użytkownik nie może określić odrębnego zadania dla konkretnego procesora SMP. Użytkownik może jednak rozpocząć dwa niezależne procesy lub proces wielowątkowy i spodziewać się poprawy wydajności w stosunku do systemu z pojedynczym CPU.

Programowe architektury API

Istnieją dwa podstawowe sposoby określania momentów zbieżnych w programie:

  1. Komunikaty wysyłane między procesorami
  2. Wątki systemu operacyjnego

Istnieją inne metody, ale powyższe są najszerzej wykorzystywane. Należy zapamiętać, że sposób określania zbieżności nie musi zależeć od warstwy sprzętowej. Zarówno komunikaty, jak i wątki mogą zostać zaimplementowane w systemach SMP, NUMA-SMP jak i klastrach -- mimo że, jak wyjaśniono poniżej, istotnymi kwestiami są efektywność i przenośność.

Komunikaty

Z punktu widzenia historii, technologia przekazywania komunikatów odzwierciedla projekty wczesnych komputerów równoległych z lokalną pamięcią. Komunikaty wymagają kopiowania danych, podczas gdy wątki korzystają z danych na miejscu. Tajność i szybkość kopiowania komunikatów to wartości ograniczające ten model. Komunikat jest stosunkowo prosty: jakieś dane oraz procesor docelowy. Najpopularniejsze API do przesyłania komunikatów to: PVM lub MPI. Przekazywanie komunikatów może zostać efektywnie zaimplementowane przy wykorzystaniu wątków, a komunikaty pracują równie dobrze na maszynach SMP i pomiędzy klastrami maszyn. Zaletą korzystania z komunikatów na maszynach SMP, w przeciwieństwie do wątków, jest to, że jeśli zdecydujesz się na korzystanie w przyszłości z klastrów, dodawanie maszyn i skalowanie aplikacji będzie bardzo łatwe.

Wątki

Wątki systemu operacyjnego zostały stworzone, ponieważ projekty SMP (symmetrical multiprocessing -- symetryczna wieloprocesowość) dopuszczały bardzo szybką komunikację poprzez pamięć dzieloną, oraz synchronizację pomiędzy zbieżnymi fragmentami programu. Wątki działają bardzo dobrze na systemie SMP, ponieważ komunikuje się on poprzez pamięć dzieloną. Z tego powodu użytkownik musi oddzielić dane lokalne od globalnych, w przeciwnym wypadku programy nie będą działać poprawnie. W przeciwieństwie do komunikatów, wiele operacji kopiowania może zostać wyeliminowanych przez użycie wątków, ponieważ dane są dzielone pomiędzy procesami (wątkami). Linux wspomaga wątki POSIX. W przypadku wątków problemem jest to, że trudno rozszerzyć ich zasięg poza maszynę SMP oraz, ponieważ dane ją dzielone pomiędzy procesory, koherencja pamięci podręcznej może doprowadzić do opóźnień. Efektywne rozciągnięcie wątków poza granicę SMP wymaga technologi NUMA, która jest kosztowna i nie wspomagana bezpośrednio przez Linuxa. Implementacja wątków poprzez wiadomości jest możliwa ( http://syntron.com/ptools/ptools_pg.htm), ale wątki są często nieefektywne gdy zaimplementowane przy użyciu komunikatów.

Można wyciągnąc następujące wnioski jeśli chodzi o wydajność: 

          wydajność na     wydajność w     skalowalność
          maszynie SMP       klastrze
          -----------     ---------------  -----------
messages    dobra           najlepsza       najlepsza

threads     najlepsza        słaba*          słaba*

* wymaga kosztownej technologii NUMA.

Architektura aplikacji

Aby uruchomić aplikację równolegle na wielu CPU, musi ona zostać rozbita na konkurencyjne części. Standardowa jednoprocesorowa aplikacja nie będzie działać szybciej na wielu procesorach. Istnieją pewne narzędzia i kompilatory, które potrafią podzielić program, ale przekształcenie kodu na równoległy nie jest operacją "plug and play". Zależnie od aplikacji, może to być proste, ekstremalnie trudne a w pewnych przypadkach nawet niemożliwe, ze względu na zależności algorytmów.

Zanim zostaną omówione kwestie sprzętowe, koncepcja musi zostać wprowadzona. Before the software issues can be addressed the concept of Suitability needs to be introduced.

4.4 Suitability

Odpowiedzią na większość pytań dotyczących przetwarzania równoległego jest:

"Wszystko zależy od zastosowania."

Zanim przejdziemy do tego tematu, należy dokonać jeszcze jednego bardzo ważnego podziału -- różnicy pomiędzy KONKURENCYJNYM i RÓWNOLEGŁYM. Dla celów tej dyskusji zdefiniujemy te dwa pojęcia następująco:

KONKURENCYJNE części programu, to te, które mogą zostać wykonane niezależnie.

RÓWNOLEGŁE części programu, to te KONKURENCYJE części, które są wykonywane na osobnym procesorze w tym samym czasie.

Różnica jest bardzo ważna, ponieważ KONKURENCJA to własność programu, a efektywna RÓWNOLEGŁOŚĆ, to właśność maszyny. Na ogół wykonywanie RÓWNOLEGŁE powoduje przyspieszenie pracy. Czynnikiem ograniczającym wydajność systemu równoległego jest prędkość komunikacji i opóźnienie pomiędzy węzłami (opóźnienie występuje także w wielowątkowych aplikacji SMP, z powodu koherencji pamięci podręcznej). Większość programów testujących wydajność jest wysoce równoległa, a komunikacja i opóźnienia nie są wąskim gardłem. Ten tym zadania można nazwać "typowo równoległym". Inne aplikacje nie są takie proste i wywołanie KONKURENCYJNYCH części programu RÓWNOLEGLE może spowolnić go, zmniejszając tym samym zysk z innych KONKURENCYJNYCH części. Mówiąc prosto, koszt czasu komunikacji musi zwrócić się w oszczędnościach czasu obliczenia, w przeciwnym wypadku RÓWNOLEGŁE wykonanie KONKURENCYJNEJ części jest nieefektywne.

Zadaniem programisty jest stwierdzenie, które KONKURENCYJNE części programu POWINNY być wykonane RÓWNOLEGLE, a które NIE. Od odpowiedź na te pytania zależy EFEKTYWNOŚĆ aplikacji. Poniższy wykres podsumowuje sytuację: 




         | *
         | *
         | *
 %       | *
 zasto-  |  *
 sowań   |  *
         |  *
         |  *
         |    *
         |     *
         |      *
         |        ****
         |            ****
         |                ********************
         +-----------------------------------
          czas komunikacji/czas przetwarzania

W idealnym komputerze równoległym, wskaźnik komunikacji/przetwarzania jest równy i wszystko, co jest KONKURENCYJNE może zostać zaimplementowane RÓWNOLEGLE. Niestety, rzeczywiste komputery równoległe, włączając w to maszyny z pamięcią dzieloną, podlegają efektom pokazanym na wykresie. Podczas projektowania Beowulfa, użytkownicy powinni zapamiętać ten wykres, ponieważ efektywność równoległa zależy do wskaźnika czasu komunikacji do czasu przetwarzania dla KONKRETNEGO KOMPUTERA RÓWNOLEGŁEGO. Aplikacje mogą być przenośne, ale nie można zagwarantować że będą efektywne na innej platformie.

NA OGÓŁ NIE ISTNIEJE PRZENOŚNY I EFEKTYWNY PROGRAM RÓWNOLEGŁY

Jest jeszcze jedna konsekwencja powyższego wykresu. Jako że efektywność zależy od wskaźnika komunikacji/przetwarzania, zmiana jedynie jednego elementu wskaźnika nie musi koniecznie powodować wzrostu szybkości. Zmiana prędkości procesora, nie zmieniając czasu komunikacji, może mieć nietypowy wpływ na program. Na przykład podwojenie albo potrojenie prędkości CPU, zachowując tę samą prędkość komunikacji, może sprawić, że poprzednio efektywne RÓWNOLEGŁE fragmenty programu staną się bardziej efektywne gdy zostaną uruchomione SEKWENCYJNIE. To znaczy uruchomienie poprzednio RÓWNOLEGŁYCH fragmentów jako SEKWENCYJNE może okazać się lepsze. Wykonywanie nieefektywnych części programu równolegle uniemożliwia uzyskanie maksymalnej prędkości. Tak więc dodając szybszy procesor, możesz spowolnić aplikację (CPU nie wykorzystuje swojej pełnej szybkości).

ZMIANA CPU NA SZYBSZY MOŻE SPOWOLNIĆ APLIKACJĘ

Podsumowując, aby wiedzieć, czy można wykorzystać środowisko równoległe, należy przyjrzeć się, czy konkretna maszyna pasuje do aplikacji. Musisz wziąść pod uwagę wiele kwestii, takich jak prędkość CPU, kompilator, API przekazywania komunikatów, sieć itd. Należy zauważyć, że zwykłe profilowanie aplikacji nie zamyka sprawy. Możesz zidentyfikować fragment programu wymagający wielu obliczeń, ale nie znasz kosztów komunikacji tego fragmentu. Może się zdarzyć, że koszty komunikacji sprawią, że kod równoległy nie będzie efektywny.

Ostatnia uwaga na temat pewnego niedomówienia. Często twierdzi się, że program "jest RÓWNOLEGŁY", ale w rzeczywistości jedynie zidentyfikowano KONKURENCYJNE fragmenty. Z powodów podanych powyżej program nie jest RÓWNOLEGŁY. Efektywna RÓWNOLEGŁOŚĆ jest własnością maszyny.

4.5 Pisanie i przenoszenie oprogramowania równoległego

Gdy zdecydujesz, że potrzebujesz przetwarzania równoległego i chcesz zaprojektować i zbudować Beowulfa, dobrym pomysłem jest kilka chwil zastanowienia nad aplikacją, z poszanowaniem wcześniejszych uwag.

No ogół możesz zrobić dwie różne rzeczy:

  1. Iść dalej i skonstruować Beowulfa KLASY I a następnie "dopasować" do niego swoją aplikację, lub korzystać z istniejącej równoległej aplikacji o której wiesz, że pracuje na Beowulfie (ale pamiętaj o kwestiach efektywności i przenośności poruszanych wcześniej).
  2. Przyjrzeć się aplikacjom które mają działać na Beowulfie i na ich podstawie dokonać wyboru sprzętu i oprogramowania.

W każdym z przypadków w pewnym momencie musisz zastanowić się nad kwestiami efektywności. Na ogół powinieneś zrobić trzy rzeczy:

  1. Wyznaczyć konkurencyjne części programu
  2. Obliczyć równoległą efektywność
  3. Opisać konkurencyjne części programu

Przyjrzyjmy się im po kolei.

Wyznaczanie konkurencyjnych części programu

Ten krok jest często nazywany "urównolegleniem programu". Decyzje podejmiemy dopiero w kroku 2. Teraz musisz jedynie wyznaczyć zależności pomiędzy danymi.

Z praktycznego punktu widzenia, aplikacje mogą wykazywać dwa typy konkurencji: obliczeń i wejścia/wyjścia. Mimo że w wielu wypadkach konkurencje obliczeń i wejścia/wyjścia są niezależne, to istnieją aplikacje, które wymagają obu. Istnieją narzędzia, które mogą wykonać analizę konkurencji istniejącej aplikacji. Wiele z tych narzędzi jest projektowanych dla FORTANa. Są dwa powody dla których używa się FORTAN: historycznie większość aplikacji obliczeniowych było pisanych w FORTANie oraz jest on łatwiejszy w analizie. Jeśli nie istnieją żadne narzędzia, to ten krok może okazać się dość trudny dla istniejących aplikacji.

Obliczanie efektywności równoległej

Bez pomocy narzędzi, ten krok wymagał by użycia metody prób i błędów, lub po prostu zgadywania. Jeśli bierzesz pod uwagę pojedynczą aplikację, postaraj się określić czy jest ograniczona przez CPU (granica obliczeniowa) lub przez twardy dysk (granica wejścia/wyjścia). Wymagania Beowulfa mogą być dość różne, zależnie od potrzeb. Na przykład problem ograniczony obliczeniowo może wymagać kilku bardzo szybkich CPU i szybkiej sieci z małym opóźnieniem, gdy problem ograniczony przez wejście/wyjście może działać lepiej na wolniejszym CPU i szybkiej sieci Ethernet.

To zalecenem często zaskakuje wiele osób, ponieważ zwykle uważa się, że szybszy procesor jest zawsze lepszy. Jest to prawdą jeśli dysponuje się nieograniczonym budżetem, jednak w przypadku prawdziwych systemów powinno się minimalizować koszty. Dla problemów ograniczonych przez wejście/wyjście istnieje prosta zasada (zwana Prawem Eadline'a-Dedkova) która jest dość pomocna:

Z dwóch komputerów równoległych o tej samym zsumowanym wskaźniku wydajności CPU lepszą wydajność dla aplikacji z dominującymi operacjami wejścia/wyjścia będzie miał ten, który posiada wolniejsze procesory (i prawdopodobnie także wolniejszą komunikację międzyprocesorową).

Dowód tego prawa wychodzi poza zakres tego dokumenty, jednak może zainteresować cię dokument Performance Considerations for I/O-Dominant Applications on Parallel Computers (w formacie Postscript 109K) (ftp://www.plogic.com/pub/papers/exs-pap6.ps)

Gdy już określiłeś typ konkurencji aplikacji, musisz obliczyć jak efektywna będzie ona równolegle. Patrz dział Oprogramowanie aby znaleźć opis narzędzi programowych.

W razie nieobecności narzędzi, możesz próbować po prostu zgadnąć. Jeśli pętla obliczeniowa trwa minuty, a dane mogą zostać przesłane w ciągu sekund, to prawdopodobnie jest to dobry kandydat na program równoległy. Ale pamiętaj, jeśli rozbijesz 16-minutową pętle na 32 części, a transfer danych wymaga kilku sekund, to zaczyna robić się ciasno.

Opisywanie konkurencyjnych części programu

Istnieje kilka sposobów opisu konkurencyjnych części programu: There are several ways to describe concurrent parts of your program:

  1. Wyraźne wykonanie równoległe
  2. Domniemane wykonanie równoległe

Te dwa sposoby różnią się głównie tym, że równoległość "wyraźna" jest określana przez użytkownika, a domniemana jest określana przez kompilator.

Metody wyraźne

Są to po prostu metody, w których użytkownik musi zmodyfikować kod źródłowy specjalnie dla komputera równoległego. Użytkownik musi dodać obsługę komunikatów korzystając z PVM lub MPI, albo wątków korzystając z wątków POSIX (pamiętaj jednak że wątki nie działają na komputerach SMP).

Metody wyraźne są bardzo trudne w implementacji i poprawianiu błędów. Użytkownicy najczęściej osadzają wyraźne wywołania funkcji w standardowym kodzie źródłowym FORTAN 77 lub C/C++. Biblioteka MPI dodaje pewne funkcje ułatwiające implementację standardowych równoległych metod (np. funkcje scatter/gather). Dodatkowo możliwe jest także użycie standardowych bibliotek napisanych dla równoległych komputerów. Pamiętaj jednak, że przenośność nie idzie w parze z efektywnością.

Ze względów historycznych, większość programów operujących na liczbach zostało napisanych w FORTANie. Z tego powodu FORTAN posiada największe wsparcie (narzędzia, biblioteki itp.) dla przetwarzania rówoległego. Teraz wielu programistów korzysta z C, lub przepisuje istniejące programy FORTAN w C, jako że C działa szybciej. Może jest prawdą, że C jest najbliższe uniwersalnemu kodowi maszynowemu, posiada jednak kilka poważnych wad. Użycie wskaźników w C znacznie utrudnia wyznaczanie zależności pomiędzy danymi. Automatyczna analiza wskaźników jest bardzo trudna. Jeśli dysponujesz gotowym programem w FORTANie i myślisz, że mógłbyś uczynić go równoległym w przyszłości -- NIE KONWERTUJ GO NA C!

Domniemane metody

Domniemane metody to te, w których użytkownik pozostawia niektóre (lub wszystkie) decyzje dotyczące równoległości kompilatorowi. Przykładem jest FORTAN 90, High Performance FORTAN, Bulk Synchronous Parallel (BSP) oraz cała lista metod rozwijanych obecnie.

Metody domyślne wymagają od użytkownika podania pewnych informacji na temat konkurencyjnej natury aplikacji, ale to kompilator podejmie następnie decyzje jak wykonywać tą konkurencję równolegle. Te metody gwarantują pewien stopień przenośności i efektywności, jednak ciągle nie istnieje najlepszy sposób opisu problemu konkurencyjnego dla komputera równoległego.

5. Zasoby dotyczące Beowulfa

5.1 Punkty startowe

5.2 Documentation

5.3 Dokumenty

5.4 Oprogramowanie

5.5 Maszyny Beowulf

5.6 Inne interesujące strony

5.7 Historia

6. Kod źródłowy

6.1 sum.c

/* Jacek Radajewski jacek@usq.edu.au */
/* 21/08/1998 */

#include <stdio.h>
#include <math.h>

int main (void) {

  double result = 0.0;
  double number = 0.0;
  char string[80];
  

  while (scanf("%s", string) != EOF) {

    number = atof(string);
    result = result + number;
  }
    
  printf("%lf\n", result);
  
  return 0;
  
}

6.2 sigmasqrt.c

/* Jacek Radajewski jacek@usq.edu.au */
/* 21/08/1998 */

#include <stdio.h>
#include <math.h>

int main (int argc, char** argv) {

  long number1, number2, counter;
  double result;
  
  if (argc < 3) {
    printf ("usage : %s number1 number2\n",argv[0]);
    exit(1);
  } else {
    number1 = atol (argv[1]);
    number2 = atol (argv[2]);
    result = 0.0;
  }

  for (counter = number1; counter <= number2; counter++) {
    result = result + sqrt((double)counter);
  }
    
  printf("%lf\n", result);
  
  return 0;
  
}

6.3 prun.sh

#!/bin/bash
# Jacek Radajewski jacek@usq.edu.au
# 21/08/1998

export SIGMASQRT=/home/staff/jacek/beowulf/HOWTO/example1/sigmasqrt

# $OUTPUT must be a named pipe
# mkfifo output

export OUTPUT=/home/staff/jacek/beowulf/HOWTO/example1/output

rsh scilab01 $SIGMASQRT         1  50000000 > $OUTPUT < /dev/null&
rsh scilab02 $SIGMASQRT  50000001 100000000 > $OUTPUT < /dev/null&
rsh scilab03 $SIGMASQRT 100000001 150000000 > $OUTPUT < /dev/null&
rsh scilab04 $SIGMASQRT 150000001 200000000 > $OUTPUT < /dev/null&
rsh scilab05 $SIGMASQRT 200000001 250000000 > $OUTPUT < /dev/null&
rsh scilab06 $SIGMASQRT 250000001 300000000 > $OUTPUT < /dev/null&
rsh scilab07 $SIGMASQRT 300000001 350000000 > $OUTPUT < /dev/null&
rsh scilab08 $SIGMASQRT 350000001 400000000 > $OUTPUT < /dev/null&
rsh scilab09 $SIGMASQRT 400000001 450000000 > $OUTPUT < /dev/null&
rsh scilab10 $SIGMASQRT 450000001 500000000 > $OUTPUT < /dev/null&
rsh scilab11 $SIGMASQRT 500000001 550000000 > $OUTPUT < /dev/null&
rsh scilab12 $SIGMASQRT 550000001 600000000 > $OUTPUT < /dev/null&
rsh scilab13 $SIGMASQRT 600000001 650000000 > $OUTPUT < /dev/null&
rsh scilab14 $SIGMASQRT 650000001 700000000 > $OUTPUT < /dev/null&
rsh scilab15 $SIGMASQRT 700000001 750000000 > $OUTPUT < /dev/null&
rsh scilab16 $SIGMASQRT 750000001 800000000 > $OUTPUT < /dev/null&
rsh scilab17 $SIGMASQRT 800000001 850000000 > $OUTPUT < /dev/null&
rsh scilab18 $SIGMASQRT 850000001 900000000 > $OUTPUT < /dev/null&
rsh scilab19 $SIGMASQRT 900000001 950000000 > $OUTPUT < /dev/null&
rsh scilab20 $SIGMASQRT 950000001 1000000000 > $OUTPUT < /dev/null&

# # # #

Hosting by: Hurra Communications Sp. z o.o.
Generated: 2007-01-26 18:02:22