parallel-processing - `#pragma parallel for collapse` 和 `#pragma omp parallel for` 之间的区别
问题描述
首先,这个问题可能会有点误导,我理解平行区域中的折叠子句和没有的区域之间的主要区别。假设我想转置一个矩阵,有以下两种方法,第一种是SIMD
用于内部循环的并行 for with 指令,第二种方法是使用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
解决方案
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:我假设矩阵以行优先顺序存储。
推荐阅读
- java - 如何使用 Java Apache HttpClient 正确发出 POST 请求?
- ios - 在 Master App 中组合的两个模块之间传递数据
- angular - TypeError:无法读取空 p-treetable 角度的属性“parentElement”
- kubernetes - Rancher:kube-system pod 卡在 ContainerCreating 上
- c# - Prism:DialogService - 激活现有的非模态对话框
- tensorflow - tf.data.experimental.save VS TFRecords
- git - 有什么方法可以防止提交到本地 git 分支?
- python - 如何从包含其他元素旁边的数组的数据中制作张量流模型?
- android - 关于 ExpandableListView ChildView 的按钮 ClickListener 的问题
- reactjs - 反应不加载图像