唐俊奇

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

0 引言

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

1 集中式工作池

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

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

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

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

集中式工作池最突出的優(yōu)點(diǎn)是:主處理器很容易識(shí)別計(jì)算會(huì)何時(shí)終止。對(duì)一個(gè)計(jì)算，如果其中的任務(wù)是從任務(wù)隊(duì)列中獲取的，則當(dāng)滿足下面兩項(xiàng)時(shí)計(jì)算終止:

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

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

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

1.2 集中式工作池算法

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

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

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

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

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

1.4 仿真實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

2 分布式工作池

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

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

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

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

2.2 分布式工作池算法

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

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

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

2.4 仿真實(shí)驗(yàn)結(jié)果

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

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

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

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

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

3 結(jié)語

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

［1］王珊，王會(huì)舉，覃雄派.架構(gòu)大數(shù)據(jù):挑戰(zhàn)、現(xiàn)狀與展望［J］.計(jì)算機(jī)學(xué)報(bào)，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］.計(jì)算機(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］唐俊奇.多處理機(jī)工作池方式負(fù)載平衡技術(shù)在機(jī)器人的應(yīng)用［J］.計(jì)算機(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ù)的模式抽?。跩］.吉林大學(xué)學(xué)報(bào):信息科學(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ì)算［J］.吉林大學(xué)學(xué)報(bào):信息科學(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并行計(jì)算系統(tǒng)安全通信策略研究［J］.吉林大學(xué)學(xué)報(bào):信息科學(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ī)的并行模擬測試［J］.上海電力學(xué)院學(xué)報(bào)，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è)計(jì)及實(shí)現(xiàn)［J］.浙江大學(xué)學(xué)報(bào):理學(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.