`#pragma parallel for collapse` 和 `#pragma omp parallel for` 的区别

Question

首先，这个问题可能有点误导，我理解平行区域中的崩溃子句和没有崩溃子句的区域之间的主要区别。假设我想转置一个矩阵，并且有以下两种方法，第一种是用于内部循环的 SIMD 指令的并行方法，第二种方法是使用 collapse(2) 子句

#pragma omp parallel for
    for(int i=0; i<rows; i++){
#pragma omp simd
      for(int j=0; j<columns; j++){
         *(output + j * rows + i) = *(input + i * columns + j);
    }
}

#pragma omp parallel for collapse(2)
    for(int i=0; i<rows; i++){
      for(int j=0; j<columns; j++){
         *(output + j * rows + i) = *(input + i * columns + j);
    }

以上两种方法，哪种方法效率更高，尤其是在缓存方面？。
在以上两种实施方式中，哪种实施方式更高效、更快速？有什么方法可以让我们仅通过查看实现来确定这一点。

并且鉴于所有循环计数器彼此独立，是否可以设置一个关于何时使用何时使用的基本准则？
TIA

Answer 1

TL;DR: 这两种实现都非常低效。第二个在实践中可能会比第一个慢，尽管理论上它可以扩展得更好。

第一个实现不太可能被向量化，因为访问在内存中不连续。 GCC 10 和 Clang 11 都会生成低效代码。重点是 OpenMP 不提供高级 SIMD 结构 来处理数据转置！因此，如果您想高效地完成它，您可能需要亲自动手（或使用为您完成的外部库）。

第二个实现可能比第一个实现慢得多，因为循环迭代器是线性化的，通常会导致在热路径中执行更多指令。某些实现（例如 Clang 11 和 ICC 19 但不是 GCC 10）甚至使用非常慢的模运算（即 div 指令）来执行此操作，从而导致循环速度慢得多。

第二个实现在理论上也应该比第一个更好地扩展，因为 collapse 子句提供 更多的并行性 。事实上，在第一个实现中，只有 rows 行在 n 线程之间共享。因此，如果您在大规模并行机器或 宽矩形矩阵 上工作，并且 n 与 rows 相比并不小，这可能会导致一些 工作不平衡，甚至线程饥饿

为什么这两种实现都效率低下

由于内存访问模式，这两种实现效率低下。事实上，在大矩阵上，写入 output 是不连续的，会导致许多缓存未命中。一个完整的缓存行（在大多数常见架构上为 64 字节）将被写入，而只有几个字节将被写入其中。如果 columns 是 2 的幂，则会发生缓存抖动并进一步降低性能。

缓解这些问题的一种解决方案是使用平铺。这是一个例子：

// Assume rows and columns are nice for sake of clarity ;)
constexpr int tileSize = 8;
assert(rows % tileSize == 0);
assert(columns % tileSize == 0);

// Note the collapse clause is needed here for scalability and 
// the collapse overhead is mitigated by the inner loop.
#pragma omp parallel for collapse(2)
for(int i=0; i<rows; i+=tileSize)
{
    for(int j=0; j<columns; j+=tileSize)
    {
        for(int ti=i; ti<i+tileSize; ++ti)
        {
            for(int tj=j; tj<j+tileSize; ++tj)
            {
                output[tj * rows + ti] = input[ti * columns + tj];
            }
        }
    }
}

上面的代码应该更快，但不是最优的。成功编写快速转置代码具有挑战性。这里有一些改进代码的建议：

使用临时块缓冲区改进内存访问模式（因此编译器可以使用快速 SIMD 指令）
使用方形图块改善缓存的使用
使用多级平铺来改进 L2/L3 缓存的使用或使用 Z 平铺方法

或者，您可以简单地使用快速 BLAS 实现 提供矩阵转置函数非常优化（不是所有的，但 AFAIK OpenBLAS 和 MKL 做）。

PS：我假设矩阵以行优先顺序存储。

`#pragma parallel for collapse` 和 `#pragma omp parallel for` 的区别

Differences between `#pragma parallel for collapse` and `#pragma omp parallel for`

parallel-processing

simd

vectorization

openmp

为什么这两种实现都效率低下