c-使用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

当您尝试并行化循环嵌套时，您应该问问自己有多少级别是无冲突的。如：每次迭代都写到不同的位置。如果两次迭代(可能(写入同一位置，则需要1。使用减幅2。使用关键部分或其他同步3。决定这个循环不值得并行化，或者4。重写你的算法。

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

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

Answer 2

您可以使用collapse说明符在两个循环上并行化。

#   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];
}
}
}
}

顺便说一句，我认为你应该交换最里面的两个循环。通常，当你在按顺序写作和按顺序阅读之间做出选择时，写作对表现更重要。

Answer 3

我想过只为添加#pragma omp parallel，但不是这样只是将外循环并行化？

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

• (正如Victor Eijkhout所指出的(。尽管这并不直接适用于您的代码片段，但通常情况下，对于要并行化的每个新循环，都应该考虑潜在的较新竞争条件，例如，这种并行化可能添加了。例如，不同线程同时写入同一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];(的代码中尤其如此