c++ - 嵌套循环的 OpenMP 偶数/奇数分解

Question

我的代码中有一部分可以并行完成，所以我开始阅读有关 openMP 的内容并做了这些介绍示例。现在，我正尝试将其应用于以下问题，此处以示意图形式呈现:

Grid.h

class Grid
{
public:
    // has a grid member variable
    std::vector<std::vector<int>> 2Dgrid;
    // modifies the components of the 2Dgrid, no push_back() etc. used what could possibly disturbe the use of openMP
    update_grid(int,int,int,in);

};

测试.h

class Test
{
public:
    Grid grid1;
    Grid grid2;
    update();
    repeat_update();
};

测试.cc

.
.
.
Test::repeat_update() {
    for(int i=0;i<100000;i++)
        update();

}



Test::update() {
    int colIndex = 0;
    int rowIndex = 0;
    int rowIndexPlusOne = rowIndex + 1;
    int colIndexPlusOne = colIndex + 1;

// DIRECTION_X (grid[0].size()), DIRECTION_Y (grid.size) are the size of the grid

    for (int i = 0; i < DIRECTION_Y; i++) {
        // periodic boundry conditions
        if (rowIndexPlusOne > DIRECTION_Y - 1)
            rowIndexPlusOne = 0;

        // The following could be done parallel!!!
        for (int j = 0; j < DIRECTION_X - 1; j++) {
             grid1.update_grid(rowIndex,colIndex,rowIndexPlusOne,colIndexPlusOne);
             grid2.update_grid(rowIndex,colIndex,rowIndexPlusOne,colIndexPlusOne);


            colIndexPlusOne++;
            colIndex++;
        }
        colIndex = 0;
        colIndexPlusOne = 1;
        rowIndex++;
        rowIndexPlusOne++;
    }


}
.
.
.

事实是，Test::update(...) 中完成的更新可以并行方式完成，因为 Grid::update(...) 只依赖于网格的最近邻居。因此，例如在内部循环中，多个线程可以独立地完成 colIndex = 0,2,4,... 的工作，这将是均匀分解。之后，可以更新奇数索引 colIndex=1,3,5,...。然后外循环向前迭代一次，方向 x 的更新可以再次并行完成。我有 16 个内核，进行并行化可以节省很多时间。但我完全不知道如何做到这一点，主要是因为我不知道如何跟踪 colIndex、rowIndex 等，因为 #pragma omp parallel for 应用于 i,j 索引。如果有人能告诉我走出黑暗的道路，我将不胜感激。

Answer 1

在不知道 update_grid(int,int,int,int) 到底做了什么的情况下，很难给出明确的答案。您显示了一对嵌入式循环

for(int i = 0; i < Y; i++)
{
    for(int j = 0; j < X; j++)
    {
        //...
    }
}

并断言 j 循环可以并行完成。这将是一个细粒度的例子 parallelism .您也可以并行化 i 循环，这是一种更粗粒度的并行化。如果每个单独线程的工作量大致相等，则粗粒度方法具有开销较小的优势(假设两个循环的并行化是等效的)。

在并行化循环时，您必须注意一些事项。对于初学者，您在内循环中递增 colIndexPlusOne 和 colIndex。如果您有多个线程和一个用于colIndexPlusOne 和colIndex 的变量，那么每个线程都会递增变量和/或有race conditions。 .您可以通过多种方式绕过它，或者为每个线程提供变量的拷贝，或者使增量 atomic 或 critical，或者通过完全删除变量的依赖关系和即时计算循环的每一步应该是什么。

我将从并行化整个 update 函数开始:

Test::update()
{
    #pragma omp parallel
    {
        int colIndex = 0;
        int colIndexPlusOne = colIndex + 1;

         // DIRECTION_X (grid[0].size()), DIRECTION_Y (grid.size) are the size of the grid
        #pragma omp for
        for (int i = 0; i < DIRECTION_Y; i++)
        {
            int rowIndex = i;
            int rowIndexPlusOne = rowIndex + 1;
            // periodic boundary conditions
            if (rowIndexPlusOne > DIRECTION_Y - 1)
                rowIndexPlusOne = 0;

            // The following could be done parallel!!!
            for (int j = 0; j < DIRECTION_X - 1; j++)
            {
                 grid1.update_grid(rowIndex,colIndex,rowIndexPlusOne,colIndexPlusOne);
                 grid2.update_grid(rowIndex,colIndex,rowIndexPlusOne,colIndexPlusOne);

                // The following two can be replaced by j and j+1...
                colIndexPlusOne++;
                colIndex++;
            }
            colIndex = 0;
            colIndexPlusOne = 1;
            // No longer needed:
            // rowIndex++;
            // rowIndexPlusOne++;
        }
    }

}

通过将 #pragma omp parallel 放在开头，所有变量都是每个线程的本地变量。此外，在 i 循环的开始，我分配了 rowIndex = i，至少在显示的代码中是这样。 j 循环和 colIndex 也可以这样做。