algorithm - MPI:混淆算法实现

Question

我有一个纯代码:

double eps;
A[N][N][N]; 

    ...


        for(i=1; i<=N-2; i++)
            for(j=1; j<=N-2; j++)
                for(k=1; k<=N-2; k++)
                {
                    A[i][j][k] = (A[i-1][j][k]+A[i+1][j][k])/2.;
                }
        for(i=1; i<=N-2; i++)
            for(j=1; j<=N-2; j++)
                for(k=1; k<=N-2; k++)
                {
                    A[i][j][k] = (A[i][j-1][k]+A[i][j+1][k])/2.;
                }
        for(i=1; i<=N-2; i++)
            for(j=1; j<=N-2; j++)
                for(k=1; k<=N-2; k++)
                {
                    double e;
                    e=A[i][j][k];
                    A[i][j][k] = (A[i][j][k-1]+A[i][j][k+1])/2.;
                    eps=Max(eps,fabs(e-A[i][j][k]));
                }

我需要使用 MPI 编写并行代码。

好的，我明白了，如何处理 eps - 它是全局变量，我需要在任何地方进行计算。所以，我创建局部变量，计算它并从每个节点返回结果。或使减少。

但是如何处理矩阵 A？它必须由每个节点共享。如何同步每个三元组 for 构造？ (如果使用 see，当前 A[i][j][k] 元素是使用他的邻居计算的 - 左右 A[i-1][][] A [i+1][][] 或顶部和底部 A[][j+1][] A[][j-1][] 或前后 A[][][k-1] A[][][k+1])

谢谢!

第一版:

我的第一个解决方案是替换 for 结构以最小化索引的依赖性，例如:

        for(j=1; j<=N-2; j++)
            for(k=1; k<=N-2; k++)
//MPI here, Send processor (j,k) - coordinates of vector to compute next statement
                for(i=1; i<=N-2; i++)
                {
                    A[i][j][k] = (A[i-1][j][k]+A[i+1][j][k])/2.;
                }

等等:

        for(i=1; i<=N-2; i++)
            for(k=1; k<=N-2; k++)
                for(j=1; j<=N-2; j++)
//here (i,k) is free dimensions, dependency only from j. send vector(i,k) to every processor
                {
                    A[i][j][k] = (A[i][j-1][k]+A[i][j+1][k])/2.;
                }

        for(i=1; i<=N-2; i++)
            for(j=1; j<=N-2; j++)
                for(k=1; k<=N-2; k++)
//dependency only from k, (i,j) are free. send it to processor
                {
                    double e;
                    e=A[i][j][k];
                    A[i][j][k] = (A[i][j][k-1]+A[i][j][k+1])/2.;
                    eps=Max(eps,fabs(e-A[i][j][k]));
                }

Answer 1

您的算法表现出数据依赖性，与 3D FFT 算法非常相似。无论您选择如何分布数据，它都不是其中一个循环的最佳分布。例如。如果您沿 k 轴分布，那么第一个和第二个循环可以并行运行，但最后一个循环不能。

解决方案是在最后一个循环之前转置矩阵。分布式矩阵的全局转置通常使用 all-to-all 操作完成，MPI_ALLTOALL 或 MPI_ALLTOALLV，具体取决于矩阵是否被划分为大小相等的缝隙(这通常取决于矩阵大小是否可以被 MPI 进程数整除)。看看this excellent answer乔纳森·杜西 (Jonathan Dursi) 着。它适用于 2D 情况，但也可以轻松扩展到 3D。