并行计算在矩阵中的应用

王涛　赵映诚　刘鑫源

摘 要： 在解决许多实际问题时，经常需要计算一些高阶矩阵。然而传统的串行计算方法往往效率比较低。因此，需将串行程序并行化来提高计算效率。文章分别研究了Windows API、OpenMP、MPI、PPL这四种并行计算方法在矩阵乘法并行化中的应用。通过测试不同规模的矩阵，根据加速比衡量并行化的加速效果，对这四种并行化方法的加速效果进行了对比。结果表明，这四种方法都可以提高计算效率，其中MPI的加速效果最好。

关键词： 计算效率； 串行计算； 并行化； 加速比

中图分类号：TP338.6 文献标志码：A 文章编号：1006-8228（2017）09-33-04

Abstract： In solving many practical problems， some high-order matrices often need to be calculated. However， the traditional serial computing methods are often inefficient. Therefore， serial programs need to be parallelized to improve computational efficiency. In this paper， four parallel computing methods， Windows， API， OpenMP， MPI and PPL， are studied on their application in matrix multiplication. By testing the matrices of different size， and measuring the acceleration effect of parallelization according to the acceleration ratio， the acceleration effect is compared. The results show that all the four methods can improve the computational efficiency， and the acceleration effect of MPI is the best.

Key words： computational efficiency； serial computing； parallelization； acceleration ratio

0 引言

在实际应用中，很多问题往往归结于矩阵运算方面的应用[1]。为了解决传统的串行计算方法在运算高阶矩阵时效率低下的问题，考虑将串行程序并行化[2]。并行计算是指将顺序执行的计算任务分成同时执行的子任务，并行地执行这些子任务，从而完成整个计算任务。由于在矩阵乘法运算过程中元素之间没有数据依赖性和数据竞争的问题，可以充分使用计算机资源，因此很适合并行化。本文分别对Windows API、MPI[3]、OpenMP[4]和PPL这四种多核并行计算方法在矩阵乘法的并行化做了详细的研究。

1 矩阵并行化模型的建立

1.1 矩阵乘法的并行化

以为例，由矩阵乘法運算规则，可以将A矩阵按行、B矩阵按列分为若干块，每个矩阵子块作相应的乘法运算，最后再将运算得到的矩阵块组合就能得到矩阵相乘的结果C。现在假设一个并行系统，含有n个处理机，每个处理机计算一个矩阵子块的乘积。则对矩阵A、矩阵B进行分块操作：

就得到了C矩阵中第i行、j列的元素，再将最后得到的m*p个矩阵拼接起来，就可以得到最终的结果C。

2 基于Windows API的多核并行算法的设计

2.1 基于Windows API的多核并行算法分析

根据矩阵乘法的并行化思路，在Windows API程序中，利用DWORD WINAPI语句，创建四个线程。通过for循环将矩阵A分块，再分别与B进行乘法运算，由此得到了矩阵C的若干部分。在计算前，将矩阵C初始化为零矩阵，在计算时不断给矩阵C中相应元素赋值。在各个线程均计算结束后，就能得到完整的矩阵C。值得注意的是，在实际应用中，由于可能存在的计算量、计算机资源分配不均，使得某一线程先于其他进程计算完毕，过早进入矩阵C的拼接整合阶段（此时C中某些矩阵块还为0）导致计算结果错误。因此，为了避免这一种情况，使用了WaitForMultipleObjects（）函数使所有线程运算结束后一起离开并行部分，进入拼接整合阶段。

2.2 算法程序

2.3 运行时间和效率

在实验中，取矩阵A、B均为方阵。例如在矩阵阶数为500时，表明矩阵A、B均为500阶的方阵。通过多次运行程序取平均值得到串行与并行计算的运行时间，以单线程运行与多线程并行运算的时间的商作为加速比。在64位Intel 5四核环境下运行结果见图1。

根据图1，在Win API的程序中创建了四个线程，这意味着将运算分为四部分同时运行，所以理论上的最高加速比为4。但在实际运行中发现加速比最高时达到了3.3左右，随着矩阵规模的增大加速比稳定在2.6左右。

2.4 理论与数据分析

在程序的运行时发现在矩阵规模较小时加速效率偏低，这是由于矩阵规模较小时，串行运算的时间本来就很短，而并行计算时不仅要与串行计算时做相同的准备工作，如函数库载入，程序的编译等，还需要搭建相应的并行环境，这就导致了加速比在矩阵规模较小时偏低和实际加速比达不到理论加速比。从图1的加速比曲线中发现，矩阵规模在700-1500阶时加速效果最好，这说明Win API适合中小规模矩阵的并行计算。endprint

3 基于OpenMP的多核并行算法的设计

3.1 基于OpenMP的矩阵相乘的并行算法分析

在OpenMP中，利用parallel指令创建四个线程。由于parallel指令中的并行域是复制执行方式，惟一的区别是ID号不同。parallel指令根据要求矩阵的大小分为计算量大致相同的四个部分，且所有线程均执行该源代码中并行区域里的程序块。

3.2 算法程序

3.3 运行时间和效率

由于OpenMP对矩阵的分块并不需要人为规定，它能根据矩阵规模和可用的线程数自动分配计算量。在这个程序中取了四个线程，在64位Intel 5四核环境下运行结果见图2。

根据图2，OpenMP加速比较为稳定，在矩阵规模达到700阶以后没有明显起伏，大约为2.3。

3.4 程序与数据分析

由于在并行计算的程序块中出现for循环，而并行程序不断向并行域外取循环变量的值会造成时间上的浪费，所以利用private子句将循环变量作为线程的私有量，能够减少运行的时间。特别地，在这个程序中使用了dynamic来分配计算量。因为各线程实际使用情况的差异使线程计算不同，存在部分线程等待其他线程的情况。使用动态分配能使动态分配、平衡计算机资源，这样使得计算效率有所提升。整体来说，加速比在2以上，加速效果是不错的。

4 基于MPI的多核并行算法的设计

4.1 基于MPI的矩阵相乘的并行算法分析

MPI是一种基于信息传递的并行编程技术[6]。MPI程序在消息传递过程中，并行执行的各个进程具有自己独立的堆栈和代码段，而进程之间信息的交互完全通过显式地调用通信函数来完成。程序的灵活性大。关于矩阵乘法的并行计算的MPI算法，使用了偏移量（offset）的概念。

偏移量在各个进程中都存在且各不相同。思路基本与Win API相同，与Windows API的并行方法不同的是，要确定一个根线程（root），其中根线程不参与计算，只负责将分块后的A矩阵、B矩阵发送给各线程，然后将各线程的计算结果整合起来，得到矩阵C。计时也在根线程里完成。这就意味着一个四线程的MPI程序，理论上最高的加速比为三。为了使四种并行方法便于比较，使用五个线程，理论上的最高加速比为4。

4.2 程序设计与分析

在利用MPI并行化方法计算矩阵相乘时，线程0仅仅负责初始化，发送，接受和输出数据。其余线程参与计算。在MPI程序中，矩阵A的分块是连续的矩阵块。比如，矩阵A为400*400的矩阵，对于一个五线程的MPI程序，0号线程（根线程（root））将矩阵A第1行到第100行分为一块，然后发送给线程1；将矩阵A的第101行到第200行分为一块，发送给线程2；以此类推。在根线程MPI_Send和MPI_Recv中，需要对矩阵分块发送，则需要每个矩阵块首元素的地址，这时引入偏移量（offset）的概念。offset初始化为0，以offset作为每个矩阵块在A中的相对应的行，所以&（offset，0）就是每个矩阵块的首地址。得到首地址后，需要计算發送数据的个数，即每个矩阵块的元素个数，rows等于矩阵A的行数除以参与计算的线程数。即每次发送的数据为rows乘以A的列。因为偏移量和rows在每个线程都有自己的值，就不用考虑发送接受时的具体细节。在从线程中，每个线程收到的矩阵块接收地址不用考虑偏移量的问题，因为它们收到的仅仅是一个矩阵而已，他们仅需计算C的相应部分。同理，利用根线程传进来的rows可以算出他们计算的矩阵C的元素个数。再将所有信息发送给根线程。

4.3 运行时间和效率

利用MPI对矩阵乘法进行并行化比较复杂。如编程环境的配置麻烦；各线程之间的通信的对应关系要求高；调试程序不友好等。但是MPI的优点也是很明显的。支持多种操作系统，易于使用，可移植性较高。MPI是一个正式被详细说明的函数库，已经成为一个标准，有很强的扩展性。MPI还拥有完善的异步通信，在计算方面带来便捷等。在64位Intel 5四核环境下运行结果见图3。

从图3中仍发现在矩阵规模偏小时并行计算的加速比偏低的情况约为2.5。随后加速比基本稳定在3左右，其计算效率（参与计算线程/理论加速比）为75%。

5 基于PPL的多核并行算法的设计

5.1 基于PPL的矩阵相乘的并行算法分析

PPL 提供了一种命令式的编程模式，提升了开发并行应用程序的可延伸性和易用性。PPL的矩阵计算问题思想与OpenMP的思想类似，不同之处在于PPL在并发运行时提供动态计划程序，利用parallel_for 算法（lambda 表达式，函数对象或函数指针）将for循环进行并行执行，提高计算效率。基于PPL矩阵乘法的算法实现，考虑到矩阵乘法相应的特点，利用 parallel_for 指令的复制执行的方式实现对任务的划分，提高计算效率。

5.2 算法程序

5.3 运行时间和效率

由于PPL程序是根据本地计算的核数来分配计算量进行并行计算的，所以理论上PPL的加速比应该为4。在64位Intel 5四核环境下运行结果见图4。

根据图4，在矩阵规模较小时仍出现加速比偏低的情况，在矩阵规模为500-1500时加速比在2左右，随着矩阵增加加速比在1.5左右。所以PPL在中小型矩阵的运行情况比较好，但是矩阵规模一大，加速比迅速下降，运算效率较低。

6 四种并行方法的对比

我们分别得到了四种并行方法在矩阵乘法并行化的结果。接下来对这四种方法的加速效果作一个对比。根据上文数据可以发现，对于矩阵运算的并行化来说，MPI算法是最理想的，四个线程参与计算加速比能达到3左右。OpenMP与PPL是算法设计中比较简单的，许多细节性问题程序自己就能解决，但是加速比不如人意。Win API是加速比较高的一个方法，程序较简单，是矩阵并行化一个较理想的方法。

7 结束语

本文完成了Windows API、OpenMP、MPI以及PPL这四种多核并行化方法在矩阵乘法中的应用，解决了传统的串行计算方法在计算高阶矩阵时效率低下的问题。其中MPI算法是最理想的并行化方法，Win API也是加速比较高的一个方法。在矩阵乘法的并行计算中，元素之间没有数据依赖性和数据竞争的问题，这使得并行计算结果准确且能得到较好的加速效果，在实际应用中，尤其是处理大型矩阵问题中很有应用价值。然而，受硬件条件的限制，本文矩阵的阶数也仅仅是到达2000阶的方阵，没有达到真正大型矩阵的要求。所以，大型矩阵乘法的并行化效果还有待于进一步研究。

参考文献（References）：

[1] 陈一昭.并行计算在矩阵运算中的应用[D].昆明理工大学，

2010.

[2] 迟学斌，王彦棢，王珏等.并行计算与实现技术[M].科学出版

社，2015.

[3] 张锦雄.矩阵相乘并行算法的MPI实现[M].广西计算机学会.

广西计算机学会2004年学术年会论文集[C].广西计算机学会，2004：3

[4] 张艳华，刘祥港.一种基于MPI与OpenMP的矩阵乘法并行

算法[J].计算机与现代化，2011.7：84-87

[5] 迟学斌.分布式系统矩阵并行计算[J].数值计算与计算机应

用，1997.4：271-275

[6] 周灿.基于MPI的矩阵运算并行算法研究[D].重庆大学，

2010.endprint