 |
 |
|
|
Nie ponosimy �adnej odpowiedzialno�ci za jakiekolwiek b��dne informacje zawarte w tym dokumencie, ani za uszkodzenia kt�re mog� one spowodowa�.
Copyright © 1997 - 1998 Jacek Radajewski and Douglas Eadline. Udzielono zezwolenia na dystrybucj� i modyfikowanie tego dokumentu zgodnie z licencj� GNU General Public Licence.
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).
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.
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.
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.
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.
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.
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.
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.024sKomenda
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.
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�.
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.
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.
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�.
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:
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.
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.
Tylko jedna kasa jest otwarta, i musi obs�u�y� ka�dego klienta pojedynczo.
Przyk�ad: MS-DOS
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
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
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.
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.
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.
Istniej� dwa podstawowe sposoby ��czenia sprz�tu:
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.
Istniej� dwa podstawowe sposoby okre�lania moment�w zbie�nych w programie:
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��.
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 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.
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.
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.
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:
W ka�dym z przypadk�w w pewnym momencie musisz zastanowi� si� nad kwestiami efektywno�ci. Na og� powiniene� zrobi� trzy rzeczy:
Przyjrzyjmy si� im po kolei.
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.
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.
Istnieje kilka sposob�w opisu konkurencyjnych cz�ci programu: There are several ways to describe concurrent parts of your program:
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.
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 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.
/* 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;
}
/* 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;
}
#!/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