du1

[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
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.

[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_]

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.

[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.

[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_]

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_]

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.

[Necroman]

...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.

[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!? ).

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_]

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_]

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_]

Uz jsou na webu zverejne vysledky.

[Necroman]

http://ulita.ms.mff.cuni.cz/pub/predn/ppp/ppp07/du1.html

Tak se koukam, zatim mam nejlepsi reseni, ktere proslo na vsech trech testech

[_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.