王濤　趙映誠　劉鑫源

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

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

中圖分類號：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 引言

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

1 矩陣并行化模型的建立

1.1 矩陣乘法的并行化

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

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

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

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

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

2.2 算法程序

2.3 運行時間和效率

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

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

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

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

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

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

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

3.2 算法程序

3.3 運行時間和效率

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

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

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

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

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

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

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

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

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

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

4.3 運行時間和效率

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

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

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

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

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

5.2 算法程序

5.3 運行時間和效率

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

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

6 四種并行方法的對比

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

7 結(jié)束語

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

參考文獻（References）：

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

2010.

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

社，2015.

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

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

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

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

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

用，1997.4：271-275

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

2010.endprint