Jak jsem paralelizoval aplikaci?

16.10.2010 15:41 | Přečteno: 1995×

Cíl zvýšit rychlost desktopové aplikace dlouhodobě odolával úsilí programátorů. Dokonce se koketovalo s myšlenkou radikálně přepsat aplikaci, což by ale znamenalo nemožnost v řádném termínu předání provést testování předělané verze a dalších úkonů. Na doporučení mých bývalých klientů jsem byl osloven, abych přinesl jiný pohled a přišel s novými podněty.

Intuice mi napovídala, že cesta vede přes paralelizaci. Něco velmi málo jsem věděl o knihovnách jako MPI a OpenMP, které se zaměřují spíše na numerické úlohy počítané na superpočítačích a problémy jako sdílení operační paměti v clusteru. Nezdály se mi proto úplně vhodné. Kvůli šibeničnímu termínu jsem se rozhodl riskovat znovuobjevování kola. Místo zdlouhavého hledání kvalitního stávajícího řešení jsem zamýšlel vyvinout vlastní primitivní řešení, které by však uspokojovalo z hlediska času potřebného na realizaci vývoje i zvýšení rychlosti v této konkrétním zakázce.

Brzy mě upoutalo, že v důsledku designu algoritmu se během dlouhých intervalů výpočetního času pracuje jen s velmi omezeným počtem proměnných. Zdrojový kód přímo sváděl ke svému rozdělení do souvislých bloků instrukcí, které by respektovali zmíněné "malé množiny relevantních proměnných" a které by nějak umožňovali navrhnout rozklad zátěže mezi jádra. Nedokázal jsem však kvalitně přímo navrhnout jednotlivá vlákna.

Důležité upozornění : Nyní se pro jednoduchost omezme na programy, které jsou posloupností bloků instrukcí. Jak jsem se v praxi vypořádal s bloky instrukcí ve for cyklech, if větvení apod. můžu popsat v některém z následujících postů.

Při další práci jsem vycházel z následujícího banálního pozorování. Nechť proměnná Xč (resp. Xz) je libovolně zvolená proměnná, kterou blok instrukcí I čte (resp. do ní zapisuje). Před vykonáním bloku instrukcí I musí být vykonány předcházející bloky instrukcí:

• které do proměnné Xč zapisují,
• které proměnou Xz čtou nebo do ní zapisují. (Poznámka : Tuto podmínku by šlo potlačit systémem klonování a verzování obsahu proměnné.)

Můžeme s pomocí předchozích podmínek definovat binární relaci "Blok instrukcí I1 je spočítán před blokem instrukcí I2 v každém korektním pořadí bloků." Korektním pořadím bloků míním každou permutaci pořadí bloků, která pro libovolné dva bloky a proměnnou splňuje předchozí podmínky. Bloky instrukcí neuspořádané touto relací mohou být prohozeny či spočteny paralelně.

Programátor by s pomocí této relace (např. s využitím Hasseho diagramů) mohl výkon bloků napevno přidělit jednotlivým vláknům a napsat podmínky vzájemné synchronizace. Bohužel předem neznáme dobu výkonu jednotlivých bloků, která výrazně závisela na hodnotách zpracovávaných proměnných, latenci vstupně-výstupních operací atd., proto kvůli blokovaní "předbíhajících se" vláken "zaostávajícími" vlákny by byl běh více méně sekvenční.

Proto jsem navrhl systém distribuci bloků mezi vlákna až za běhu. Vycházel jsem z notoricky známého hladového algoritmu. Program se spouští ve více vláknech, každé vlákno prochází následující ještě nevykonané bloky instrukcí a začne počítat první blok instrukcí, který je možné začít počítat a který není právě počítán v jiném vlákně. Veškerá práce tak spočívala v:

• návrhu řízení plánovače bloků instrukcí a logiky řešení,
• rozdělení programu do bloků a stanovení, kterou proměnou který blok čte a zapisuje,
• vhodné přepsání for cyklů, if podmínek apod., které jsem zde nepopisoval.

Vlastní splnění prvního úkolu a vypořádání se s dodatečnými problémy (např. rekonstrukce pořadí fragmentů generovaného výstupu) trvalo přibližně dva dny. Zbylé úkoly jsem přenechal autorům paralelizované aplikace. Během dvou dnů stihli rozdělit aplikaci do přibližně padesát bloků instrukcí. Další týden jsme věnovali ladění a různému zlepšování.

Především jsme si všimli, že za určitých podmínek souvisejících s výsledky vstupně/výstupních operací nebudou určité bloky již číst určité proměnné. Do kódu jsme implementovali testy těchto podmínek a navazující dynamické měnění informací o množinách proměnných čtených a zapisovaných jednotlivými bloky instrukcí; tím jsme dosáhli překvapivě výrazného pokroku.

Během necelých dvou týdnů se podařilo snížit odezvu na běžných dvoujádrech v průměru o přibližně 40%, což představuje nárůst výkonu o více jak 60%. Podařilo se tak splnit požadavek zadavatele na alespoň padesátiprocentní navýšení výkonu.

Demonstrační ukázka

K příspěvku jsem připravil kraťoučkou demonstrační ukázku (200 řádků včetně komentářů) v jazyce Java. Demonstrační ukázku jsem narychle napsal pouze za účelem předvedení popisovaného postupu. Kód není nijak otestován. Třída spouští tři vlákna, která vykonávají "maketu" paralelizovaného programu. Čas na vykonání bloků instrukcí simuluji funkcí sleep() s předaným náhodným parametrem.

Protože jsem nedokázal nahrát zdrojový kód jako přílohu příspěvku. Nabízím stažení z mých osobních stránek zde.

       

Komentáře

[David Watzke]

Kdyžtak do toho zdrojáku doplň(te) licenci.

[František Bártík]

Je to drobný neodzkoušený neefektivní demonstrační kód, takže jej uvolňuji jako public domain. Hodí se jen pro "přečtení".

[Non_E]

Označení public domain nepatří licenci. Jde o stav, kdy dílo není vůbec chráněno. Pokud rozhodným právem bude právo ČR, pak nejde dílo žádným právním úkonem zbavit autorskoprávní ochrany (majetkové). Ta uplyne za 70 let od prvního dne roku následujícího po vaší smrti.

Nemám žádný zájem na užití demonstračního kódu, jen upozorňuju na rozšířený omyl. Jinak hezký první zápisek blogu. Přeju hodně tvůrčího elánu

[František Bártík]

Myslím, že takto lze udělit licenci. Předcházejícím komentářem jsem projevil vůli umožnit komukoli užívat dílo v rozsahu užívání děl v režimu volného díla public domain. Tento srozumitelný projev vůle ustanovil licenci k libovolnému užívání díla a posktl ji bezúplatně každému.

(Z hlediska některých cizích právních řádů jsem se tím vzdal majetkových autorských práv.)

[Jakub Lucký]

V česku public domain opravdu nejde... Podle autorského zákona se prostě nejde těch práv vzdát...

Neumím to teď doložit (resp. jsem líný se hrabat v zákoně), ale vysvětlovali nám to na mediálním právu...

[petr_p]

Na to není třeba složité hledání. Český autorský zákon rozděluje práva autorská a majetková. Těch autorských (= já jsem autor) se vzdát nelze.

Předřečník by mohl argumentovat tím, že ta část „licence public domain“, která se týká autorského práva je prostě neplatná, což nemá vliv její na ostatní ustanovení (udělení majetkových práv). Ale jestli by mu to soudce spolkl, to nevím.

[Jakub Lucký]

No, to je rozepsané to, co jsem psal, já myslel doložení (odkazem na příslušný paragraf třeba)

Co se toho soudu týče, nejsem si moc jistý, jak by to dopadlo...

[petr_p]

Odstavec 4 § 11.

[František Bártík]

Pokud tomu správně rozumím (nejsem právník). Autorská práva se dělí na osobnostní a majetková. Z hlediska majetkových se neliší public domain dílo a dílo, ke kterému je každému udělena bezúplatná licence na libovolné používání.

Osobnostní práva jsou nepřenositelná, ale autor může osobnostní práv využít; což jsem učinil:

• právo na pseudonym : při zveřejnění jsem jej nevyužil
• právo udělit svolení změnit či zásahovat do díla : toto svolení jsem udělil každému
• a tak dále

Podle mě ani v osobnostních právech není žádný problém.

[petr_p]

Z hlediska majetkových se neliší public domain dílo a dílo, ke kterému je každému udělena bezúplatná licence na libovolné používání.

Efektivně ano, ale z hlediska formulace tu rozdíl je. Podle českého práva musíte v licenci právo na libovolné užití udělit. Podle amerického stačí říct, že se práva vzdáváte (což není udělení licence).

Spor by mohl nastat, když byste na dílo jen přilepil značku „public domain“. Zatímco jedna strana by tvrdila, že dá rozum, co tím básník chtěl říci, druhá strana by mohla tvrdit, že to básník ale neřekl.

Nicméně úvaha je to zřejmě jen teoretická, protože v praxi se autor nebude s příjemcem díla o smysl své public domain „licence“ soudit a nikdo jiný takový proces nemůže zahájit, protože se jedná o občanskoprávní záležitost, kde nikomu jinému než těmto dvěma stranám do věci nic není.

[Jakub Lucký]

Z hlediska majetkového se pro uživatele/přebiratele nic nemění (mezi public domain dílem a dílem, ke kterému je každému udělena bezúplatná licence na libovolné používání)

Bohužel právo mluví jinak. Pokud prohlásíte, že dílo prohlašujete za public domain, tak se tím (v souladu s public domain) zbavujete všech osobnostních i majetkových práv. Jenže tím vzniká spor s autorským zákonem, který říká, že "výlučná práva osobnostní" jsou nezrušitelná a nepřenositelná... A teoreticky, když něco zveřejníte pod public domain v ČR, tak byste pak mohl někoho žalovat za porušení vašich osobnostních práv...

[pc2005]

Tak licenci WTFPL.

[=^..^= AmigaPower®]

...nenene, já už nic spouštět nebudu, ten Kralykův skriptík mi stačil, neparalizoval mi jen aplikaci, ale celej system...

[pc2005]

geniální dvousmysl. Musím někdy vytvořit podmínky na to, abych mohl to slovo taky použít .

[Jardík]

Není v tom od slova paralýza tvrdé y?

[pc2005]

Tak když to bereš jako grammar nazi, tak je to hlavně paralelizovat. Ale jinak dobrý...

[xsubway]

to by už ale nebylo tak vtipný

[=^..^= AmigaPower®]

Rozhodně ne, jde o lízání parašutistů!

[kotyz]

para-lízace?

[=^..^= AmigaPower®]

Ano, jde o orální styk při volném pádu...

[kotyz]

to musí bejt ultra žůžo

[belisarivs]

Neni na to Rimmerova direktiva?

"Se zubni protezou se neoddavejte oralnimu sexu ve stavu beztize."

[Jakub Lucký]

To nebyla Rimmerova direktiva, ale direktiva Vesmírného sboru #34124...

Ale jinak je to správně

[JS]

Zajimave. Nejak mi ale neni jasne, ktere z kroku delal clovek a ktere program. Jestli to chapu dobre, tak ten rozklad na bloky, analyzu tech promennych a vytvoreni toho grafu delal clovek.

Druha vec, ktera by me zajimala, jak to fungovalo pri tom vykonavani. Pisete o Jave. Znamena to tedy, ze kazdy blok byl v samostatne metode tridy implementujici urcite rozhrani? Nebo jak to bylo technicky poresene?

[František Bártík]

Ano, rozklad na bloky a analýzu proměnných dělal člověk. (Nebylo to těžké.)

Javu jsem použil k demonstrační příkladu jen proto, že mi přijde kód v ní dobře srozumitelný. Ve skutečnosti se jednalo o aplikaci v C/C++, bloky instrukcí byly definovány jako funkce a pracovalo se s ukazeteli na tyto funkce.

V případě Javy bych také volil bloky jako samostané třídy implementující určité rozhraní s jednou funkcí.

[sivlk]

> zvýšit rychlost desktopové aplikace
> v jazyce Java

<flamebait>Tam niekde som prestal čítať</flamebait>

[Ladicek]

Tak tos dočetl až na konec. Hurá!

[bubak]

me se dost osvedcil profiler

[Antares]

Hlavně neudělat tu chybu a nezačínat si s Erlangem nebo Haskellem. O to víc pak, nejenom kvůli snadnosti paralelizace, skřípu zubama když v práci zasednu zpátky k Jave nebo C++

[mimi.vx]

+1

[Trained.Monkey]

He, zkus Akka a Scala. Bezi to v JVM a boss vubec nemusi vedet ze v tom delas

[Bubak]

Dost bych se bal ze rozdeleni do bloku nebude 100% a nekde se zapomene nejaka vazba.

[zulu]

Cha!

[whistleblower]

ja dovedu aplikaci jenom paralyzovat

[kotyz]

takovej je nas tu vic ...

[whistleblower]

[kotyz]

jak jsem paralelne olizoval aplikace ...