松耦合多處理機在大數(shù)據(jù)處理中的應(yīng)用

唐俊奇

(湄洲灣職業(yè)技術(shù)學(xué)院信息工程系，福建莆田 351254)

0 引言

隨著社會的不斷發(fā)展，人們需要處理的數(shù)據(jù)量在不斷增大，己由TB級升至PB級，并且還在不斷地增長，在某些情況下甚至還達到了EB級，其增長速度大大超過了摩爾定律的增長速度。由于數(shù)據(jù)量的快速增長，通常所用的并行數(shù)據(jù)庫的規(guī)模也必須隨之增大，所以導(dǎo)致了企業(yè)成本的快速增長。為降低成本，不少企業(yè)用戶已將應(yīng)用由原來高端的服務(wù)器轉(zhuǎn)向了由中低端硬件構(gòu)成的機群平臺［1，2］。這種機群平臺也稱為松耦合多處理機系統(tǒng)，面對所要處理的巨大數(shù)據(jù)量，使用工作池技術(shù)可以使松耦合多處理機系統(tǒng)(尤其是異構(gòu)機群平臺)能及時給系統(tǒng)中處于空閑狀態(tài)的處理器分派工作任務(wù)，這大大地提高了數(shù)據(jù)的處理速度。工作池可分為集中式工作池和分散式工作池兩種。

1 集中式工作池

集中式工作池［3，4］是指:在松耦合多處理機系統(tǒng)中，當有某個處理器(機器)處于空閑狀態(tài)時就立即向其分派工作任務(wù)，工作池中包含所有要完成的任務(wù)集合(任務(wù)池)。

1.1 集中式工作池的工作過程

在松耦合多處理機系統(tǒng)中，一旦某個處理器處于空閑狀態(tài)，主處理器會立即向其分派工作任務(wù)。工作池中擁有所要完成的任務(wù)集(池)，工作池中的每個任務(wù)由主處理器分發(fā)給各個從處理器，每個從處理器完成一個任務(wù)后，它們都會向主處理器請求另一個任務(wù)。工作池技術(shù)雖然可用于那些任務(wù)很不相同、大小不同的問題，但最好優(yōu)先分配較大或最復(fù)雜的任務(wù)。因為如果在計算過程中，較大的任務(wù)分配較晚時，那些己經(jīng)完成小任務(wù)的從處理器就會一直等待持有較大或最復(fù)雜任務(wù)的處理器完成任務(wù)。

在各個處理器執(zhí)行任務(wù)期間，如果出現(xiàn)任務(wù)數(shù)經(jīng)常發(fā)生變化時，工作池技術(shù)就會充分發(fā)揮其優(yōu)越性。在分析和處理大數(shù)據(jù)的搜索算法中，往往在一個任務(wù)的執(zhí)行過程中還可能產(chǎn)生一些新的任務(wù)。在這種情況下，可采用一個隊列存放當前等待的任務(wù)(見圖1)。如果所有任務(wù)大小相同且同等重要，則可以用簡單的先進先出隊列;如果某些任務(wù)比其他任務(wù)更重要(如期望更快地得到解)，就優(yōu)先把這些任務(wù)送到從處理器中，而其他的一些信息，如當前的最佳解等，可以用主處理器加以保存。

集中式工作池最突出的優(yōu)點是:主處理器很容易識別計算會何時終止。對一個計算，如果其中的任務(wù)是從任務(wù)隊列中獲取的，則當滿足下面兩項時計算終止:

1)任務(wù)隊列為空;

2)每個處理器己經(jīng)請求了另一個任務(wù)，而又沒有任何新的任務(wù)產(chǎn)生。

圖1 集中式工作池Fig.1 Centralized work pool

1.2 集中式工作池算法

如圖1所示，在集中式工作池中，主處理器負責(zé)運行主調(diào)度程序，循環(huán)檢測從處理器的當前狀態(tài)，當從處理器空閑時，主調(diào)度程序就按一定的策略給從處理器分配任務(wù)，其算法(pascal語言)的形式化描述如下:

集中式工作池的從處理器負責(zé)接收主處理器發(fā)送的消息并進行相應(yīng)的處理工作，其算法(pascal語言)的形式化描述如下:

1.3 減少通信時間的集中式工作池算法

如果機群平臺(松耦合多處理機系統(tǒng))中各個節(jié)點的存貯器容量足夠大，即可在系統(tǒng)中安排一臺主機，專門備份系統(tǒng)中每個節(jié)點工作池中要完成的所有任務(wù)(任務(wù)本地化)。這樣主處理器向從處理器發(fā)送任務(wù)時只需發(fā)送所要處理的任務(wù)號，可有效減少通信量，因為從處理器i發(fā)送運行子任務(wù)taskid所需的數(shù)據(jù)會產(chǎn)生較大的通信時間開銷。其算法(pascal語言)的形式化描述如下:

集中式工作池的從處理器負責(zé)接收主處理器發(fā)送的消息并進行相應(yīng)的工作，其算法(pascal語言)的形式化描述如下:

1.4 仿真實驗結(jié)果

筆者分別采用1個處理器、5個處理器和6個處理器對一個較大的數(shù)據(jù)進行仿真實驗，得到結(jié)果如表1所示。

表1 仿真運行結(jié)果(不包含通信時間開銷)Tab.1 Simulation run results(not including communication time)

單個處理器串行計算時間T1=1.109 ms。加速度:sp=T1/Tp。效率:Ep=sp/P。其中T1為串行算法在單個處理器上的執(zhí)行時間，TP表示并行算法在P個處理器上的執(zhí)行時間。計算結(jié)果如表2所示。

由表2中的加速度可知，隨著處理器的增多，運行速度得到了較大的提高。

表2 計算結(jié)果Tab.2 Calculation result

在現(xiàn)實中有下面的一種情況:機群平臺(松耦合多處理機系統(tǒng))中的各個節(jié)點的存貯器容量不足于備份工作池中要完成的所有任務(wù)。這種情況下，加速度計算必須考慮通信時間，則加速度就相應(yīng)小一些。如果在計算中有大任務(wù)存在且分配較晚，則系統(tǒng)中就會出現(xiàn)己經(jīng)完成了小任務(wù)的從處理器一直空閑，直到分配到大任務(wù)的處理器完成任務(wù)。從而造成資源浪費，而且集中式工作池較大的缺點是:主處理器一次只能發(fā)送一個任務(wù)，在初始任務(wù)發(fā)送后，它只能一次一個地響應(yīng)新的任務(wù)請求，因此，當很多從處理器同時請求時就存在著潛在的瓶頸［5，6］。采用分布式工作池可以克服該瓶頸，從而提高機群(松耦合多處理機系統(tǒng))的處理效率。

2 分布式工作池

在任務(wù)粒度比較細和從處理器較多的情況下，如果能把工作池分布在多個地點以實現(xiàn)分布式動態(tài)負載平衡［7，8］，會使系統(tǒng)的功能更加強大。如圖2所示，把工作池分布在多個地點稱為分布式工作池。

圖2 分布式工作池Fig.2 Distributed work pool

2.1 分布式工作池的工作過程

在分布式工作池中，主處理器將初始的工作池分成幾部分，并且將每部分發(fā)送給其中的一個小型主處理器“(M0到Mn－1)”。每個小型主處理器控制一組從處理器。在任務(wù)執(zhí)行過程中，小型的主處理器會找到各自的本地最優(yōu)解，然后再將其返回給主處理器，主處理器再從眾多小型的主處理器送來的解中選出最優(yōu)解，從而有效地實現(xiàn)了問題的優(yōu)化［9-11］。由此可見，可通過幾個層次的分解擴展這種方法。把從處理器放在葉結(jié)點上，采取內(nèi)部結(jié)點分割工作的方法，就可形成一棵樹。這種基本方法是將一個任務(wù)分成若干個相等的子任務(wù)。對于一棵二叉樹，可在樹的每層處理器把任務(wù)的一半送給一棵子樹［12，13］，而把另一半送給另一棵子樹。這樣就能有效地克服集中式工作池中較復(fù)雜的任務(wù)在計算中因大任務(wù)分配較晚，造成完成小任務(wù)的從處理器空閑的缺點。

2.2 分布式工作池算法

在分布式工作池中，主處理器負責(zé)運行主調(diào)度程序循環(huán)檢測小主處理器的當前狀態(tài)，當小主處理器空閑時主調(diào)度程序按一定的策略給從處理器分配任務(wù)，小主處理器又負責(zé)循環(huán)檢測從處理器的當前狀態(tài)，當從處理器空閑時，小主處理器也按一定的策略給從處理器分配任務(wù)，其算法(pascal語言)的形式化描述如下:

2.3 通信和數(shù)據(jù)計算間的時間共享算法

由于分布式工作池中存在主處理器、小主處理器和從處理器，雖然事先也可給系統(tǒng)中的各節(jié)點進行備份主工作池中擁有要完成的所有任務(wù)，但在隨后的數(shù)據(jù)通信處理中很難進行合理任務(wù)分配，甚至還有可能發(fā)生沖突。為提高加速度和處理效果，如果在通信過程中數(shù)據(jù)計算也同時進行，則可有效提高系統(tǒng)的處理速度。以下為實現(xiàn)通信和計算之間的時間共享的算法(pascal語言)的形式化描述如下:

2.4 仿真實驗結(jié)果

筆者仍然采用1個處理器、5個處理器和6個處理器對一個較大的數(shù)據(jù)進行仿真實驗，得到結(jié)果如表3所示，它將為表4中的計算提供數(shù)據(jù)。

表3 仿真運行結(jié)果(通信和數(shù)據(jù)計算之間的時間共享)Tab.3 Simulation run results(time used by communication and calculating)

單個處理器串行計算時間T1=1.109 ms。加速度計算:sp=T1/Tp。效率計算:Ep=sp/P。計算結(jié)果如表4所示。

表4 計算結(jié)果Tab.4 Calculation result

對照表4和表2可以看出:在計算中有大任務(wù)存在且分配較晚的情況下，應(yīng)該采用分布工作池方式。若采用集中工作池方式，則系統(tǒng)中己經(jīng)完成了小任務(wù)的從處理器會一直空閑，直到分配到大任務(wù)的處理器完成任務(wù)，造成資源浪費(加速度和效率都下降)，因此，集中式工作池技術(shù)最好用在任務(wù)大小相近和復(fù)雜程度較為均勻的松耦合多處理機系統(tǒng)中。

3 結(jié)語

綜上所述，通過仿真實驗，筆者成功地在松耦合多處理機系統(tǒng)中利用工作池技術(shù)及時給系統(tǒng)中處于空閑狀態(tài)的處理器分派工作任務(wù)，實現(xiàn)了系統(tǒng)中各機器充分均衡協(xié)調(diào)地工作，大大地提高了數(shù)據(jù)的處理效率，達到預(yù)期的效果。

［1］王珊，王會舉，覃雄派.架構(gòu)大數(shù)據(jù):挑戰(zhàn)、現(xiàn)狀與展望［J］.計算機學(xué)報，2011，34(10):1741-1752.WANG Shan，WANG Huiju，QIN Xiongpai.Architecting Big Data:Challenges，Studies and Forecasts［J］.Chinese Journal of Computers，2011，34(10):1741-1752.

［2］孟小峰，慈祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)［J］.計算機研究與發(fā)展，2013，50(1):146-169.MENG Xiaofeng，CI Xiang.Big Data Management:Concepts，Techniques and Challenges［J］.Journal of Computer Research and Development，2013，50(1):146-169.

［3］唐俊奇.多處理機工作池方式負載平衡技術(shù)在機器人的應(yīng)用［J］.計算機系統(tǒng)應(yīng)用，2008，17(11):82-86.TANG Junqi.Work Pool Load Balancing Technology of Multiprocessor in the Application of Robots［J］.Computer Systems ＆Applications，2008，17(11):82-86.

［4］李穎，張曉賢，孫佳慧.基于頻繁模式半結(jié)構(gòu)化數(shù)據(jù)的模式抽取［J］.吉林大學(xué)學(xué)報:信息科學(xué)版，2012，30(5):540-543.LI Ying，ZHANG Xiaoxian，SUN Jiahui.Semi-Structured Data Model Extraction Based on Frequent Patterns［J］.Journal of Jilin University:Information Science Edition，2012，30(5):540-543.

［5］楊柳，劉鐵英.GPU架構(gòu)下的并行計算［J］.吉林大學(xué)學(xué)報:信息科學(xué)版，2012，30(6):629-632.YANG Liu，LIU Tieying.GPU Architecture of Parallel Computing［J］.Journal of Jilin University:Information Science Edition，2012，30(6):629-632.

［6］董延華，李曉佳，張曄.基于MPICH并行計算系統(tǒng)安全通信策略研究［J］.吉林大學(xué)學(xué)報:信息科學(xué)版，2011，29(5):481-483.DONG Yanhua，LI Xiaojia，ZHANG Ye.Research on Security Telecommunication of MPICH Parallel Computing System［J］.Journal of Jilin University:Information Science Edition，2011，29(5):481-483.

［7］劉輝，黃海生.分布式多處理機的并行模擬測試［J］.上海電力學(xué)院學(xué)報，2012，28(5):485-489.LIU Hui，HUANG Haisheng.The Parallel Simulation Test in Distributed Multiprocessors［J］.Journal of Shanghai University of Electric，2012，28(5):485-489.

［8］靖常峰，劉仁義，劉南.大數(shù)據(jù)量遙感圖像處理系統(tǒng)算法模塊的設(shè)計及實現(xiàn)［J］.浙江大學(xué)學(xué)報:理學(xué)版，2005，32(4):471-474.JING Changfeng，LIU Renyi，LIU Nan.Design and Development of Algorithm Module for a Remote Sensing Image Processing System［J］.Journal of Zhejiang University:Sciences Edition，2005，32(4):471-474.

［9］CHRIS ANDERSON J，JAN LEHNARDT，NOAH SLATER.O'Reilly Media［M］.CouchDB:The Definitive Guide，2010.

［10］JOE LENNON.Beginning CouchDB［M］.New York:Springer-Verlag，2009.

［11］BRADLEY HOLT.Writing and Querying MapReduce Views in CouchDB［M］.Beijing:O'Reilly Media，2011.

［12］COUCHDB WIKI.Apache CouchDB ［EB/OL］.(2010-08-18).http://wiki.apache.org/couchdb/.

［13］BRADLEY HOLT.Scaling CouchDB［M］.Beijing:O'Reilly Media，2011.