¿Por qué se desea eficiencia laboral en la programación de GPU?

He estado leyendo el siguiente artículo sobre cómo hacer un escaneo paralelo en CUDA:

https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html

En el artículo, se hace hincapié en hacer que el escaneo "funcione eficientemente". En otras palabras, un algoritmo de GPU no debe realizar más adiciones que un algoritmo de CPU, O (n). Los autores presentan dos algoritmos, uno "ingenuo" que hace adiciones de O (nlogn) y otro que consideran "eficiente en el trabajo". Sin embargo, el algoritmo de trabajo eficiente realiza el doble de iteraciones de bucle.

Según tengo entendido, las GPU son simplemente procesadores SIMD gigantes y deberían funcionar en el paso de bloqueo. Hacer el doble de bucles en el algoritmo de "trabajo eficiente" parece implicar que muchos subprocesos estarán inactivos y disminuirán el rendimiento a largo plazo. ¿Qué me estoy perdiendo?

En primer lugar, re: "las GPU son simplemente procesadores SIMD gigantes y deberían funcionar en el paso de bloqueo", es un poco más complicado que eso. La totalidad de la GPU no se ejecuta al mismo paso. Los hilos de sombreado se organizan en grupos de 32 llamados "urdimbres" (en NVIDIA; en AMD son grupos de 64 llamados "frentes de onda", pero el mismo concepto). Dentro de una deformación, todos los hilos se ejecutan en bloque como una matriz SIMD. Sin embargo, las diferentes urdimbres no están unidas entre sí. Además, algunas deformaciones pueden estar ejecutándose activamente mientras que otras pueden estar suspendidas, al igual que los subprocesos de la CPU. Los warps pueden suspenderse porque están esperando algo (como las transacciones de memoria para regresar o las barreras para borrar), o porque no hay

Ahora, volviendo a tu pregunta. Puedo ver dos maneras en que el algoritmo "eficiente en el trabajo" de ese documento parece que sería más eficiente que el algoritmo "ingenuo".

1. La versión de trabajo eficiente requiere la mitad de hilos para comenzar. En el algoritmo ingenuo, tienen un hilo por elemento de matriz; pero en la versión de trabajo eficiente, cada subproceso opera en dos elementos adyacentes de la matriz y, por lo tanto, solo necesitan la mitad de subprocesos que los elementos de la matriz. Menos hilos significa menos urdimbres, por lo que una fracción mayor de las urdimbres puede estar funcionando activamente.

2. Aunque la versión eficiente en el trabajo requiere más pasos, esto se compensa con el hecho de que el número de subprocesos activos disminuye más rápido y el número total de subprocesos activos en todas las iteraciones es considerablemente menor. Si un warp no tiene hilos activos durante una iteración, ese warp simplemente saltará a la siguiente barrera y se suspenderá, permitiendo que se ejecuten otros warps. Por lo tanto, tener menos deformaciones activas a menudo puede dar sus frutos en el tiempo de ejecución. (Implícito en esto es que el código de la GPU debe diseñarse de tal manera que los hilos activos se agrupen en la menor cantidad de deformaciones posible; no desea que estén dispersos escasamente, ya que incluso un hilo activo forzará toda la deformación mantenerse activo)

   Considere la cantidad de hilos activos en el algoritmo ingenuo. Mirando la Figura 2 en el artículo, puede ver que todos los hilos están activos, excepto los primeros 2 ^k en la iteración k . Entonces, con N hilos, el número de hilos activos es como N - 2 ^k . Por ejemplo, con N = 1024, el número de hilos activos por iteración es:

   1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512
   

   Si convierto esto en un número de deformaciones activas (dividiendo entre 32 y redondeando), obtengo:

   32, 32, 32, 32, 32, 31, 30, 28, 24, 16
   

   por una suma de 289. Por otro lado, el algoritmo de trabajo eficiente comienza con la mitad de los subprocesos, luego reduce a la mitad el número de activos en cada iteración hasta que se reduce a 1, luego comienza a duplicarse hasta que vuelve a subir a la mitad del tamaño de la matriz nuevamente:

    512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
   

   Convirtiendo esto en warps activos:

   16, 8, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 16
   

   La suma es 71, que es solo una cuarta parte. Por lo tanto, puede ver que en el transcurso de toda la operación, el número de deformaciones activas es mucho menor con el algoritmo de trabajo eficiente. (De hecho, para una ejecución larga en el medio solo hay un puñado de deformaciones activas, lo que significa que la mayor parte del chip no está ocupado. Si hay tareas de cálculo adicionales en ejecución, por ejemplo, desde otras secuencias CUDA, podrían expandirse para llenar eso espacio desocupado.)

Dicho todo esto, es lamentable que el artículo de GPU Gems no explique claramente nada de esto, sino que se centra en el análisis de "número de adiciones" de gran O que, aunque no es completamente irrelevante, pierde muchos de los detalles sobre por qué este algoritmo es Más rápido.