cudaRiduzione parallela (es. Come sommare una matrice)


Osservazioni

L'algoritmo di riduzione parallela si riferisce in genere a un algoritmo che combina una serie di elementi, producendo un singolo risultato. I problemi tipici che rientrano in questa categoria sono:

  • riassumere tutti gli elementi in un array
  • trovare un massimo in un array

In generale, la riduzione parallela può essere applicata per qualsiasi operatore associativo binario, cioè (A*B)*C = A*(B*C) . Con tale operatore *, l'algoritmo di riduzione parallela raggruppa ripetutamente gli argomenti dell'array in coppie. Ogni coppia è calcolata in parallelo con altre, dimezzando la dimensione complessiva dell'array in un solo passaggio. Il processo viene ripetuto fino a quando esiste un solo elemento.

Se l'operatore è commutativo (cioè A*B = B*A ) oltre ad essere associativo, l'algoritmo può accoppiarsi in un modello diverso. Dal punto di vista teorico non fa alcuna differenza, ma in pratica fornisce un modello di accesso alla memoria migliore:

Non tutti gli operatori associativi sono commutativi, ad esempio, prendere la moltiplicazione della matrice.

Riduzione parallela (es. Come sommare una matrice) Esempi correlati