姜海韜 羊帆 陳媛媛 付繼發(fā) 張輝國

摘 要：文章對(duì)R語言已有的并行計(jì)算框架進(jìn)行系統(tǒng)分類、比較，分析了適用于基于R+MPI與基于R+Hadoop的應(yīng)用場景。在此基礎(chǔ)上，結(jié)合兩者優(yōu)勢提出了一種基于R+MPI的優(yōu)化計(jì)算環(huán)境，該環(huán)境可以使用戶僅修改少量代碼就可以將原有的串行程序并行執(zhí)行。最后，通過一個(gè)多元線性回歸模型的代碼實(shí)例展示編程的便捷性，通過與現(xiàn)有工具包的速度比較驗(yàn)證了其有效性。

關(guān)鍵詞：代碼并行化；分布式算法；MPI；Hadoop；多元線性回歸

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-2945（2018）23-0037-04

Abstract： In this paper， the existing parallel computing frameworks in R language are classified and compared， and the application scenarios based on R+MPI and R+Hadoop are analyzed. On this basis， and in view of the advantages of both， an optimized computing environment based on R+MPI is proposed， which enables users to execute the original serial program in parallel only by modifying a small amount of code. Finally， the convenience of programming is demonstrated by a code example of a multivariate linear regression model， and its effectiveness is verified by comparing with the speed of the existing toolkits.

Keywords： code parallelization； distributed algorithm； MPI； Hadoop； multivariate linear regression

引言

由于人們數(shù)據(jù)收集能力的提高以及“數(shù)據(jù)即資產(chǎn)”意識(shí)的發(fā)展，數(shù)據(jù)集的規(guī)模與維度已今非昔比。以使用二維矩陣或者表格儲(chǔ)存的數(shù)據(jù)為例，其屬性數(shù)（列數(shù)）與樣本數(shù)（行數(shù)）都達(dá)到了前所未有的數(shù)量級(jí)，這使得并行編程與分布式存儲(chǔ)與計(jì)算必然地成為了處理大數(shù)據(jù)問題的主流解決方案。

R語言是一款基于GNU協(xié)議的開源軟件，致力于統(tǒng)計(jì)計(jì)算、數(shù)據(jù)可視化以及數(shù)據(jù)分析。該語言擁有龐大的用戶社區(qū)，在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)盛行的今天發(fā)展速度極快。對(duì)于研究較多的數(shù)學(xué)模型，CRAN或GitHub上多有現(xiàn)成的R語言實(shí)現(xiàn)。但與此同時(shí)，R語言也有自身的不足之處：R語言以單線程運(yùn)行，不能發(fā)揮目前多核處理器的全部計(jì)算能力；對(duì)于單臺(tái)計(jì)算機(jī)內(nèi)存無法存儲(chǔ)的數(shù)據(jù)集，R語言無法直接處理。這些問題的解決方案之一是將R語言與其他輔助軟件結(jié)合使用。

Message Passing Interface（MPI）是一個(gè)基于Socket的跨語言通訊協(xié)議，用于編寫高性能的并行程序。調(diào)用MPI的R工具包就可以使多個(gè)R語言進(jìn)程間具有數(shù)據(jù)交換的能力，從而能夠分布式地對(duì)數(shù)據(jù)進(jìn)行高效的計(jì)算處理。

Hadoop是一款開源的商業(yè)數(shù)據(jù)庫，使用Hadoop Distributed File System（HDFS）儲(chǔ)存構(gòu)架，其良好的效率、可拓展性與高可用性吸引了很多工業(yè)界與學(xué)術(shù)界的科研工作者。基于HDFS的MapReduce計(jì)算框架為分布式計(jì)算提供了一種備選方案：R語言的接口包rhdfs，rmr允許R調(diào)用Hadoop進(jìn)行海量的數(shù)據(jù)處理。

由于任務(wù)的差異性，目前并不存在統(tǒng)一的、將串行實(shí)現(xiàn)的代碼并行化的解決方案，因此目前并不存在一個(gè)能高效解決一切并行計(jì)算問題的“完美系統(tǒng)”。但對(duì)于規(guī)模相對(duì)不太大的數(shù)學(xué)模型，在能發(fā)揮R語言現(xiàn)有優(yōu)勢的情況下提供一個(gè)相對(duì)統(tǒng)一的解決方案卻能大大減少任務(wù)并行化的工作量。

本文在探討目前R語言并行計(jì)算框架的基礎(chǔ)上，提出一種基于R+MPI的優(yōu)化并行計(jì)算環(huán)境，并以實(shí)例展示，驗(yàn)證了運(yùn)用該環(huán)境編碼的便捷性和有效性。

1 現(xiàn)有的并行框架分析

目前，能夠?yàn)镽語言提供并行計(jì)算能力的工具箱大體可分為兩類：第一類是以parallel、Rmpi為代表的并行工具包，該類工具箱的實(shí)質(zhì)是打開多個(gè)R終端并搭建終端之間的通訊網(wǎng)絡(luò)；第二類是以rhdfs、rmr為代表的接口包，這類工具箱提供了R語言與其他數(shù)據(jù)庫環(huán)境的接口。

一個(gè)較為理想的環(huán)境需要同時(shí)考慮單節(jié)點(diǎn)的計(jì)算能力、節(jié)點(diǎn)之間的數(shù)據(jù)傳輸能力、平臺(tái)兼容性與代碼的可移植性，其中單節(jié)點(diǎn)的計(jì)算能力受制于R語言自身，平臺(tái)的兼容性受制于使用的具體軟件。因此下文將從數(shù)據(jù)傳輸能力、代碼可移植性兩個(gè)方面討論適宜兩種工具包的應(yīng)用場景。

1.1 有關(guān)數(shù)據(jù)傳輸能力的討論

討論串行任務(wù)的并行化時(shí)，最核心的一個(gè)問題就是并行任務(wù)的粒度大小。所謂粒度，即將任務(wù)并行化時(shí)“切分”的細(xì)度。對(duì)于同一個(gè)數(shù)學(xué)模型，一般粗粒度的并行化方法會(huì)對(duì)單節(jié)點(diǎn)的計(jì)算能力有較高的要求，而細(xì)粒度的方法卻要求結(jié)點(diǎn)之間有較強(qiáng)的數(shù)據(jù)傳輸能力。

并行工具包的運(yùn)行模式可以歸結(jié)為：主節(jié)點(diǎn)向各子節(jié)點(diǎn)分發(fā)數(shù)據(jù)與需要運(yùn)行的程序，子節(jié)點(diǎn)計(jì)算后返回結(jié)果，經(jīng)過主節(jié)點(diǎn)整合后得到最終結(jié)果[1]。為了達(dá)到負(fù)載均衡的目的，一些并行函數(shù)采用了所有數(shù)據(jù)傳輸均通過主節(jié)點(diǎn)的解決方案（如“parallel：：parApply”），易造成主節(jié)點(diǎn)通訊管道的堵塞。這類函數(shù)更適于粗粒度的、計(jì)算量大而傳輸量較小的任務(wù)（比如迭代任務(wù)）。對(duì)于中間數(shù)據(jù)傳輸要求較高的任務(wù)，這類函數(shù)在數(shù)據(jù)傳輸過程中會(huì)消耗較多時(shí)間，從而影響了運(yùn)行效率。

而大多數(shù)接口包的本質(zhì)是借用商業(yè)數(shù)據(jù)庫的強(qiáng)勁數(shù)據(jù)處理能力，使R語言能處理遠(yuǎn)大于單機(jī)內(nèi)存容量規(guī)模的數(shù)據(jù)。目前對(duì)于Hadoop平臺(tái)上的任務(wù)并行化已經(jīng)有較多的研究，如[2-3]，通過R語言接口包rhdfs操作hdfs就可以使用R平臺(tái)進(jìn)行數(shù)學(xué)模型的計(jì)算。但商業(yè)數(shù)據(jù)庫多基于高訪問、低更改的業(yè)務(wù)特性進(jìn)行優(yōu)化，因此這些接口包更擅長于對(duì)海量數(shù)據(jù)進(jìn)行求和、篩選等具有數(shù)據(jù)庫特點(diǎn)的細(xì)粒度操作，卻不適合每次都需要將特定數(shù)據(jù)進(jìn)行更改的迭代任務(wù)。以分布式矩陣乘法為例，Hadoop將原數(shù)據(jù)切分為大小一定大?。J(rèn)為128Mb）的塊，以多備份的方式存入HDFS。由于在計(jì)算（Reduce）過程中需要整合矩陣中特定的（aij，bjk）進(jìn)行計(jì)算，沒有針對(duì)矩陣計(jì)算的特點(diǎn)進(jìn)行儲(chǔ)存優(yōu)化的自動(dòng)分配地址會(huì)使shuffle數(shù)據(jù)處理過程需要較長的時(shí)間[5]，這使其計(jì)算速度遠(yuǎn)遠(yuǎn)不及理論上的并行粒度。

1.2 有關(guān)代碼可移植性的討論

R語言擁有龐大的用戶社區(qū)與開源的可用程序包。同時(shí)，R語言又是一種向量化的語言，基本操作為向量/矩陣之間的計(jì)算。因此若能做到向量/矩陣計(jì)算的并行化，就能盡可能地利用R語言的現(xiàn)有代碼，縮短軟件的開發(fā)周期。

以Parallel為代表的并行工具包已經(jīng)實(shí)現(xiàn)了向量計(jì)算的并行化，在不考慮運(yùn)行效率的情況下，這些包僅通過少量的代碼更改即可實(shí)現(xiàn)并行版本的向量計(jì)算[4]。但目前并沒有廣泛使用的、用于矩陣并行化計(jì)算的軟件包。若使用Parallel包中的現(xiàn)有函數(shù)，不但要在每次計(jì)算前將矩陣切分為列表（list）儲(chǔ)存，還必須面對(duì)數(shù)據(jù)傳輸速度的瓶頸。

文獻(xiàn)[5-7]探討了Hadoop平臺(tái)上的矩陣操作問題，使用R語言的接口包調(diào)用Hadoop進(jìn)行矩陣計(jì)算，并讀取計(jì)算結(jié)果至R中就可以使R語言擁有分布式矩陣計(jì)算的能力。但基于此方案的所有代碼需要修改為數(shù)據(jù)庫語言，這會(huì)使代碼的可移植性變?nèi)?，難以發(fā)揮R語言所擁有的龐大用戶社區(qū)、海量開源腳本的優(yōu)勢。

1.3 適宜場景小結(jié)

使用R語言進(jìn)行分布式并行處理的兩種方法的優(yōu)缺點(diǎn)淺析見表1，可以發(fā)現(xiàn)兩種方式各有其優(yōu)缺點(diǎn)。并行包有較強(qiáng)的代碼可移植性，從而能發(fā)揮R大量現(xiàn)有工具包的優(yōu)勢，但數(shù)據(jù)傳輸能力有待提高；接口包的數(shù)據(jù)傳輸能力相對(duì)較強(qiáng)，能夠突破內(nèi)存容量的限制，但數(shù)據(jù)庫語言的使用使其代碼可移植性降低。

2 并行框架設(shè)計(jì)

本文搭建的并行環(huán)境基于R語言與MPI，由于使用的工具都具有跨平臺(tái)的優(yōu)良特性，該環(huán)境在Windows與linux操作系統(tǒng)上均可使用，具有很好的操作系統(tǒng)兼容性?？紤]到Windows系統(tǒng)是目前被廣大高校所使用的，也是開發(fā)者保有量最多的環(huán)境，且R語言在該系統(tǒng)下可用的分布式環(huán)境一直較少，因此后文均在Windows系統(tǒng)上討論并行環(huán)境的搭建與應(yīng)用。

2.1 基本框架

本環(huán)境中的并行計(jì)算運(yùn)行流程可以用圖1表示。首先將計(jì)算環(huán)境初始化，然后將計(jì)算所需的矩陣存入環(huán)境中。至此就可以對(duì)已存入系統(tǒng)的矩陣進(jìn)行并行迭代計(jì)算，而且每一步的計(jì)算結(jié)果仍然以相同的格式儲(chǔ)存在系統(tǒng)中，這樣可以做到靈活地調(diào)用、輸出計(jì)算過程中任意一步的結(jié)果。體現(xiàn)了本環(huán)境在使用過程中的友好性。

對(duì)于主從節(jié)點(diǎn)拓?fù)渚W(wǎng)絡(luò)的設(shè)置，選擇二維的矩形排布，其中節(jié)點(diǎn)標(biāo)號(hào)以行優(yōu)先。特別地，為了增加本系統(tǒng)的通用性，對(duì)于存入環(huán)境的矩陣均按塊狀劃分，所有矩陣行與列的切割策略相同。這是由于塊狀劃分的分布式矩陣計(jì)算方法具有較高的執(zhí)行效率[8]，同時(shí)可以保證存入的矩陣無論作為矩陣乘法的被乘矩陣或者乘子矩陣都可以直接進(jìn)行矩陣計(jì)算，而且計(jì)算結(jié)果還可以繼續(xù)迭代直接參與計(jì)算。避免了每一步計(jì)算之前都對(duì)矩陣進(jìn)行切分并重復(fù)發(fā)送的繁瑣操作，為需要迭代或操作較為復(fù)雜的任務(wù)提供了較多的便利。

2.2 函數(shù)設(shè)計(jì)

本工具箱中的函數(shù)分為兩類：第一類是基本函數(shù)，用于環(huán)境的啟動(dòng)、將數(shù)據(jù)存入/取出并行環(huán)境與資源的回收。第二類是附加函數(shù)，用于對(duì)存入本環(huán)境中的數(shù)據(jù)進(jìn)行操作，可以根據(jù)具體需要靈活增刪。以第三節(jié)要實(shí)現(xiàn)的多元線性回歸為例：需要加入矩陣預(yù)分配函數(shù)、數(shù)據(jù)傳輸函數(shù)、數(shù)據(jù)計(jì)算函數(shù)并包裝成統(tǒng)一的并行矩陣乘模板。

基本函數(shù)：

（1）初始化函數(shù)Mpinit（nrow，ncol）用于mpi環(huán)境的初始化、二維網(wǎng)格的設(shè)置。用戶可以自由設(shè)置二維網(wǎng)格的行列結(jié)點(diǎn)數(shù)量，一共開啟nrow*ncol個(gè)mpi進(jìn)程。初始化完成后會(huì)返回“done”。

（2）發(fā)送函數(shù)SendtoSlave（Data，Name），用于將變量分發(fā)給各個(gè)子節(jié)點(diǎn)、存入并行環(huán)境。若Data為矩陣，則Name為一個(gè)字符串代表儲(chǔ)存進(jìn)入環(huán)境中的變量名；若Data為一個(gè)列表，則Name也是一個(gè)長度相同的列表代表每個(gè)變量的名字。運(yùn)行完畢后會(huì)返回成功存入環(huán)境中的矩陣數(shù)量。

（3）回收函數(shù)GetfromSlave（Name），用于從各個(gè)子節(jié)點(diǎn)回收特定變量名的數(shù)據(jù)，并以矩陣類型返回。

（4）退出函數(shù)mpiexit（），用于釋放空間，退出mpi環(huán)境。

附加函數(shù)（例）：

（1）函數(shù)getGrid（Rank，nrow，ncol），在輸入子節(jié)點(diǎn)編號(hào)與網(wǎng)格配置后返回當(dāng)前結(jié)點(diǎn)的二維坐標(biāo)。（2）函數(shù)getPos（Pos，nrow，ncol），在輸入子節(jié)點(diǎn)二維坐標(biāo)與網(wǎng)格配置后返回當(dāng)前結(jié)點(diǎn)的編號(hào)。

（3）函數(shù)DDD（Name1，Name2，Name3），用于分布式計(jì)算已經(jīng)存在于環(huán)境中的名為Name1與Name2的矩陣的乘積，結(jié)果以名字Name3存入環(huán)境。返回值為當(dāng)次計(jì)算所消耗的時(shí)間。

3 數(shù)值實(shí)驗(yàn)

3.1 多元線性回歸

回歸分析作為統(tǒng)計(jì)學(xué)的一個(gè)重要研究方向，在生物、醫(yī)學(xué)、農(nóng)業(yè)、林業(yè)、金融等領(lǐng)域都有廣泛應(yīng)用。而多元回歸分析是最為基本的一種回歸模型，利用所得到的回歸方程，可以評(píng)價(jià)單個(gè)預(yù)測變量的重要性，也可以預(yù)測一組給定的已知變量所對(duì)應(yīng)的目標(biāo)值[9]。伴隨大數(shù)據(jù)時(shí)代所帶來的樣本在激增、數(shù)據(jù)量巨大等問題，使得多元回歸分析的應(yīng)用受到了制約。因此，在并行優(yōu)化環(huán)境中實(shí)現(xiàn)回歸分析無論是在理論上還是在應(yīng)用上都有重要的意義。

假設(shè)y是可觀測的隨機(jī)變量，共有p個(gè)影響因素，分別為x1，x2，…，xp。對(duì)于n組獨(dú)立觀測樣本：（yi；xi1，xi2，…，xip），i=1，2，…n可以建立如下p元線性回歸模型：

在樣本量n與屬性數(shù)p較大的時(shí)候，如何計(jì)算XT X與XT Y是需要考慮的主要問題。這里在實(shí)現(xiàn)了分布式矩陣乘（DDD算法[10]）的前提下，給出本環(huán)境中實(shí)現(xiàn)多元線性回歸的R語言關(guān)鍵代碼（見代碼1）。

代碼1顯示了在本環(huán)境中實(shí)現(xiàn)數(shù)學(xué)模型的便捷性——只需要將大矩陣存入環(huán)境，并用環(huán)境自帶的矩陣計(jì)算函數(shù)進(jìn)行計(jì)算，最后從環(huán)境中取出計(jì)算結(jié)果即可。取定n=10000，p=30，運(yùn)行該代碼后觀察圖2可以發(fā)現(xiàn)回歸系數(shù)的估計(jì)值基本以微小的誤差均勻分布在真值的兩側(cè)，可以認(rèn)為是噪聲ε的影響，回歸模型的輸出結(jié)果是正確的。

3.2 矩陣乘法速度比較

本節(jié)通過比較R語言現(xiàn)有的Parallel工具包與本環(huán)境中實(shí)現(xiàn)的分布式矩陣乘法（DDD算法）來驗(yàn)證本環(huán)境的高