1

C# で Parallel プレフィックス合計を書きたいと思います。私はこのアルゴリズムを使用しました：

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]
私のコードの何が問題なのか知っている人はいますか?
編集:
すべてのプロセッサがローカルで配列 A を参照していることがわかりました。問題は、すべてのプロセッサが 1 つの配列を参照できるように、配列 A をグローバルに定義する方法です。

4

1 に答える 1

0

正しさについては、元のアルゴリズムの対数は 2 を底にしています。これはあなたのエラー (またはそれらの 1 つ) です。

効率に関しては、ダブル バッファ アルゴリズムを正しく理解していませんでした。B[i] に書き込み、同期してから、次の反復の前に A 配列と B 配列を交換することになっています。2 つの障壁や A[i] = B[i] は必要ありません。ただし、t が i 以上の場合は、B[i] = A[i] を実行する必要があります。

最後に、Math.Pow は非効率的です。t = 1 から始めて、反復ごとに 2 を掛ける必要があります (t <<= 1)。とにかく、より高速で、前述のエラーを修正する次のループを使用するだけです (ログはもう必要ありません)。

for (int t = 1; t < n; t <<= 1)
于 2014-09-29T07:39:56.917 に答える