Somma prefisso parallelo - implementazione rapida

Question

Desidero implementare l'algoritmo di somma del prefisso parallelo utilizzando C++. Il mio programma dovrebbe prendere l'array di input x[1....N] e dovrebbe visualizzare l'output nell'array y[N]. (Nota il valore massimo di N è 1000.)

Finora ho analizzato molti documenti di ricerca e persino l'algoritmo di Wikipedia. Ma il mio programma dovrebbe anche visualizzare l'output, i passaggi e anche le operazioni/istruzioni di ogni passaggio.

Voglio l'implementazione più veloce come voglio ridurre al minimo il numero di operazioni così come i passaggi.

Ad esempio ::

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

Ma insieme con la visualizzazione della matrice y come uscita, il mio programma dovrebbe contenere anche le operazioni di ogni passo. Mi riferisco anche a questo thread calculate prefix sum, ma potrebbe ottenere molto aiuto da esso.

Answer 1

seguente pezzo di codice farà il lavoro

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; 
} 

Ecco l'output sull'esecuzione

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 

È possibile evitare l'input dell'utente di 1000 elementi di matrice x [] alimentando dal file o così.

Answer 2

L'anwer a questa domanda è qui: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html e qui http://www.cs.cmu.edu/~guyb/papers/Ble93.pdf. L'articolo di NVidia fornisce la migliore implementazione possibile utilizzando le GPU CUDA e il documento PDF della Carnegie Mellon University spiega l'algoritmo. Ho anche implementato un O (n/p) somma prefisso utilizzando MPI, che potete trovare qui: In my github repo

Questa è la pseudocodice per l'algoritmo generico (indipendente dalla piattaforma):

Esempio 3. L'Up-Sweep (Ridurre) Fase di un algoritmo di scansione Sum Work-efficiente (Dopo 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] 

Esempio 4. Il Down-Sweep fase di un algoritmo di scansione parallela Sum Work-efficiente (Dopo 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] 

Dove x sono i dati di ingresso, n è la dimensione dell'input e d è il grado di parallelismo (numero di CPU). Questo è un modello di computazione memoria memoria condivisa , se utilizzato memoria distribuita è necessario aggiungere passaggi di comunicazione a tale codice, come ho fatto nell'esempio Github fornito.

Answer 3

Ho implementato solo la somma di tutti gli elementi in un array (la parte di swell di sweep in alto), non la somma del prefisso completo utilizzando Aparapi (https://code.google.com/p/aparapi/) in java/opencl. È disponibile a https://github.com/klonikar/trial-aparapi/blob/master/src/trial/aparapi/Reducer.java ed è scritto per una dimensione di blocco generale (chiamata localBatchSize nel codice) invece di 2. Ho trovato che la dimensione del blocco di 8 funziona meglio per la mia GPU.

Mentre l'implementazione funziona (calcolo della somma è corretto), si comporta molto peggio della somma sequenziale.Sul mio core-i7 (8 core) CPU, la somma sequenziale richiede circa 12ms per 8388608 (8MB) numeri, l'esecuzione in parallelo su GPU (NVidia Quadro K2000M con 384 core) richiede circa 100ms. Ho persino ottimizzato il trasferimento della somma finale dopo il calcolo e non dell'intero array. Senza questa ottimizzazione, ci vogliono 20ms in più. L'implementazione sembra essere secondo l'algoritmo descritto in risposta da @ marcel-valdez-orozco.