基于R的并行優(yōu)化環(huán)境設計

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

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

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

中圖分類號：TP312 文獻標志碼：A 文章編號：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)”意識的發(fā)展，數(shù)據(jù)集的規(guī)模與維度已今非昔比。以使用二維矩陣或者表格儲存的數(shù)據(jù)為例，其屬性數(shù)（列數(shù)）與樣本數(shù)（行數(shù)）都達到了前所未有的數(shù)量級，這使得并行編程與分布式存儲與計算必然地成為了處理大數(shù)據(jù)問題的主流解決方案。

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

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

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

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

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

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

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

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

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

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

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

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

1.2 有關代碼可移植性的討論

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

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

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

1.3 適宜場景小結

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

2 并行框架設計

本文搭建的并行環(huán)境基于R語言與MPI，由于使用的工具都具有跨平臺的優(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)境的搭建與應用。

2.1 基本框架

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

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

2.2 函數(shù)設計

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

基本函數(shù)：

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

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

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

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

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

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

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

3 數(shù)值實驗

3.1 多元線性回歸

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

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

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

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

3.2 矩陣乘法速度比較

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