Level

Prvni krucky

Obsah

Jenom takove bleskove obrazky k praci:

Prvni obrazky na ctvercove mrizce procesu. Levy sloupec je prime vykresleni vzdalenosti - cim svetlejsi, tim vzdalenejsi. Pravy sloupec je vyznaceni bodu se stejnou vzdalenosti od krivky (Opet cim svetlejsi, tim vzdalenejsi - prostredni tmavy pruh je primo zadana krivka).

1. Asteroida na mrizce s krokem 0.05

2. Kruznice s krokem 0.001 (obrazek je zmensen)

3. Asteroida s krokem 0.001 (opet zmenseno)

4. A aby bylo videt, ze obrazek je pocitany na vic procesech a je pozdeji skladany, zaclenili jsme umyslnou chybu do vystupu.

Dalsim krokem bylo zacleneni znamenka do vzdalenosti. Prozatim je napocitavano z explicitne zadane fce. Prezentovane vystupy se tudiz meni o dalsi informaci - cervena oznacuje kladne, zelena ( neni moc videt :-) ) zaporne hodnoty. Jeden priklad za vsechny pro porovnani.

5. Asteroida s barevnym rozlisenim znamenka

Poslednim provedenym krokem je Narrow Band - nejdriv je krivka na zaklade parametrizace rozdelena dle parametru jednotlivym procesum. Pote je vytvoren na kazdem uzlu blok pokryvajici tuto cast. A nasleduje prime pokryti krivky pomoci "ctvercu." Znovu je znazorneno, zda bod lezi uvnitr ci vne krivky (zelena / cervena, intenzitou je tentokrat vyznacena prislusnost k procesum - v tomto pripade dvou).

6. Naznaceni pokryti krivky procesy	7. Vnitrni pokryti krivky pomoci malych "ctvercu"

Dalsi krokem je napocitani skutecnych vzdalenosti jako v pripade ctvercove mrizky procesu. Za timto ucelem je uzitecne napsat a odladit opakovatelne pouzitelne metody na zpracovani bloku. Program je navrzen na minimalni redundanci kodu pro jednotlive pripady zpracovani 2D/3D(vyhledove)/ctvercova mrizka/narrow band blokove/narrow band bodove a vysledkem je skutecne vypocetni zpracovani stejnou metodou, lisi se nepatrne pouze jeji volani. Nanestesti jsem zakufroval na mnoha indexech pri ladeni... :-) Vysledek: Jsou jiz napsany obecne metody na bodove a cache-blokove (zpracovava se po malych blocich s nadeji, ze se vlezou do L1 cache procesoru) zpracovani narrow bandu.

A vysledky pri aplikaci: Levy obrazek zobrazuje, kolikrat je bod pokryt (cim vyraznejsi, tim vicekrat). Abychom mohli v budoucnu snadno pocitat derivace, cache-bloky se prekryvaji (tenke cary v kazdem pokryvajicim bloku). V nasem pripadeje kazdy pokryvajici blok tvoren 3 x 3 cache-bloky. Vyrazne prekryti temer stejnych bloku vpravo uprostred je zpusobeno obecnosti pokryvajiho algoritmu, ktery vzdy prvni a posledni bod povinne pokryje blokem (zde tyto body temer splyvaji) - voleno z duvodu vice procesu, protoze pak vime presne, kde se dva procesy dotykaji. Snad mi to v budoucnu pomuze. :-) Kdyztak neni problem oddelat. Pravy obrazek jsou napocitane vzdalenosti jako v minulych pripadech.

8. Prekryvani pokryti pri narrow band	9. Napocitane vzdalenosti na narrow band

10. Prekryvani pokryti pri narrow band	11. Napocitane vzdalenosti na narrow band

S Petrem (Vokacem) jsme zapracovali na tom MPI clusteru, dohodli jsme reseni a kupodivu stroje jsou pripraveny uz ted k vypoctu, staci jen aby je "nekdo" nevypnul. :-) Rozhodli jsem se nekonfigurovat zadny ze stroju jako master, protoze si je pry lide casto pujcuji do kanclu, nejedou z HW pricin atp. Proto je reseni na jine bazi: malym skriptem se nadetekuji bezici masiny a z nich se vytvori cluster. Tuto jednoduchou cast jsem jiz napsal a funkcnost byla slavnostne vyzkousena za PLNEHO PROVOZU na pocitacich KM134, KM131, KM024 a KM034 (nebo tak nejak). Na jinych strojich bohuzel nebezel v dobe pokusu linux. Vykonove testy ukazuje nasledujici tabulka.

1 stroj 1.33GHz, krok 0.001, 2 procesy	2 stroje 800MHz, krok 0.001, 2 procesy	2x800MHz+2x750MHz, krok 0.001, 4 procesy
Narrow: 448 s, Full: 1024 s	256 s	128 s

Temer linearni zrychleni je znakem dobre napsaneho algoritmu (co si nepochvali clovek sam, to nema :-) ). A protoze sebechvala smrdi, tak je take nutno rict, ze algoritmus vypoctu vzdalenosti zatim neni prilis efektivni a na zlepseni se tvrde pracuje (napad uz je). Dalsim duvodem pomalosti je zapnuty ElecetricFence a spousta assert podminek na pretekani natvrdo nastavenych poli.

A aby to nebylo tak suche, tak taky nejaky obrazek (ze kterych lze primo citit, ze nebyly nakreslene Pejntbrasem a jsou pocitane na 4 masinach)... Uz je videt mnohem lepe jemnost pokryti.

11. Prekryvani pokryti pri narrow band	12. Napocitane vzdalenosti na narrow band

Dalsi krokem bylo vyse zminene vylepseni napocitavani vzdalenosti - presneji zmena paralelizace. Na porovnani je potreba aspon zhruba 10 procesoru, takze prozatim silne neobjektivni na 4 procesorech. Porovnavane metody:

Kazdy proces posle informace o svoji krivce VSEM ostatnim. K posilani se pouziva Bcast, takze MPI muze pozitivnim zpusobem ovlivnit zasilani dat (napr. multicasting). Nevyhodou je samozrejme zbytecne pocitani. Vylepseni tim, ze si nebudou pocitat procesy, ktere s sebou nesousedi je neefektivni - prestoze nebude pocitat, stejne budou cekat, az dopocitaji ostatni (kdyz by necekal, tak uz je snad nikdy nedam dohromady - slozite na synchronizaci).
Kazdy proces posle informace jen svym sousedum, z nich se vytvori komunikujici skupina. Timto zpusobem se vytvori maximalni pocet nezavislych skupin a vsechny se zaroven spocitaji. Jednoduse znejici, lec na implementaci velice slozita myslenka, coz tady ale nebudu popisovat, kde vsude jsou boty. Vysledek: je uspesne implementovano. Nevyhoda: Kdyz se procesy prilis prekryvaji, tak centralni bod pocita mnohem dele nez ostatni - neefektivni. V nejhorsim pripade zkonverguje do zpusobu 1 s tim rozdilem, ze se nepouziva jedina vyhoda, a to Bcasting.
Napadla me az pri zrudne implementaci dvojky, ale je nejprirozenejsi - v kazdem kroku najdi dva procesy, ktere spolu sousedi, oznac je jako aktivni. Hledej dvojice, dokud to jde. Spocitej svojice. A cele opakuj, dokud jeste neco neni spocitane. Vyhody: Maximalni vytizeni procesoru (tusim :-) ). Nevyhoda: Jako u 2, tzn. pouziti Sendrecv metody, ktera je pomerne pomala.

Shrnuti: Metoda 3 se jevi jako obecne nejlepsi. Dokud nebude Bcast nadlidsky rychlejsi nez Sendrecv, neni duvod pouzivat jinou metodu (jinak zauvazovat o Metode 1). Metoda 2 bude mozna dobra pri malem poctu prekryvajicich se procesu, ale je to jen domnenka. Spis se snazim oduvodnit tolik prace... :-))

V prekladu o znamena, ze metoda s ladicim casem 3 dny (m. 2) prohrala s metodou napsanou za 3 hodiny (m. 3). V jednoduchosti je krasa a 3 dny prace zbytecnych. Indzoj. :-)

Prave mi nekdo vypnul cluster, takze jsem stihnul zatim jen tak zhruba vyzkouset druhe dve metody. Vsechny pokusy na 4x800MHz v ucebne 115. Vysledky zatizeny aktivitou uzivatelu prave pouzivajicich pocitace.

Metoda	4 procesy (1 procesor ~ 1 proces)	8 procesu (1 ~ 2)	12 procesu (1 ~ 3)
Metoda 2	128s	128s	256s
Metoda 3	128s	64s	128s

Vysledky zhruba stejne jako pri pouziti Metody 1. Zatim jsem neladil ten ocividny bug nasobku 64... Jdu to spravit. Tak chyba byla v tom, ze ja mel float MPI_Wtime() a ono to vraci double. :-) Lze videt docela prekvapivy vysledek, ze kdyz pustime 2 procesy na kazdem procesoru, tak se nam vypocet u Metody 3 zrychli - zpusobeno prave lepsi vytizenosti. Na 12 procesech uz prevazi administrativni slozky...

Vlastnost, ktera bude nejvice ovlivnovat vykon algoritmu, je zajiste zpusob pokryti krivky. Hlavne se jedna a prekryvani bloku. Za timto ucelem jsme metodu pokryvani doplnili o jeden parametr a tim je prave 'minimalni procento prekryvani'. Neni to nic high-tech, ale rychle se to pocita. Do budoucna by to chtela sahnout po sofistikovanejsi metode, treba i nejaky optimalizacni problem. Nasledujici obrazky ukazuji narrow band pri ruznem nastaveni minimalniho pokryti. Je videt, ze za vhodneho nastaveni je tento parametr postacujici (pro nase jednoduche testovaci priklady). Vyrazny ctverec je opet zpusoben prekrytim prvniho a posledniho bloku.

13. (Temer) Zadny prekryv - 1%	14. Prekryv 33%

Tak v teto pozici opoustim inicializacni cast vypoctu a prechazime na vlastni vyvoj v case...