基于向量線性組合的并行矩陣乘法研究

鄭建華，沈玉利，朱蓉

基于向量線性組合的并行矩陣乘法研究

鄭建華，沈玉利，朱蓉

為了解決MapReduce框架下現(xiàn)有矩陣乘法算法性能不高的問(wèn)題，提出了一種基于向量線性組合（Vector Linear Combination：VLC）的矩陣乘法處理模式，介紹了采用MapReduce框架實(shí)現(xiàn)基于VLC模式的矩陣乘法算法的過(guò)程，其中Map函數(shù)負(fù)責(zé)實(shí)現(xiàn)數(shù)據(jù)預(yù)處理，Reduce函數(shù)完成數(shù)乘操作和向量線性疊加。隨后，討論了影響算法執(zhí)行時(shí)間的因素，并從理論方面比較了兩種算法性能。實(shí)驗(yàn)結(jié)果顯示，新算法所需執(zhí)行時(shí)間更少，效率更高，與理論分析相吻合。

并行矩陣乘法；MapReduce；線性組合

0 引言

矩陣乘法應(yīng)用廣泛，傳統(tǒng)串行矩陣乘法算法需要占用較多工作單元和較大存儲(chǔ)空間，其時(shí)間復(fù)雜度一般為隨著n值的增大，計(jì)算效率將受到很大的影響[1]。隨著科學(xué)技術(shù)的發(fā)展，并行計(jì)算機(jī)的出現(xiàn)使大規(guī)模地提高矩陣運(yùn)算速度成為可能，為了實(shí)現(xiàn)并行計(jì)算，需要將矩陣進(jìn)行預(yù)劃分，然后指派給不同的處理器。常用的矩陣分塊乘法運(yùn)算都是將矩陣分塊再用遞歸算法進(jìn)行計(jì)算，比較著名的分塊矩陣乘法算法有Cannon[2]算法，F(xiàn)ox[3]算法，DNS算法，但是采用這些算法實(shí)現(xiàn)較為復(fù)雜，它們要求處理器個(gè)數(shù)P和矩陣的規(guī)模n之間存在關(guān)系而且單臺(tái)計(jì)算機(jī)價(jià)格較為昂貴。

在大數(shù)據(jù)時(shí)代，隨著MapReduce[4]成為最廣泛用于處理數(shù)據(jù)密集計(jì)算的并行計(jì)算框架，許多研究者開始將MapReduce用于矩陣乘法[5-9]。其中文獻(xiàn)[10]關(guān)注多個(gè)矩陣乘法，并提出一種將乘法轉(zhuǎn)換為表連接的計(jì)算模式。其他文獻(xiàn)[11,12]重點(diǎn)關(guān)注兩個(gè)矩陣的乘法，但是他們主要是采用塊級(jí)乘法模式（Block-level Multiplication：BLM）（注：本文命名的BLM與傳統(tǒng)的分塊矩陣乘法不是同一個(gè)概念），即用左矩陣A的一個(gè)行向量乘以右矩陣B的一個(gè)列向量得到目標(biāo)矩陣C的一個(gè)元素。對(duì)于這種模式，在采用MapReduce計(jì)算框架計(jì)算時(shí)，存在兩點(diǎn)不足，第一點(diǎn)當(dāng)矩陣規(guī)模變大時(shí)，計(jì)算性能急劇下降，所耗費(fèi)的計(jì)算時(shí)間急劇上升。其次，如果A為稀疏矩陣，采用BLM模式會(huì)導(dǎo)致大量無(wú)意義乘法運(yùn)算。

在MapReduce計(jì)算框架中，每個(gè)MapReduce計(jì)算任務(wù)過(guò)程被分為兩個(gè)階段：Map階段和Reduce階段，每個(gè)階段都是用鍵值對(duì)（key/value）作為輸入（Input）和輸出（Output）。其中Map階段輸出的鍵值對(duì)經(jīng)過(guò)分區(qū)、排序和融合后作為Reduce階段的輸入。當(dāng)采用BLM模式在MapReduce框架中實(shí)現(xiàn)矩陣乘法時(shí)，為得到矩陣C的一個(gè)元素，Map階段為矩陣A和矩陣B的每個(gè)元素都產(chǎn)生一個(gè)鍵值對(duì)，然后在Reduce階段先組合成一個(gè)行向量和一個(gè)列向量，再執(zhí)行兩個(gè)向量乘法計(jì)算，從而得到矩陣C的一個(gè)元素。這種模式的設(shè)計(jì)過(guò)程使得Map階段產(chǎn)生太多的鍵值對(duì)，并存入Hadoop分布式文件系統(tǒng)HDFS[4]中，由于Reduce階段需要從HDFS上讀取Map的輸出，導(dǎo)致系統(tǒng)I/O時(shí)間增加[13]，從而影響整個(gè)計(jì)算性能。

為解決BLM模式在MapReduce框架中出現(xiàn)的問(wèn)題，本文提出采用向量線性組合的模式實(shí)現(xiàn)矩陣乘法，擬主要通過(guò)減少M(fèi)ap階段輸出的中間鍵值對(duì)來(lái)提高計(jì)算性能。

1 向量線性組合的矩陣乘法原理

圖 1所示：

圖 1 VLC計(jì)算模式原理示意圖

本文稱這種計(jì)算模式為VLC（Vector Linear Combination）模式。

則在VLC模式中，矩陣C的計(jì)算過(guò)程表述如下：

最終得到矩陣C公式（3）：

用MapReduce框架實(shí)現(xiàn)基于VLC的矩陣乘法時(shí)，Map函數(shù)主要負(fù)責(zé)矩陣A和矩陣B數(shù)據(jù)預(yù)處理工作，即將矩陣A拆分成單個(gè)元素，而矩陣B拆分成k個(gè)行向量，這種拆分方式將減少臨時(shí)中間輸出鍵值對(duì)。而Reduce函數(shù)主要通過(guò)數(shù)乘到中間權(quán)重向量，并對(duì)中間權(quán)重向量進(jìn)行線性組合疊加得到矩陣C，當(dāng)矩陣A為稀疏矩陣的時(shí)候，即如果aip為零，則Vijw也是一個(gè)零向量，不需要進(jìn)行乘法計(jì)算，從而節(jié)省了計(jì)算時(shí)間，因此VLC模式也同樣適合稀疏矩陣的乘法，故采用VLC模式可以有效的避免BLM模式中兩大不足。

2 MapReduce框架下基于VLC模式的算法設(shè)計(jì)

根據(jù)MapReduce計(jì)算框架要求，編寫基于MapReduce計(jì)算框架的算法關(guān)鍵是要實(shí)現(xiàn)Map階段函數(shù)和Reduce階段函數(shù)，為此本小節(jié)主要闡述這兩個(gè)函數(shù)的實(shí)現(xiàn)過(guò)程。

本研究中將采用一個(gè)MapReduce工作任務(wù)（Job）完成整個(gè)基于VLC的矩陣并行乘法計(jì)算，Map函數(shù)負(fù)責(zé)接收矩陣輸入，并根據(jù)VLC模式要求產(chǎn)生相應(yīng)的中間輸出鍵值對(duì)，而Reduce函數(shù)則對(duì)Map函數(shù)產(chǎn)生的中間鍵值對(duì)執(zhí)行數(shù)乘操作，然后進(jìn)行向量線性組合疊加，最后輸出結(jié)果矩陣C。Map和Reduce函數(shù)的輸入輸出如

所示：

表1 Map和Reduce函數(shù)的輸入輸出

在MapReduce框架中，MapReduce框架會(huì)收集Map函數(shù)拋出的結(jié)果，并且把具有相同的鍵的鍵值對(duì)分組、排序，而Reduce函數(shù)接受MapReduce庫(kù)分過(guò)組的(key,value[]),然后對(duì)具有相同鍵的中間結(jié)果集進(jìn)行規(guī)約及相關(guān)處理，最后結(jié)果返回給MapReduce庫(kù)。

因此在本文中，Reduce函數(shù)將接受矩陣行下標(biāo)相同的鍵值對(duì)，這些數(shù)據(jù)即為計(jì)算矩陣C行向量的全部數(shù)據(jù)。Reduce函數(shù)將根據(jù)將復(fù)合數(shù)據(jù)中的區(qū)分矩陣A和B，并對(duì)滿足條件復(fù)合數(shù)據(jù)中值進(jìn)行數(shù)乘操作，即這個(gè)數(shù)乘結(jié)果即為中間權(quán)重向量，最后對(duì)同一個(gè)結(jié)點(diǎn)的Reduce函數(shù)的所有中間權(quán)重向量進(jìn)行向量線性組合疊加即得到矩陣C的行向量這也是Reduce函數(shù)的輸出。

基于以上分析Map函數(shù)實(shí)現(xiàn)過(guò)程偽代碼描述如下：

Algorithm of Map Function：

Output：輸出兩種類型鍵-值序列對(duì)：○1 左矩陣輸出其中鍵為i，是元素的行號(hào)，值為○2右矩陣輸出：其中鍵為p,值為對(duì)。矩陣B的輸出則與矩陣A不同，將針對(duì)矩陣B的每一

Procedure:

Begin

1: IF 輸入矩陣是左矩陣

5: ELSE

6: 不輸出任何鍵值對(duì)

7: END IF

8: END FOR

9: ELSE IF 輸入矩陣是右矩陣

10: FOR p=1 to m DO BEGIN

12: END FOR

13: END IF

End

類似的Reduce函數(shù)實(shí)現(xiàn)過(guò)程偽代碼描述如下：

Algorithm of Reduce Function：

Input：每個(gè)node得到輸入數(shù)據(jù)是具有相同鍵值的一系列鍵值序列對(duì)：

3 算法分析

3.1 理論分析

計(jì)算時(shí)間是衡量矩陣乘法算法是否優(yōu)越性的一個(gè)重要指標(biāo)，特別是隨著矩陣的增大，一般計(jì)算時(shí)間會(huì)快速地增加。對(duì)MapReduce計(jì)算框架而言，時(shí)間開銷包括I/O耗時(shí)和CPU耗時(shí)，其中I/O開銷包括從HDFS和本地硬盤讀/寫時(shí)間，而CPU開銷包括執(zhí)行 Mapper/Reducer/Combiner的時(shí)間和進(jìn)行中間數(shù)據(jù)的分區(qū)、排序和融合所耗費(fèi)的時(shí)間[13]。故減少中間鍵值對(duì)的數(shù)量將有助于提高整個(gè)算法計(jì)算性能。

文獻(xiàn)[7]描述了一個(gè)典型的基于BLM模式的矩陣乘法，本文稱該算法為BLMA算法。另外命名本文提出的基于VLC的矩陣并行乘法為VLCA算法，為了比較方便，假定A和B矩陣均為N階方陣。

本文主要考慮兩個(gè)影響計(jì)算性能的因素，第一個(gè)是Map函數(shù)所產(chǎn)生的中間鍵值對(duì)，第二個(gè)因素是元素被轉(zhuǎn)移的次數(shù)。

在BLMA中，為計(jì)算矩陣C中的一個(gè)元素，需要左矩陣A的一個(gè)行向量和右矩陣B的一個(gè)列向量，因此對(duì)矩陣A和矩陣B的每個(gè)元素，Map函數(shù)要輸出個(gè)中間鍵值，因此一共產(chǎn)生了鍵值對(duì)。而在VLCA中，Map函數(shù)產(chǎn)生的中間鍵值對(duì)為?個(gè)，而右矩陣輸出個(gè)（參考第2小節(jié)）。如表2所示：

表2 兩種影響因素比較

基于以上分析，我們定義理論計(jì)算性能如公式（4）、（5）：

基于以上分析，我們得到的理論性能對(duì)比曲線如圖2所示：

圖2 理論性能比較曲線

圖中顯示當(dāng)n逐漸增加的時(shí)候，兩種算法的差距越來(lái)越大，表明了VLCA算法的優(yōu)越性。

3.2 實(shí)驗(yàn)結(jié)果

不同的矩陣存儲(chǔ)格式會(huì)產(chǎn)生不同的預(yù)處理開銷，為了得到準(zhǔn)確的實(shí)驗(yàn)比較結(jié)果，本次實(shí)驗(yàn)中對(duì)兩種算法采用相同的輸入格式，如圖3所示：

圖3 矩陣格式

實(shí)驗(yàn)中采用隨機(jī)的方式生成不同大小的矩陣。

本次實(shí)驗(yàn)采用3臺(tái)計(jì)算機(jī)構(gòu)成的Hadoop集群，每臺(tái)機(jī)CPU為2.13GHz，操作系統(tǒng)采用Ubuntu，Hadoop版本為1.0.4。為了獲取最原始的計(jì)算性能數(shù)據(jù)，本集群并未做任何的配置優(yōu)化。

不同類型矩陣的VLCA計(jì)算時(shí)間如圖4所示：

圖4 不同類型的矩陣的VLCA計(jì)算時(shí)間

dense表示稠密矩陣，sparse表示稀疏矩陣，當(dāng)n從0增加到1000，用于稠密矩陣的計(jì)算時(shí)間一直大于用于計(jì)算稀疏矩陣的計(jì)算時(shí)間，并且呈擴(kuò)大趨勢(shì)，這表明了該算法在計(jì)算稀疏矩陣時(shí)能節(jié)省計(jì)算時(shí)間。

BLMA算法和VLCA算法的計(jì)算時(shí)間比較如圖5所示：

圖5 兩種算法的計(jì)算時(shí)間比較

當(dāng)n <200的局部視圖如圖6所示：

圖6 兩種算法的計(jì)算時(shí)間比較(n<=200)

圖6中清晰表明兩種算法的執(zhí)行時(shí)間差距隨著n的增加而增加，VLCA算法顯示了較為優(yōu)越的性能。而當(dāng)n小于50，二者的執(zhí)行時(shí)間基本相等，這是因?yàn)榇藭r(shí)的計(jì)算量不飽和，整個(gè)任務(wù)的執(zhí)行時(shí)間主要是啟動(dòng)MapReduce工作任務(wù)的時(shí)間。

3.3 分析結(jié)果通過(guò)對(duì)比理論分析和實(shí)驗(yàn)結(jié)果，可以得到3個(gè)結(jié)論：1）當(dāng)矩陣比較小時(shí)，BLMA與VLCA性能相當(dāng)，而當(dāng)矩陣比較大時(shí)，VLCA顯示出較優(yōu)越的性能。

2）對(duì)比圖2和圖5發(fā)現(xiàn)，當(dāng)n 為500，實(shí)驗(yàn)結(jié)果的時(shí)間耗比倍數(shù)（VLCA算法時(shí)間/BLMA算法時(shí)間）比理論分析的時(shí)間耗比倍數(shù)要小，這說(shuō)明a不應(yīng)該是0.5，應(yīng)該是更大，可達(dá)0.9。說(shuō)明基于MapReduce框架的并行算法中Map函數(shù)輸出的中間鍵值多少是影響算法性能的最重要z因素。

3）VLCA用于稀疏矩陣并沒(méi)有體現(xiàn)較大的性能優(yōu)勢(shì)，這進(jìn)一步證明了第二個(gè)結(jié)論的正確性，即MapReduce框架處理中間鍵值對(duì)的時(shí)間要遠(yuǎn)比執(zhí)行乘法運(yùn)算耗費(fèi)的時(shí)間多。

4 總結(jié)

面對(duì)越來(lái)越大規(guī)模的數(shù)據(jù)集，傳統(tǒng)的矩陣并行算法并不適用，而MapReduce框架顯示出了較好性能優(yōu)勢(shì)。當(dāng)傳統(tǒng)的基于MapReduce的BLMA矩陣乘法由于產(chǎn)生的中間鍵值對(duì)過(guò)多導(dǎo)致算法性能較低，為此本文提出了基于向量線性組合疊加的方式實(shí)現(xiàn)MapReduce框架下矩陣乘法，該方法極大地減少了中間數(shù)據(jù)的產(chǎn)生，實(shí)驗(yàn)結(jié)果表明算法性能得到提高。在后續(xù)的研究中將進(jìn)一步優(yōu)化算法，以提升對(duì)稀疏矩陣的算法性能。

[1] 雷瀾. 矩陣乘法的并行計(jì)算及可擴(kuò)展性分析 [J]. 重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版), 2004, 21(02): 121-123.

[2] Cannon L E. A cellular computer implement the Kalman filter algorithm [D]. Bozeman US: Montana State University, 1969.

[3] Fox G C, Otto S W, HEY A J G. Matrix algorithm on a hypercube I:matrix multiplication [J]. Parallel computing, 1987, 4(1): 17-31.

[4] Dean J, Ghemawat S. MapReduce: a flexible data processing tool [J]. Communications of the ACM, 2010, 53(1): 72-77.

[5] Huang B, Wu Y. Matrix multiplication in MapReduce [EB/OL].https://www.cs.duke.edu/courses/cps216/current/ Project/Project/projects/Matrix_Multiply/proj_report.pdf,2 013,02.

[6] Norstad John. A MapReduce algorithm for matrix multiplication [EB/OL].http://www.norstad.org/matrixmultiply/,2013,02.

[7] Rajaraman A, Ullman J D. Mining of massive datasets [M]. Cambridge: Cambridge University Press, 2011.

[8] Seo S, Yoon E J, Kim J, et al. HAMA: an efficient matrix computation with the MapReduce framework[C]// Proceedings of the 2010 IEEE Second International Conference on Cloud Computing Technology and Science.Washington:IEEE Computer Society, 2010:721-726;

[9] Zhang J. Implementation for large scale matrix multiplication on mapreduce parallel framework [J]. Computer Applications and Software, 2012, 29(6):267-71.

[10] J. Myung,S. G. Lee.Matrix chain multiplication via multi-way join algorithms in MapReduce [C]//Proceedings of the 6th International Conference on Ubiquitous Information and Communication. 2012:53-58.

[11] Zeng D J. Large matrix multiplication processing program design of cloud platform [J]. Science Mosaic, 2012, 24(5): 42-45.

[12] Z. G. Sun, T. Li,N. Rishe. Large-scale matrix factorization using MapReduce[C]//Proceedings of the IEEE International Conference on Data Mining Workshops. Washington:IEEE Computer Society, 2010:1242-1248

[13] Dawei Jiang, Beng Chin, Ooi Lei, et al.The Performance of MapReduce: An In-depth Study[J].Proceedings of the VLDB Endowment 2010,3(1):472-483.

TP312

A

2015.04.16）

1007-757X (2015)07-0005-03

廣東省科技計(jì)劃項(xiàng)目（2012B040500040）；廣東省科技計(jì)劃高新技術(shù)產(chǎn)業(yè)化項(xiàng)目（2012B010100048）；廣州市海珠區(qū)科技計(jì)劃項(xiàng)目（2014-cg-31）

鄭建華（1977-），男，漢族，湖南嘉禾，仲愷農(nóng)業(yè)工程學(xué)院，講師，博士，研究方向：系統(tǒng)架構(gòu)設(shè)計(jì)，云計(jì)算，大數(shù)據(jù)處理與挖掘，廣州，510225

沈玉利（1955-），男，漢族，山東費(fèi)縣，仲愷農(nóng)業(yè)工程學(xué)院，教授，博士，研究方向：模式識(shí)別與智能處理，大數(shù)據(jù)處理與挖掘，廣州，510225

朱蓉（1976.9-），女，漢族，江西吉安，仲愷農(nóng)業(yè)工程學(xué)院，講師，碩士，研究方向：系統(tǒng)架構(gòu)設(shè)計(jì)，云計(jì)算，大數(shù)據(jù)處理與挖掘，廣州，510225