Come parallelizzare la piccola funzione pura?

Question

Ho il programma D2 che, nella sua forma attuale, è a thread singolo e chiama la stessa funzione pura da 10 a 100 volte in un loop interno per ogni iterazione del ciclo esterno di questo programma. Non esiste alcuna dipendenza dai dati tra le chiamate, ovvero nessuna chiamata utilizza il risultato di un'altra chiamata. Nel complesso, questa funzione è chiamata milioni di volte ed è il principale collo di bottiglia nel mio programma. I parametri sono unici quasi ogni volta, quindi il caching non aiuta.

A prima vista, questo sembra il candidato perfetto per la parallelizzazione. L'unico problema è che la funzione impiega solo circa 3 microsecondi per chiamata, ben al di sotto della latenza di creazione di un nuovo thread, e non molto oltre il sovraccarico di aggiunta di un lavoro a un pool di attività (ovvero, acquisizione di un mutex, allocazione della memoria a conservare le informazioni sull'attività, trattando possibili conflitti per la coda del gruppo di attività, ecc.). C'è un buon modo per sfruttare il parallelismo che è questo a grana fine?

Answer 1

Che dire creare più thread con la propria coda da cui lavorare? Poiché non vi è alcuna sovrapposizione delle code, non è necessario creare blocchi.

Answer 2

A seconda della struttura del programma, è sempre possibile combinare un gruppo di chiamate in un'unica operazione. Se ogni attività esegue 50 chiamate di funzione, il sovraccarico per la gestione delle attività non è più un fattore così importante.

Answer 3

Non avviare ciascun thread per eseguire una singola attività, quindi chiuderla verso il basso.

All'inizio del programma, creare un thread per ciascun core stando lì seduto in attesa di dati da una coda (pipe o qualche meccanismo di propria creazione). Se riesci a trovare un meccanismo in cui tutti i thread attendono sulla stessa coda, meglio ancora, ma il metodo get della coda dovrà essere sincronizzato ...

Ogni volta che hai un blocco di poche centinaia o migliaia dei tuoi processi da calcolare, rilascia l'intero blocco nella prossima coda vuota.

In realtà finirai con uno o più thread che alimentano le code, un gruppo di thread che elaborano i dati dalle code e uno o più che leggono e gestiscono i risultati.

Potrebbe essere necessario inserire un numero sufficiente di dati negli "articoli" in elaborazione per essere in grado di dire cosa fare con essi dopo aver terminato. Dovrebbero quasi certamente essere un oggetto e potresti volere che contengano informazioni di stato.

Probabilmente non si desidera che più thread eseguano l'elaborazione rispetto ai core.

Modifica: guarda anche alcune delle librerie concorrenti, come ThreadPoolExecutor. È facile dimenticare la libreria concomitante (come ho appena fatto), probabilmente è esattamente quello che stavi cercando (da qui l'enfasi)

Answer 4

Questo suona come qualcosa in cui le istruzioni SIMD possono aiutare. Se hai un compilatore auto-vettoriale, dovresti essere in grado di riscrivere la funzione per operare simultaneamente su 4 valori, e il compilatore può condensarla nelle appropriate istruzioni SSE. Questo potrebbe aiutare a ridurre il sovraccarico della chiamata di funzione. Se il tuo compilatore non è adatto al codice auto-vettoriale, allora potresti essere in grado di utilizzare gli intrinseci SSE per arrivare quasi al livello di assembly per programmare il corpo della funzione.

Answer 5

Come suggerito sopra, non dare il via a un thread ogni volta che si accede a questa funzione e inoltre si ha una granularità di "lavoro" maggiore di un'operazione della funzione interna in modo che l'overhead di creazione del lavoro sia ben ammortizzato.Descrivendo la vostra routine originale come qualcosa di simile:

void OuterFunction(Thingy inputData[N]) 
{ 
    for (int i = 0 ; i < N ; ++i) 
    InnerFunction(inputData[i]); 
} 

Vorremmo risolvere il vostro problema da (ipotizzando un sistema di coda di lavoro è presente):

void JobFunc(Thingy inputData[], int start, int stop) 
{ 
    for (int i = start ; i < stop ; ++i) 
    InnerFunction(inputData[i]); 
} 
void OuterFunction(Thingy inputData[N], int numCores) 
{ 
    int perCore = N/numCores; // assuming N%numCores=0 
           // (omitting edge case for clarity) 
    for (int c = 0 ; c < numCores ; ++c) 
    QueueJob(JobFunc, inputData, c * perCore, (c + 1) * perCore); 
} 

Fino a quando i dati in ingresso è completamente indipendente, come tu dici nella tua domanda originale, non è necessario bloccarlo; la sincronizzazione è necessaria solo quando c'è una dipendenza tra i thread e qui non ce n'è.

Inoltre, a questo livello di prestazioni le microottimazioni iniziano a diventare rilevanti: , soprattutto, localizzazione cache. Il prefetching può farti sorprendere a lungo.

Quindi considerare la possibilità di SIMD che è possibile vettorializzare per eseguire contemporaneamente quattro punti di ingresso attraverso un singolo registro. Con quattro core e SIMD a 4 ampiezze è possibile teoricamente ottenere un incremento di 16 volte, ma ciò presuppone che il lavoro svolto da InnerFunction sia principalmente una funzione matematica fissa, poiché la ramificazione tende a cancellare i guadagni di prestazioni di SSE/VMX.

Answer 6

Che domanda divertente ... come hai notato, non potrai permetterti i costi generali associati al blocco tradizionale per una coda di lavoro. Ti incoraggio a provare a utilizzare uno degli esistenti ambienti di programmazione a grana fine se puoi ... Ci penso su tre bucket di lavoro:

Il primo problema del problema è garantire la sicurezza , correttezza e parallelizzazione, e suona come se fosse coperto perché la tua funzione è pura.

Penso che la prossima parte più impegnativa è la descrizione della concorrenza, in particolare si menziona questa funzione è chiamata molte volte. Puoi eseguire la pipeline e separare la programmazione della funzione dal suo lavoro? Se non è possibile eseguire la pipeline, sembra un ciclo parallelo, un attraversamento di alberi o è più non strutturato di questo. Specificamente, obeying Amdahl se non riesci a sovrapporre il lavoro e assicurati che ci siano diverse istanze di esso o qualcos'altro in esecuzione nello stesso momento, sei effettivamente seriale anche se sei puro. Tutto ciò che è possibile fare per rifattorizzare il lavoro in una pipeline, un attraversamento dell'albero ricorsivo (o loop parallelo) o se è necessario un lavoro più non strutturato con dipendenze esplicite tra le attività sarà di aiuto qui, indipendentemente dalla libreria utilizzata.

L'ultima area a cui penso è quella di garantire un'esecuzione efficiente sulla piattaforma e ciò comporta la riduzione dei costi generali e di contenimento sia nel codice che nel codice di programmazione e garantisce che qualsiasi codice seriale sia il più efficiente possibile. Se non puoi utilizzare una delle librerie esistenti e devi crearne una tua, ti incoraggio a consultare gli algoritmi di pianificazione auto-guidata work-stealing queue, come hai notato che non sarai in grado di vedere i guadagni dall'usare un serrature tradizionali perché i loro costi superano i costi della tua funzione e molto probabilmente dovrai esaminare le tecniche di blocco per ridurre il costo della pianificazione e la rimozione di un'attività su qualsiasi coda utilizzata. Dovrai inoltre dedicare molta attenzione alla condivisione e alla contesa sia all'interno dell'algoritmo di pianificazione che all'interno della tua funzione, perché a questo livello di granularità oltre ai soliti problemi di malversazione e di throughput delle istruzioni, dovrai anche guardare allo shared state and contention even on reads because they can be sources of contention too.

Mi dispiace se questo non era super specifico, ma spero che sia stato utile.

Answer 7

si potrebbe essere in grado di trasformare il ciclo dentro e fuori utilizzando Confronto-e-Swap per ottenere un incremento libera serratura atomica:

void OuterFunction() 
{ 
    for(int i = 0; i < N; i++) 
    InnerFunction(i); 
} 

va a:

void OuterFunction() 
{ 
    int i = 0, j = 0; 

    void Go() 
    { 
     int k; 
     while((k = atomicInc(*i)) < N) 
     { 
     InnerFunction(k); 

     atomicInc(*j); 
     } 
    } 

    for(int t = 0; t < ThreadCount - 1; t++) Thread.Start(&Go); 

    Go(); // join in 

    while(j < N) Wait(); // let everyone else catch up. 
} 

---

Edit : il mio threading è arrugginito, quindi non verrà compilato perché i nomi sono tutti errati

Answer 8

Non esiste alcuna dipendenza dei dati tra le chiamate, ovvero nessuna chiamata utilizza il risultato di un'altra chiamata.

Questo aiuterà con la parallelizzazione, ma è assolutamente certo che la funzione non ha effetti collaterali. Se la funzione sta aggiornando una struttura dati, è thread-safe? Se sta facendo IO, l'IO finirà per essere un collo di bottiglia se riuscirai a parallelizzare l'esecuzione della funzione?

Se la risposta è "sì" a queste domande, i suggerimenti precedenti vanno bene, basta provare a massimizzare la granularità dell'app assegnando le esecuzioni della funzione a quante più thread possibili.

Eppure, probabilmente non sarà possibile ottenere alcun beneficio dal parallelismo massiccio, ma forse un po 'più modesto aumento di velocità si può avere ...