并行計算在矩陣中的應用

王濤　趙映誠　劉鑫源

摘 要： 在解決許多實際問題時，經常需要計算一些高階矩陣。然而傳統的串行計算方法往往效率比較低。因此，需將串行程序并行化來提高計算效率。文章分別研究了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