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

鄭建華，沈玉利，朱蓉

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

鄭建華，沈玉利，朱蓉

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

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

0 引言

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

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

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

為解決BLM模式在MapReduce框架中出現的問題，本文提出采用向量線性組合的模式實現矩陣乘法，擬主要通過減少Map階段輸出的中間鍵值對來提高計算性能。

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

圖 1所示：

圖 1 VLC計算模式原理示意圖

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

則在VLC模式中，矩陣C的計算過程表述如下：

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

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

2 MapReduce框架下基于VLC模式的算法設計

根據MapReduce計算框架要求，編寫基于MapReduce計算框架的算法關鍵是要實現Map階段函數和Reduce階段函數，為此本小節主要闡述這兩個函數的實現過程。

本研究中將采用一個MapReduce工作任務（Job）完成整個基于VLC的矩陣并行乘法計算，Map函數負責接收矩陣輸入，并根據VLC模式要求產生相應的中間輸出鍵值對，而Reduce函數則對Map函數產生的中間鍵值對執行數乘操作，然后進行向量線性組合疊加，最后輸出結果矩陣C。Map和Reduce函數的輸入輸出如

所示：

表1 Map和Reduce函數的輸入輸出

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

因此在本文中，Reduce函數將接受矩陣行下標相同的鍵值對，這些數據即為計算矩陣C行向量的全部數據。Reduce函數將根據將復合數據中的區分矩陣A和B，并對滿足條件復合數據中值進行數乘操作，即這個數乘結果即為中間權重向量，最后對同一個結點的Reduce函數的所有中間權重向量進行向量線性組合疊加即得到矩陣C的行向量這也是Reduce函數的輸出。

基于以上分析Map函數實現過程偽代碼描述如下：

Algorithm of Map Function：

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

Procedure:

Begin

1: IF 輸入矩陣是左矩陣

5: ELSE

6: 不輸出任何鍵值對

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函數實現過程偽代碼描述如下：

Algorithm of Reduce Function：

Input：每個node得到輸入數據是具有相同鍵值的一系列鍵值序列對：

3 算法分析

3.1 理論分析

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

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

本文主要考慮兩個影響計算性能的因素，第一個是Map函數所產生的中間鍵值對，第二個因素是元素被轉移的次數。

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

表2 兩種影響因素比較

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

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

圖2 理論性能比較曲線

圖中顯示當n逐漸增加的時候，兩種算法的差距越來越大，表明了VLCA算法的優越性。

3.2 實驗結果

不同的矩陣存儲格式會產生不同的預處理開銷，為了得到準確的實驗比較結果，本次實驗中對兩種算法采用相同的輸入格式，如圖3所示：

圖3 矩陣格式

實驗中采用隨機的方式生成不同大小的矩陣。

本次實驗采用3臺計算機構成的Hadoop集群，每臺機CPU為2.13GHz，操作系統采用Ubuntu，Hadoop版本為1.0.4。為了獲取最原始的計算性能數據，本集群并未做任何的配置優化。

不同類型矩陣的VLCA計算時間如圖4所示：

圖4 不同類型的矩陣的VLCA計算時間

dense表示稠密矩陣，sparse表示稀疏矩陣，當n從0增加到1000，用于稠密矩陣的計算時間一直大于用于計算稀疏矩陣的計算時間，并且呈擴大趨勢，這表明了該算法在計算稀疏矩陣時能節省計算時間。

BLMA算法和VLCA算法的計算時間比較如圖5所示：

圖5 兩種算法的計算時間比較

當n <200的局部視圖如圖6所示：

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

圖6中清晰表明兩種算法的執行時間差距隨著n的增加而增加，VLCA算法顯示了較為優越的性能。而當n小于50，二者的執行時間基本相等，這是因為此時的計算量不飽和，整個任務的執行時間主要是啟動MapReduce工作任務的時間。

3.3 分析結果通過對比理論分析和實驗結果，可以得到3個結論：1）當矩陣比較小時，BLMA與VLCA性能相當，而當矩陣比較大時，VLCA顯示出較優越的性能。

2）對比圖2和圖5發現，當n 為500，實驗結果的時間耗比倍數（VLCA算法時間/BLMA算法時間）比理論分析的時間耗比倍數要小，這說明a不應該是0.5，應該是更大，可達0.9。說明基于MapReduce框架的并行算法中Map函數輸出的中間鍵值多少是影響算法性能的最重要z因素。

3）VLCA用于稀疏矩陣并沒有體現較大的性能優勢，這進一步證明了第二個結論的正確性，即MapReduce框架處理中間鍵值對的時間要遠比執行乘法運算耗費的時間多。

4 總結

面對越來越大規模的數據集，傳統的矩陣并行算法并不適用，而MapReduce框架顯示出了較好性能優勢。當傳統的基于MapReduce的BLMA矩陣乘法由于產生的中間鍵值對過多導致算法性能較低，為此本文提出了基于向量線性組合疊加的方式實現MapReduce框架下矩陣乘法，該方法極大地減少了中間數據的產生，實驗結果表明算法性能得到提高。在后續的研究中將進一步優化算法，以提升對稀疏矩陣的算法性能。

[1] 雷瀾. 矩陣乘法的并行計算及可擴展性分析 [J]. 重慶工商大學學報(自然科學版), 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

廣東省科技計劃項目（2012B040500040）；廣東省科技計劃高新技術產業化項目（2012B010100048）；廣州市海珠區科技計劃項目（2014-cg-31）

鄭建華（1977-），男，漢族，湖南嘉禾，仲愷農業工程學院，講師，博士，研究方向：系統架構設計，云計算，大數據處理與挖掘，廣州，510225

沈玉利（1955-），男，漢族，山東費縣，仲愷農業工程學院，教授，博士，研究方向：模式識別與智能處理，大數據處理與挖掘，廣州，510225

朱蓉（1976.9-），女，漢族，江西吉安，仲愷農業工程學院，講師，碩士，研究方向：系統架構設計，云計算，大數據處理與挖掘，廣州，510225