Как написать параллельную префиксную сумму в C#?

Question

Я хочу написать сумму параллельного префикса в C#. я использовал этот алгоритм:

initial condition: list of n >= 1 elements stored in A[0...(n-1)] 
final condition: each element A[i] contains A[0]+A[1]+...+A[i] 
begin 
    spawn (p1,p2,...,p(n-1)) 
    foe all pi where 1 <= i <= n-1 do 
    for j←0 to ⌈logn⌉-1 do 
     if i - 2^j >= 0 then 
     A[i] ← A[i] + A[i - 2^j] 
     end if 
    end for 
    end for 
end 

и мой окончательный код в C# является:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 
using MPI; 

namespace prefixsum3 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      int[] A = new int[] { 4, 3, 8, 2, 9, 1, 3, 5, 6, 3 }; 
      using (new MPI.Environment(ref args)) 
      { 
       Intracommunicator comm = Communicator.world; 
       int size, rank, n, i; 
       size = comm.Size; 
       i = comm.Rank + 1; 
       n = A.Length; 
       int[] B = new int[10]; 
       for (int j = 0; j <= (Math.Ceiling(Math.Log(n))) - 1; j++) 
       { 
        int t = Convert.ToInt32(Math.Pow(2, j)); 
        if (i - t >= 0) 
        { 
         B[i] = A[i] + A[i - t]; 
        } 
        comm.Barrier(); 
        A[i] = B[i]; 
        comm.Barrier(); 
       } 
       if (comm.Rank == 0) 
       { 
        for (int z = 0; z < n; z++) 
        { 
         Console.Write(A[z].ToString() + ","); 
        } 
       } 
      } 
     } 
    } 
} 

выход райт должен быть: [4,7,15,17,26,27,30,35, 41,44]
, но мой код выхода: [4,7,8,2,9,1,3,5,6,3]
Кто-нибудь знает, что не так с моим кодом?
EDIT:
Я обнаружил, что каждый процессор видит массив A локально. теперь проблема заключается в том, как определить массив A Глобально, что все процессоры видят один массив?

Answer 1

Что касается правильности, то логарифм в исходном алгоритме относится к базе 2, это ваша ошибка (или одна из них).

Что касается эффективности, вы не правильно поняли алгоритм двойного буфера: вы должны писать в B [i], синхронизировать, а затем менять массивы A и B до следующей итерации. Вам не нужны два барьера или A [i] = B [i]. Однако вы должны сделать B [i] = A [i], когда t больше или равно i.

Наконец-то Math.Pow неэффективен, лучше начать с t = 1, а затем умножить его на 2 на каждой итерации (t < < = 1). не В любом случае вы должны просто использовать следующий цикл, который быстрее и фиксирует ранее упомянутую ошибку (вам больше не нужен журнал):

for (int t = 1; t < n; t <<= 1)