mar
Založen: 16. 06. 2012
Příspěvky: 608
|
 Zaslal: 26. březen 2015, 00:10:33 Předmět: parallel for |
 |
|
Právě jsem dodělal svoji implementaci "parallel for", tak kdyby někoho zajímaly detaily:
co je potřeba:
n-1 helper threadů, kde n je počet cores, které chci využít.
atomické operace (add/increment, load, store)
eventy (=pthread_mutex + pthread_cond nebo implementace přímo v jazyce).
run se volá s delegate na to, co se má paralelizovat (tady je spousta možností, kdo používá C++11 může použít třeba std::function a tím pádem i lambdy).
další parametry jsou velikost (=počet) a krok.
na začátku nastavím activeThreads (atomic int) na n
každý helper sedí na eventu (třeba startWork)
zjednodušený pseudo-kód helper threadu:
| kód: |
while (!killThread)
{
wait(startWork);
while ( (index += step) < count ) {
delegate( index, threadId );
}
if ( !--activeThreads ) {
signal(done);
}
}
|
Na začátku se index nastaví na -step.
thread, ze kterého se volá parallel for nejdřív nastaví startWork event pro všechny helpery a pak provádí totéž, co tělo helper threadu (dá se to přesunout do společné funkce). Na konci čeká na done event.
pozn.: index a activeThreads jsou atomické integery (nemám to implementované přes operátory, ale volám funkce)
Thready tedy si aktivně rozebírají práci.
threadId je důležitý pro případ, kdyby bylo potřeba si ukládat nezávisle průbežný stav a na závěr zmergovat výsledky.
Step je krok (default 1), jak se naseká rozsah. Tím se dají paralelizovat dlouhé loopy (s konstantní složitostí) s vnitřkem, co toho moc nedělá (zkoušel jsem porovnávat s openmp (msc implementace), ten to dynamicky forkuje a rozloží loop na n částí a každá pak provádí část smyčky. docela mě proto překvapilo, že to bylo nakonec pomalejší, možná menší batch size líp využije výpočetní sílu v případě, že nějaký helper doběhne dřív?).
Příklad:
| kód: |
void ParallelCallback( Int idx, Int /*thrIdx*/ )
{
Int idxMax = Min( count, idx + BATCH_SIZE );
for (; idx < idxMax; idx++ ) {
// small body...
}
}
...
ParallelFor::Run(delegate(ParallelCallback), count, BATCH_SIZE);
|
Optimální krok (batch size) je samozřejmě potřeba nastavit ručně (na to je dobrý profiler).
Pro tasky, které trvají relativně dlouho (a každý může trvat různě dlouho) je nejlepší default step 1 a mít je seřazené od nejnáročnějšího dolů (důvod je zřejmý) - v takovém případě samozřejmě callback provede jen jednu iteraci a odpadne smyčka.
Použít n-1 helper threadů sice znamená blokování volajícího threadu, dokud se smyčka nedokončí, ale výhoda je ta, že pokud je k dispozici jenom 1 core, měl by být overhead minimální.
Počet threadů ideálně nastavit ručně, nebo si vyčíst počet CPU (cores) ze systému, bohužel většina vrací počet logických, což je u i7 quadu se zaplým hyperthreadingem 8, ale radši bych v takovém případě 4 (na win se to dá zjistit pomocí GetLogicalProcessorInformation, ale to je od Vist+. na jiných systémech nic použitelného nenašel).
Kdy to nepoužít:
- pro malé smyčky, kde doba probuzení helper threadů a následná synchronizace po dokončení by trvala déle, než provedení smyčky přímo na 1 core
- je potřeba být opatrný v případech, kde je potřeba synchronizaci k prevenci race conditions (tam lze do určité míry využít ten thread id)
- v audio callbacku, na systémech, kde je modifikovaný scheduler, aby měl audio thread prioritu před ostatními a nedocházelo k preempci
(OT: viz velmi zajímavé https://www.youtube.com/watch?v=d3kfEeMZ65c) |
|
Hlavní strana
FAQ
Test
Hledat
Seznam uživatelů
Uživatelské skupiny
Registrace
Ke Stažení
Nastavení
Přihlášení
Calendar
