C、OpenMP : How can I make this parallisation of a triple loop better?

Question

我正在尝试并行化 Floyd-Warshall使用 OpenMP 的算法(基本上就地编辑 2D 数组)，但我怀疑我是否以最好的方式处理它，这是我到目前为止所得到的:

    #pragma omp parallel for private(i, j, k) shared(g)
    for ( i = 0; i < n; i++ ) {
        for ( j = 0; j < n; j++ ) {
            for ( k = 0; k < n; k++ ) {
                g->A[j][k] = imin( g->A[j][k], g->A[j][i] + g->A[i][k] );
            }
        }
    }

关于如何更好地利用 OpenMP 的任何想法？目前运行时间仅减半，当然可以改进。

此外，如果有人对用于并行化的其他技术有任何建议，我会洗耳恭听。我考虑过 MPI，但我必须让我的整个 main 函数并行，对吗？

谢谢。

编辑

上面的代码不起作用，下面的答案说明了原因。

Answer 1

并行化算法并不简单。看这里的注释 http://www.mcs.anl.gov/~itf/dbpp/text/node35.html 有关并行运行它的信息。如果您的处理器数量较少(双核、四核、八核机器)，那么 Parallel Floyd 1 可能适合您。如果您拥有大量处理器(非常棒的 GPU、网状计算机)，那么 Parallel Floyd 2 可能会更好。