suma de prefijo paralelo - implementación más rápida

Question

Quiero implementar el algoritmo de suma de prefijo paralelo usando C++. Mi programa debe tomar la matriz de entrada x[1....N], y debe mostrar la salida en la matriz y[N]. (Tenga en cuenta que el valor máximo de N es 1000).

Hasta ahora, he revisado muchos documentos de investigación e incluso el algoritmo en Wikipedia. Pero mi programa también debería mostrar la salida, los pasos y también las operaciones/instrucciones de cada paso.

Quiero la implementación más rápida, como quiero minimizar el número de operaciones, así como los pasos.

Por ejemplo ::

x = {1, 2, 3, 4, 5, 6, 7, 8 } - Input 
y = (1, 3, 6, 10, 15, 21, 28, 36) - Output 

Pero junto con la visualización de la matriz como de salida y, mi programa también debe mostrar las operaciones de cada paso. También recomiendo este hilo calculate prefix sum, pero podría obtener mucha ayuda de él.

Answer 1

siguiente fragmento de código hará el trabajo

void prfxSum() 
{ 
    int *x=0; 
    int *y=0; 
    int sum=0; 
    int num=0; 
    int i=0; 

    cout << "Enter the no. of elements in input array : "; 
    cin >> num; 

    x = new int[num]; 
    y = new int[num]; 

    while(i < num) 
    { 
     cout << "Enter element " << i+1 << " : "; 
     cin >> x[i++]; 
    } 

    cout << "Output array :- " << endl; 
    i = 0; 
    while(i < num) 
    { 
     sum += x[i]; 
     y[i] = sum; 
     cout << y[i++] << ", "; 
    } 

    delete [] x; 
    delete [] y; 
} 

siguiente es la salida de la ejecución

Enter the no. of elements in input array : 8 
Enter element 1 : 1 
Enter element 2 : 2 
Enter element 3 : 3 
Enter element 4 : 4 
Enter element 5 : 5 
Enter element 6 : 6 
Enter element 7 : 7 
Enter element 8 : 8 
Output array :- 
1, 3, 6, 10, 15, 21, 28, 36 

Usted puede evitar la entrada del usuario de 1000 elementos de array x [] por la alimentación de archivo más o menos.

Answer 2

El contestador a esta pregunta está aquí: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html y aquí http://www.cs.cmu.edu/~guyb/papers/Ble93.pdf. 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 he implementado un O (n/p) suma prefijo utilizando MPI, que se puede encontrar aquí: In my github repo

Este es el pseudocódigo para el algoritmo genérico (independiente de la plataforma):

Ejemplo 3. La UP-Sweep (Reducir) Fase de una suma de escaneo Algoritmo de trabajo eficientes (Después 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 baja barrido de fase de un paralelo suma Scan-Algoritmo de trabajo eficientes (Después 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 es los datos de entrada, n es el tamaño de la entrada y d es el grado de paralelismo (número de CPU). Este es un modelo de computación de memoria compartida, si usara la memoria distribuida , necesitaría agregar pasos de comunicación a ese código, como hice en el ejemplo provisto de Github.

Answer 3

Implementé solo la suma de todos los elementos en una matriz (el barrido ascendente reduce parte de Blelloch), no la suma de prefijo completa 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é que el tamaño de bloque de 8 funciona mejor para mi GPU.

Mientras la implementación funciona (el cómputo de la suma es correcto), funciona mucho peor que la suma secuencial.En mi core-i7 (8 núcleos) CPU, la suma secuencial toma aproximadamente 12ms para 8388608 (8MB) números, la ejecución paralelizada en GPU (NVidia Quadro K2000M con 384 núcleos) toma aproximadamente 100ms. Incluso he optimizado para transferir solo la suma final después del cálculo y no toda la matriz. Sin esta optimización, lleva 20ms más. La implementación parece estar de acuerdo con el algoritmo descrito en la respuesta de @ marcel-valdez-orozco.