Miglior algoritmo per multi-thread di questa applicazione?

Questa risposta si basa sulla risposta di Erik Eidt .

There are three methods by which you can slice the data: subranges of A, subranges of B, and subranges of N, the latter of which you've already done with your own answer.

Oltre a tagliare semplicemente uno dei set, è possibile tagliare sia su A che su B.

Prima di spiegare, devo prima scusarmi per non aver usato le notazioni matematiche. Questo sito non supporta MathJax , quindi non è possibile per scrivere notazioni che contengono più di un livello di pedici.

Il nome per l'affettatura su più di un sottoinsieme (o dimensione dei dati) è Piastrellatura del loop .

Per semplificare le cose, dividiamo A come segue: (A ₁ ... A ₁₀ ), (A ₁₁ .. .A ₂₀ ), (A ₂₁ ... A ₃₀ ), ... e allo stesso modo B come segue: (B ₁ ... B ₁₀ ), (B ₁₁ ... B ₂₀ ), (B ₂₁ ... B ₃₀ )

La scelta di affettare A e B in gruppi di 10 è arbitraria. Dovresti provare diverse dimensioni di raggruppamento per trovare una combinazione ottimale.

Lo pseudocodice è quindi:

for each ten consecutive items taken from A, namely A(10*j+1...10*j+9)
    for each ten consecutive items taken from B, namely B(10*k+1...10*k+9)
        for each item in the subrange of A(10*j+1...10*j+9), namely "a"
            for each item in the subrange of B(10*k+1...10*k+9), namely "b"
                for i=1...n
                    process f(a, b, ...)

Alcuni dettagli sono omessi nello pseudocodice per evidenziare le specifiche della tecnica del "loop tiling".

Ho omesso l'aspetto della parallelizzazione, ma fondamentalmente si può scegliere uno dei "per" e convertirlo in "parallelo per" per massimizzare completamente l'utilizzo multicore.

Alcuni consigli più generali.

Come spiegato nell'articolo Wikipedia collegato sopra, non esiste una regola semplice che possa aiutare a scegliere la dimensione di subrange più ottimale per A e B. I computer del mondo reale e le prestazioni di esecuzione del software sono influenzati da troppi fattori. Invece, si devono provare valori diversi e vedere quale combinazione viene eseguita più velocemente. Dalla sperimentazione della performance si può scoprire quale dei fattori di prestazione del software sta dominando. Questo può essere scoperto, e non è facile da prevedere con la sola teoria.

Dato che stai usando C, hai diverse scelte:

• OpenMP
• MPI
• Programmazione multithread scritta manualmente mediante pthreads

Vedo che hai tag pthreads nel tag. Tuttavia, per questo tipo di calcolo, sarebbe più semplice ottenere prestazioni migliori utilizzando OpenMP.

Dovresti già sapere sicurezza dei thread . Se non lo fai, è probabile che nessuno dei tuoi programmi multithreaded possa darti una risposta corretta in primo luogo. Quindi è molto importante che tu sappia di cosa si tratta, altrimenti dovresti evitare di utilizzare più thread.

Un modo per aumentare l'utilizzo della CPU multi-core senza multithreading consiste nell'utilizzare più processi (processi OS). Vale a dire, aprire più terminali di console e avviare il programma in ciascun terminale. Indicare a ciascun programma di salvare l'output in un nome file diverso. Al termine di tutti i programmi, combina questi file diversi nel risultato finale.

Non c'è molto da lavorare qui. Non stai divulgando f e inoltre non stai chiedendo di parallelizzare gli interni di f , solo i cicli doppiamente nidificati che invocano f . Mentre esiste una relazione tra f (, n) ed f (, n-1), non vedo come trarne vantaggio a causa del componente randomizzante non rivelato.

(presumo che questo sia il tuo intento, ma per essere chiari, potrebbe esserci una soluzione migliore se potessimo capire il componente randomizzante, dal momento che ripeterlo ripetutamente sembra che tutto il lavoro sia davvero, e fare qualcosa di diverso potrebbe invece essere più efficace.)

Quindi, l'unica cosa che puoi fare è tagliare i dati per mantenere occupati tutti i core.

Esistono tre metodi con cui è possibile suddividere i dati: subranges di A, subranges di B e subranges di N, l'ultimo dei quali hai già fatto con la tua risposta.

Inoltre non hai divulgato la struttura di A o B, tranne che sono ovviamente raccolte, o almeno generatori.

Se si tratta di una raccolta manifestata dalla memoria (array, liste, ecc.), quindi se sono di dimensioni significative, quindi iterando su A e B da ciascun core è possibile eseguire il thrash della cache, a meno che in qualche modo i nuclei cooperino e capiti di funziona allo stesso intervallo di A & B allo stesso tempo, quindi otterranno effettivamente una spinta l'uno dall'altro!

Ma se capita di essere significativamente fuori sincrono tra loro (diciamo perché la logica condizionale in f non sta valutando lo stesso), quindi si combatteranno a vicenda per la cache.

(Un'analogia sta facendo la copia di cartelle / directory di grandi dimensioni sul tuo disco rigido. Se avvii un'altra copia di diverse cartelle contemporaneamente, entrambe le copie rallenteranno probabilmente la ricerca per indicizzazione e, insieme, eseguiranno 10 volte in serie somma delle copie.)

Quindi, per mitigare il combattimento della cache, se questo è davvero un problema, puoi scegliere di limitare le singole cpu a una porzione della matrice A x B che si adatta alla cache e avere tutto il lavoro della cpu su quell'insieme limitato che si adatta alla cache fino a quando tutte le CPU sono terminate, quindi passa ad un altro sottoinsieme della matrice A x B. Se una CPU termina per prima, probabilmente non gli darei nemmeno un nuovo lavoro, presumendo che (a) questo thrashing della cache sia un vero problema per il tuo dominio, e (b) che tutte le CPU finiranno con il loro sottoinsieme A x B in più- o meno allo stesso tempo. Supponendo che probabilmente saremmo più bravi a eseguire tutti i cpus fino al completamento sul sottoinsieme prima di iniziare il prossimo sottogruppo.

Ovviamente, anche tu vuoi generare il maggior numero di thread possibile perché rappresenta anche overhead, il che è un vantaggio dell'affinamento nella tua risposta. Ma è possibile che i thread non sincronizzati riducano la cache in modo sufficientemente risoluto che varrebbe la pena di generare thread aggiuntivi.

D'altra parte, generando esattamente tanti thread come core, ma con un algoritmo che funziona in modo incrementale su sottogruppi matriciali di A x B, quindi aspetta che tutti gli altri core confermino il completamento prima di iniziare il prossimo subrange può fornire il meglio di tutte le soluzioni. Ogni thread annuncia il completamento del sottoinsieme e quindi si sospende in attesa di notifica che tutti i thread sono stati completati.

Quindi ogni core passerebbe attraverso lo stesso sottoinsieme A x B usando la tua nozione di iterazioni n / C, quindi tutti i core passerebbero al successivo sottoinsieme A x B.

In effetti, anche l'utilizzo di subranges per A x B su un singolo algoritmo threadded può migliorare le prestazioni rispetto a tutte le A x B numerose volte, il che è del tutto possibile se la memoria toccata nella matrice A x B non si adatta nella cache. Ogni corsa attraverso A x B deve riportare l'intera struttura di entrambi i dati nella cache (e forse anche ancora e ancora solo per una iterazione attraverso A x B), mentre un singolo thread in esecuzione su un sottoinsieme gestibile potrebbe portare ognuno di questi sottoinsiemi nella cache solo una volta per le iterazioni, quindi potresti iniziare con una singola versione a thread di subset di matrice, quindi aggiungere la sincronizzazione parallela.

Ecco la soluzione al problema molto più generale di parallelizzare qualsiasi loop in modo pulito.

Consenti a ogni thread di tirare gli elementi (coppie di a, b nel tuo caso) uno dopo l'altro e calcola il risultato parziale fino a quando tutti sono consumati.

Filetto principale:

output = 0
iter = iterator_over(A,B)

// start threads and wait until done

answer = output / size(A) / size(B)
return answer

Ogni thread:

res = 0
while true:
   synchronized:
       if !iter.hasNext():
           break
       a,b = it.next()

   res += f(a, b, n)

synchronized:
    output += res

Per prestazioni ottimali, la quantità di thread dovrebbe essere uguale alla quantità di core della CPU.

Diciamo che ho C molti core cpu, e che vorrei eseguire questo in parallelo su C nuclei. Ecco la mia soluzione attuale:

Primo thread:

THREAD_1
count = 0
output = 0

for a in A:
    for b in B:
        output += f(a,b,n/C)
        count += 1

thread_1_answer = output / count

return thread_1_answer

Secondo thread:

THREAD_2
count = 0
output = 0

for a in A:
    for b in B:
        output += f(a,b,n/C)
        count += 1

thread_2_answer = output / count

return thread_2_answer

...

Thread Cth:

THREAD_C
count = 0
output = 0

for a in A:
    for b in B:
        output += f(a,b,n/C)
        count += 1

thread_C_answer = output / count

return thread_C_answer

Infine definisco la risposta finale come segue:

answer = (thread_1_answer + thread_2_answer + ... + thread_C_answer)/C