Solución:
La respuesta a esta pregunta está aquí: Suma de prefijos paralelos (escaneo) con CUDA y aquí: Sumas de prefijos y sus aplicaciones. El artículo de NVidia proporciona la mejor implementación posible utilizando GPU CUDA, y el documento PDF de la Universidad Carnegie Mellon explica el algoritmo. También implementé una suma de prefijo O (n / p) usando MPI, que puede encontrar aquí: En mi repositorio de github.
Este es el pseudocódigo del algoritmo genérico (independiente de la plataforma):
Ejemplo 3. La fase de barrido ascendente (reducción) de un algoritmo de escaneo de suma eficiente en el trabajo (después de Blelloch 1990)
for d = 0 to log2(n) – 1 do
for all k = 0 to n – 1 by 2^(d+1) in parallel do
x[k + 2^(d+1) – 1] = x[k + 2^d – 1] + x[k + 2^(d+1) – 1]
Ejemplo 4. La fase de barrido descendente de un algoritmo de barrido de suma paralela eficiente en el trabajo (después de Blelloch 1990)
x[n – 1] = 0
for d = log2(n) – 1 down to 0 do
for all k = 0 to n – 1 by 2^(d+1) in parallel do
t = x[k + 2^d – 1]
x[k + 2^d – 1] = x[k + 2^(d+1) – 1]
x[k + 2^(d+1) – 1] = t + x[k + 2^(d+1) – 1]
Dónde X son los datos de entrada, norte es el tamaño de la entrada y D es el grado de paralelismo (número de CPU). Esto es un memoria compartida modelo de cálculo, si se utiliza memoria distribuida necesitaría agregar pasos de comunicación a ese código, como hice en el ejemplo de Github proporcionado.
Implementé solo la suma de todos los elementos en una matriz (el barrido ascendente reduce parte de Blelloch), no la suma completa del prefijo usando Aparapi (https://code.google.com/p/aparapi/) en java / opencl. Está disponible en https://github.com/klonikar/trial-aparapi/blob/master/src/trial/aparapi/Reducer.java y está escrito para un tamaño de bloque general (llamado localBatchSize en el código) en lugar de 2. Encontré ese tamaño de bloque de 8 funciona mejor para mi GPU.
Si bien la implementación funciona (el cálculo de la suma es correcto), funciona mucho peor que la suma secuencial. En mi CPU core-i7 (8 núcleos), la suma secuencial toma aproximadamente 12 ms para números 8388608 (8 MB), la ejecución paralelizada en GPU (NVidia Quadro K2000M con 384 núcleos) tarda unos 100 ms. Incluso he optimizado para transferir solo la suma final después del cálculo y no la matriz completa. Sin esta optimización, se necesitan 20 ms más. La implementación parece estar de acuerdo con el algoritmo descrito en la respuesta de @ marcel-valdez-orozco.