使用OpenMP+MPI的矩陣乘法并行實(shí)現(xiàn)

茍悅宬

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044）

1 引言

矩陣乘法是線性代數(shù)中的基礎(chǔ)運(yùn)算，也是科學(xué)研究、工業(yè)生產(chǎn)中很常見(jiàn)的計(jì)算。可它往往會(huì)因?yàn)榫仃囈?guī)模過(guò)大而出現(xiàn)運(yùn)算時(shí)間過(guò)長(zhǎng)等耗費(fèi)時(shí)間的現(xiàn)象，在現(xiàn)實(shí)用于生產(chǎn)時(shí)，顯然無(wú)法承受性能低下帶來(lái)的經(jīng)濟(jì)損失。

基于集群計(jì)算機(jī)的并行算法主要有MPI 和OpenMP 兩種[1]。其中，MPI是一種消息傳遞編程模式，其實(shí)現(xiàn)關(guān)鍵在于正確地進(jìn)行消息傳遞，它的編程模式復(fù)雜，需要分析和合理地劃分計(jì)算程序[1]。OpenMP是一套用于共享內(nèi)存并行系統(tǒng)多線程程序設(shè)計(jì)的指導(dǎo)性注釋(compiler directive)，是為共享內(nèi)存的多處理器系統(tǒng)設(shè)計(jì)的并行編程方法，OpenMP 特別適合用在多核處理器計(jì)算機(jī)上運(yùn)行的并行程序設(shè)計(jì)[2]。MPI+OpenMP 混合并行程序執(zhí)行流程圖如圖1 所示[3]。OpenMP用于每個(gè)結(jié)點(diǎn)上的計(jì)算密集型工作，MPI用于實(shí)現(xiàn)結(jié)點(diǎn)間的通信和數(shù)據(jù)共享。在集群內(nèi)采用MPI技術(shù)，減少消息傳遞的次數(shù)以提高速度，在集群的每個(gè)成員上又采用OpenMP 技術(shù)，節(jié)省內(nèi)存的開(kāi)銷，綜合兩種并行的優(yōu)勢(shì)，可以提升并行程序的執(zhí)行效率。

圖1 MPI+OpenMP 混合并行程序執(zhí)行流程圖[3]

關(guān)于OpenMP和MPI的一些更具體的對(duì)比見(jiàn)表1。

表1 OpenMP和MPI的比較

此外，本實(shí)驗(yàn)在PC 機(jī)與華為鯤鵬處理器上完成，鯤鵬920 處理器采用華為自主開(kāi)發(fā)的處理器內(nèi)核，兼容ARMV8.2 指令集，通過(guò)優(yōu)化分支預(yù)測(cè)算法、提升運(yùn)算單元數(shù)量、改進(jìn)內(nèi)存子系統(tǒng)架構(gòu)等一系列微架構(gòu)設(shè)計(jì)，大幅提高了處理器單核性能[4]，且集成了64核，主頻提升至2.6GHz[5]。

本實(shí)驗(yàn)選取兩個(gè)1000*1000 的矩陣相乘，在此種規(guī)模矩陣的相乘下設(shè)計(jì)了MPI+OpenMP混合編程的優(yōu)化方法，采用OpenMP在每個(gè)結(jié)點(diǎn)計(jì)算，使用MPI進(jìn)行進(jìn)程間通信。并在PC機(jī)、華為鯤鵬服務(wù)器上得到了不同線程的運(yùn)行結(jié)果，并給出了性能分析與相關(guān)結(jié)論。

2 并行算法的設(shè)計(jì)與實(shí)現(xiàn)

本實(shí)驗(yàn)取兩個(gè)1000*1000 矩陣Matrix_one和Matrix_two進(jìn)行乘法運(yùn)算，運(yùn)用MPI_Scatter 數(shù)據(jù)分發(fā)的思想將Matrix_one分為數(shù)個(gè)行數(shù)為1000除以進(jìn)程數(shù)、列數(shù)為1000的小矩陣，并使用MPI_Bcast將Matrix_two廣播至每個(gè)進(jìn)程，在每個(gè)MPI 進(jìn)程中，使用OpenMP 輔助進(jìn)行小矩陣和Matrix_two的相乘運(yùn)算。最后再用MPI_Gather聚集運(yùn)算結(jié)果，并顯示時(shí)間性能的相關(guān)信息。圖2是在進(jìn)程數(shù)為4時(shí)的運(yùn)算流程。

圖2 MPI+OpenMP 混合并行程序執(zhí)行示意圖

2.1 兩個(gè)矩陣的形成

為進(jìn)行運(yùn)算首先需要生成兩個(gè)矩陣，采用rand()%10 生成每個(gè)單元都為10以內(nèi)的整數(shù)的矩陣，代碼如下：

這里矩陣2生成的時(shí)候相當(dāng)于直接將一個(gè)矩陣的轉(zhuǎn)置存入，這是為方便后續(xù)運(yùn)算時(shí)兩個(gè)矩陣都是每一行對(duì)應(yīng)相乘，讀取是連續(xù)的，速度較快。

2.2 數(shù)據(jù)分發(fā)與廣播

此處實(shí)現(xiàn)將矩陣1 分塊并將矩陣2 廣播給各線程的工作，做好并行計(jì)算的準(zhǔn)備。代碼如下：

2.3 OpenMP計(jì)算部分

矩陣1 分成的小矩陣和矩陣2 相乘采用OpenMP 執(zhí)行，實(shí)現(xiàn)代碼如下，注意此處ii和kk兩個(gè)局部變量需要在線程內(nèi)部定義，否則會(huì)出現(xiàn)多線程使用同一變量的局面，造成運(yùn)行失敗。代碼如下：

此外，對(duì)于不能整除的情況，即分割過(guò)程中矩陣1剩余的行，直接在線程0中計(jì)算即可，過(guò)程與上述類似。

2.4 結(jié)果聚集

使用MPI_Gather 匯聚計(jì)算結(jié)果，如有需要，也可以將結(jié)果矩陣輸出至文件觀察。匯聚結(jié)果的代碼如下：

MPI_Gather(local_result, local_M * N, MPI_INT, result_Matrix,local_M*N,MPI_INT,0,MPI_COMM_WORLD);

3 測(cè)試結(jié)果

3.1 PC機(jī)測(cè)試結(jié)果

首先進(jìn)行PC機(jī)的測(cè)試，所用PC機(jī)具有8核CPU，分別分配1/2/4/8個(gè)進(jìn)程，所得運(yùn)行時(shí)間如表2。

表2 PC機(jī)測(cè)試結(jié)果

3.2 鯤鵬處理器測(cè)試結(jié)果

單個(gè)華為鯤鵬處理器的運(yùn)行結(jié)果如表3，分別在進(jìn)程數(shù)為1/2/4/8/16/32的情況下進(jìn)行。

表3 鯤鵬處理器（單機(jī)）測(cè)試結(jié)果

多機(jī)運(yùn)行結(jié)果為表4，其分配的線程數(shù)量與單機(jī)一致。

表4 鯤鵬處理器（多機(jī)）測(cè)試結(jié)果

4 性能分析

PC 機(jī)運(yùn)行結(jié)果折線圖如圖3，可見(jiàn)在一般的8 核CPU中，1000*1000 規(guī)模的矩陣乘法運(yùn)算速度隨著進(jìn)程數(shù)提高而顯著加快。

圖3 PC機(jī)結(jié)果折線圖

鯤鵬處理器的運(yùn)行結(jié)果折線圖如圖4，可見(jiàn)鯤鵬處理器的性能比一般PC 機(jī)CPU 高很多，但是這里出現(xiàn)的情況是運(yùn)行時(shí)間隨著進(jìn)程數(shù)的增加、處理器數(shù)量的增加而增加。由此可見(jiàn)并不是進(jìn)程數(shù)越多運(yùn)算就越快，還涉及進(jìn)程通信的時(shí)間損耗、硬件資源的環(huán)境限制、問(wèn)題的規(guī)模大小等諸多因素。

圖4 鯤鵬處理器結(jié)果折線圖

5 結(jié)語(yǔ)

本實(shí)驗(yàn)完成了規(guī)模選取、算法設(shè)計(jì)、代碼編寫與調(diào)試、結(jié)果性能分析的完整過(guò)程，得出了運(yùn)算速度不是單純地取決于進(jìn)程數(shù)量的結(jié)論，這與人們一般的思維方式是不同的，進(jìn)程通信、服務(wù)器交互過(guò)程中發(fā)生的時(shí)間損耗、所用不同硬件環(huán)境的資源限制、欲解決問(wèn)題的規(guī)模大小等許多的因素都會(huì)影響到運(yùn)算時(shí)間的長(zhǎng)短。工業(yè)生產(chǎn)等諸多領(lǐng)域都會(huì)用到此并行編程模型，對(duì)于影響運(yùn)行性能的要素需要格外注意。