Esempio di algoritmo di somma parallela su GPU

0

Cercando di immaginare come implementare la somma (o la riduzione?) su un'architettura parallela e sto avendo un momento difficile.

Pensare specificamente in termini di array WebGL di vettori come questo:

[integer1, integer2, integer3, ...]

Ti stai chiedendo se esiste un modo per farlo in parallelo

var array = [ 1, 2, 3, 4, 5, ... ]

var sum = 0
array.forEach(function(number){
  sum += number
})

return sum

Il problema che sto incontrando è penso qui menzionato in questo documento NVidia sulla riduzione della GPU (non del tutto seguendo):

come comunichiamo i risultati parziali tra i blocchi di thread ?

Chiedersi se è possibile descrivere un algoritmo che calcola la somma di qualcosa in parallelo, poiché esiste una variabile condivisa che deve essere utilizzata in qualche modo (la variabile sum). O forse questo non è possibile.

    
posta Lance Pollard 25.04.2018 - 15:39
fonte

1 risposta

1

La risposta breve è che non condividi l'accumulatore. Hai un accumulatore separato per ogni sommatore e inizia ciascuno a 0 . Il passo finale è sommare i risultati.

Ciò si generalizza al di là dell'aritmetica aggiunta, in quanto un riduttore parallelo assumerà che gli argomenti formino un Monoid .

Suppose that S is a set and is some binary operation S × S → S, then S with is a monoid if it satisfies the following two axioms:

  • Associativity
    • For all a, b and c in S, the equation (a • b) • c = a • (b • c) holds.
  • Identity element
    • There exists an element e in S such that for every element a in S, the equations e • a = a • e = a hold.

Dove S è l'insieme di tutti i valori di un particolare tipo, è l'operazione e l'identità e è il valore iniziale (o in alternativa che un'istanza predefinita di S è e )

    
risposta data 25.04.2018 - 17:15
fonte

Leggi altre domande sui tag