基于hadoop大矩陣乘法處理方法

《基于hadoop大矩陣乘法處理方法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、基于Hadoop大矩陣乘法處理方法　　摘要：目前的矩陣乘法算法無法處理大規(guī)模和超大規(guī)模的矩陣，而隨著MapReduce編程框架的提出，并行處理矩陣乘法成為解決大矩陣運算的主要手段。總結(jié)了矩陣乘法在MapReduce編程模型上的并行實現(xiàn)方法，并提出了實現(xiàn)高性能大矩陣乘法的策略——折中單個工作節(jié)點的計算量和需要網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量。實驗證明，并行實現(xiàn)算法在大矩陣上明顯優(yōu)于傳統(tǒng)的單機算法，而且隨著集群中節(jié)點數(shù)目的增多，并行算法會表現(xiàn)出更好的性能。關(guān)鍵詞：大矩陣；矩陣乘法；矩陣運算；MapReduce；Hadoop；并行計算；海量數(shù)據(jù)中

2、圖分類號：TP391；TP311文獻(xiàn)標(biāo)志碼：A0引言隨著數(shù)據(jù)規(guī)模的爆炸性增長，我們希望數(shù)據(jù)挖掘算法能夠適應(yīng)當(dāng)前不斷增長的數(shù)據(jù)處理要求。19矩陣乘法算法廣泛應(yīng)用于圖像處理、推薦系統(tǒng)、數(shù)據(jù)降維等數(shù)據(jù)挖掘領(lǐng)域，然而，傳統(tǒng)的技術(shù)架構(gòu)和僅靠單臺計算機基于串行的方式越來越不適應(yīng)當(dāng)前海量數(shù)據(jù)處理的要求。因此，擴大矩陣乘法的運算規(guī)模并降低其運算時間，將有利于滿足矩陣分解算法處理大規(guī)模數(shù)據(jù)的要求。然而，矩陣乘法具有較高的時間復(fù)雜度，因此利用并行方法降低矩陣乘法的運算時間得到了廣泛的研究與應(yīng)用。隨著技術(shù)的發(fā)展，單機的性能有了突飛猛進的提升，尤其

3、是內(nèi)存和處理器等硬件的性能，但是硬件技術(shù)的發(fā)展在理論上總是有限度的，如果說硬件性能的提升在縱向上提高了系統(tǒng)處理數(shù)據(jù)的能力，那么并行技術(shù)的發(fā)展就是從橫向上拓展了系統(tǒng)的性能。但是，目前許多并行技術(shù)依賴于分布式文件系統(tǒng)[1]，當(dāng)要處理的文件規(guī)模很大時，連接分布式文件系統(tǒng)網(wǎng)絡(luò)的帶寬，便成了制約系統(tǒng)性能的瓶頸。MapReduce[2]是由Google公司推出的一個用于處理大規(guī)模數(shù)據(jù)集并行運算的軟件框架，該架構(gòu)能夠在大量普通配置的計算機上實現(xiàn)并行化處理。根據(jù)MapReduce框架，Apache基金會開發(fā)了開源項目Hadoop[3]，因其

4、在處理海量數(shù)據(jù)時所表現(xiàn)出的顯著性能以及編程模型的簡易性吸引了業(yè)界人士的廣泛關(guān)注。Hadoop中基于GFS（GoogleFileSystem）[4]原理的模塊Hadoop分布式文件系統(tǒng)（HadoopDistributeFileSystem，HDFS）有效地利用數(shù)據(jù)的本地特性，很好地解決了網(wǎng)絡(luò)帶寬的瓶頸問題。一些基于MapReduce并行框架的機器學(xué)習(xí)算法如K均值和K近鄰等算法都已經(jīng)在Hadoop上實現(xiàn)，并獲得了良好的算法性能[5-6]。所以本文選擇在Hadoop平臺上實現(xiàn)矩陣乘法的分布式算法。19傳統(tǒng)矩陣乘法通過求左矩陣行與右

5、矩陣列的內(nèi)積來求解矩陣的乘積。這種算法可以實現(xiàn)為分布式算法，但是其性能不容樂觀。對于矩陣乘法的另外一種形式是將左矩陣的列和右矩陣相應(yīng)的行進行外積運算，從而得到結(jié)果矩陣的部分結(jié)果，最后對各個部分結(jié)果求和。雖然在并行化方面，這種算法與傳統(tǒng)算法相比在效率有了很大提升，但也存在一定的瓶頸：當(dāng)矩陣規(guī)模非常大，大到單個機器的內(nèi)存不能存放左矩陣的一行和右矩陣的一列時，便不能計算。解決這一瓶頸的另一種方法，就是將相乘的兩個矩陣分塊[7]，計算小塊的乘積，從而可以實現(xiàn)無限大的矩陣乘法，當(dāng)然這樣需要很多的額外處理，但是當(dāng)分布式集群中的計算節(jié)點達(dá)

6、到一定數(shù)量時，損失的時間可以用節(jié)約的計算時間彌補。本文在Hadoop框架上討論矩陣乘法的各種實現(xiàn)方法，并實驗對比各種方法的適用情形。1矩陣乘法相關(guān)研究矩陣運算在數(shù)據(jù)挖掘領(lǐng)域有著廣泛的應(yīng)用，比如圖像處理、文本挖掘[8]、推薦系統(tǒng)和生物信息學(xué)等。矩陣乘法是矩陣運算中的一項重要運算。在矩陣分解方法并行化處理中，矩陣乘法在總計算量中占據(jù)很大比重[9-11]。目前研究學(xué)者已經(jīng)提出了很多矩陣乘法的算法并對這些算法進行了優(yōu)化，但這些算法大都基于單機運行。19傳統(tǒng)矩陣乘法的時間復(fù)雜度是O（n3），1969年Strassen利用分治算法，將時

7、間復(fù)雜度降至O（n2.8074），Strassen算法的這一優(yōu)化在現(xiàn)實實踐中得到了廣泛的應(yīng)用[12]。后面雖然仍在改進，但時間復(fù)雜度降低很小。針對這些算法現(xiàn)在已經(jīng)開發(fā)了一些包，比如Jampack[13]和JAMA[14]。這些軟件包沒有采用并行技術(shù)，不能解決我們當(dāng)前面臨的海量數(shù)據(jù)問題。由于矩陣運算在各領(lǐng)域的廣泛應(yīng)用，這一問題能夠得到有效解決將是一件非常有意義的事。因此，有許多學(xué)者將注意力轉(zhuǎn)向矩陣運算的并行處理，經(jīng)過不斷的努力，提出了很多基于多核的高性能單機算法，并開發(fā)出了很多成熟的算法庫，比如PSBLAS[15]。雖然性能上

8、有一定提升，但是這些并行技術(shù)是基于多線程的，它們利用線程之間共享資源的輕量性；而分布式集群中的數(shù)據(jù)共享和通信不是輕量的，多線程并行算法的實現(xiàn)都需要將數(shù)據(jù)讀入到計算機的內(nèi)存當(dāng)中，因此，當(dāng)處理的數(shù)據(jù)量增大時，單機內(nèi)存容量便成為算法處理數(shù)據(jù)的瓶頸。隨著信息爆炸時代的到來，大部分研究學(xué)者逐漸將注意