language-agnostic - 使用OpenMP的多个并行级别-可能吗？聪明的？实际的？

Question

我目前正在为我管理的仿真工具开发C++稀疏矩阵/数学/迭代求解器库。我本来希望使用现有的程序包，但是，经过广泛的调查，没有一个适合我们的模拟器(我们查看了flens，it++，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)矩阵，block是子域矩阵的数组，.range返回矢量的一部分，从开始索引到结束索引。

显然，循环可以(并且已经)并行化，因为操作独立于循环的其他迭代(范围不重叠)。因为在一个典型的系统中我们有10-15个块，所以4个以上的线程实际上会产生很大的不同。

并行化被认为是一个不错的选择的另一个地方是每个子域存储方案的MxV操作(上述代码的第1行和第6行中的调用)。关于并行化CRS，CDS和密集矩阵MxV操作，有很多方法可以解决。通常情况下，使用2个线程可以看到不错的提升，随着添加更多线程， yield 将大大减少。

我正在构想一个方案，其中在上面的代码的块循环中将使用4个线程，而这些线程中的每个线程将在子域求解中使用2个线程。但是，我不确定使用OpenMP如何管理线程池-是否可以限制openmp for循环中的线程数？在实践中，这种多级并行性是否有意义？对于我在这里提出的任何其他想法，将不胜感激(并感谢您一直以来的阅读!)

Answer 1

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

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

是的。有不同的方法可以做到这一点。设置omp_set_nested(1);并在外部循环中使用类似#pragma omp parallel for num_threads(4)或类似内容的内容，在内部循环中使用#pragma omp parallel for num_threads(2)指令。这应该给您8个线程(取决于实现，如果内核少于8个，则可能还必须设置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
}

您有时可以使用 #pragma omp task在OpenMP 3.0中更有效地执行相同的操作。

或者，您启动8个线程并在并行部分中获取当前线程号，然后根据线程号手动进行调度。

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

在实践中，这种多级并行性是否有意义？

这要看情况，而且您必须找出自己的位置。通常，多级并行处理使您的问题更具可扩展性。但是，调度可能会更加复杂。这个 paper可能很有趣。

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

手动设置嵌套并行性中的线程数的主要缺点是，最内层循环中的线程可能会在隐式屏障处闲置等待，而其他工作可能会完成( example)。而且，粗粒度并行度不能很好地扩展。因此，如果您的外循环在循环内的运行时非常不同，则您希望比仅拆分为4个线程更灵活地进行调度。

其他想法

您是否想通过SIMD执行MxV。根据体系结构，这可以使速度提高2-4。我迅速为您搜索了这个 presentation。

对于MxV， loop tiling， register and cache blocking和相关技术可以增加数据的位置并减少其他问题，例如虚假分享。第11章 book(您可以预览)可能会为您提供有关如何重组数据访问的其他一些想法。