使用 OpenMP 优化矩阵转置函数

Question

我有这段代码使用循环平铺策略转置矩阵。

void transposer(int n, int m, double *dst, const double *src) {
   int blocksize;
   for (int i = 0; i < n; i += blocksize) {
      for (int j = 0; j < m; j += blocksize) {
          // transpose the block beginning at [i,j]
          for (int k = i; k < i + blocksize; ++k) {
              for (int l = j; l < j + blocksize; ++l) {
                  dst[k + l*n] = src[l + k*m];
               }
          }
      }
   }
}

我想使用 OpenMP 通过多线程对此进行优化，但是我不确定在有这么多嵌套 for 循环时该怎么做。我考虑只添加 #pragma omp parallel for 但这不只是并行化外循环吗？

Answer 1

您可以使用折叠说明符并行处理两个循环。

#   pragma omp parallel for collapse(2) 
    for (int i = 0; i < n; i += blocksize) {
        for (int j = 0; j < m; j += blocksize) {
            // transpose the block beginning at [i,j]
            for (int k = i; k < i + blocksize; ++k) {
                for (int l = j; l < j + blocksize; ++l) {
                    dst[k + l*n] = src[l + k*m];
                }
            }
        }
    }

作为side-note，我认为你应该交换最里面的两个循环。通常，当你在顺序写入和顺序读取之间做出选择时，写入对性能更重要。

Answer 2

I thought about just adding #pragma omp parallel for but doesnt this just parallelize the outer loop?

是的。要并行化多个连续循环，可以使用 OpenMP 的子句。但是请记住：

（正如所指出的）。尽管这并不直接适用于您的代码片段，但通常，对于每个要并行化的新循环，应该推断出潜在的更新 race-conditions ，例如， 这个并行化可能已经添加了。例如，不同线程同时写入同一个 dst 位置。
在某些情况下，与并行化单个循环相比，并行化嵌套循环可能会导致执行时间变慢。因为，collapse 子句的具体实现使用更复杂的启发式（比简单的循环并行化）在线程之间划分循环的迭代，这可能导致开销高于它提供的收益。

您应该尝试使用单个并行循环进行基准测试，然后使用两个，依此类推，并相应地比较结果。

void transposer(int n, int m, double *dst, const double *src) {
    int blocksize;
    #pragma omp parallel for collapse(...)
    for (int i = 0; i < n; i += blocksize)
       for (int j = 0; j < m; j += blocksize)
           for (int k = i; k < i + blocksize; ++k
               for (int l = j; l < j + blocksize; ++l)
                  dst[k + l*n] = src[l + k*m];
}

根据线程数、核心数、矩阵大小以及其他因素，运行顺序版本实际上可能比并行版本更快。这在您的代码中尤其如此 不是很 CPU 密集（即 dst[k + l*n] = src[l + k*m];）

Answer 3

当您尝试并行化循环嵌套时，您应该问问自己有多少层没有冲突。如：每次迭代写入不同的位置。如果两次迭代（可能）写入同一位置，您需要 1. 使用缩减 2. 使用临界区或其他同步 3. 确定此循环不值得并行化，或者 4. 重写您的算法。

在您的情况下，写入位置取决于 k,l。由于 k<n 和 l*n，没有 k.l / k',l' 对写入同一位置。此外，没有两个内部迭代具有相同的 k 或 l 值。所以四个循环都是并行的，而且是完美嵌套的，所以可以用collapse(4).

你也可以通过抽象地考虑算法得出这个结论：在矩阵转置中每个目标位置恰好被写入一次，所以无论你如何遍历目标数据结构，它都是完全并行的。

使用 OpenMP 优化矩阵转置函数

Optimizing a matrix transpose function with OpenMP

c

parallel-processing

performance

multithreading

openmp