Leçon 20 : Réduction parallèle : somme basée sur un arbre

Une réduction effondre un tableau entier en une seule valeur — par exemple, la somme de tous les éléments. Sur un CPU, ça se fait dans une boucle séquentielle : un accumulateur qui parcourt les n éléments en n étapes. Mais ça gaspille le GPU : un thread travaille pendant que des milliers restent ina

Imagine 8 personnes qui doivent additionner 8 nombres. Au lieu qu'une seule les additionne tous, chaque paire additionne en même temps : 8 deviennent 4, puis 2, puis un seul résultat. Trois tours au lieu de sept — c'est la force de l'arbre.

réduction (reduction): Effondrer un tableau en une seule valeur via une opération associative (somme, maximum, etc.). Sur un GPU, ça se fait sous forme d'arbre.
réduction en arbre (tree reduction): À chaque étape, la moitié des threads additionnent des paires ; la profondeur est de log2(n) étapes au lieu de n.
stride: La distance entre les deux éléments additionnés à une étape donnée. Elle commence grande et est divisée par deux à chaque étape jusqu'à atteindre 1.
synchronisation entre étapes: __syncthreads() après chaque étape garantit que toutes les écritures se sont terminées avant que l'étape suivante ne les lise — sans elle, il y a une condition de course.