可平行算法,用于遍历知道col/row-wise邻域的2D矩阵

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

inner std::vector<int>记录行/ col索引.

我把我的串行版本放在这里,但发现很难进行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

我将创建另一个数组来保存列和行方面最近的邻居。显然，这必须作为第一步完成。我建议创建一个二维数组，其中包含您想要的索引。我会做一个成对的向量，而不是两个向量。对是可并行的并且易于排序。

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