OpenMP na multicore spomaľuje

[aladarus]

Snažím sa zrýchliť výpočet IDS algoritmu na viacjadrovom procesore pomocou OpenMP. Ide o jednoduchý cyklus. Avšak čas výpočtu s použitím OpenMP na paralelizáciu výpočtu sa  približne zdvojnásobí oproti výpočtu bez použitia OpenMP na tom istom procesore.
Kde je chyba?
Prikladám zdrojový kód:
RASTER* IDS(RASTER* raster, DATA* data)
{
   int i,j;
   float final_time;
   float sum_up; //citatel vo vzorci
   float sum_down; //menovatel vo vzorci
   float distance;
   clock_t start = clock();
   #pragma omp parallel for default(none) shared(raster,data) private(j, sum_up, sum_down, distance,th_id)
   for(i = 0; i < raster->points_count; i++)
   {
      sum_up = 0;
      sum_down = 0;
      for(j =0; j < data->_data; j++)
      {
         distance = SQR(raster->x - data->x[j]) + SQR(raster->y - data->y[j]);
         sum_up += (data->value[j]/distance);
         sum_down += (1.00/distance);
      }
      
      raster->value = sum_up/sum_down;   
   }
   
   final_time = ((double)clock() - start) / CLOCKS_PER_SEC;   
   printf("Time elapsed: %f\n", final_time);
   return raster;
}

[Reklama]

[logikk]

Přímo s openMP jsem nedělal, ale nevidím tam nikde rozdělení práce. IMHO výsledkem je, že počítáš sice na X jádrech, ale na každym všechno, takže to pak jede samozřejmě pomalejc než když to počítáš na jednom. Ale možná se pletu, nezkoumal jsem to detailně....

[koso]

Ja by som tipoval, ze je to sposobene rezijnymi vypoctovymi nakladmi distribucie vypoctu a hlavne ochranu zdielanych casti pameti, ku ktorym sa vo vypocte pristupuje velmi casto.

PS: na co je v tom algoritme cyklus "for(i = 0; i < raster->points_count; i++)"? Z laickeho pohladu mi to nedava zmysel.

PPS: ten vypocet realne trva 2 krat dlhsie, alebo to tak len zobrazi program po skonecni?

[D.E.X.]

Davej si bacha jak casto tu funkci IDS volas, bo vytvoreni tymu vlaken a paralelizace neco stoji - cca. mikrosekundy.

Z tohoto duvodu je treba dbat na to, aby byla v paralelizovane casti dost velka porce prace. Ta funkce je velice jednoducha a pokud nejsou indexy i a j dostatecne velke (cca. > 1000), pak se pouziti OpenMP nevyplati.

Pro tento pripad bych doporucil schedule static.

[D.E.X.]

Přímo s openMP jsem nedělal, ale nevidím tam nikde rozdělení práce. IMHO výsledkem je, že počítáš sice na X jádrech, ale na každym všechno, takže to pak jede samozřejmě pomalejc než když to počítáš na jednom. Ale možná se pletu, nezkoumal jsem to detailně....

To rozdeleni prace tam je - direktiva #pragma omp parallel for ... - zpusobi paralelizaci for cyklu nasledujicho tuto direktivu.

[Reklama]

[qwerti]

Davej si bacha jak casto tu funkci IDS volas, bo vytvoreni tymu vlaken a paralelizace neco stoji - cca. mikrosekundy.

Z tohoto duvodu je treba dbat na to, aby byla v paralelizovane casti dost velka porce prace. Ta funkce je velice jednoducha a pokud nejsou indexy i a j dostatecne velke (cca. > 1000), pak se pouziti OpenMP nevyplati.

Pro tento pripad bych doporucil schedule static.

Hodnota raster->points_count a teda aj index i sa pohybuje medzi 1 000 000 az 100 000 000. Index j je radovo mensi - asi 15 - 20.

Implementacia tohto algoritmu pre CUDA (gefroce 9800gt 512MB) bola cca 7-krat rychlejsia ako 1 CPU (jedno vlakno). Tam je este navyse rezia s prenosom dat do GK a naspat do RAM.

S openMP skusenosti nemam, ale podla prikladov (openmp.org) to vyzeralo tak jednoducho :-) ...

[aladarus]

Funkcia IDS sa volá len raz. Premenná i v nej nadobúda hodnoty podľa rozmeru počítaného rastra a to je minimálne 2000 x 2000 bodov. Pri výpočte sa pohybujeme rádovo okolo 6000 x 6000 bodov a viac.

Ad. koso P.P.S.: 2x toľko sa to zobrazí po skončení programu. Reálne neviem posúdiť. 

[potejo]

Zdravim,
algoritmus IDS taky neznam, takze me neni jasny vyznam ono prvniho cyklu, jak uz se tu psalo, protoze promenna i neni nikdy pouzita (nema tam byt treba data->xi nebo yi?) ale muze to byt jen preklep pri prepisovani.
Co se tyce OpenMP zkusil bych:
1) pohrajte si s klauzuli schedule - vyzkouset static, dynamic a rozhodne specifikovat velikost chunk_size treba zkusit 1000 pokud mate matici 6k x 6k, ve vychozim je chunk_size tusim 1 a pro tak velke matice by to byla obrovska degradace vykonu
2) konstanty a ukazatele dejte jako firstprivate, cili rozebrat strukturu RASTER a DATA na cleny a ulozit zvlast. Docilite toho, ze nebude dochazet k vybijeni cache pameti mezi jadry. Kazde jadro bude mit ve sve cache kopii ukazatele napr na data, ale pristup na data(i) uz bude sdileny, protoze ukazuji na stejne misto v pameti. Cili konstanty raster->points_count, data->_data urcite mohou byt firstprivate misto shared a i ukazatele raster->x, y taky
3) tusim ze aspon u gcc je doporuceno zapnout vysoky stupen optimalizaci -O3, zkouste obdobu pro vas kompilator
4) pro mereni casu pouzit omp_get_wtime()

[aladarus]

Vdaka, vdaka, vdaka!

Pomohlo to.
1. a hlavny problem bol (medzi klavesnicou a stolickou) v merani casu. Robil som to zle!!! Mojim sposobom sa spocitavali casy na jednotlivych vlaknach a vysledkom bola suma casov (zrejme). Po uprave kodu je zobrazovany cas vypoctu optimisticky. Vypocet na dual-core dosahuje dvojnasobne zrychlenie a na i7 viac ako 7 nasobne zrychlenie.
2. Pouzivam gcc kompilator a zapnutie optimalizacia -O3 znacne zrychlilo vypocty.
3. Nastavenie chunk_size tiez zrychlilo vypocet. Staci nastavit na 500 (experimentalne overene).
4. Nastavenie direktivy schedule nemalo velky vplyv.
5. Jedine co som nedokazal, bolo rozobrat strukturu RASTER (DATA) vo firstprivate/shared. Pri zadani raster->x (a pod.) kompilator vyhadzuje chybu. Asi aj tu robim chybu.

[potejo]

Zdravim, s tim rozebranim jsem to myslel tak, ze si vytvorite pomocne promenne a ty potom nadeklarujete jako firstprivate, napr:

Kód: [Vybrat]

int points_count = raster->points_count;
int* xx = raster->x;
...
#pragma ... firstprivate(points_count, xx)Pripadne zkusit celou strukturu nastavit jako firstprivate, ale nemam zdani jak vypada, takze zalezi na vas. Ono se to mozna ani nejak vyznamne neprojevi pri takove velikosti matic, takze klidne se na to mozete vykvaknut, ale za vyzkouseni by to mohlo stat, lesti mate cas.