并行計(jì)算在矩陣中的應(yīng)用

王濤　趙映誠(chéng)　劉鑫源

摘 要： 在解決許多實(shí)際問題時(shí)，經(jīng)常需要計(jì)算一些高階矩陣。然而傳統(tǒng)的串行計(jì)算方法往往效率比較低。因此，需將串行程序并行化來提高計(jì)算效率。文章分別研究了Windows API、OpenMP、MPI、PPL這四種并行計(jì)算方法在矩陣乘法并行化中的應(yīng)用。通過測(cè)試不同規(guī)模的矩陣，根據(jù)加速比衡量并行化的加速效果，對(duì)這四種并行化方法的加速效果進(jìn)行了對(duì)比。結(jié)果表明，這四種方法都可以提高計(jì)算效率，其中MPI的加速效果最好。

關(guān)鍵詞： 計(jì)算效率； 串行計(jì)算； 并行化； 加速比

中圖分類號(hào)：TP338.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

在實(shí)際應(yīng)用中，很多問題往往歸結(jié)于矩陣運(yùn)算方面的應(yīng)用[1]。為了解決傳統(tǒng)的串行計(jì)算方法在運(yùn)算高階矩陣時(shí)效率低下的問題，考慮將串行程序并行化[2]。并行計(jì)算是指將順序執(zhí)行的計(jì)算任務(wù)分成同時(shí)執(zhí)行的子任務(wù)，并行地執(zhí)行這些子任務(wù)，從而完成整個(gè)計(jì)算任務(wù)。由于在矩陣乘法運(yùn)算過程中元素之間沒有數(shù)據(jù)依賴性和數(shù)據(jù)競(jìng)爭(zhēng)的問題，可以充分使用計(jì)算機(jī)資源，因此很適合并行化。本文分別對(duì)Windows API、MPI[3]、OpenMP[4]和PPL這四種多核并行計(jì)算方法在矩陣乘法的并行化做了詳細(xì)的研究。

1 矩陣并行化模型的建立

1.1 矩陣乘法的并行化

以為例，由矩陣乘法運(yùn)算規(guī)則，可以將A矩陣按行、B矩陣按列分為若干塊，每個(gè)矩陣子塊作相應(yīng)的乘法運(yùn)算，最后再將運(yùn)算得到的矩陣塊組合就能得到矩陣相乘的結(jié)果C?，F(xiàn)在假設(shè)一個(gè)并行系統(tǒng)，含有n個(gè)處理機(jī)，每個(gè)處理機(jī)計(jì)算一個(gè)矩陣子塊的乘積。則對(duì)矩陣A、矩陣B進(jìn)行分塊操作：

就得到了C矩陣中第i行、j列的元素，再將最后得到的m*p個(gè)矩陣拼接起來，就可以得到最終的結(jié)果C。

2 基于Windows API的多核并行算法的設(shè)計(jì)

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

根據(jù)矩陣乘法的并行化思路，在Windows API程序中，利用DWORD WINAPI語(yǔ)句，創(chuàng)建四個(gè)線程。通過for循環(huán)將矩陣A分塊，再分別與B進(jìn)行乘法運(yùn)算，由此得到了矩陣C的若干部分。在計(jì)算前，將矩陣C初始化為零矩陣，在計(jì)算時(shí)不斷給矩陣C中相應(yīng)元素賦值。在各個(gè)線程均計(jì)算結(jié)束后，就能得到完整的矩陣C。值得注意的是，在實(shí)際應(yīng)用中，由于可能存在的計(jì)算量、計(jì)算機(jī)資源分配不均，使得某一線程先于其他進(jìn)程計(jì)算完畢，過早進(jìn)入矩陣C的拼接整合階段（此時(shí)C中某些矩陣塊還為0）導(dǎo)致計(jì)算結(jié)果錯(cuò)誤。因此，為了避免這一種情況，使用了WaitForMultipleObjects（）函數(shù)使所有線程運(yùn)算結(jié)束后一起離開并行部分，進(jìn)入拼接整合階段。

2.2 算法程序

2.3 運(yùn)行時(shí)間和效率

在實(shí)驗(yàn)中，取矩陣A、B均為方陣。例如在矩陣階數(shù)為500時(shí)，表明矩陣A、B均為500階的方陣。通過多次運(yùn)行程序取平均值得到串行與并行計(jì)算的運(yùn)行時(shí)間，以單線程運(yùn)行與多線程并行運(yùn)算的時(shí)間的商作為加速比。在64位Intel 5四核環(huán)境下運(yùn)行結(jié)果見圖1。

根據(jù)圖1，在Win API的程序中創(chuàng)建了四個(gè)線程，這意味著將運(yùn)算分為四部分同時(shí)運(yùn)行，所以理論上的最高加速比為4。但在實(shí)際運(yùn)行中發(fā)現(xiàn)加速比最高時(shí)達(dá)到了3.3左右，隨著矩陣規(guī)模的增大加速比穩(wěn)定在2.6左右。

2.4 理論與數(shù)據(jù)分析

在程序的運(yùn)行時(shí)發(fā)現(xiàn)在矩陣規(guī)模較小時(shí)加速效率偏低，這是由于矩陣規(guī)模較小時(shí)，串行運(yùn)算的時(shí)間本來就很短，而并行計(jì)算時(shí)不僅要與串行計(jì)算時(shí)做相同的準(zhǔn)備工作，如函數(shù)庫(kù)載入，程序的編譯等，還需要搭建相應(yīng)的并行環(huán)境，這就導(dǎo)致了加速比在矩陣規(guī)模較小時(shí)偏低和實(shí)際加速比達(dá)不到理論加速比。從圖1的加速比曲線中發(fā)現(xiàn)，矩陣規(guī)模在700-1500階時(shí)加速效果最好，這說明Win API適合中小規(guī)模矩陣的并行計(jì)算。endprint

3 基于OpenMP的多核并行算法的設(shè)計(jì)

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

在OpenMP中，利用parallel指令創(chuàng)建四個(gè)線程。由于parallel指令中的并行域是復(fù)制執(zhí)行方式，惟一的區(qū)別是ID號(hào)不同。parallel指令根據(jù)要求矩陣的大小分為計(jì)算量大致相同的四個(gè)部分，且所有線程均執(zhí)行該源代碼中并行區(qū)域里的程序塊。

3.2 算法程序

3.3 運(yùn)行時(shí)間和效率

由于OpenMP對(duì)矩陣的分塊并不需要人為規(guī)定，它能根據(jù)矩陣規(guī)模和可用的線程數(shù)自動(dòng)分配計(jì)算量。在這個(gè)程序中取了四個(gè)線程，在64位Intel 5四核環(huán)境下運(yùn)行結(jié)果見圖2。

根據(jù)圖2，OpenMP加速比較為穩(wěn)定，在矩陣規(guī)模達(dá)到700階以后沒有明顯起伏，大約為2.3。

3.4 程序與數(shù)據(jù)分析

由于在并行計(jì)算的程序塊中出現(xiàn)for循環(huán)，而并行程序不斷向并行域外取循環(huán)變量的值會(huì)造成時(shí)間上的浪費(fèi)，所以利用private子句將循環(huán)變量作為線程的私有量，能夠減少運(yùn)行的時(shí)間。特別地，在這個(gè)程序中使用了dynamic來分配計(jì)算量。因?yàn)楦骶€程實(shí)際使用情況的差異使線程計(jì)算不同，存在部分線程等待其他線程的情況。使用動(dòng)態(tài)分配能使動(dòng)態(tài)分配、平衡計(jì)算機(jī)資源，這樣使得計(jì)算效率有所提升。整體來說，加速比在2以上，加速效果是不錯(cuò)的。

4 基于MPI的多核并行算法的設(shè)計(jì)

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

MPI是一種基于信息傳遞的并行編程技術(shù)[6]。MPI程序在消息傳遞過程中，并行執(zhí)行的各個(gè)進(jìn)程具有自己獨(dú)立的堆棧和代碼段，而進(jìn)程之間信息的交互完全通過顯式地調(diào)用通信函數(shù)來完成。程序的靈活性大。關(guān)于矩陣乘法的并行計(jì)算的MPI算法，使用了偏移量（offset）的概念。

偏移量在各個(gè)進(jìn)程中都存在且各不相同。思路基本與Win API相同，與Windows API的并行方法不同的是，要確定一個(gè)根線程（root），其中根線程不參與計(jì)算，只負(fù)責(zé)將分塊后的A矩陣、B矩陣發(fā)送給各線程，然后將各線程的計(jì)算結(jié)果整合起來，得到矩陣C。計(jì)時(shí)也在根線程里完成。這就意味著一個(gè)四線程的MPI程序，理論上最高的加速比為三。為了使四種并行方法便于比較，使用五個(gè)線程，理論上的最高加速比為4。

4.2 程序設(shè)計(jì)與分析

在利用MPI并行化方法計(jì)算矩陣相乘時(shí)，線程0僅僅負(fù)責(zé)初始化，發(fā)送，接受和輸出數(shù)據(jù)。其余線程參與計(jì)算。在MPI程序中，矩陣A的分塊是連續(xù)的矩陣塊。比如，矩陣A為400*400的矩陣，對(duì)于一個(gè)五線程的MPI程序，0號(hào)線程（根線程（root））將矩陣A第1行到第100行分為一塊，然后發(fā)送給線程1；將矩陣A的第101行到第200行分為一塊，發(fā)送給線程2；以此類推。在根線程MPI_Send和MPI_Recv中，需要對(duì)矩陣分塊發(fā)送，則需要每個(gè)矩陣塊首元素的地址，這時(shí)引入偏移量（offset）的概念。offset初始化為0，以offset作為每個(gè)矩陣塊在A中的相對(duì)應(yīng)的行，所以&（offset，0）就是每個(gè)矩陣塊的首地址。得到首地址后，需要計(jì)算發(fā)送數(shù)據(jù)的個(gè)數(shù)，即每個(gè)矩陣塊的元素個(gè)數(shù)，rows等于矩陣A的行數(shù)除以參與計(jì)算的線程數(shù)。即每次發(fā)送的數(shù)據(jù)為rows乘以A的列。因?yàn)槠屏亢蛂ows在每個(gè)線程都有自己的值，就不用考慮發(fā)送接受時(shí)的具體細(xì)節(jié)。在從線程中，每個(gè)線程收到的矩陣塊接收地址不用考慮偏移量的問題，因?yàn)樗鼈兪盏降膬H僅是一個(gè)矩陣而已，他們僅需計(jì)算C的相應(yīng)部分。同理，利用根線程傳進(jìn)來的rows可以算出他們計(jì)算的矩陣C的元素個(gè)數(shù)。再將所有信息發(fā)送給根線程。

4.3 運(yùn)行時(shí)間和效率

利用MPI對(duì)矩陣乘法進(jìn)行并行化比較復(fù)雜。如編程環(huán)境的配置麻煩；各線程之間的通信的對(duì)應(yīng)關(guān)系要求高；調(diào)試程序不友好等。但是MPI的優(yōu)點(diǎn)也是很明顯的。支持多種操作系統(tǒng)，易于使用，可移植性較高。MPI是一個(gè)正式被詳細(xì)說明的函數(shù)庫(kù)，已經(jīng)成為一個(gè)標(biāo)準(zhǔn)，有很強(qiáng)的擴(kuò)展性。MPI還擁有完善的異步通信，在計(jì)算方面帶來便捷等。在64位Intel 5四核環(huán)境下運(yùn)行結(jié)果見圖3。

從圖3中仍發(fā)現(xiàn)在矩陣規(guī)模偏小時(shí)并行計(jì)算的加速比偏低的情況約為2.5。隨后加速比基本穩(wěn)定在3左右，其計(jì)算效率（參與計(jì)算線程/理論加速比）為75%。

5 基于PPL的多核并行算法的設(shè)計(jì)

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

PPL 提供了一種命令式的編程模式，提升了開發(fā)并行應(yīng)用程序的可延伸性和易用性。PPL的矩陣計(jì)算問題思想與OpenMP的思想類似，不同之處在于PPL在并發(fā)運(yùn)行時(shí)提供動(dòng)態(tài)計(jì)劃程序，利用parallel_for 算法（lambda 表達(dá)式，函數(shù)對(duì)象或函數(shù)指針）將for循環(huán)進(jìn)行并行執(zhí)行，提高計(jì)算效率。基于PPL矩陣乘法的算法實(shí)現(xiàn)，考慮到矩陣乘法相應(yīng)的特點(diǎn)，利用 parallel_for 指令的復(fù)制執(zhí)行的方式實(shí)現(xiàn)對(duì)任務(wù)的劃分，提高計(jì)算效率。

5.2 算法程序

5.3 運(yùn)行時(shí)間和效率

由于PPL程序是根據(jù)本地計(jì)算的核數(shù)來分配計(jì)算量進(jìn)行并行計(jì)算的，所以理論上PPL的加速比應(yīng)該為4。在64位Intel 5四核環(huán)境下運(yùn)行結(jié)果見圖4。

根據(jù)圖4，在矩陣規(guī)模較小時(shí)仍出現(xiàn)加速比偏低的情況，在矩陣規(guī)模為500-1500時(shí)加速比在2左右，隨著矩陣增加加速比在1.5左右。所以PPL在中小型矩陣的運(yùn)行情況比較好，但是矩陣規(guī)模一大，加速比迅速下降，運(yùn)算效率較低。

6 四種并行方法的對(duì)比

我們分別得到了四種并行方法在矩陣乘法并行化的結(jié)果。接下來對(duì)這四種方法的加速效果作一個(gè)對(duì)比。根據(jù)上文數(shù)據(jù)可以發(fā)現(xiàn)，對(duì)于矩陣運(yùn)算的并行化來說，MPI算法是最理想的，四個(gè)線程參與計(jì)算加速比能達(dá)到3左右。OpenMP與PPL是算法設(shè)計(jì)中比較簡(jiǎn)單的，許多細(xì)節(jié)性問題程序自己就能解決，但是加速比不如人意。Win API是加速比較高的一個(gè)方法，程序較簡(jiǎn)單，是矩陣并行化一個(gè)較理想的方法。

7 結(jié)束語(yǔ)

本文完成了Windows API、OpenMP、MPI以及PPL這四種多核并行化方法在矩陣乘法中的應(yīng)用，解決了傳統(tǒng)的串行計(jì)算方法在計(jì)算高階矩陣時(shí)效率低下的問題。其中MPI算法是最理想的并行化方法，Win API也是加速比較高的一個(gè)方法。在矩陣乘法的并行計(jì)算中，元素之間沒有數(shù)據(jù)依賴性和數(shù)據(jù)競(jìng)爭(zhēng)的問題，這使得并行計(jì)算結(jié)果準(zhǔn)確且能得到較好的加速效果，在實(shí)際應(yīng)用中，尤其是處理大型矩陣問題中很有應(yīng)用價(jià)值。然而，受硬件條件的限制，本文矩陣的階數(shù)也僅僅是到達(dá)2000階的方陣，沒有達(dá)到真正大型矩陣的要求。所以，大型矩陣乘法的并行化效果還有待于進(jìn)一步研究。

參考文獻(xiàn)（References）：

[1] 陳一昭.并行計(jì)算在矩陣運(yùn)算中的應(yīng)用[D].昆明理工大學(xué)，

2010.

[2] 遲學(xué)斌，王彥棢，王玨等.并行計(jì)算與實(shí)現(xiàn)技術(shù)[M].科學(xué)出版

社，2015.

[3] 張錦雄.矩陣相乘并行算法的MPI實(shí)現(xiàn)[M].廣西計(jì)算機(jī)學(xué)會(huì).

廣西計(jì)算機(jī)學(xué)會(huì)2004年學(xué)術(shù)年會(huì)論文集[C].廣西計(jì)算機(jī)學(xué)會(huì)，2004：3

[4] 張艷華，劉祥港.一種基于MPI與OpenMP的矩陣乘法并行

算法[J].計(jì)算機(jī)與現(xiàn)代化，2011.7：84-87

[5] 遲學(xué)斌.分布式系統(tǒng)矩陣并行計(jì)算[J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)

用，1997.4：271-275

[6] 周燦.基于MPI的矩陣運(yùn)算并行算法研究[D].重慶大學(xué)，

2010.endprint