Leçon 21 : Optimisation de la réduction : adressage séquentiel

Dans la leçon précédente, on a construit une réduction en arbre en mémoire partagée : à chaque étape, la moitié des threads additionne une paire de valeurs, réduisant la somme jusqu'à une seule valeur. Mais la façon dont on choisit quels threads sont actifs et quels indices ils touchent change radic

Imagine 8 enfants en rang qui doivent additionner des nombres. Dans la mauvaise méthode, tu demandes à l'enfant 0, 2, 4 et 6 de travailler — l'un travaille, l'un se repose, un vrai désordre. Dans la bonne méthode, tu demandes seulement aux 4 premiers enfants, chacun additionnant le nombre de l'enfant qui lui fait face dans la seconde moitié du rang. La même somme, mais un groupe ordonné travaille pendant que l'autre se repose — sans désordre.

adressage entrelacé (interleaved addressing): Un schéma de réduction où le stride grandit (s *= 2) et le thread actif est 2*s*tid, donc les threads actifs sont dispersés — causant divergence de warp et conflits de bank.
adressage séquentiel (sequential addressing): Un schéma de réduction avec une boucle inversée (s >>= 1) où chaque thread avec tid < s fait tile[tid] += tile[tid+s], donc les threads actifs sont contigus — sans divergence, sans conflits.
conflit de bank (bank conflict): Quand des threads du même warp accèdent au même bank de la mémoire partagée, les accès sont sérialisés au lieu de s'exécuter en parallèle — nuisant à la performance.
threads actifs: Les threads qui travaillent à une étape donnée de la réduction. En adressage séquentiel, c'est un segment contigu 0..s-1 ; en entrelacé, ils sont dispersés.