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

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

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

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

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

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

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

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

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

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