Ask Your Question
2

MI-PPR ukončení výpočtu

asked 2014-11-15 16:20:14 +0100

Iva Houdková gravatar image

updated 2014-11-15 19:55:32 +0100

shejby gravatar image

Pracuju na paralelní verzi semestrálky hledání minimálních koster. Mám jasně danou spodní mez - pokud některý procesor najde kostru stupně 2, je to automaticky ta nejlepší možná a měl by se ukončit výpočet. Ale tak nějak netuším, jak to udělat.

Nedělala jsem ještě ani normální ukončení výpočtu při projití všech dat, ale mám funkční inicializační rozšíření zásobníku a rozeslání dat procesorům. Můj hlavní problém je nějaká synchronizace. Pokud se stane, že více procesorů najednou najde tu kostru stupně 2, tak se to deadlockne, ať se to snažím ukončit jakkoliv. Zkoušela jsem odeslat všem ostatním zprávu o konci výpočtu a čekat na potvrzení, což logicky nefunguje, protože když to udělá víc procesorů najednou, čekají pak donekonečna. Zkoušela jsem použít i tu redukci, ale to už se dokonce ani nedeadlockne, prostě to skončí bez chyb, i když podle výpisů je vidět, že ty procesy stejně přestaly pracovat někde uprostřed kódu.

Ta bariéra mi na tohle přijde nesmysl, protože jestli musí být umístěná v kódu tak, že k ní dojdou úplně všechny procesory, tak jí na tohle těžko můžu použít a bariérovat to po každém rozšíření zásobníku se mi taky nezdá jako moc dobrý řešení. Stejně tak broadcast jak jsem to pochopila taky musí volat všichni.

Možná se ptám na nějakej úplnej nesmysl a mám úplně špatně celej kód (což je dost dobře možný :D), ale už se tu s tím plácám spoustu hodin a trochu mi to leze na mozek :D

edit retag flag offensive close delete

Comments

Protože dobrou odpověď už poslal @Josef Kokeš, tak jen okomentuji, že se můžeš podívat třeba sem: https://github.com/hroncok/mi-ppr-krs - také tam může nastat situace, že už není třeba počítat dál.

Miro Hrončok ( 2014-11-16 20:24:05 +0100 )edit

1 Answer

Sort by » oldest newest most voted
2

answered 2014-11-15 16:44:33 +0100

Josef Kokeš gravatar image

updated 2014-11-17 14:41:37 +0100

V třetí přednášce je (thx. @Filip Vondrášek) první přednášce býval vždycky algoritmus ukončení výpočtu, ve kterém si procesory postupně dokolečka posílají token, který obarvují (modifikovaný Dijkstrův algoritmus ukončení výpočtu). Podle toho, jakou barvu tokenu dostane odesílajícií uzel, se pak pozná , jestli je možne bezpečně skončit, protože už s tím všechny uzly počítají. K deadlocku v tom nemůže dojít. Dá se to použít na váš algoritmus třeba tak, že uzel s optimem pošle zprávu o tomto potěšitelném faktu řídícímu uzlu (0) a ten vyšle ukončovací token.

Jenom doplním pro případ, že by to nebylo zřejmé: Mechanismus zpracování zpráv v jednotlivých uzlech nesmí fungovat tak, že když vyšlu zprávu A, tak budu čekat na odpověďA a všechno ostatní zahazovat. Při čekání na odpověď musím přijímat i zprávy, které nejsou odpovědí, a nějak na ně reagovat. To platí obecně ve všech situacích. Speciálně ale pro čekání na odpověď "ukončuju výpočet" tedy musím umět řešit i všechny standardní zprávy - např. na požadavek o další práci mohu odpovědět "nemám", případně i "nemám, ukončuju se" (aby volající uzel věděl, že je zbytečné žádat další uzly a radši se také přepnul do stavu "ukončuju se"). Ale vlastní ukončení dělá až ten ukončovací token od řídícího uzlu.

edit flag offensive delete publish link more

Comments

1

Tyhle algoritmy teď jsou v třetí přednášce, jen pro doplnění. :)

Filip Vondrášek ( 2014-11-15 23:17:52 +0100 )edit

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2014-11-15 16:20:14 +0100

Seen: 756 times

Last updated: Nov 17 '14