OMP nežádoucí čekání vláken na dokončení

Ondra..

OMP nežádoucí čekání vláken na dokončení
« kdy: 29. 06. 2018, 20:42:48 »
Ahoju

Mám ve fortranu OMP cyklus
Kód: [Vybrat]
!$OMP DO   
do i=1,n
      call function1(...)
      ...
end do
Jde o numerickou integraci, tedy nic programově složitého, ale každá z iterací je numericky náročná, navíc každá jinak. Například, n=1000, rozsahy i=1...500 jsou jednodušší než i=501...1000.
Co jsem ale vypozoroval, program si již na začátku rozdělí kroky mezi jednotlivá vlákna, například pro dvě vlákna budou nultému přisouzeny úseky i=1...500, prvnímu i=501...1000. Zde vyvstává problém, neboť po skončení nultého vlákna se čeká na první; tomuto prvnímu se nepřiřadí automaticky nedokončené věci z druhého úseku. Během tohoto dokončování běží program reálně jednovláknově.

Nedokázal byste mi někdo poradit, zda lze kroky v cyklu přiřazovat operativně a po skončení jednoho úseku se volné vlákno automaticky věnovalo iteracím původně vyčleněným pro vlákno jiné?


Neviditelný

Re:OMP nežádoucí čekání vláken na dokončení
« Odpověď #1 kdy: 29. 06. 2018, 22:23:12 »
V C třeba takto:

Kód: [Vybrat]
#pragma omp parallel for schedule(dynamic, 64)
for (i = 0; i < N; i++) { ... }

Celý cyklus se rozdělí na bloky, zde o velikosti 64, a každé OMP vlákno dostane ke zpracování jeden blok. Když skončí, dostane další. Velikost bloku a způsob schedulingu je nutné vychytat, dynamický scheduling je sice teoreticky nejlepší v rovnoměrném rozdělení zátěže ale zase má největší režii za běhu. Více třeba zde:

https://software.intel.com/en-us/articles/openmp-loop-scheduling
http://pages.tacc.utexas.edu/~eijkhout/pcse/html/omp-loop.html

xxxxx

Re:OMP nežádoucí čekání vláken na dokončení
« Odpověď #2 kdy: 29. 06. 2018, 22:56:03 »
Tuším, že ve fortranu je to obdobné
!$OMP DO SCHEDULE(DYNAMIC,64)

případně GUIDED místo DYNAMIC

Ondra..

Re:OMP nežádoucí čekání vláken na dokončení
« Odpověď #3 kdy: 30. 06. 2018, 05:49:20 »
Zkusím, děkuji!

uuuuu

Re:OMP nežádoucí čekání vláken na dokončení
« Odpověď #4 kdy: 30. 06. 2018, 08:57:14 »
Ahoju

Mám ve fortranu OMP cyklus
Kód: [Vybrat]
!$OMP DO   
do i=1,n
      call function1(...)
      ...
end do
Jde o numerickou integraci, tedy nic programově složitého, ale každá z iterací je numericky náročná, navíc každá jinak. Například, n=1000, rozsahy i=1...500 jsou jednodušší než i=501...1000.


muzes mi vysvetlit jak je to mozne?
volas stale stejnou funkci, v ni se pouzivaji stale stejne vzorecky, tak jak to muze byt ruzne narocne pro 0...500
a pro 501...1000 ?

chapu, ze pocitac to muze pocitat ruzne rychle, ale matematicky to je furt stejne, ne?!


karel

Re:OMP nežádoucí čekání vláken na dokončení
« Odpověď #5 kdy: 30. 06. 2018, 14:05:10 »
Domnívám se, že pomocí  parametru i se určuje podinterval pro numerickou integraci. Výpočet v jednotlivých podintervalech může vyžadovat různý počet iterací, protože funkce v různých intervalech může být různě "divoká" (např. může neomezeně růst v nějakém bodě atp.).

Ondra..

Re:OMP nežádoucí čekání vláken na dokončení
« Odpověď #6 kdy: 01. 07. 2018, 07:39:18 »
Domnívám se, že pomocí  parametru i se určuje podinterval pro numerickou integraci. Výpočet v jednotlivých podintervalech může vyžadovat různý počet iterací, protože funkce v různých intervalech může být různě "divoká" (např. může neomezeně růst v nějakém bodě atp.).
Ano, přesně něco takového. Navíc jsem to napsal zjednodušeně, detaily nejsou myslím důležité a evidentně to stačilo :-).

Je to kombinace variace (hledání minima selfkonzistentně) a té numerické integrace. Dopředu není jasné, jak dlouho první část bude trvat, extrémně závisí na mnoha parametrech. Následně, podle složitosti nalezené funkce trvá integrace různou dobu. Pracuje se s různými maticemi apod. Zjednodušené je i rozdělení na dva intervaly (do 500 a 1000), typicky je nejnáročnější "střed", ale program také obvykle běhá s podstatně více než dvěma vlákny ... Principiálně by to šlo rozdělit do menších kroků, ale numericky bych si nepomohl, jen by extrémně rostla paměťová náročnost.

Každopádně děkuji všem za rady, výsledek vypadá úspěšně!

Ondra..

Re:OMP nežádoucí čekání vláken na dokončení
« Odpověď #7 kdy: 01. 07. 2018, 07:45:31 »
chapu, ze pocitac to muze pocitat ruzne rychle, ale matematicky to je furt stejne, ne?!

Ještě doplnění, ani matematicky to není zcela identické. Rozdělení na matematicky stejné úseky by nejspíš šlo udělat, ale vyžadovalo by to další testování někde nepředem, tj. zbytečné předpočítání několika věcí, navíc je to takto přehlednější.
Představ si to třeba jako Fourierovu transformaci, kde podle divokosti funkce používáš různý počet koeficientů nebo různé báze.