Lección 21: Optimización de la reducción: direccionamiento secuencial

En la lección anterior construimos una reducción en árbol en memoria compartida: en cada paso la mitad de los hilos suma un par de valores, reduciendo la suma hasta un único valor. Pero la forma en que elegimos qué hilos están activos y qué índices tocan cambia drásticamente el rendimiento. En la ve

Imagina a 8 niños en fila que deben sumar números. En el método malo le pides al niño 0, al 2, al 4 y al 6 que trabajen — uno trabaja, uno descansa, un desorden. En el método bueno le pides solo a los primeros 4 niños, cada uno sumando el número del niño que tiene enfrente en la segunda mitad de la fila. La misma suma, pero un grupo ordenado trabaja mientras el otro descansa — sin desorden.

direccionamiento intercalado (interleaved addressing): Un esquema de reducción donde el stride crece (s *= 2) y el hilo activo es 2*s*tid, así que los hilos activos están dispersos — causando divergencia de warp y conflictos de bank.
direccionamiento secuencial (sequential addressing): Un esquema de reducción con un bucle invertido (s >>= 1) donde cada hilo con tid < s hace tile[tid] += tile[tid+s], así que los hilos activos son contiguos — sin divergencia, sin conflictos.
conflicto de bank (bank conflict): Cuando hilos del mismo warp acceden al mismo bank de la memoria compartida, los accesos se serializan en lugar de ejecutarse en paralelo — perjudicando el rendimiento.
hilos activos: Los hilos que trabajan en un paso dado de la reducción. En el direccionamiento secuencial son un tramo contiguo 0..s-1; en el intercalado están dispersos.