openMP C++ 简单并行区域 - 输出不一致

Question

如上所述，我一直在尝试制作一个简单的并行循环，但它对于不同数量的线程具有不一致的行为。这是我的代码（可测试！）

#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <string>

using namespace std;

int row = 5, col = 5;
int token = 1;

int ar[20][20] = {0};

int main (void)
{

    unsigned short j_end = 1, k = 1;
    unsigned short mask;

    for (unsigned short i=1; i<=(row + col -1); i++)
    {

        #pragma omp parallel default(none) shared(ar) firstprivate(k, row, col, i, j_end, token) private(mask)
        {
            if(i > row) {
                mask = row;
            }
            else {
                mask = i;
            }

            #pragma omp for schedule(static, 2)
            for(unsigned short j=k; j<=j_end; j++)
            {
                ar[mask][j] = token;
                if(mask > 1) {
                    #pragma omp critical
                    {
                        mask--;
                    }
                }       
            } //inner loop - barrier

        }//end parallel

        token++;
        if(j_end == col) {                          
            k++;
            j_end = col;
        }
        else {
            j_end++;
        }

    } // outer loop

    // print the array
    for (int i = 0; i < row + 2; i++)
    {
       for (int j = 0; j < col + 2; j++)
       {
           cout << ar[i][j] << " ";
       }

        cout << endl;
    }

    return 0;
} // main

我相信大部分代码都是不言自明的，但总而言之，我有 2 个循环，内部循环遍历方阵 ar[row][col] 的反对角线，(row & col 变量可用于更改 ar) 的总大小。

视觉辅助：5x5 的所需输出 ar（连续版）（注意：当 OMP_NUM_THREADS=1 时也会发生这种情况。）

但是当 OMP_NUM_THREADS=2 或 OMP_NUM_THREADS=4 时输出如下所示：

串行（和 1 个线程）代码是一致的，所以我认为实现没有问题。此外，鉴于串行代码的输出，内部循环中不应该有任何依赖关系。

我也试过：

向量化
内循环的 threadpivate 计数器

但到目前为止似乎没有任何效果...

我的方法是否有错误，或者我是否遗漏了导致此行为的 API-wise？

提前感谢您抽出时间。

Answer 1

分析算法

如您所述，算法本身在内部或外部循环中没有依赖性。证明这一点的一种简单方法是将并行性 "up" 移至外循环，以便您可以同时遍历所有不同的反对角线。

现在，您编写的算法的主要问题是它在内循环和外循环中都以串行算法的形式呈现。如果你要在内部循环中并行化，那么 mask 需要特殊处理。如果要在外部循环中并行化，则需要特殊处理 j_end、token 和 k。 "handled specially," 我的意思是它们需要独立于其他线程进行计算。如果您尝试将关键区域添加到您的代码中，您将扼杀最初添加 OpenMP 所带来的所有性能优势。

解决问题

在下面的代码中，我对外部循环进行了并行处理。 i对应你所说的token。也就是说，它既是要添加到反对角线的值，也是该对角线的假定起始长度。请注意，为了正确并行化，length、startRow 和 startCol 必须独立于其他迭代计算为 i 的函数。

最后请注意，一旦以这种方式重写了算法，实际的 OpenMP pragma 就非常简单了。默认情况下假定每个变量都是共享的，因为它们都是只读的。唯一的例外是 ar ，我们小心不要覆盖另一个线程的数组值。所有必须私有的变量仅在并行循环内创建，因此根据定义是线程私有的。最后，我将时间表更改为动态，以展示该算法表现出负载不平衡。在您的示例中，如果您有 9 个线程（最坏的情况），您可以看到分配给 i=5 的线程如何比分配给 i=1 或 i=9 的线程做更多的工作.

示例代码

#include <iostream>  
#include <omp.h>

int row = 5;
int col = 5;

#define MAXSIZE 20
int ar[MAXSIZE][MAXSIZE] = {0};

int main(void)
{

    // What an easy pragma!

    #pragma omp parallel for default(shared) schedule(dynamic)
    for (unsigned short i = 1; i < (row + col); i++)
    {
        // Calculates the length of the current diagonal to consider
        // INDEPENDENTLY from other i iterations!
        unsigned short length = i;
        if (i > row) {
            length -= (i-row);
        }
        if (i > col) {
            length -= (i-col);
        }

        // Calculates the starting coordinate to start at
        // INDEPENDENTLY from other i iterations!
        unsigned short startRow = i;
        unsigned short startCol = 1;
        if (startRow > row) {
            startCol += (startRow-row);
            startRow = row;
        }

        for(unsigned short offset = 0; offset < length; offset++) {
            ar[startRow-offset][startCol+offset] = i;    
        }

    } // outer loop

    // print the array
    for (int i = 0; i <= row; i++)
    {
       for (int j = 0; j <= col; j++)
       {
           std::cout << ar[i][j] << " ";
       }

        std::cout << std::endl;
    }

    return 0;
} // main

最终积分

我想说最后几点。

如果您只是在小型阵列 (row,col < 1e6) 上添加并行性，您很可能无法从 OpenMP 中获益。在小型阵列上，算法本身需要几微秒，而设置线程可能需要几毫秒……与原始串行代码相比，执行时间大大减慢！
虽然我确实重写了这个算法并更改了变量名，但我尽量保持你的实现精神。因此，反对角线扫描和嵌套循环模式仍然存在。
不过，有一种更好的方法可以并行化此算法以避免负载平衡。相反，如果你给每个线程一行，让它迭代其标记值（即 row/thread 2 将数字 2->6），那么每个线程将处理完全相同数量的数字，你可以更改编译指示 schedule(static).
正如我在上面的评论中提到的，当你的意思是 shared 时，不要使用 firstprivate。一个好的经验法则是所有只读变量都应该是 shared.
当运行 1 个线程上的并行代码意味着实现正确时，假设获得正确的输出是错误的。事实上，除非灾难性地使用 OpenMP，否则你不太可能只用 1 个线程得到错误的输出。使用多线程测试表明您之前的实现不正确。

希望这对您有所帮助。

编辑：对于 5x5 矩阵，我得到的输出是 the same as yours。

openMP C++ 简单并行区域 - 输出不一致

openMP C++ simple parallel region - inconsistent output

c++

parallel-processing

multithreading

openmp

分析算法

解决问题

示例代码

最终积分