Beowulf HOWTO
Autor: Jacek Radajewski i Douglas Eadline
v1.1.1, 22 padziernik 1998
WWeerrssjjaa ppoollsskkaa:: AAddaamm BByyrrtteekk aallpphhaa@@iirrcc..ppll
v1.0, lipiec 1999
Ten dokument jest wprowadzeniem do architektury superkomputerw Beowulf
i dostarcza podstawowych informacji na temat programowania rwnolegego,
wraz z odnonikami do bardziej szczegowych dokumentw oraz stron WWW.
______________________________________________________________________
Spis treci
1. Wstp
1.1 Zastrzeenie
1.2 Prawa autorskie
1.3 Informacje o dokumencie
1.4 Informacje o autorach
1.5 Podzikowania
2. Wstp
2.1 Kto powinien czyta ten dokument?
2.2 Czym jest Beowulf?
2.3 Klasyfikacja
3. Oglny opis architektury
3.1 Jak to wyglda?
3.2 Jak wykorzysta pozostae wzy?
3.3 Czym Beowulf rni si od COW?
4. Planowanie systemu
4.1 Krtkie wprowadzenie do przetwarzania rwnolegego.
4.2 Metody przetwarzania rwnolegego
4.2.1 Po co wicej ni jeden procesor?
4.2.2 Sklep z przetwarzaniem rwnolegym
4.2.2.1 Jednozadaniowy system operacyjny
4.2.2.2 Wielozadaniowy system operacyjny
4.2.2.3 Wielozadaniowe systemy operacyjne z wieloma CPU
4.2.2.4 Wtki w wielozadaniowym systemie operacyjnym z wieloma CPU
4.2.2.5 Wysyanie komunikatw w wielozadaniowych systemach z wieloma CPU
4.3 Architektury przetwarzania rwnolegego
4.3.1 Architektury sprztowe
4.3.2 Programowe architektury API
4.3.2.1 Komunikaty
4.3.2.2 Wtki
4.3.3 Architektura aplikacji
4.4 Suitability
4.5 Pisanie i przenoszenie oprogramowania rwnolegego
4.5.1 Wyznaczanie konkurencyjnych czci programu
4.5.2 Obliczanie efektywnoci rwnolegej
4.5.3 Opisywanie konkurencyjnych czci programu
4.5.3.1 Metody wyrane
4.5.3.2 Domniemane metody
5. Zasoby dotyczce Beowulfa
5.1 Punkty startowe
5.2 Documentation
5.3 Dokumenty
5.4 Oprogramowanie
5.5 Maszyny Beowulf
5.6 Inne interesujce strony
5.7 Historia
6. Kod rdowy
6.1 sum.c
6.2 sigmasqrt.c
6.3 prun.sh
______________________________________________________________________
11.. WWssttpp
11..11.. ZZaassttrrzzeeeenniiee
Nie ponosimy adnej odpowiedzialnoci za jakiekolwiek bdne informacje
zawarte w tym dokumencie, ani za uszkodzenia ktre mog one spowodowa.
11..22.. PPrraawwaa aauuttoorrsskkiiee
Copyright (C) 1997 - 1998 Jacek Radajewski and Douglas Eadline.
Udzielono zezwolenia na dystrybucj i modyfikowanie tego dokumentu
zgodnie z licencj GNU General Public Licence.
11..33.. IInnffoorrmmaaccjjee oo ddookkuummeenncciiee
Jacek Radajewski rozpocz prac nad tym dokumentem w padzierniku 1997,
niedugo potem doczy do niego Douglas Eadline. W przecigu kilku miesicy
dokument Beowulf HOWTO znacznie si rozrs, 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 zostaa wydana w ramach Linux Documentation
Project (Projektu Dokumentacji Linuxa) 11 padziernika 1998. Mamy
nadziej, e to jedynie pocztek tego, co stanie si wkrtce Beowulf
Documentation Project (Projektem Dokumentacji Beowulfa).
11..44.. IInnffoorrmmaaccjjee oo aauuttoorraacchh
+o Jacek Radajewski pracuje jako zarzdca sieci i studiuje nauki
komputerowe na Uniwersytecie Poudniowego Queensland, w Australii.
Jacek pierwszy raz spotka si z Linuxem w 1995 roku, i bya to mio od
pierwszego spojrzenia. Jacek wybudowa swj pierwszy klaster Beowulf
w maju 1997 i od tamtego czasu eksperymentuje, starajc si znale
nowe i lepsze sposoby rozwizywania problemw. Mona skontaktowa si z
Jackiem wysyajc mu email na adres jacek@usq.edu.au
+o Douglas Eadline, Ph.D. jest Prezesem i Pierwszym Naukowcem w
Paralogic, Inc., Bethlehem, PA, USA. Z wyksztacenia chemik
fizyczny/analityczny, zainteresowany komputerami od 1978, gdy
zbudowa swj pierwszy komputer do uycia z instrumentami chemicznymi.
Teraz Dr. Eadline interesuje si Linuxem, klastrami Beowulf i
algorytmami rwnolegymi. Mona skontaktowa si z nim wysyajc email na
adres deadline@plogic.com
11..55.. PPooddzziikkoowwaanniiaa
Pisanie Beowulf HOWTO byo dugim procesem, zakoczonym dziki wielu
osobom. Chciaem podzikowa nastpujcym ludziom za pomoc i wkad w ten
dokument.
+o Becky za jej mio, wsparcie i zrozumienie.
+o Tom'owi Sterling, Don'owi Becker oraz innym ludziom z NASA, ktrzy
rozpoczli projekt Beowulf.
+o Thanh Tran-Cong i Katedrze Inynierii i Pomiarw za stworzenie
maszyny Beowulf _t_o_p_c_a_t, udostpnionej do eksperymentw.
+o Mojemu nadzorcy Christopher'owi Vance za wiele wietnych pomysw.
+o Mojemu przyjacielowi Russell'owi Waldron za wietne pomysy
programistyczne, jego zainteresowanie projektem i wsparcie.
+o Mojemu przyjacielowi David'owi Smith za przeczytanie tego dokumentu
w poszukiwaniu bdw.
+o Wielu innym ludziom z listy dyskusyjnej Beowulfa, ktrzy dostarczyli
mi opinii i pomysw.
+o Wszystkim ludziom odpowiedzialnym za system operacyjny Linux i
pozostae darmowe oprogramowanie wykorzystywane na _t_o_p_c_a_t i innych
maszynach Beowulf.
22.. WWssttpp
Jako e wydajno sprztu komputerowego i sieciowego wci ronie, a jego
ceny spadaj, bardziej praktyczne ni kupowanie bardzo kosztownego
superkomputera staje si budowanie rwnolegych systemw obliczeniowych ze
skadnikw dostpnych w kadym sklepie. W rzeczywistoci wskanik wydajnoci
do ceny maszyny typu Beowulf jest od trzech do dziesiciu razy wyszy ni
tradycyjnych superkomputerw. Architektura Beowulf jest atwo
skalowalna, atwa w budowie i paci si jedynie za sprzt, jako e wikszo
oprogramowania jest darmowa.
22..11.. KKttoo ppoowwiinniieenn cczzyyttaa tteenn ddookkuummeenntt??
To HOWTO jest zaprojektowane dla osoby majcej przynajmniej podstawowe
dowiadczenie z systemem operacyjnym Linux. Znajomo technologii Beowulf
czy rozumienie bardziej zoonych koncepcji zwizanych z systemami
operacyjnymi i sieciami nie jest konieczne, ale podstawowa wiedza o
przetwarzaniu rwnolegym bdzie przydatna (w kocu musisz mie jaki powd,
czytajc ten dokument). To HOWTO nie odpowie na wszystkie moliwe
pytania na temat Beowulf'a, ale by moe da ci pomysy i poprowadzi we
waciwym kierunku. Celem tego dokumentu jest udzielenie podstawowych
informacji, oraz odnonikw do bardziej zaawansowanych dokumentw.
22..22.. CCzzyymm jjeesstt BBeeoowwuullff??
_F_a_m_e_d _w_a_s _t_h_i_s _B_e_o_w_u_l_f_: _f_a_r _f_l_e_w _t_h_e _b_o_a_s_t _o_f _h_i_m_, _s_o_n _o_f _S_c_y_l_d_, _i_n
_t_h_e _S_c_a_n_d_i_a_n _l_a_n_d_s_. _S_o _b_e_c_o_m_e_s _i_t _a _y_o_u_t_h _t_o _q_u_i_t _h_i_m _w_e_l_l _w_i_t_h _h_i_s
_f_a_t_h_e_r_'_s _f_r_i_e_n_d_s_, _b_y _f_e_e _a_n_d _g_i_f_t_, _t_h_a_t _t_o _a_i_d _h_i_m_, _a_g_e_d_, _i_n _a_f_t_e_r
_d_a_y_s_, _c_o_m_e _w_a_r_r_i_o_r_s _w_i_l_l_i_n_g_, _s_h_o_u_l_d _w_a_r _d_r_a_w _n_i_g_h_, _l_i_e_g_e_m_e_n _l_o_y_a_l_: _b_y
_l_a_u_d_e_d _d_e_e_d_s _s_h_a_l_l _a_n _e_a_r_l _h_a_v_e _h_o_n_o_r _i_n _e_v_e_r_y _c_l_a_n_. Beowulf to
najstarszy zachowany poemat epicki w jzyku angielskim. Jest to opowie
o bohaterze dysponujcym wielk si i odwag, ktry pokona potwora zwanego
Grendel. Patrz do dziau ``Historia'' aby dowiedzie si wicej o
walecznym Beowulf'ie.
Prawdopodobnie istnieje co najmniej tyle definicji Beowulf'a, ile
ludzi ktrzy budowali lub korzystali z architektury superkomputera
Beowulf. Niektrzy twierdz e system moe zosta nazwany Beowulf tylko
jeli zosta zbudowany tak samo, jak oryginalna maszyna NASA. Inni
zmierzaj do drugiej skrannoci, nazywajc imieniem Beowulf kady system
stacji roboczych wykonujcych kod rwnolegy. Moja definicja Beowulf'a
mieci si mniej wicej porodku, i jest oparta na wielu opiniach z listy
dyskusyjnej Beowulf'a:
Beowulf to wielo-komputerowa architektura ktra moe zosta uyta do
oblicze rwnolegych. Jest to system, ktry na ogl skada si z jednego wz-
serwera i jednego lub wicej wza-klienta poczonego przez Ethernet lub
jak inn sie. Jest to system zbudowany w oparciu o powszechnie dostpne
komponenty sprztowe, jak kady PC zdolny do uruchomienia Linuxa,
standardowe karty Ethernet i switch'e. Nie zawiera adnych unikalnych
komponentw sprztowych i jest atwy w tworzeniu. Beowulf korzysta rwnie
ze zwykego oprogramowania, jak system operacyjny Linux, Parallel
Virtual Machine (PVM) oraz Message Passing Interface (MPI). Wze-serwer
kontroluje cay klaster i udostpnia pliki klientom. Peni on take funkcj
konsoli klastra i jest jego bram do zewntrznego wiata. Due maszyny
Beowulf mog posiada wicej ni jeden wze-serwer, oraz inne wzy stworzone
dla specyficznych zada, na przykad konsole lub stacje monitorujce. W
wikszoci przypadkw wzy-klienci w systemie Beowulf s gupie, im gupsze
tym lepiej. Wzy s konfigurowane i kontrolowane przez wze-serwer, i
robi tylko to, co kazano im robi. W konfiguracji bezdyskowej klienci
nie znaj nawet swojego adresu IP lub nazwy, dopki serwer im ich nie
poda. Jedn z podstawowych rnic pomidzy Beowulf'em a architektur
Cluster of Workstations (COW) jest to, e Beowulf zachowuje si bardziej
jak jedna maszyna, ni wiele stacji roboczych. W wikszoci przypadkw
wzy-klienci nie posiadaj klawiatur czy monitorw, a dostp do nich jest
moliwy jedynie przez odlege logowanie bdz opcjonalny terminal
szeregowy. Wezy Beowulf mona sobie wyobrazi jako pakiej CPU + pami,
ktry moe zosta podczony do klastra, tak jak CPU czy modu pamici moe
zosta doczony do pyty gwnej.
Beowulf to nie aden specjalny pakiet oprogramowania, nowa topologia
sieci czy nowa nakadka na jdro. Beowulf to technologia czenia
komputerw Linux aby utworzy rwnolegy, wirtualny superkomputer. Chocia
istnieje wiele pakietw oprogramowania, takich jak modyfikacje jdra,
biblioteki PVM i MPI, narzdzia konfiguracyjne, ktre przyspieszaj
architektur Beowulf, uatwiaj konfiguracj i zwikszaj uyteczno, jednak
moliwe jest zbudowanie maszyny Beowulf wykorzystujc standardow
dystrybucj Linux, bez adnego dodatkowego oprogramowania. Jeli masz
przynajmniej dwa usieciowione komputery Linux ktre dziel przynajmniej
katalog /home poprzez NFS, i ufaj sobie nawzajem na tyle, aby uruchomi
odleg powok (rsh), moesz si upiera e dysponujesz prost, dwu-wzow
maszyn Beowulf.
22..33.. KKllaassyyffiikkaaccjjaa
Systemy Beowulf za konstruowane z rnorodnych czci. W celu zwikszenia
moliowci obliczeniowych czasami korzysta ci z pewnych niedostpnych
powszechnie komponentw (tzn. produkowanych przez pojedynczego
producenta). W celu odrnienia osigw rnych typw systemw, i uatwienia
dyskusji na ich temat, proponujemy nastpujc klasyfikacj:
BEOWULF KLASY I:
Maszyna tej klasy jest zbudowana wycznie z powszechnie dostpnych
komponentw. W celu sprawdzenia powszechnoci elementw przeprowadzmy
test przy uyciu "Computer Shopper" (calowej gruboci
miesicznika/katalogu systemw PC i komponentw). Test ten wyglda
nastpujco:
Beowulf KLASY I to maszyna, ktra moe zosta skonstruowana z czci
znalezionych przynajmiej w 3 krajowych/oglnowiatowych katalogach
reklamowych.
Zalety systemw KLASY I to:
+o sprzt dostpny z wielu rdel (niskie ceny, atwa konserwacja)
+o niezalenoc od konkretnego producenta
+o wsparcie standardowych sterownikw Linux
+o najczciej oparte o standardy (SCSI, Ethernet itp.)
Wady systemw KLASY I to:
+o najlepsza wydajno moe wymaga sprztu KLASY II
BEOWULF KLASY II
Beowulf KLASY II to po prostu kada maszyna ktra nie przejdzie testu z
uyciem "Computer Shopper". To nie jest co zego, jest to jedynie
klasyfikacja maszyny.
Zalety systemw KLASY II to:
+o cakiem dobra wydajno!
Wady systemw KLASY II to:
+o problemy ze sterownikami
+o zaleno od konkretnego producenta
+o moe by droszy ni system klasy I
adna KLASA nie jest lepsza ni inna. Wszystko zaley wycznie do potrzeb
i moliwoci finansowych. Ta klasyfikacja zostaa utworzona jedynie w
celu uatwienia i wikszej zwizoci dyskusji na temat systemw Beowulf.
Dzia "Projektowanie systemu" moe pomc ustali, ktry typ systemu
pardziej pasuje do twoich potrzeb.
33.. OOggllnnyy ooppiiss aarrcchhiitteekkttuurryy
33..11.. JJaakk ttoo wwyyggllddaa??
Myl, e najlepszym sposobem opisu architektury superkomputera Beowulf
jest uycie przykadu, ktry jest bardzo podobny do prawdziwego
Beowulf'a, ale znany wikszoci administratorw systemu. Przykad
najbliszy Beowulf'owi to laboratorium komputerw Unix z serwerem i
klientami. Aby by bardziej szczegowym uyj jako przykadu laboratorium
komputerw DEC Alpha na Katedrze Nauk Komputerowych, USQ. Serwer nazywa
si _b_e_l_d_i_n, a klienci nazywaj si _s_c_i_l_a_b_0_1, _s_c_i_l_a_b_0_2, a do _s_c_i_l_a_b_2_0.
Wszyscy klienci maj zainstalowan lokaln kopi systemu operacyjnego
Digital Unix 4.0, ale korzystaj z katalogw uytkownika (/home) oraz
/usr/local serwera poprzez NFS (Network File System). Kady klient
posiada wpis dla serwera i wszystkich pozostaych klientw w swoim pliku
/etc/hosts.equiv, wic wszyscy klienci mog uruchomi rsh na kadym innym.
Serwer jest jednoczenie serwerem NIS dla caego laboratorium, wic
informacje ksigowania s identyczne dla wszystkich maszyn. Osoba moe
siedzie przed konsol _s_c_i_l_a_b_0_2, zalogowa si i pracowa w tym samym
rodowisku, w jakim pracowaa by gdyby zalogowaa si z serwera bdz z
_s_c_i_l_a_b_1_5. Spowodowane jest to tym, e system operacyjny na wszystkich
komputerach jest zainstalowany i skonfigurowany w ten sam sposb, a
katalogi uytkownika /home i /usr/local mieszcz si fizycznie na
serwerze, i s udostpniane przez NFS. Wicej informacji o NIS i NFS
znajdziesz w dokumentach HOWTO NIS oraz NFS.
33..22.. JJaakk wwyykkoorrzzyyssttaa ppoozzoossttaaee wwzzyy??
Gdy mamy ju jakie pojcie o architekturze systemu, moemy spojrze jak
wykorzysta dostpne cykle CPU maszyn w laboratorium komputerowym. Kada
osoba moe zalogowa si na dowolnej maszynie, i uruchomi program i swoim
katalogu domowym, ale moe take wykona to zadanie na innej maszynie
wywoujc po prostu odleg powok. Przykadowo zamy e chcemy obliczy sum
pierwiastkw kwadratowych wszystkich liczb cakowitych od 1 do 10
wcznie. Piszemy prosty program nazwany sigmasqrt (patrz ``kod
rdowy''), ktry wykonuje oblicznia. Aby obliczy sum pierwiastkw
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 upyw czasu podczas wykonywania zadania.
Jak wida, ten przykad zaj jedynie may uamek sekundy (0.029s), ale co
bdzie jeli sprbujemy doda pierwiastki kwadratowe liczb od 1 do
1000000000? Sprbujmy, ponownie obliczajc upyw czasu.
[jacek@beldin sigmasqrt]$ time ./sigmasqrt 1 1000000000
21081851083600.559000
real 16m45.937s
user 16m43.527s
sys 0m0.108s
Tym razem wykonianie programu trwao znacznie duej. Oczywistym pytaniem
jest co moemy zrobi aby przyspieszy wykonanie programu? Jak moemy
zmieni sposb wykonania zadania aby zmniejszy upyw czasu? Oczywist
odpowiedzi jest rozbicie zadania na wiele pod-zada rwnolegych na
wszystkich komputerach. Moemy rozbi jedno due zadanie dodawania na 20
czci, obliczajc jeden zakres pierwiastkw kwadratowych i dodajc je na
kadym wle. Gdy wszystkie wzy zakocz obliczenia i zwrc rezultaty, 20
liczb powinno zosta dodanych do siebie aby otrzyma kocowy 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 zajo to okoo 58.5s. Jest to czas od rozpoczcia zadania do
zakoczenia go przez wszystkie wzy i zwrcenia rezultatu przez potok.
Ten czas nie zawiera kocowego dodania 20 liczb, ale to jedynie may
uamek sekundy, ktry moe zosta zignorowany. Zauwaamy e nastpia znaczna
poprawa przy rwnolegym wykonaniu zadania. Rwnolege zadanie wykonao si
ponad 17 razy szybciej, co jest bardzo dobrym wynikiem przy 20-krotnym
zwikszeniu iloci CPU. Powyszy przykad ma na celu zilustrowanie
najprostszej metody zmiany zwykego kodu na rwnolegy. W praktyce takie
proste przypadki s niezwykle rzadkie, i rne techniki (takie jak API
PVM i PMI) s wykorzystywane do osignicia rwnolegoci.
33..33.. CCzzyymm BBeeoowwuullff rrnnii ssii oodd CCOOWW??
Laboratorium komputerowe opisane powyej jest doskonaym przykadem
klastra stacji roboczych (COW). Tak wic co jest szczeglnego w
Beowulf'ie, i w jaki sposb rni si on od COW? Prawd jest, e nie jest to
wielka rnica, ale Beowulf posiada kilka unikalnych cech. Po pierwsze,
w wikszoci przypadkw wzy-klienci klastra Beowulf nie posiadaj
klawiatury, myszy, karty graficznej czy monitora. Dostp do wzw-klientw
odbywa si poprzez odlege poczenia z wza-serwera, dedykowanego wza-
konsoli lub konsoli szeregowej. Jako e wzy-klienci nie musz mie dostpu
do maszyn spoza klastra, ani maszyny spoza klastra nie musz mie
bezporedniego dostpu do wzw-klientw, powszechnie stosowan praktyk jest
nadawanie wzom-klientom prywatnych adresw IP, z prywatnych zakresw
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 podczon do wiata zewntrznego za pomoc drugiej karty sieciowej
jest wze-serwer. Najczciej korzysta si z systemu poprzez bezporedni
dostp do konsoli serwera, lub poprzez telnet czy odlege logowanie na
serwer z odlegej stacji roboczej. Na serwerze uytkownicy mog edytowa i
kompilowa swj kod, a take uruchamia procesy na wszystkich wzach w
klastrze. W wikszoci przypadkw systemy COW s uywane do oblicze
rwnolegych w nocy i w weekendy, gdy uytkownicy nie korzystaj ze swoich
stacji roboczych do pracy, wykorzystujc w ten sposb z niepotrzebne
cykle procesora. Z kolei maszyna Beowulf jest maszyn dedykowan do
przetwarzania rwnolegego, i zoptymalizowan w tym celu. Beowulf
zapewnia take wikszy wspczynnik ceny do wydajnoci, jako e jest
zbudowany z oglnie dostpnych komponentw i korzysta na og z darmowego
oprogramowania. Beowulf ma take wicej cech pojedynczego systemu, ktre
pomagaj uytkownikom dostrzega klaster Beowulf jako pojedyncz
obliczeniow stacj robocz.
44.. PPllaannoowwaanniiee ssyysstteemmuu
Przed zakupem sprztu dobrym pomysem moe okaza si przemylenie planu
gotowego systemu. Przy tworzeniu systemu Beowulf naley wzi pod uwag
przede wszystkim dwie gwne kwestie sprztowe: typ komputerw/wzw ktrych
masz zamiar uy, oraz sposb ich poczenia. Istnieje jedna kwestia
programowa, ktra moe wpyn na decyzj w sprawie sprztu: biblioteka
komunikacyjna lub API. Bardziej szczegowe rozwaania na temat sprztu i
oprogramowania znajduj si w innym miejscu tego dokumentu.
Mimo e wybr nie jest zbyt wielki, istniej jednak pewne istotne decyzje
ktre musz zosta podjte przy konstruowaniu systemu Beowulf. Jako e
dziedzina wiedzy (bd sztuka) "przetwarzanie rwnolege" posiada wiele
moliwych interpretacji, poniej zamieszczone wprowadzenie do niej.
Jeli nie jeste zainteresowany takim materiaem wprowadzajcym, moesz
pomin t sekcj, jednak zaleca si, aby przeczyta sekcj ``Suitability''
zanim podejmiesz ostateczne decyzje sprztowe.
44..11.. KKrrttkkiiee wwpprroowwaaddzzeenniiee ddoo pprrzzeettwwaarrzzaanniiaa rrwwnnoolleeggeeggoo..
Ta sekcja stanowi wprowadzenie do koncepcji przetwarzania rwnolegego.
NIE jest to wyczerpujcy materia, jest to jedynie krtki opis spraw,
ktre mog by istotne dla projektanta i uytkownika Beowulf'a.
Podczas projektowania i budowania Beowulf'a, wiele z opisanych poniej
zagadnie moe okaza si istotnych dla twoich decyzji. Ze wzgldu na
szczeglne cechy komponentw superkomputera Beowulf, naley uwanie
zastanowi si nad wieloma aspektami, dopki jeszcze zale one od ciebie.
Wcale nie jest tak trudno zrozumie podstawowe zagadnienia zwizane z
przetwarzaniem rwnolegym. W rzeczywistoci gdy ju zrozumie si te
zagadnienia, oczekiwania oka si bardziej rzeczywiste i sukces bdzie
bardziej prawdopodobny. W przeciwiestwie do "wiata sekwencyjnego",
gdzie szybko procesora jest najwaniejszym aspektem, szybko procesora w
"wiecie rwnolegym" jest tylko jednym z wielu aspektw wpywajcych na
ogln wydajno i efektywno systemu.
44..22.. MMeettooddyy pprrzzeettwwaarrzzaanniiaa rrwwnnoolleeggeeggoo
Przetwarzanie rwnolege moe zosta osignite w rny sposb. Z perspektywy
uytkownika istotne jest rozpatrzenie zalet i wad kadej metody. Ponisze
dziay prbuj dostarczy informacji na temat metod przetwarzania
rwnolegego i stwierdzaj, czy maszyna Beowulf podpada pod t kategori.
44..22..11.. PPoo ccoo wwiicceejj nnii jjeeddeenn pprroocceessoorr??
Odpowied na to pytanie jest bardzo istotna. Korzystanie z 8 procesorw
aby uruchomi twj ulubiony edytor tekstw to lekka przesada. A co z
serwerem www, baz danych, programem renderujcym? Moe wicej CPU pomoe.
A co ze zoon symulacj, kodem dynamiki cieczy czy aplikacj grnicz?
Dodatkowe CPU na pewno pomog w tych przypadkach. Faktem jest e
architektury wieloprocesorowe s wykorzystywane do rozwizywania coraz
wikszej liczby problemw.
Najczciej nastpnym pytaniem jest: "Dlaczego potrzebuj dwch czy
czterech CPU? Po prostu poczekam na turbo-hiper ukad 986." Istnieje
kilka powodw:
1. Podczas korzystania z wielozadaniowych systemw operacyjnych mona
robi wicej ni jedn rzecz w tym samym czasie. Jest to naturalna
"rwnolego", ktra moe by atwo wykorzystana przez wicej ni jeden tani
CPU.
2. Szybko procesorw podwaja si co kade 18 miesicy, ale co z prdkoci
pamici i dysku twardego? Niestety te szybkoci nie rosn tak szybko,
jak szybko CPU. Pamitaj, e wikszo aplikacji wymaga dostpu do pamici
i twardego dysku. Wykonywanie zada rwnolegle jest sposobem obejcia
tych ogranicze.
3. Badania wskazuj, e szybko procesorw przestanie rosn dwukrotnie co
18 miesicy po roku 2005. Istniej pewne bardzo powane przeszkody
ktre naley pokona aby utrzyma ten wskanik.
4. Zalenie od aplikacji, przetwaanie rwnolege moe przyspieszy dziaanie
od 2 do 500 razy (w pewnych przypadkach nawet wicej). Taka wydajno
nie jest dostpna przy uyciu pojedynczego procesora. Nawet
superkomputery, ktre kiedy korzystay z bardzo szybkiego,
specjalnego procesora teraz s budowane z wielu oglnodostpnych CPU.
Jeli do rozwizania zoonego problemu potrzebujesz szybkoci,
przetwarzanie rwnolege jest warte rozwaenia. Poniewa przetwarzanie
rwnolege moe zosta zaimplementowane na rne sposoby, rozwizanie
problemu wymaga podjcia pewnych bardzo wanych decyzji. Te decyzje mog
drastycznie wpyn na przenono, wydajno i koszt systemu.
Zanim dojdziemy do spraw technicznych, spjrzmy na realny problem dla
przetwaania rwnolegego, korzystajc z przykadu ktry dobrze znamy --
oczekiwania w dugich kolejkach w sklepie.
44..22..22.. SSkklleepp zz pprrzzeettwwaarrzzaanniieemm rrwwnnoolleeggyymm
Rozwamy wielki sklep z omioma kasami zgrupowanymi razem na przedzie
sklepu. Zamy e kada kasa/kady kasjer jest CPU, a kady klient jest
programem komputerowym. Wielko zamwienia kadego klienta jest rozmiarem
programu komputerowego (iloci pracy). Te analogie mog zosta
wykorzystane do zilustrowania poj przetwarzania rwnolegego.
44..22..22..11.. JJeeddnnoozzaaddaanniioowwyy ssyysstteemm ooppeerraaccyyjjnnyy
Tylko jedna kasa jest otwarta, i musi obsuy kadego klienta pojedynczo.
Przykad: MS-DOS
44..22..22..22.. WWiieelloozzaaddaanniioowwyy ssyysstteemm ooppeerraaccyyjjnnyy
Otwarta jest jedna kasa, ale teraz przetwarzany jest tylko fragment
zamwienia klienta, a nastpnie obsugiwany jest fragment zamwienia
klienta nastpnego. Kademu wydaje si, e wszyscy s obsugiwani
jednoczenie, ale jeli nie ma nikogo innego w kolejce klient zostanie
obsuony szybciej.
Przykad: UNIX, NT korzystajcy z jednego CPU
44..22..22..33.. WWiieelloozzaaddaanniioowwee ssyysstteemmyy ooppeerraaccyyjjnnee zz wwiieelloommaa CCPPUU
Teraz sklep dysponuje wieloma kasami. Kade zamwienie moe zosta
przetworzone przez odrbn kas i kolejka moe zosta obsuona szybciej.
Nazywane jest to SMP -- Symmetric Multi-processing. Mimo e istnieje
wiele kas, to jeli jeste sam w kolejce, nie zostaniesz obsuony
szybciej, ni gdyby istniaa tylko jedna kasa.
Przykad: UNIX oraz NT z wieloma CPU
44..22..22..44.. WWttkkii ww wwiieelloozzaaddaanniioowwyymm ssyysstteemmiiee ooppeerraaccyyjjnnyymm zz wwiieelloommaa CCPPUU
Jeli podzielisz produkty w zamwieniu, by moe zdoasz szybciej przej
przez kolejk korzystajc z kilku kas jednoczenie. Najpierw musimy zaoy,
e posiadasz du ilo towaru, poniewa czas powicony na rozbijanie
zamwienia musi zwrci si przez korzystanie z wielu kas. Teoretycznie
powiniene przej kolejk n-razy szybciej ni poprzednio, gdzie `n' to ilo
kas. Gdy kasjer musi podsumowa zamwienie, moe wymieni informacj i
komunikowa si z wszystkimi innymi `lokalnymi' kasami. Kasy mog nawet
`zaglda' do innych kas aby uzyska informacj, ktra przyspieszy ich
prac. Istnieje jednak limit iloci kas w jednym sklepie, aby praca
przebiegaa efektywnie.
Prawo Amdala take ogranicza prdko programu do prdkoci jego
najwolniejszego, sekwencyjnego fragmentu.
Przykad: UNIX lub NT z wielona CPU na jednej pycie gwnej uruchamiajce
programy wielo-wtkowe.
44..22..22..55.. WWyyssyyaanniiee kkoommuunniikkaattww ww wwiieelloozzaaddaanniioowwyycchh ssyysstteemmaacchh zz wwiieelloommaa
CCPPUU
Aby zwikszy wydajno, sklep dodaje 8 kas na tyach sklepu. Jako e nowe
kasy s daleko od kas z przodu, kasjerzy musz przekazywa sobie sumy
czstkowe przez telefon. Ta odlego zwiksza nieco opnienie w komunikacji
midzy kasjerami, ale jeli uda si zminimalizowa komunikacj, to wszystko
jest w porzdku. Jeli masz naprawd wielkie zamwienie, wymagajce
wszystkich kas jednoczenie, to przed obliczeniem zyskw czasowych naley
rozway opnienia komunikacji. W pewnych przypadkach sklep moe posiada
pojedyncze kasy (lub zgrupowania kas) rozmieszczone na terenie caego
sklepu -- kada kasa (lub zgrupowanie) musi komunikowa si przez
telefon. Jako e kady kasjer moe rozmawia z dowolnym innym, nie jest
istotne gdzie oni si znajduj.
Przykad: Jedna lub wicej kopii UNIX lub NT z wieloma CPU na tej samej
lub innej pycie gwnej, porozumiewajcych si poprzez komunikaty.
Powysze scenariusze, mimo e niedokadne, s dobym przykadem ogranicze
nakadanych na system rwnolegy. W przeciwiestwie do pojedynczego CPU
(lub kasy) komunikacja jest istotna.
44..33.. AArrcchhiitteekkttuurryy pprrzzeettwwaarrzzaanniiaa rrwwnnoolleeggeeggoo
Popularne metody i architektury przetwarzania rwnolegego s
zaprezentowane poniej. Mimo e opis ten nie jest pod adnym wzgldem
wyczerpujcy, jest jednak wystarczajcy do zrozumienia podstaw projektu
Beowulf.
44..33..11.. AArrcchhiitteekkttuurryy sspprrzzttoowwee
Istniej dwa podstawowe sposoby czenia sprztu:
1. Maszyny z pamici lokaln, komunikujce si przez komunikaty (klastry
Beowulf)
2. Maszyny z pamici dzielon, komunikujce si przez pami (maszyny SMP)
Typowy Beowulf to zbir jednoprocesorowych maszyn poczonych przez szybk
sie Ethernet, a wic jest systemem z wasn pamici. System SMP to maszyna
z pamici dzielon, ktra moe zosta wykorzystana do przetwarzania
rwnolegego -- aplikacje rwnolege komunikuj si przez pami dzielon. Tak
jak w przykadzie sklepu, maszyny z pamici lokaln (pojedyncze kasy) s
skalowalne do duej liczby CPU, gdy liczba CPU maszyn z pamici dzielon
jest ograniczona przez pami.
Jest jednak moliwe poczenie wielu maszyn z pamici dzielon aby utworzy
"hybrydow" maszyn z pamici dzielon. Te hybrydowe maszyny wygldaj dla
uytkownika jak pojedyncze, due maszyny SMP i czsto zwane s maszynami
NUMA (non uniform memory access -- nietypowy dostp do pamici), poniewa
globalna pami widoczna dla programisty i dzielona przez wszystkie CPU
moe by ukrywana. Jednak na pewnym poziomie maszyna NUMA musi
przekazywa wiadomoci pomidzy lokalnymi obszarami pamici dzielonej.
Moliwe jest take podczenie maszyn SMP jako lokalnych wzw
obliczeniowych. Typowe pyty gwne KLASY I maj 2 lub 4 procesory, jest
to sposb zredukowania kosztw. Wewntrzny scheluder Linuxa okrela, w
jaki sposb te CPU s dzielone. W tym przypadku uytkownik nie moe okreli
odrbnego zadania dla konkretnego procesora SMP. Uytkownik moe jednak
rozpocz dwa niezalene procesy lub proces wielowtkowy i spodziewa si
poprawy wydajnoci w stosunku do systemu z pojedynczym CPU.
44..33..22.. PPrrooggrraammoowwee aarrcchhiitteekkttuurryy AAPPII
Istniej dwa podstawowe sposoby okrelania momentw zbienych w programie:
1. Komunikaty wysyane midzy procesorami
2. Wtki systemu operacyjnego
Istniej inne metody, ale powysze s najszerzej wykorzystywane. Naley
zapamita, e sposb okrelania zbienoci nie musi zalee od warstwy
sprztowej. Zarwno komunikaty, jak i wtki mog zosta zaimplementowane w
systemach SMP, NUMA-SMP jak i klastrach -- mimo e, jak wyjaniono
poniej, istotnymi kwestiami s efektywno i przenono.
44..33..22..11.. KKoommuunniikkaattyy
Z punktu widzenia historii, technologia przekazywania komunikatw
odzwierciedla projekty wczesnych komputerw rwnolegych z lokaln pamici.
Komunikaty wymagaj kopiowania danych, podczas gdy wtki korzystaj z
danych na miejscu. Tajno i szybko kopiowania komunikatw to wartoci
ograniczajce ten model. Komunikat jest stosunkowo prosty: jakie dane
oraz procesor docelowy. Najpopularniejsze API do przesyania komunikatw
to: PVM lub MPI. Przekazywanie komunikatw moe zosta efektywnie
zaimplementowane przy wykorzystaniu wtkw, a komunikaty pracuj rwnie
dobrze na maszynach SMP i pomidzy klastrami maszyn. Zalet korzystania
z komunikatw na maszynach SMP, w przeciwiestwie do wtkw, jest to, e
jeli zdecydujesz si na korzystanie w przyszoci z klastrw, dodawanie
maszyn i skalowanie aplikacji bdzie bardzo atwe.
44..33..22..22.. WWttkkii
Wtki systemu operacyjnego zostay stworzone, poniewa projekty SMP
(symmetrical multiprocessing -- symetryczna wieloprocesowo) dopuszczay
bardzo szybk komunikacj poprzez pami dzielon, oraz synchronizacj
pomidzy zbienymi fragmentami programu. Wtki dziaaj bardzo dobrze na
systemie SMP, poniewa komunikuje si on poprzez pami dzielon. Z tego
powodu uytkownik musi oddzieli dane lokalne od globalnych, w
przeciwnym wypadku programy nie bd dziaa poprawnie. W przeciwiestwie
do komunikatw, wiele operacji kopiowania moe zosta wyeliminowanych
przez uycie wtkw, poniewa dane s dzielone pomidzy procesami (wtkami).
Linux wspomaga wtki POSIX. W przypadku wtkw problemem jest to, e
trudno rozszerzy ich zasig poza maszyn SMP oraz, poniewa dane j
dzielone pomidzy procesory, koherencja pamici podrcznej moe doprowadzi
do opnie. Efektywne rozcignicie wtkw poza granic SMP wymaga technologi
NUMA, ktra jest kosztowna i nie wspomagana bezporednio przez Linuxa.
Implementacja wtkw poprzez wiadomoci jest moliwa
(http://syntron.com/ptools/ptools_pg.htm), ale wtki s czsto
nieefektywne gdy zaimplementowane przy uyciu komunikatw.
Mona wycignc nastpujce wnioski jeli chodzi o wydajno:
wydajno na wydajno w skalowalno
maszynie SMP klastrze
----------- --------------- -----------
messages dobra najlepsza najlepsza
threads najlepsza saba* saba*
* wymaga kosztownej technologii NUMA.
44..33..33.. AArrcchhiitteekkttuurraa aapplliikkaaccjjii
Aby uruchomi aplikacj rwnolegle na wielu CPU, musi ona zosta rozbita
na konkurencyjne czci. Standardowa jednoprocesorowa aplikacja nie
bdzie dziaa szybciej na wielu procesorach. Istniej pewne narzdzia i
kompilatory, ktre potrafi podzieli program, ale przeksztacenie kodu na
rwnolegy nie jest operacj "plug and play". Zalenie od aplikacji, moe
to by proste, ekstremalnie trudne a w pewnych przypadkach nawet
niemoliwe, ze wzgldu na zalenoci algorytmw.
Zanim zostan omwione kwestie sprztowe, koncepcja musi zosta
wprowadzona. Before the software issues can be addressed the concept
of Suitability needs to be introduced.
44..44.. SSuuiittaabbiilliittyy
Odpowiedzi na wikszo pyta dotyczcych przetwarzania rwnolegego jest:
"Wszystko zaley od zastosowania."
Zanim przejdziemy do tego tematu, naley dokona jeszcze jednego bardzo
wanego podziau -- rnicy pomidzy KONKURENCYJNYM i RWNOLEGYM. Dla celw
tej dyskusji zdefiniujemy te dwa pojcia nastpujco:
KONKURENCYJNE czci programu, to te, ktre mog zosta wykonane
niezalenie.
RWNOLEGE czci programu, to te KONKURENCYJE czci, ktre s wykonywane na
osobnym procesorze w tym samym czasie.
Rnica jest bardzo wana, poniewa KONKURENCJA to wasno programu, a
efektywna RWNOLEGO, to wano maszyny. Na og wykonywanie RWNOLEGE
powoduje przyspieszenie pracy. Czynnikiem ograniczajcym wydajno
systemu rwnolegego jest prdko komunikacji i opnienie pomidzy wzami
(opnienie wystpuje take w wielowtkowych aplikacji SMP, z powodu
koherencji pamici podrcznej). Wikszo programw testujcych wydajno jest
wysoce rwnolega, a komunikacja i opnienia nie s wskim gardem. Ten tym
zadania mona nazwa "typowo rwnolegym". Inne aplikacje nie s takie
proste i wywoanie KONKURENCYJNYCH czci programu RWNOLEGLE moe spowolni
go, zmniejszajc tym samym zysk z innych KONKURENCYJNYCH czci. Mwic
prosto, koszt czasu komunikacji musi zwrci si w oszczdnociach czasu
obliczenia, w przeciwnym wypadku RWNOLEGE wykonanie KONKURENCYJNEJ
czci jest nieefektywne.
Zadaniem programisty jest stwierdzenie, ktre KONKURENCYJNE czci
programu POWINNY by wykonane RWNOLEGLE, a ktre NIE. Od odpowied na te
pytania zaley EFEKTYWNO aplikacji. Poniszy wykres podsumowuje sytuacj:
| *
| *
| *
% | *
zasto- | *
sowa | *
| *
| *
| *
| *
| *
| ****
| ****
| ********************
+-----------------------------------
czas komunikacji/czas przetwarzania
W idealnym komputerze rwnolegym, wskanik komunikacji/przetwarzania
jest rwny i wszystko, co jest KONKURENCYJNE moe zosta zaimplementowane
RWNOLEGLE. Niestety, rzeczywiste komputery rwnolege, wczajc w to
maszyny z pamici dzielon, podlegaj efektom pokazanym na wykresie.
Podczas projektowania Beowulfa, uytkownicy powinni zapamita ten
wykres, poniewa efektywno rwnolega zaley do wskanika czasu komunikacji
do czasu przetwarzania dla KONKRETNEGO KOMPUTERA RWNOLEGEGO. Aplikacje
mog by przenone, ale nie mona zagwarantowa e bd efektywne na innej
platformie.
NA OG NIE ISTNIEJE PRZENONY I EFEKTYWNY PROGRAM RWNOLEGY
Jest jeszcze jedna konsekwencja powyszego wykresu. Jako e efektywno
zaley od wskanika komunikacji/przetwarzania, zmiana jedynie jednego
elementu wskanika nie musi koniecznie powodowa wzrostu szybkoci.
Zmiana prdkoci procesora, nie zmieniajc czasu komunikacji, moe mie
nietypowy wpyw na program. Na przykad podwojenie albo potrojenie
prdkoci CPU, zachowujc t sam prdko komunikacji, moe sprawi, e
poprzednio efektywne RWNOLEGE fragmenty programu stan si bardziej
efektywne gdy zostan uruchomione SEKWENCYJNIE. To znaczy uruchomienie
poprzednio RWNOLEGYCH fragmentw jako SEKWENCYJNE moe okaza si lepsze.
Wykonywanie nieefektywnych czci programu rwnolegle uniemoliwia
uzyskanie maksymalnej prdkoci. Tak wic dodajc szybszy procesor, moesz
spowolni aplikacj (CPU nie wykorzystuje swojej penej szybkoci).
ZMIANA CPU NA SZYBSZY MOE SPOWOLNI APLIKACJ
Podsumowujc, aby wiedzie, czy mona wykorzysta rodowisko rwnolege,
naley przyjrze si, czy konkretna maszyna pasuje do aplikacji. Musisz
wzi pod uwag wiele kwestii, takich jak prdko CPU, kompilator, API
przekazywania komunikatw, sie itd. Naley zauway, e zwyke profilowanie
aplikacji nie zamyka sprawy. Moesz zidentyfikowa fragment programu
wymagajcy wielu oblicze, ale nie znasz kosztw komunikacji tego
fragmentu. Moe si zdarzy, e koszty komunikacji sprawi, e kod rwnolegy
nie bdzie efektywny.
Ostatnia uwaga na temat pewnego niedomwienia. Czsto twierdzi si, e
program "jest RWNOLEGY", ale w rzeczywistoci jedynie zidentyfikowano
KONKURENCYJNE fragmenty. Z powodw podanych powyej program nie jest
RWNOLEGY. Efektywna RWNOLEGO jest wasnoci maszyny.
44..55.. PPiissaanniiee ii pprrzzeennoosszzeenniiee oopprrooggrraammoowwaanniiaa rrwwnnoolleeggeeggoo
Gdy zdecydujesz, e potrzebujesz przetwarzania rwnolegego i chcesz
zaprojektowa i zbudowa Beowulfa, dobrym pomysem jest kilka chwil
zastanowienia nad aplikacj, z poszanowaniem wczeniejszych uwag.
No og moesz zrobi dwie rne rzeczy:
1. I dalej i skonstruowa Beowulfa KLASY I a nastpnie "dopasowa" do
niego swoj aplikacj, lub korzysta z istniejcej rwnolegej aplikacji
o ktrej wiesz, e pracuje na Beowulfie (ale pamitaj o kwestiach
efektywnoci i przenonoci poruszanych wczeniej).
2. Przyjrze si aplikacjom ktre maj dziaa na Beowulfie i na ich
podstawie dokona wyboru sprztu i oprogramowania.
W kadym z przypadkw w pewnym momencie musisz zastanowi si nad
kwestiami efektywnoci. Na og powiniene zrobi trzy rzeczy:
1. Wyznaczy konkurencyjne czci programu
2. Obliczy rwnoleg efektywno
3. Opisa konkurencyjne czci programu
Przyjrzyjmy si im po kolei.
44..55..11.. WWyyzznnaacczzaanniiee kkoonnkkuurreennccyyjjnnyycchh cczzccii pprrooggrraammuu
Ten krok jest czsto nazywany "urwnolegleniem programu". Decyzje
podejmiemy dopiero w kroku 2. Teraz musisz jedynie wyznaczy zalenoci
pomidzy danymi.
Z praktycznego punktu widzenia, aplikacje mog wykazywa dwa typy
konkurencji: oblicze i wejcia/wyjcia. Mimo e w wielu wypadkach
konkurencje oblicze i wejcia/wyjcia s niezalene, to istniej aplikacje,
ktre wymagaj obu. Istniej narzdzia, ktre mog wykona analiz konkurencji
istniejcej aplikacji. Wiele z tych narzdzi jest projektowanych dla
FORTANa. S dwa powody dla ktrych uywa si FORTAN: historycznie wikszo
aplikacji obliczeniowych byo pisanych w FORTANie oraz jest on
atwiejszy w analizie. Jeli nie istniej adne narzdzia, to ten krok moe
okaza si do trudny dla istniejcych aplikacji.
44..55..22.. OObblliicczzaanniiee eeffeekkttyywwnnooccii rrwwnnoolleeggeejj
Bez pomocy narzdzi, ten krok wymaga by uycia metody prb i bdw, lub po
prostu zgadywania. Jeli bierzesz pod uwag pojedyncz aplikacj, postaraj
si okreli czy jest ograniczona przez CPU (granica obliczeniowa) lub
przez twardy dysk (granica wejcia/wyjcia). Wymagania Beowulfa mog by
do rne, zalenie od potrzeb. Na przykad problem ograniczony
obliczeniowo moe wymaga kilku bardzo szybkich CPU i szybkiej sieci z
maym opnieniem, gdy problem ograniczony przez wejcie/wyjcie moe dziaa
lepiej na wolniejszym CPU i szybkiej sieci Ethernet.
To zalecenem czsto zaskakuje wiele osb, poniewa zwykle uwaa si, e
szybszy procesor jest zawsze lepszy. Jest to prawd jeli dysponuje si
nieograniczonym budetem, jednak w przypadku prawdziwych systemw
powinno si minimalizowa koszty. Dla problemw ograniczonych przez
wejcie/wyjcie istnieje prosta zasada (zwana Prawem Eadline'a-Dedkova)
ktra jest do pomocna:
Z dwch komputerw rwnolegych o tej samym zsumowanym wskaniku wydajnoci
CPU lepsz wydajno dla aplikacji z dominujcymi operacjami wejcia/wyjcia
bdzie mia ten, ktry posiada wolniejsze procesory (i prawdopodobnie
take wolniejsz komunikacj midzyprocesorow).
Dowd tego prawa wychodzi poza zakres tego dokumenty, jednak moe
zainteresowa ci dokument _P_e_r_f_o_r_m_a_n_c_e _C_o_n_s_i_d_e_r_a_t_i_o_n_s _f_o_r _I_/_O_-_D_o_m_i_n_a_n_t
_A_p_p_l_i_c_a_t_i_o_n_s _o_n _P_a_r_a_l_l_e_l _C_o_m_p_u_t_e_r_s (w formacie Postscript 109K)
(ftp://www.plogic.com/pub/papers/exs-pap6.ps)
Gdy ju okrelie typ konkurencji aplikacji, musisz obliczy jak efektywna
bdzie ona rwnolegle. Patrz dzia ``Oprogramowanie'' aby znale opis
narzdzi programowych.
W razie nieobecnoci narzdzi, moesz prbowa po prostu zgadn. Jeli ptla
obliczeniowa trwa minuty, a dane mog zosta przesane w cigu sekund, to
prawdopodobnie jest to dobry kandydat na program rwnolegy. Ale
pamitaj, jeli rozbijesz 16-minutow ptle na 32 czci, a transfer danych
wymaga kilku sekund, to zaczyna robi si ciasno.
44..55..33.. OOppiissyywwaanniiee kkoonnkkuurreennccyyjjnnyycchh cczzccii pprrooggrraammuu
Istnieje kilka sposobw opisu konkurencyjnych czci programu: There are
several ways to describe concurrent parts of your program:
1. Wyrane wykonanie rwnolege
2. Domniemane wykonanie rwnolege
Te dwa sposoby rni si gwnie tym, e rwnolego "wyrana" jest okrelana
przez uytkownika, a domniemana jest okrelana przez kompilator.
44..55..33..11.. MMeettooddyy wwyyrraannee
S to po prostu metody, w ktrych uytkownik musi zmodyfikowa kod rdowy
specjalnie dla komputera rwnolegego. Uytkownik musi doda obsug
komunikatw korzystajc z PVM lub MPI, albo wtkw korzystajc z wtkw POSIX
(pamitaj jednak e wtki nie dziaaj na komputerach SMP).
Metody wyrane s bardzo trudne w implementacji i poprawianiu bdw.
Uytkownicy najczciej osadzaj wyrane wywoania funkcji w standardowym
kodzie rdowym FORTAN 77 lub C/C++. Biblioteka MPI dodaje pewne funkcje
uatwiajce implementacj standardowych rwnolegych metod (np. funkcje
scatter/gather). Dodatkowo moliwe jest take uycie standardowych
bibliotek napisanych dla rwnolegych komputerw. Pamitaj jednak, e
przenono nie idzie w parze z efektywnoci.
Ze wzgldw historycznych, wikszo programw operujcych na liczbach zostao
napisanych w FORTANie. Z tego powodu FORTAN posiada najwiksze wsparcie
(narzdzia, biblioteki itp.) dla przetwarzania rwolegego. Teraz wielu
programistw korzysta z C, lub przepisuje istniejce programy FORTAN w
C, jako e C dziaa szybciej. Moe jest prawd, e C jest najblisze
uniwersalnemu kodowi maszynowemu, posiada jednak kilka powanych wad.
Uycie wskanikw w C znacznie utrudnia wyznaczanie zalenoci pomidzy
danymi. Automatyczna analiza wskanikw jest bardzo trudna. Jeli
dysponujesz gotowym programem w FORTANie i mylisz, e mgby uczyni go
rwnolegym w przyszoci -- NIE KONWERTUJ GO NA C!
44..55..33..22.. DDoommnniieemmaannee mmeettooddyy
Domniemane metody to te, w ktrych uytkownik pozostawia niektre (lub
wszystkie) decyzje dotyczce rwnolegoci kompilatorowi. Przykadem jest
FORTAN 90, High Performance FORTAN, Bulk Synchronous Parallel (BSP)
oraz caa lista metod rozwijanych obecnie.
Metody domylne wymagaj od uytkownika podania pewnych informacji na
temat konkurencyjnej natury aplikacji, ale to kompilator podejmie
nastpnie decyzje jak wykonywa t konkurencj rwnolegle. Te metody
gwarantuj pewien stopie przenonoci i efektywnoci, jednak cigle nie
istnieje najlepszy sposb opisu problemu konkurencyjnego dla komputera
rwnolegego.
55.. ZZaassoobbyy ddoottyycczzccee BBeeoowwuullffaa
55..11.. PPuunnkkttyy ssttaarrttoowwee
+o Lista dyskusyjna Beowulf. Aby si zapisa napisz list do beowulf-
request@cesdis.gsfc.nasa.gov ze sowem _s_u_b_s_c_r_i_b_e w treci listu.
+o Beowulf Homepage http://www.beowulf.org
+o Extreme Linux http://www.extremelinux.org
+o Extreme Linux Software from Red Hat http://www.redhat.com/extreme
55..22.. DDooccuummeennttaattiioonn
+o Najnowsza wersja Beowulf HOWTO
http://www.sci.usq.edu.au/staff/jacek/beowulf.
+o Building a Beowulf System
http://www.cacr.caltech.edu/beowulf/tutorial/building.html
+o Jacek's Beowulf Links
http://www.sci.usq.edu.au/staff/jacek/beowulf.
+o Beowulf Installation and Administration HOWTO (DRAFT)
http://www.sci.usq.edu.au/staff/jacek/beowulf.
+o Linux Parallel Processing HOWTO
http://yara.ecn.purdue.edu/~pplinux/PPHOWTO/pphowto.html
55..33.. DDookkuummeennttyy
+o Chance Reschke, Thomas Sterling, Daniel Ridge, Daniel Savarese,
Donald Becker, and Phillip Merkey _A _D_e_s_i_g_n _S_t_u_d_y _o_f _A_l_t_e_r_n_a_t_i_v_e
_N_e_t_w_o_r_k _T_o_p_o_l_o_g_i_e_s _f_o_r _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n.
Proceedings Fifth IEEE International Symposium on High Performance
Distributed Computing, 1996.
http://www.beowulf.org/papers/HPDC96/hpdc96.html
+o Daniel Ridge, Donald Becker, Phillip Merkey, Thomas Sterling
Becker, and Phillip Merkey. _H_a_r_n_e_s_s_i_n_g _t_h_e _P_o_w_e_r _o_f _P_a_r_a_l_l_e_l_i_s_m _i_n
_a _P_i_l_e_-_o_f_-_P_C_s. Proceedings, IEEE Aerospace, 1997.
http://www.beowulf.org/papers/AA97/aa97.ps
+o Thomas Sterling, Donald J. Becker, Daniel Savarese, Michael R.
Berry, and Chance Res. _A_c_h_i_e_v_i_n_g _a _B_a_l_a_n_c_e_d _L_o_w_-_C_o_s_t _A_r_c_h_i_t_e_c_t_u_r_e
_f_o_r _M_a_s_s _S_t_o_r_a_g_e _M_a_n_a_g_e_m_e_n_t _t_h_r_o_u_g_h _M_u_l_t_i_p_l_e _F_a_s_t _E_t_h_e_r_n_e_t _C_h_a_n_n_e_l_s
_o_n _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n. Proceedings, International
Parallel Processing Symposium, 1996.
http://www.beowulf.org/papers/IPPS96/ipps96.html
+o Donald J. Becker, Thomas Sterling, Daniel Savarese, Bruce Fryxell,
Kevin Olson. _C_o_m_m_u_n_i_c_a_t_i_o_n _O_v_e_r_h_e_a_d _f_o_r _S_p_a_c_e _S_c_i_e_n_c_e _A_p_p_l_i_c_a_t_i_o_n_s
_o_n _t_h_e _B_e_o_w_u_l_f _P_a_r_a_l_l_e_l _W_o_r_k_s_t_a_t_i_o_n. Proceedings,High Performance
and Distributed Computing, 1995.
http://www.beowulf.org/papers/HPDC95/hpdc95.html
+o Donald J. Becker, Thomas Sterling, Daniel Savarese, John E.
Dorband, Udaya A. Ranawak, Charles V. Packer. _B_E_O_W_U_L_F_: _A _P_A_R_A_L_L_E_L
_W_O_R_K_S_T_A_T_I_O_N _F_O_R _S_C_I_E_N_T_I_F_I_C _C_O_M_P_U_T_A_T_I_O_N. Proceedings, International
Conference on Parallel Processing, 95.
http://www.beowulf.org/papers/ICPP95/icpp95.html
+o Dokumenty na stronie Beowulf
http://www.beowulf.org/papers/papers.html
55..44.. OOpprrooggrraammoowwaanniiee
+o PVM - Parallel Virtual Machine
http://www.epm.ornl.gov/pvm/pvm_home.html
+o LAM/MPI (Local Area Multicomputer / Message Passing Interface)
http://www.mpi.nd.edu/lam
+o BERT77 - FORTRAN program konwertujcy
http://www.plogic.com/bert.html
+o Oprogramowanie ze strony Beowulf Project
http://beowulf.gsfc.nasa.gov/software/software.html
+o Jacek's Beowulf-utils ftp://ftp.sci.usq.edu.au/pub/jacek/beowulf-
utils
+o bWatch - program monitorujcy klaster
http://www.sci.usq.edu.au/staff/jacek/bWatch
55..55.. MMaasszzyynnyy BBeeoowwuullff
+o Avalon skada si z 140 procesorw Alpha, 36GB RAM i jest
prawdopodobnie najszybsz maszyn Beowulf, osigajc prdko 47.7Gflops i
zajmujc 144-te miejsce w rankingu Top 500.
http://swift.lanl.gov/avalon/
+o Megalon-A Massively PArallel CompuTer Resource (MPACTR) skada si z
14 poczwrnych wzw Pentium Pro 200 i 14 GB RAM.
http://megalon.ca.sandia.gov/description.html
+o theHIVE - Highly-parallel Integrated Virtual Environment jest innym
szybkim superkomputerem Beowulf. theHIVE skada si z 64 wzw, 128 CPU
posiadajc w sumie 4GB RAM. http://newton.gsfc.nasa.gov/thehive/
+o Topcat to o wiele mniejsza maszyna, skada si z 16 CPU i 1.2GB RAM.
http://www.sci.usq.edu.au/staff/jacek/topcat
+o MAGI cluster - to bardzo interesujca strona z wieloma dobrymi
odnonikami. http://noel.feld.cvut.cz/magi/
55..66.. IInnnnee iinntteerreessuujjccee ssttrroonnyy
+o SMP Linux http://www.linux.org.uk/SMP/title.html
+o Paralogic - kup Beowulfa http://www.plogic.com
55..77.. HHiissttoorriiaa
+o Legends - Beowulf http://legends.dm.net/beowulf/index.html
+o The Adventures of Beowulf
http://www.lnstar.com/literature/beowulf/beowulf.html
66.. KKoodd rrddoowwyy
66..11.. ssuumm..cc
/* 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;
}
66..22.. ssiiggmmaassqqrrtt..cc
/* 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;
}
66..33.. pprruunn..sshh
#!/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&
