du1

Vícejádrové procesory přináší možnost provádět paralelní výpočty i na běžných počítačích. Implementace aplikací využívajících paralelní výpočty je netriviální záležitostí. Cílem předmětu je proto seznámit studenty teoreticky i prakticky se současně používanými softwarovými technologiemi pro zápis paralelních algoritmů, naučit studenty ladit paralelní programy a v neposlední řadě naučit studenty ladit výkon paralelních programů.
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

du1

Příspěvek od Necroman »

Uz mate hotovy prvy ukol na parprog, pthreads?
Jakych jste dosahli vysledku pri pusteni na 8 jadrech, s optimalizaci jen g++ -O3, na datech large.a * large.b.
Mereno pomoci ./time -f %e ./vas_program ../ppp/large.a ../ppp/large.b large.c

Aktualizace:
serial verze:
medium matice: 3,68, large matice: 118,74, huge matice: 1102,36
Matrix Kernel Library, seriova verze(!) 'mkl': 8.4 vterin :shock:
Threading Building Blocks 'tbb': 29.2 vterin

Muj vysledek, pthreads: 30.9 vterin
+- podle nalady kompilatoru a serveru, 28-36 vterin, sice to na osmi jadru neni optimalni, ale lepsi, nez nic.
Naposledy upravil(a) Necroman dne 1. 4. 2008 23:44, celkem upraveno 2 x.
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
qk_

Re: NPRG042 Programování v paralelním prostředí

Příspěvek od qk_ »

Sem na tom podobne, uz ze svyho algortimu vic nevymacknu, chytrik prehazenim promennych sem v podstate to cely udelal pres iterovani v poli. Jediny co by mozna pomohlo je zarovnat kazdej radek matice na velikost procesorovy cache.
_mffcore_

Re: NPRG042 Programování v paralelním prostředí

Příspěvek od _mffcore_ »

Programy se chovaji dosti odlisne (resp. doba jejich behu) v zavislosti na tom, zda jsou nacachovana vstupni data v pameti. Zkuste program spustit nekolikrat brzy po sobe.
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Re: du1

Příspěvek od Necroman »

Po precteni tohoto sikovneho manualu http://people.redhat.com/drepper/cpumemory.pdf se mi podarilo ztlacit cas ze 30 vterin na large maticich na cca 13 vterin :) . Kompilace jen s -O3 parametrem.
Je dobre vyuzivat principu lokality pri cteni z matic, rozdelit si matici na bloky o velikosti L1 cache. Potom neni treba tolikrat nacitat nove hodnoty a s temi starymi v cache se da pracovat rychleji.
Take se vyplati volat 4 operace nasobeni soucasne - g++ je automaticky prevadi na SSE intrukce, aspon mam ten pocit, a da se vypozorovat 5-10% zrychleni.
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Uživatelský avatar
joshis
Matfyz(ák|ačka) level III
Příspěvky: 127
Registrován: 23. 11. 2006 01:47
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: du1

Příspěvek od joshis »

Jeste jsem koukal na jednu vec - mozna je to trivka, ale me to spis prekvapilo.

Moje reseni nebylo ani v nejmensim tak genialni jako "Necromana" (- smekam pred tebou za ten research co jsi kolem toho udelal, fakt parada). Vlastne jsem jen vyslednou matici prevedl na vektor ("slepil jsem radky") a pak jsem kazdemu vlaknu pridelil prvky ktere ma spocitat "modulo". Viz ("cyclic distribution"):

http://www.math.uu.nl/people/bisselin/PSC/psc1_3.pdf (Utrecht University, Parallel algorithms)
http://www.math.uu.nl/people/bisselin/ (pripadne dalsi podklady z Utrechtu)

Vzhledem k tomu, ze jsem nevyuzil zadnou vychytavku a nehrabal jsem se v architekture procesoru jsem se uz pomalu smiroval s tim, ze dosahnu jen 2.5 nasobneho zrychleni (47s na "large").

Pak jsem si ale ("pak"="ve 23:54 hod. soudneho dne") rekl, ze zaexperimentuju s poctem vlaken. Nejdriv jsem puvodni a spise nudny pocet 8 zmenil na 16. Kdyz jsem nevidel vubec zadnou zmenu, zavtipkoval jsem s poctem vlaken 64 - a ejhle! Zrychleni na asi 35s. Tak jsem postupne "binarnim vyhledavanim" dosel k tomu, ze idealni pocet vlaken pro matici "large" je 256. Kdyz jsem takhle "vypalil" 256 vlaken, stlacil jsem cas na v prumeru 25s (oproti puvodnim 47), obcas jsem byl na hrane dvacitky.

Btw: Kolik jste na to spousteli vlaken vy? Meli jste nejaky algoritmus na to kolik vlaken se spousti pro matici danych rozmeru, nebo jste to meli zadratovano napevno (tak to mam v reseni odevzdanem po deadline), jako parametr na prikazove radce (tak to mam ja v resenich odevzdanych pred deadline), ... ???
qk_

Re: du1

Příspěvek od qk_ »

joshis píše:Jeste jsem koukal na jednu vec - mozna je to trivka, ale me to spis prekvapilo.

Moje reseni nebylo ani v nejmensim tak genialni jako "Necromana" (- smekam pred tebou za ten research co jsi kolem toho udelal, fakt parada). Vlastne jsem jen vyslednou matici prevedl na vektor ("slepil jsem radky") a pak jsem kazdemu vlaknu pridelil prvky ktere ma spocitat "modulo". Viz ("cyclic distribution"):

http://www.math.uu.nl/people/bisselin/PSC/psc1_3.pdf (Utrecht University, Parallel algorithms)
http://www.math.uu.nl/people/bisselin/ (pripadne dalsi podklady z Utrechtu)

Vzhledem k tomu, ze jsem nevyuzil zadnou vychytavku a nehrabal jsem se v architekture procesoru jsem se uz pomalu smiroval s tim, ze dosahnu jen 2.5 nasobneho zrychleni (47s na "large").

Pak jsem si ale ("pak"="ve 23:54 hod. soudneho dne") rekl, ze zaexperimentuju s poctem vlaken. Nejdriv jsem puvodni a spise nudny pocet 8 zmenil na 16. Kdyz jsem nevidel vubec zadnou zmenu, zavtipkoval jsem s poctem vlaken 64 - a ejhle! Zrychleni na asi 35s. Tak jsem postupne "binarnim vyhledavanim" dosel k tomu, ze idealni pocet vlaken pro matici "large" je 256. Kdyz jsem takhle "vypalil" 256 vlaken, stlacil jsem cas na v prumeru 25s (oproti puvodnim 47), obcas jsem byl na hrane dvacitky.

Btw: Kolik jste na to spousteli vlaken vy? Meli jste nejaky algoritmus na to kolik vlaken se spousti pro matici danych rozmeru, nebo jste to meli zadratovano napevno (tak to mam v reseni odevzdanem po deadline), jako parametr na prikazove radce (tak to mam ja v resenich odevzdanych pred deadline), ... ???
No ja to zkousel a memu reseni vice vlaken spise uskodilo. Mozna to je algoritmem. Osm bylo nejlepsich
_mffcore_

Re: du1

Příspěvek od _mffcore_ »

Zkousel jsem ruzny pocet vlaken, ale 8 mi vychazelo nejlepe ze vsech moznosti, ktere jsem zkousel. Vyrazne vetsi pocet vlaken mi vypocet nekolikanasobne zpomalil (treba onech 256 asi 3x). Popravde bych cekal jako optimalni hodnotu bud 8 nebo 16 (hyperthreading). Pocet vlaken mam pevne zadratovano na 8. Ale je pravda, ze pro velmi male matice se nevyplati vypoustet tolik vlaken. Snad na tom nebude nikdo pocitat velmi matice s tim, ze by mu zalezelo na rychlosti. Large mi to dela pod 5 sekund, Medium za 0.2 sekundy. Vse za predpokladu, ze vstupni data jsou nacachovana v pameti (napr. vypocet spustim 2x po sobe a pocitam cas druheho vypoctu).

Delali jste paralelizaci cteni dat ze souboru ci ukladani? Myslim, ze jedine, co by mohlo mit smysl, je zacit vypocet jeste v dobe, kdy nejsou nactena vsechna data ... a naopak zacit ukladat v dobe, kdy jeste vsechno neni spocteno. Ja to mam seriove ... napred prectu, pak spocitam, pak ulozim.
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Re: du1

Příspěvek od Necroman »

_mffcore_ píše:...Large mi to dela pod 5 sekund, Medium za 0.2 sekundy. Vse za predpokladu, ze vstupni data jsou nacachovana v pameti (napr. vypocet spustim 2x po sobe a pocitam cas druheho vypoctu).
Delali jste paralelizaci cteni dat ze souboru ci ukladani? Myslim, ze jedine, co by mohlo mit smysl, je zacit vypocet jeste v dobe, kdy nejsou nactena vsechna data ... a naopak zacit ukladat v dobe, kdy jeste vsechno neni spocteno. Ja to mam seriove ... napred prectu, pak spocitam, pak ulozim.
Pod 5 vterin, tak to uz je dobra magie. Nepodelis se o nejake konkretni triky, jak na to? ;)

Zkousel jsem poustet vlakna uz po nacteni prvni osminy dat, ale vysledek byl asi o polovinu pomalejsi. Bud jsem na to sel spatne, nebo neefektivne. Kazdpadne jsem i o tomto uvazoval.
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Uživatelský avatar
joshis
Matfyz(ák|ačka) level III
Příspěvky: 127
Registrován: 23. 11. 2006 01:47
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: du1

Příspěvek od joshis »

Re: Vsichni

Diky za odpoved ohledne poctu vlaken, asi to bylo specifikum meho reseni (vazne me to docela dost prekvapilo, ze se na 8 proc. jako idealni ukazal pocet vlaken pres 200). Koukam, ze vuci tem ostatnim je moje reseni asi tezce neoptimalni (5 vterin na Large... to je hustej mazec... to je asi 20-25x zrychleny!? :o ).

EDIT: Podel se s nami o tu magii;)!

Jeste jeden dotaz - "podvadeli" jste s prioritama a planovanim? Konkretne se ptam na to, kolik z Vas "tunilo" svoje reseni podobne jako ja pres "pthread_setschedparam".

http://linux.die.net/man/3/pthread_setschedparam

Trochu se stydim za to, ze zatimco ostatni sve reseni optimalizuji pomoci chytrych triku a pochopeni toho, co se deje v procesoru, ja to delal "na silu" (aneb vy**dat parlab co to jde)... Jako omluvu uvadim, ze za sebou nemam OSy a prekladace, takze "kernelik" se ze me teprve stane... ;)
qk_

Re: du1

Příspěvek od qk_ »

ted sem narazil na zajimavej trik s klicovym slovem restrict, pokud mu g++ veri (nebo aspon icpc) tak by se s nim to dalo hooodne optimalizovat (kdo chodi na konstrukci prekladacu vi o ce mluvim).
_mffcore_

Re: du1

Příspěvek od _mffcore_ »

Tak se nelze pripojit na parlab a pise to, ze probiha vyhodnocoveni DU1. Tak jsem zvedav, co nameri... Dneska by to mohlo byt vyvesene.
_mffcore_

Re: du1

Příspěvek od _mffcore_ »

Uz jsou na webu zverejne vysledky.
Uživatelský avatar
Necroman
Supermatfyz(ák|ačka)
Příspěvky: 459
Registrován: 20. 1. 2005 19:46
Typ studia: Informatika Mgr.
Bydliště: Louny / kolej Jednota, Praha
Kontaktovat uživatele:

Re: du1

Příspěvek od Necroman »

http://ulita.ms.mff.cuni.cz/pub/predn/p ... 7/du1.html

Tak se koukam, zatim mam nejlepsi reseni, ktere proslo na vsech trech testech 8)
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
_mffcore_

Re: du1

Příspěvek od _mffcore_ »

Je to tak. Muj program na velkych datech zdechne na tom, ze se nepodari naalokovat souvislou pamet hned pro prvni vstupni matici.

Budiz mi polehcujici okolnosti, ze jsem na alokaci pouzil intelacky _mm_malloc, ktery zajistuje zarovnani tak, aby data byla zarovnana na cacheline na nasobek dane velikosti, a ten uz odmita naalokovat tak velkou oblast pameti (tezko rict proc - normalni malloc ji naalokuje - v dokumentaci o tom nic nepisi) a horni limit velikosti matic pritom nebyl zcela exaktne zadan.
Odpovědět

Zpět na „NPRG042 Programování v paralelním prostředí“