c++ - 遍历 2D 矩阵的可并行算法，同时了解 col/row-wise 邻域

Question

我有一个相当大的N*N整数矩阵Matrix2D(假设内存充足)，

1，在每个行/列中，我需要记录元素的col/row索引，如果它的值不同于它是右/下邻居。

2，我想找到一个可并行化的最优算法，最好是通过 OMP。

所以，最后我会有一些数据结构，比如，

std::vector<std::vector<int>>   RowWiseDiscontinuity(N);// N= #of rows
std::vector<std::vector<int>>   ColWiseDiscontinuity(N);// N= #of cols

其中内部 std::vector<int>记录行/列索引。

我把我的串行版本放在这里但是发现很难并行化 OMP...有人可以提供一些想法如何使用 omp 实现遍历这个 2D 矩阵吗？

代码片段,

std::vector<std::vector<int>>   RowWiseDiscontinuity(N);// N= #of rows
std::vector<std::vector<int>>   ColWiseDiscontinuity(N);// N= #of cols
std::vector<int> TempX1;
std::vector<int> TempX2;
for (int y=0; y<N; ++y)
{
    TempX1.clear();
    for (int x =0; x<N; ++x)
    {
        int value = Matrix2D(x,y);
        TempX1.push_back(value);
    }

    auto iter1 = TempX1.begin();
    auto iter2 = TempX2.begin();

    if (y>0)
    for (int x =0; x<N; ++x)
    {
         if (*iter1 !=*(iter1+1))
         {
             RowWiseDiscontinuity[y].push_back(x); //Critical for OMP
         }
         ++iter1;
         ++iter2;
         if (*iter1 != *iter2)
         {
             ColWiseDiscontinuity[x].push_back(y); //Critical for OMP
         }
     }

     TempX2.swap(TempX1); // proceed to next row, remember previous

}

Answer 1

我会创建另一个数组，它包含列和行方面的最近邻居。显然，这必须作为第一步完成。我建议创建一个包含所需索引的二维数组对 (pair)。我会做一个成对的 vector ，而不是两个 vector 。对是可并行化的并且很容易排序。

vector<vector<pair<int, int>>> elements(N);