使用OpenMP实现多级并行 - 可能吗？聪明？实际的？

Question

我目前正在研究一个C++稀疏矩阵/数学/迭代求解器库,用于我管理的仿真工具.我宁愿使用现有的包装,但经过广泛的调查后,没有发现任何适合我们的模拟器(我们看过它们,它们是++,PetSC,eigen和其他几种).好消息是我的求解器和稀疏矩阵结构现在非常高效和稳健.坏消息是,我现在正在研究使用OpenMP进行并行化,学习曲线有点陡峭.

我们解决的域可以分解为子域,这些子域以块对角格式组合在一起.因此,我们的存储方案最终看起来像一个较小的方形矩阵(块[])数组,每个矩阵具有适合于子域的格式(例如压缩行存储:CRS,压缩对角存储:CDS,密集等等),以及用于解决子域之间连接的背景矩阵(当前使用CRS).

大多数(所有？)迭代求解器中的"热点"是矩阵向量乘法运算,这对我的库来说也是如此.因此,我一直致力于优化我的MxV例程.对于块对角线结构,M*x = b的伪代码如下:

b=background_matrix*x
start_index = 1;
end_index = 0;
for(i=1:number of blocks) {
    end_index=start_index+blocks[i].numRows();
    b.range(start_index, end_index) += blocks[i] * x.range(start_index, end_index);
    start_index = end_index+1;
}

其中background_matrix是背景(CRS)矩阵,blocks是子域矩阵的数组,而.range返回从起始索引到结束索引的向量部分.

显然,循环可以(并且已经)并行化,因为操作独立于循环的其他迭代(范围是非重叠的).由于我们在典型系统中有10-15个块,因此4个线程实际上会产生显着差异.

并行化被认为是一个很好的选择的另一个地方是每个子域存储方案的MxV操作(在上面的代码中调用第1行和第6行).有很多关于并行化CRS,CDS和密集矩阵MxV操作的东西.通常情况下,使用2个线程可以获得很好的提升,随着更多线程的添加,返回会大大减少.

我正在设想一个方案,其中4个线程将在块循环中用于上述代码,并且每个线程将使用2个线程用于子域求解.但是,我不确定如何使用OpenMP来管理线程池 - 是否可以限制openmp for循环中的线程数量？这种多层次的并行性在实践中是否有意义？关于我在这里建议的任何其他想法将不胜感激(并感谢阅读一直到最后!)

Answer 1

请注意，我描述的所有内容都依赖于实现。

是否可以限制 openmp for 循环中的线程数？

是的。有不同的方法可以做到这一点。在外循环中设置omp_set_nested(1);并使用类似或类似的内容，并在内循环中设置并使用指令。这应该给你 8 个线程（取决于实现，如果你的核心少于 8 个，你可能还必须设置）#pragma omp parallel for num_threads(4)#pragma omp parallel for num_threads(2)OMP_THREAD_LIMIT

或者，您可以手动展开循环，例如使用类似的东西

#pragma omp parallel sections {
     #pragma omp section 
     do your stuff for the first part, nest parallel region again
     #pragma omp section 
     and so on for the other parts
}

有时，您可以在 OpenMP 3.0 中使用#pragma omp task.

或者启动 8 个线程并获取并行部分中的当前线程编号，并根据线程编号手动调度。

最后，如果您有一个完美的嵌套循环（如果实际赋值仅发生在最内层循环中，则循环是完美嵌套的），您可以将所有内容重写为单个循环。基本上将两个迭代器打包i成j一个大迭代器(i, j)。请注意，这可能会减少局部性，从而降低性能

这种多级并行性在实践中有意义吗？

这要看情况，你必须自己找出答案。一般来说，多级并行性使您的问题更具可扩展性。然而，日程安排可能会更复杂。这篇论文可能很有趣。

关于手动设置线程数：设置线程数的主要优点是您可以在调度时使用有关问题的特定知识。因此，您可以减少开销并获得正在执行的代码的更高局部性，从而获得更多的缓存命中和更少的主内存 I/O。

手动设置嵌套并行线程数的主要缺点是最内层循环中的线程可能会在隐式屏障处空闲等待，而可以完成额外的工作（示例）。此外，粗粒度并行性也不能很好地扩展。因此，如果您的外循环在循环内具有非常不同的运行时，您希望比简单地分成 4 个线程更灵活地进行调度。

任何其他想法

您是否考虑过使用 SIMD 进行 MxV？根据架构的不同，这可以提供 2-4 倍的加速。我很快就在谷歌上为您搜索了这个演示文稿。

对于MxV，循环平铺、寄存器和缓存阻塞以及相关技术可以增加数据局部性并减少其他问题，例如错误共享。本书第11 章（您可以预览）可能会为您提供一些有关如何重构数据访问的其他想法。