OpenMP循环调度算法及SpMV多核并行化研究

OpenMP是一种支持Fortran，C/C++的共享存储并行编程标准。它基于fork-join的并行执行模型，将程序划分为并行区和串行区。近几年来，OpenMP在SMP(Symmetric Multi-Processing)和多核体系结构的并行编程中得到了广泛的应用。随着多核处理器的发展，实际的应用程序如何充分利用多个处理器核来提高运算效率也成为研究的热点。 在科学计算中，循环结构是最核心的并行对象之一。考虑到负载平衡、调度开销、同步开销等多方面因素，OpenMP标准制定了Static调度、Dynamic调度、Guided调度和Runtime调度等不同策略。针对Guided调度策略不适合递减型循环结构的缺点，本文提出了一种改进的new_guided调度策略，并在OMPi编译器上加以实现。New_guided调度策略的主要思想是对前半部分的循环采用Static调度，后半部分的循环采用Guided调度。此外，本文针对不同的循环结构，在多核处理器上对不同的调度策略进行了评测。测试结果表明，在一般情况下，OpenMP默认的Static策略的调度性能最差；对于规则的循环结构和递增的循环结构，Dynamic调度策略、Guided调度策略和new_guided策略的性能差别不大；对于递减型的循环结构，Dynamic调度策略和new_guided策略的性能相当，要优于Guided调度策略；对于求解Mandelbrot集合这类计算量集中在中间的随机循环结构，Dynamic调度策略优于其它策略，new_guided策略的性能介于Dynamic调度和Guided调度之间。 随着多核处理器的问世和发展，多线程程序设计也已经成为一个不可回避的问题。稀疏矩阵向量乘(SpMV, Sparse Matrix-Vector Multiplication)是一个十分重要且经常被大量调用的科学计算内核。SpMV的存储访问一般都极不规则，导致现有的SpMV算法效率都比较低。目前，多核处理器芯片上的内核数量正在逐步增加。这使得在多核处理器上对SpMV进行并行化加速变得非常重要。本文介绍了稀疏矩阵的两种常用的存储格式CSR和BCSR，并采用OpenMP实现了SpMV的多核并行化。此外，本文还讨论了寄存器分块算法、压缩列索引等优化技术，以及不同调度策略对多线程并行后的SpMV的影响。在曙光天阔服务器S4800A1上的测试表明，大部分矩阵都取得了可扩展、甚至是超线性的加速比，但是对于部分规模较大的矩阵，加速效果并不明显。在我们的测试中，与基于CSR实现的多线程SpMV相比，采用寄存器分块算法优化后的SpMV运算速度平均提高了28.09%。在基于CSR实现的多线程SpMV中，采用列索引优化技术后的程序比优化前的速度平均提高了13.05%。此外，本文实现了一种基于非零元个数的调度策略。在该策略中，每个线程处理几乎相同数量的非零元。我们将它和OpenMP标准提供的三种调度策略进行了测试和分析。测试结果表明：与OpenMP提供的调度策略相比，基于非零元个数的调度策略能取得更好的负载平衡；Dynamic调度和Guided调度在多线程SpMV中的性能基本相当，均优于Static调度策略。