cudaRéduction parallèle (par exemple comment additionner un tableau)


Remarques

L'algorithme de réduction parallèle fait généralement référence à un algorithme qui combine un ensemble d'éléments, produisant un seul résultat. Les problèmes typiques qui entrent dans cette catégorie sont les suivants:

  • résumer tous les éléments d'un tableau
  • trouver un maximum dans un tableau

En général, la réduction parallèle peut être appliquée à tout opérateur associatif binaire, à savoir (A*B)*C = A*(B*C) . Avec un tel opérateur *, l'algorithme de réduction parallèle regroupe à répétition les arguments du tableau par paires. Chaque paire est calculée en parallèle avec d'autres, réduisant de moitié la taille globale de la matrice en une seule étape. Le processus est répété jusqu'à ce qu'un seul élément existe.

Si l'opérateur est commutatif (c.-à-d. A*B = B*A ) en plus d'être associatif, l'algorithme peut se coupler selon un modèle différent. Du point de vue théorique, cela ne fait aucune différence, mais en pratique, cela donne un meilleur modèle d'accès à la mémoire:

Tous les opérateurs associatifs ne sont pas commutatifs - prenons par exemple la multiplication matricielle.

Réduction parallèle (par exemple comment additionner un tableau) Exemples Liés