Semestr´ aln´ı projekt X36PAR 2008/2009: Paraleln´ı algoritmus pro ˇ reˇ sen´ı probl´ emu Marek Handl 5. roˇ cn´ık, obor v´ ypoˇ cetn´ı technika ˇ K336 FEL CVUT, Karlovo n´ am. 13, 121 35 Praha 2 May 17, 2009
1
Definice probl´ emu a popis sekvenˇ cn´ıho algoritmu
MOT - Uspoˇ r´ ad´ an´ı elektromagnet˚ u v motoru Vstupn´ı data n = pˇrirozen´e ˇc´ıslo, n >= 1 M [1..n] = mnoˇzina n pˇrirozen´ ych ˇc´ısel pˇredstavuj´ıc´ı indukˇcnosti elektromagnet˚ u P [1..n] = mnoˇzina n u ´hl˚ u v pol´arn´ıch souˇradnic´ıch elektromagnet˚ u na jednotkov´e kruˇznici (v radi´anech) Zad´ an´ı Naleznete usporadani elektromagnetu v motoru, jehoz stator tvori jednotkovou kruznici osazenou magnety na souradnicich p 1,..,p n s indukci m 1,..,m n tak, aby osa jeho rotoru co nejmene hazela. Uvedeny problem muzeme vyjadrit matematicky jako nalezeni permutaci poradi hmotnych bodu (vsech n bodu rozmistenych na jednotkove kruznici na pozicich P) tak, aby vychylka teziste od pocatku souradneho systemu (0,0) byla minimalni. Vzorec pro polohu teziste T(x,y): P x = ni=1 mi · xi Pn y = i=1 mi · yi V´ ystup Pˇriˇrazen´ı hodnot indukˇcnosti k jednotliv´ ym u ´hl˚ um tak, aby osa byla co nejbl´ıˇze stˇredu. ˇ sen´ı Reˇ Body, kam lze um´ıstit magnety jsou pevnˇe d´any - formou u ´hl˚ u. Hledaj´ı se tedy permutace mnoˇziny indukˇcnost´ı. Metodou hrub´e s´ıly jsou zkoum´ any vˇsechny permutace a najde se ta s nejlepˇs´ım ohodnocen´ım - vzd´alenost ”indukˇcn´ıho tˇeˇziˇstˇe” je minim´aln´ı. Program pouˇz´ıv´a vlastn´ı z´asobn´ık, kter´ y simuluje rekurzi. V´ ypoˇcet vytv´aˇr´ı a proch´ az´ı strom, coˇz pˇredstavuje tvorbu permutac´ı. Strom se proch´ az´ı do hloubky. Koˇren m´a stupeˇ n roven poˇctu elektromagnet˚ u, na kaˇzd´e dalˇs´ı hladinˇe se stupeˇ n o jedna sniˇzuje. Strom obsahuje dvˇe hladiny s uzly stupnˇe jedna. V kaˇzd´em kroku algoritmu se vybere jeden uzel z vrcholu z´asobn´ıku. Pokud se jedn´a o uzel z nejniˇzˇs´ı hladiny, provede se v´ ypoˇcet ohodnocen´ı, jelikoˇz permutace je jiˇz hotov´a, a v´ ysledek se porovn´ a s nejlepˇs´ım dosavadn´ım ˇreˇsen´ım. V opaˇcn´em pˇr´ıpadˇe se na z´asobn´ık um´ıst´ı n´asledn´ıci uzlu. Poˇcet permutac´ı a tedy i poˇcet list˚ u stromu je n!. Poˇcet stav˚ u a tedy i poˇcet vˇsech uzl˚ u 1
Poˇcet magnet˚ u Namˇeˇren´ y ˇcas [min] 9 0,017 10 0,217 11 2,500 12 32,283 Table 1: Namˇeˇren´e ˇcasy sekvenˇcn´ıho programu stromu je n! ·
Pn
1 k=0 k! ,
coˇz se jiˇz pro mal´a n bl´ıˇz´ı n´asleduj´ıc´ımu vztahu. pocetStavu = e · n!
(1)
Vzhledem k faktori´aln´ı sloˇzitosti lze volit pouze mal´ y rozsah poˇctu magnet˚ u. V n´asleduj´ıc´ı tabulce jsou uvedeny namˇeˇren´e ˇcasy v´ ypoˇctu sekvenˇcn´ıho ˇreˇsen´ı na svazku Star. Program se spouˇst´ı s jedn´ım parametrem ud´avaj´ıc´ım vstupn´ı soubor. Je moˇzn´e vyuˇz´ıt program tak´e k vygenerov´an´ı pseudon´ahodn´eho vstupn´ıho souboru, syntaxe: ”program soubor -g pocet magnetu”. Program vypisuje v´ ysledek na standardn´ı v´ ystup a tak´e vytv´aˇr´ı html soubor, kde je v´ ysledek jednoduˇse vizualizov´ an.
2
Popis paraleln´ıho algoritmu a jeho implementace v MPI
Z´akladn´ı v´ ypoˇcet expanze uzlu je v paraleln´ım ˇreˇsen´ı shodn´ y s uveden´ ym sekvenˇcn´ım algoritmem. Nav´ıc ale pˇrin´aˇs´ı moˇznost dˇelen´ı z´asobn´ıku a komunikaci mezi procesy. K dˇelen´ı z´asobn´ıku byla pouˇzita technika ˇrez´ an´ı u dna. Proces si zjist´ı kolik mu pˇriˇslo ˇz´adost´ı o pr´aci (poˇcet oznaˇcme r). Pot´e vypoˇcte kolik pr´ace reprezentuje obsah jeho z´asobn´ıku - v´ ypoˇctem velikosti podstrom˚ u jednotliv´ ych uzl˚ u na z´asobn´ıku (viz rovnice 1). Objem pr´ace vydˇel´ı ˇc´ıslem r + 1 a pot´e postupnˇe odeb´ır´ a uzly ze dna z´asobn´ıku, dokud se nedos´ahne poˇzadovan´e velikosti. Z odeb´ıran´ ych uzl˚ u se vytv´aˇr´ı nov´ y z´asobn´ık a ten se pot´e pos´ıl´a procesu, kter´ y ˇz´adal o pr´aci. K dˇelen´ı nedoch´ az´ı pokud z´asobn´ık pˇredstavuje jiˇz jen m´alo pr´ace - ud´ano konstantou ve zdrojov´em k´odu, aktu´alnˇe je hodnota 10000 stav˚ u. Pro pˇrenos je z´asobn´ık k´odov´an do human-readable formy. Jedn´a se o string skl´adaj´ıc´ı se z cel´ ych ˇc´ısel oddˇelen´ ych mezerami. Nejprve je uveden poˇcet uzl˚ u v z´asobn´ıku a pak n´asleduj´ı jednotliv´e uzly. Kaˇzd´ y uzel se pˇrevede na permutaci indukˇcnost´ı, pˇresnˇeji na indexy do pole indukˇcnost´ı. Hled´an´ı d´arce je ˇreˇseno individu´aln´ım ˇc´ıtaˇcem kaˇzd´eho procesu. Ukonˇcen´ı v´ ypoˇctu se prov´ad´ı pomoc´ı algoritmu pro distribuovan´e ukonˇcen´ı v´ ypoˇctu (ADUV), kter´e vyuˇz´ıv´a dvojbarevn´eho peˇska. Z´akladn´ı popis bˇehu programu. Root proces zaˇcne s v´ ypoˇctem hned od zaˇc´ atku. Ostatn´ı procesy poˇslou root procesu ˇz´adost o pr´aci. Jakmile m´a root proces alespoˇ n n uzl˚ u na z´asobn´ıku, rozdˇel´ı ho a odeˇsle ˇzadatel˚ um. Pak poˇc´ıtaj´ı vˇsechny procesy stejnˇe - prov´ adˇej´ı expanze stav˚ u a po kaˇzd´ ych 1000 (ˇc´ıslo je nastaviteln´e pomoc´ı konstanty ve zdrojov´em k´odu) iterac´ıch kontroluj´ı, jestli jim nepˇriˇsly nˇejak´e zpr´avy. Existuj´ı tyto druhy zpr´av ˇz´adost o pr´aci, pr´ace od jin´eho procesu, neposkytnut´ı pr´ace od jin´eho procesu, peˇsek a ukonˇcen´ı v´ ypoˇctu. Proces ˇz´ad´a o pr´aci, pokud jiˇz nem´a dalˇs´ı stavy na z´asobn´ıku. Pokud mu pˇrijde pr´ace od jin´eho procesu, uloˇz´ı ji na sv˚ uj z´asobn´ık a zaˇcne znovu se standardn´ı 2
Sekvenˇcn´ı ˇcas: 2,5 min Poˇcet proces˚ u 2 4 Namˇeˇren´e ˇcasy v minut´ ach InfiniBand 1,979 0,972 Ethernet 1,995 0,978 Zrychlen´ı InfiniBand 1,263 2,572 Ethernet 1,253 2,556
8
12
24
0,493 0,492
0,329 0,378
0,169 0,216
5,071 5,081
7,599 6,614
14,793 11,574
Table 2: Mˇeˇren´ı 1 - 11 magnet˚ u Sekvenˇcn´ı ˇcas: 2,5 min Poˇcet proces˚ u 2 4 Namˇeˇren´e ˇcasy v minut´ ach InfiniBand 1,979 0,975 Ethernet 1,966 0,978 Zrychlen´ı InfiniBand 1,263 2,564 Ethernet 1,272 2,556
8
12
24
0,488 0,490
0,328 0,329
0,168 0,168
5,123 5,102
7,622 7,599
14,881 14,881
Table 3: Mˇeˇren´ı 2 - 11 magnet˚ u expanz´ı. Pokud obdrˇz´ı zpr´avu se zam´ıtnut´ım poskytnut´ı pr´ace, pt´a se dalˇs´ıho procesu, ale kaˇzd´eho procesu se pt´a v ˇradˇe nejv´ yˇse jednou. Pokud root proces obdrˇz´ı v ˇradˇe zam´ıtnut´ı od kaˇzd´eho procesu (aniˇz by mezit´ım obdrˇzel pr´aci), vyˇsle peˇska. Po zpracov´ an´ı vˇsech stav˚ u (a korektn´ım obˇehu peˇska), vyˇsle root proces vˇsem ostatn´ım zpr´avu o ukonˇcen´ı v´ ypoˇctu. Pot´e se nalezne nejlepˇs´ı ˇreˇsen´ı pomoc´ı funkce MPI Reduce. Pokud nejlepˇs´ı ˇreˇsen´ı nevlastn´ı root proces, poˇz´ad´a o nˇej a bude mu zasl´ano. Pak jiˇz dojde jen k v´ ypisu ˇreˇsen´ı a program konˇc´ı. Program se spouˇst´ı s jedn´ım parametrem ud´avaj´ıc´ım vstupn´ı soubor. Pro paraleln´ı v´ ypoˇcet na svazku Star je nutno pouˇz´ıt Sun Grid Engine. Kaˇzd´ y proces m´a sv˚ uj v´ ystupn´ı soubor s n´azvem C processI, kde C je poˇcet proces˚ u pouˇzit´ ych k v´ ypoˇctu a I je ˇc´ıslo procesu z pohledu MPI. Co vˇsechno se zapisuje do v´ ystupn´ıch soubor˚ u, lze nastavit pomoc´ı konstant ve zdrojov´em k´odu. Standardnˇe je tak´e vytvoˇren jeden html soubor s vizualizac´ı ˇreˇsen´ı a popisem instance.
3
Namˇ eˇ ren´ e v´ ysledky a vyhodnocen´ı
V´ ysledky mˇeˇren´ı jsou uvedeny v tabulk´ach 2, 3 a 4. Jsou vˇzdy uvedeny namˇeˇren´e ˇcasy ˇreˇsen´ı instance a vypoˇcten´e hodnoty paraleln´ıho zrychlen´ı. Zrychlen´ı je tak´e graficky zn´azornˇeno v grafech 1, 2 a 3. Z d˚ uvodu faktori´aln´ı sloˇzitosti jsou rozumnˇe mˇeˇriteln´e jen instance velikosti 11 a 12 magnet˚ u.
3.1
Vyhodnocen´ı
V prvn´ım mˇeˇren´ı byl znateln´ y rozd´ıl mezi ˇcasy namˇeˇren´ ymi s pouˇzit´ım s´ıtˇe InfiniBand a Ethernet. V dalˇs´ıch mˇeˇren´ıch je tento rozd´ıl jiˇz nepatrn´ y. I z povahy probl´emu lze usu-
3
25 InfiniBand Ethernet Linear 20
zrychleni
15
10
5
0 0
5
10
15
20
25
pocet procesu
Figure 1: Mˇeˇren´ı 1 - paraleln´ı zrychlen´ı Sekvenˇcn´ı ˇcas: 32,283 min Poˇcet proces˚ u 2 4 Namˇeˇren´e ˇcasy v minut´ ach InfiniBand 25,163 12,473 Ethernet 24,965 12,563 Zrychlen´ı InfiniBand 1,283 2,588 Ethernet 1,293 2,570
8
12
24
6,247 6,275
4,177 4,163
2,093 2,091
5,168 5,145
7,729 7,755
15,424 15,439
Table 4: Mˇeˇren´ı 3 - 12 magnet˚ u zovat, ˇze rozd´ıl mezi tˇemito s´ıtˇemi by mˇel b´ yt minim´aln´ı, protoˇze ke komunikaci doch´ az´ı m´alo a pˇren´aˇsej´ı se jen mal´a data - typicky jednotky uzl˚ u na z´asobn´ıku. V´ ysledky prvn´ıho mˇeˇren´ı s pouˇzit´ım Ethernetu tedy byly pravdˇepodobnˇe ovlivnˇeny moment´ aln´ım stavem syst´emu - vyt´ıˇzen´ı procesor˚ u a komunikaˇcn´ıch s´ıt´ı zp˚ usoben´e ud´alostmi mimo rozsah testovan´eho programu. Zrychlen´ı je aˇz na konstantu line´arn´ı. Tato konstanta je pˇribliˇznˇe rovna 1,55 a bylo vypozorov´ano, ˇze je zp˚ usobena vˇetˇs´ı sloˇzitost´ı a m´enˇe efektivn´ım k´odem paraleln´ıho ˇreˇsen´ı. Pokud se srovn´a ˇcas dosaˇzen´ y sekvenˇcn´ım ˇreˇsen´ım a ˇcas paraleln´ıho ˇreˇsen´ı bˇeˇz´ıc´ı jen na jednom procesu, dospˇejeme ke stejn´e hodnotˇe konstanty. Hodnotu konstanty by bylo pravdˇepodobnˇe moˇzn´e sn´ıˇzit optimalizac´ı k´odu a pˇrekladu.
3.2
Z´ avˇ er
Zadan´ y probl´em uspoˇr´ad´an´ı elektromotoru lze dobˇre paralelizovat, jelikoˇz stavov´ y prostor je pravideln´ y a lze na nˇej pohl´ıˇzet jako na strom. Neexistuj´ı tu tedy cykly a v´ ypoˇcty jednotliv´ ych proces˚ u jsou na sobˇe nez´avisl´e. Z tˇechto d˚ uvod˚ u a tak´e d´ıky faktori´aln´ı sloˇzitosti je probl´em dobˇre ˇsk´alovateln´ y.
4
25 InfiniBand Ethernet Linear 20
zrychleni
15
10
5
0 0
5
10
15
20
25
pocet procesu
Figure 2: Mˇeˇren´ı 2 - paraleln´ı zrychlen´ı Pouˇzit´e algoritmy dˇelen´ı z´asobn´ıku a hled´an´ı d´arce jsou jednoduch´e, ale funkˇcn´ı a pro dan´ y probl´em postaˇcuj´ıc´ı. Komunikace mezi procesy prob´ıh´a pomoc´ı kr´atk´ ych zpr´av, jelikoˇz je vˇzdy potˇreba pˇren´ aˇset jen mal´e mnoˇzstv´ı dat. Ide´aln´ı stav nast´av´a pokud se poˇcet procesor˚ u rovn´ a poˇctu magnet˚ u. V tomto pˇr´ıpadˇe root proces provede jednu expanzi a m˚ uˇze vˇsem ostatn´ım proces˚ um rozeslat po jednom uzlu. Kaˇzd´ y proces pot´e prohled´av´a stejnˇe velk´e stavov´ y prostor. Za pˇredpokladu, ˇze procesy bˇeˇz´ı stejnˇe rychle, skonˇc´ı vˇsechny ve stejnou chv´ıli a po obˇehnut´ı peˇska jiˇz nen´ı tˇreba ˇz´adn´e dalˇs´ı komunikace. V obecn´em pˇr´ıpadˇe samozˇrejmˇe procesy skonˇc´ı v jin´ y ˇcas a je moˇzn´e, ˇze budou ˇz´adat a dost´avat pr´aci od jin´ ych proces˚ u. Jak´akoli takov´ a akce vˇsak sniˇzuje efektivitu. Stupeˇ n paralelizmu se empiricky nepodaˇrilo zjistit. Dan´ y probl´em d´ıky sv´e pravidelnosti a pˇredv´ıdatelnosti v´ ypoˇctu lze velmi dobˇre paralelizovat. Lze pˇredpokl´adat, ˇze stupeˇ n paralelizmu je i pro pouˇzit´a n velmi vysok´ y, urˇcitˇe alespoˇ n v ˇr´ adu stovek. Nicm´enˇe k mˇeˇren´ı bylo moˇzno pouˇz´ıt jen 24 proces˚ u. Pro stanoven´ı meze, kdy rozklad v´ ypoˇctu na v´ıce proces˚ u pˇrest´ av´ a b´ yt v´ yhodn´ y je nutn´ a znalost syst´emu. Je tˇreba m´ıt zmˇeˇreno rychlost prov´ adˇen´ı v´ ypoˇctu a rychlost pˇrenosov´e s´ıtˇe. Komunikace je obecnˇe ˇcasovˇe n´aroˇcn´ a operace, a proto se nevyplat´ı pos´ılat mal´e mnoˇzstv´ı pr´ace. Program byl pro potˇreby mˇeˇren´ı odhadem nastaven, aby pos´ılal pr´aci jen pokud pˇredstavuje v´ıce jak 10000 stav˚ u a toto nastaven´ı se osvˇedˇcilo.
4
Literatura ˇ • Paraleln´ı syst´emy a algoritmy, Prof. Ing. Pavel Tvrd´ık, CSc., skripta, CVUT 2006 • Str´anky pˇredmˇetu X36PAR
5
25 InfiniBand Ethernet Linear 20
zrychleni
15
10
5
0 0
5
10
15
20
pocet procesu
Figure 3: Mˇeˇren´ı 3 - paraleln´ı zrychlen´ı
6
25
