面向服務網格的自調度算法優化技術

（蘇州大學 計算機科學與技術學院， 江蘇 蘇州 215006）

摘 要：將自調度引入到面向語言文字信息處理的服務網格中，并結合語言文字信息處理和自調度的特點，提出了一種服務網格環境下的自調度算法優化方案。該方案從數據的傳輸、子節點的處理方式這兩個方面入手，用socket傳輸數據及子節點采用生產者—消費者模式來優化經典的自調度算法。實驗證明，該方案能比原有的自調度算法在總響應時間上平均縮短5％以上。

關鍵詞：自調度；服務網格；套接字；生產者—消費者模式

中圖分類號：TP393 文獻標志碼：A

文章編號：10013695(2009)02045703



Optimization of selfscheduling algorithm for service grid



JI Qin，LI Peifeng，ZHU Qiaoming，XU Lan



(School of Computer Science Technology， Soochow University， Suzhou Jiangsu 215006， China)

Abstract:This paper introduced the selfscheduling into the service grid which oriented to language processing and proposed a method to optimize existed selfscheduling algorithms.Considering the characters of Chinese information processing grid and selfscheduling， it expounded to use socket to transfer the data and use the producerconsumer model to optimize selfscheduling algorithms. Experiment results show that the method can reduce the response time efficiently.

Key words:selfscheduling;service grid;socket;producerconsumer model

網格計算是分布式計算的一個重要方向。前期，筆者開發了一個面向語言文字信息處理的服務網格——ZHHZGrid[1~3]，該網格專門為各類用戶提供語言文字信息處理的基礎服務，如分詞服務、詞性標注服務和實體識別服務等。ZHHZGrid除了具有一般服務網格的動態性、不確定性、面向服務等特征外，還帶有語言文字信息處理的特殊性，即以數據處理為主，并且其數據量大、執行時間長。該網格的一個基本任務就是根據各個節點的資源狀態，將任務以合理的方式分配到相應的節點去完成，使它們的負載達到平衡，并使總的執行時間能趨近最小，從而提高任務的響應時間。

1 相關研究

自調度是一種在應用層的調度技術，它是指一個任務可以分解成多個子任務，然后每個任務分布到各個節點并行執行，從而提高響應時間的技術。在自調度中，各個執行服務的子節點根據自己的資源狀況主動地向主節點索取任務，而不是被動地等待主節點分配任務。自調度使用主—從結構的模型，如圖1所示。在圖1中，空閑的子節點可以發送請求給主節點請求新的任務，各子節點間互不通信。其中，主節點每次分配多少工作量給子節點是問題的關鍵，如果在不適當的時間分配大量的任務給子節點會導致負載的不平衡，而分配很多小量的任務又會導致調度次數的增多。

在一般的自調度模式中，第i步調度時，主節點計算塊大小Ci和剩余的工作Ri：

R0=I，Ci=f(Ri-1，p)，Ri=Ri-1-Ci（1）

其中：I表示總的工作量；f()表示計算塊大小的函數，輸入可以有多個而不僅僅是Ri-1，p兩個[4]。

不同的計算Ci的方式決定了不同的自調度算法，下面將介紹一些著名的自調度算法。

a）Chunk selfscheduling(CSS)[5]。Ci=k，k≥1并且固定大小，在執行過程中不會改變，一般事先指定。該算法主要的缺點是算法的有效性取決于k值的設定，當k值太大時就會導致負載的不平衡，太小又會導致過多次的數據傳輸和調度。

b)Guided selfscheduling(GSS)[5，6]。Ci=「Ri-1/p。GSS這種塊的大小越來越小的特性可以取得負載平衡和減少調度次數；而且，在并行循環執行開始時分配比較大的塊可以減少主節點與子節點之間的信息交流。該算法主要的缺點是在最后的步驟中分配了很多比較小的塊。



c)Factoring selfscheduling(FSS)[5，7，8]。Ci=「Ri-1/（α p)，參數α由計算得出，或者通常選α=2。FSS算法提出了分階段分配的思想，在每一階段每個處理器所分配的任務量相等。該算法主要的缺點是很難確定最優的α值。

d)Trapezoid selfscheduling(TSS)[5，8，9]。Ci=Ci-1-D，D=(F-L)/(N-1)」，這里第一塊大小F和最后一塊大小L可以由用戶輸入或者F=I/2p」L=1。該算法主要的缺點是依然會發生很多的同步需求。

2 自調度算法的優化

2.1 自調度算法在ZHHZGrid中的應用

ZHHZGrid是一個專門為語言文字信息處理提供了計算和服務的網格平臺，各個基礎服務常用的算法一般采用統計或機器學習的方法。所以，每個服務均存在具有處理數據量大、執行時間較長的特點。為此本文將自調度引入到ZHHZGrid中，通過將大數據量的任務分解成若干小任務再分配給網格節點并行執行，從而大大縮短任務的執行時間。其實現過程如圖2所示。

首先，根據文本的大小和所使用的自調度算法進行切分。例如：如果要處理的文本大小是1 GB，就可以將它看成是具有1 GB次獨立迭代的計算，根據特定的自調度算法對這些迭代以某個基本的單位進行切分，再根據切分的起點和終點讀出相應的文本內容：其次，主節點將切分好的文本傳輸給子節點，由子節點負責完成相應的處理并將結果返回給主節點以請求主節點分配新的任務；最后，子節點處理完所有文本后，主節點根據文本的原始順序整理好最終結果并返回給用戶。由于語言文字信息處理網格的特殊性，原有的自調度算法還存在如下的問題：

a)不同于矩陣相乘那種計算量大、數據傳輸量小的應用，語言文字信息處理傳輸的數據量較大，所以還應要考慮如何縮短傳輸時間。

b)以上算法在子節點返回一次結果給主節點到等待新任務到達的這段時間子節點處于空閑狀態，如果充分利用這段空閑將會縮短整個任務的執行時間。

在將自調度引入到ZHHZGrid中后，還需根據語言文字信息處理網格的特點對自調度模式進行優化，以提高執行的性能。

2.2 改進的自調度模式

針對傳統的自調度模式存在的問題，本文從兩方面入手：一方面通過在調度節點上使用socket發送TCP數據包，以及采用多線程方式，減少數據傳輸的時間；另一方面采用生產者—消費者模式，減少子節點的空閑時間，從而縮短任務的總響應時間。

2.2.1 數據的傳輸

為了縮短數據的傳輸時間，在主節點與子節點間不再直接使用字符串來傳輸數據，而是通過發送TCP數據包來傳輸，這樣就可以縮短數據的傳輸時間。主節點與子節點間數據傳輸方式如圖3所示。

如圖3所示，主節點與子節點間的數據傳輸步驟如下：

a)主節點上的主線程啟動后，先創建一個serverSocket，用accept()方法在指定的端口進行監聽，等待子節點的連接請求。

b)主線程一旦接收到子節點的連接請求，就創建一個新的線程來處理與該子節點的連接，而主線程則繼續負責接收下一個子節點的連接。

c)子節點與主節點的連接建立好后，等待主節點分配任務。如果通信沒有結束，則接收主節點發送來的數據，對其進行處理后將結果返回給主節點，等待下次數據的到來。

d)如果子節點收到通信結束的信息，則關閉此次socket連接并等待下次連接的建立。

TCP傳輸存在數據包斷、粘的問題。斷包主要是指如果一個TCP包太大，接收端可能會分兩次接收，這樣針對每次接收的數據都要調用一次服務，可能一次完成的任務卻要分兩次，從而造成浪費時間。粘包主要是指如果傳輸的TCP包太小，則接收端會將兩個包當成一個包來接收。為了解決斷、粘包的問題，根據TCP包的構成原理，即在每個TCP包頭上有一個包長度的數據域，這樣接收端就知道所要接收數據的長度，從而不會出現斷、粘包的問題。因此，在每個傳輸的數據包的開始處加上包的長度，當接收端接收到數據包時，首先讀出包的長度，再根據包的長度讀取相應長度的數據，只有數據讀滿后才算接收完成，否則程序就阻塞直至數據讀滿，這樣就解決了斷、粘包的問題。

2.2.2 生產者—消費者模式

在傳統的調度模式中，子節點接收數據、處理、返回結果、等待新任務的到來，這種模式會存在子節點有大量空閑等待時間的情況造成處理能力的降低以及執行時間的延長。因此，本文根據生產者—消費者模式利用多線程機制，即在子節點上同時運行兩個線程，一個線程專門用于接收、發送數據，另一個則負責數據的處理。執行過程的順序如圖4所示。

如圖4所示，主節點與子節點的連接建立好后，主節點將要處理的數據發送給子節點。為了傳輸數據和處理數據達到并行，并使數據處理線程能盡可能忙碌，為數據設置了兩個緩沖區。從圖4中可以看出，主節點先發送兩個數據包給子節點，而子節點的處理線程一旦檢測到緩沖區中有數據則取出進行處理。與此同時，數據傳輸線程可以并發地接收數據。由于接收數據所花的時間遠遠小于處理數據的時間，在圖4中可以看出如果緩沖區里都有數據時數據傳輸線程則進入阻塞狀態，直到數據處理線程處理完畢時喚醒該線程返回結果并接收下次數據。

在這種模式下，子節點的數據處理線程從程序啟動就開始運行，一直到所有的數據處理完畢才終止，也就是數據處理線程一直不停地處理數據而沒有任何空閑，提高了子節點CPU的利用率，減少了子節點的空閑時間，從而縮短整個任務的執行時間。

3 實驗和結果

本文的實驗是在ZHHZGrid平臺上進行的，網格的節點上已布置了一些常用的語言文字信息處理服務，如分詞、命名實體識別、詞性標注等。為了測試的方便，以分詞服務作為測試的樣例。

測試流程如下：用戶首先通過portal選擇需要使用的自調度算法來運行提交的任務；然后用戶提交需要分詞的文本，主節點根據選擇的自調度算法對用戶提交的文本進行切分并將切分好的文本發到各個子節點；最后，由子節點調用相應的分詞服務完成對數據的處理。由于分詞服務在執行分詞之前需先加載一個詞庫，子節點接收到數據后先加載詞庫然后才對數據進行分析。如果分的塊較多，則加載詞庫的時間就會比較長，從而影響整個文本的執行時間。

測試環境是由五臺計算機組成。其中一臺作為主節點，剩余四臺為子節點。主節點的配置為Pentium(R)D CPU 2.8 GHz，內存512 MB；子節點的配置為Pentium (R)4 CPU 3.00 GHz，內存512 MB。

采用的實驗參數定義如下：

a）總時間（響應時間）。主節點開始切分數據到所有數據處理完畢的時間。

b)切分時間。主節點對用戶提交的文本進行切分的時間。

c）傳輸時間。主節點將切分好的文本傳輸給子節點以及子節點把處理完的數據返回給主節點的時間。

d）執行時間。所有子節點執行時間的總和，即每次數據到達子節點到子節點處理完返回給主節點之前的時間之和。

e)加載時間。所有子節點上加載詞庫的時間之和。

f）空閑時間。所有子節點的空閑時間總和，即子節點處理完本次任務返回結果給主節點等待主節點分配的下次任務到達的這段時間之和。

3.1 傳統的自調度模式

在傳統模式（采用本文的方式）下使用CSS、GSS、TSS、FSS算法所得的數據如表1所示。其中，FSS算法里的α=2，TSS算法中最后塊大小L=1 024，CSS40K表示每塊大小為40 KB。

表1 傳統模式下的執行時間

算法時間/ms

傳輸時間切分時間執行時間加載時間空閑時間總時間

表1的數據無法比較不同算法之間的優劣。因為每種算法所分的塊不同，分塊少則加載詞庫的時間小，總時間相應的就短。

從表1可以發現：

a）傳輸給子節點的文本是通過服務的參數傳遞，傳輸時間與傳輸次數及每次傳輸文本大小有關。傳輸次數太多或者每塊太大均會造成傳輸時間變長，從而致使總的傳輸時間加長。例如，GSS算法在開始分配的塊比較大，而最后又分配了很多比較小的塊，因此傳輸時間比較長。而TSS算法傳輸的塊數目不多，并且每塊大小不像GSS那樣過大或過小，因此它的傳輸時間相對來說比較短。

b)如果切分的塊太多則需多次定位文件讀寫指針，導致總的切分時間變長，實驗中TSS算法切分的塊數目最少，因此切分時間最短。

c)由于每塊到達子節點都要調用分詞服務，而執行分詞服務時要先加載詞庫。隨著塊的增多，調用服務的次數增多，導致執行時間以及加載時間都會變大。

d)如果傳輸的文本比較大，則所需時間比較長。這時子節點等待新數據到來的等待時間變長，而這段時間子節點處于空閑狀態，因此空閑時間會加長，如GSS算法。

3.2 改進的自調度算法

改進后的算法OCSS、OGSS、OTSS和OFSS(分別對應于CSS、GSS、TSS和FSS)所得的數據如表2所示。

表2 改進模式下的執行時間

算法時間/ms

注：表2中各算法所使用的參數同表1。

對比表1和2中的數據，可以發現：

a)使用TCP包來傳輸數據后，消除了子節點的空閑時間，無論使用四種算法中的哪一種傳輸時間都大大減少，傳輸效率提高了12.7%～22.5%不等。

b)由于采用多線程對文本進行操作，涉及到同步及各線程搶占CPU的情況，切分時間比在傳統模式下的切分時間要長。

c)執行時間及加載時間在使用相同算法時相差無幾。

d)總時間相差較大，效率提高了5%～8%不等，如圖5所示。

可見，通過改進，四種自調度算法在傳輸時間和總時間上都比以前的方式有了較為明顯的縮短，其整體性能得到了較大的提高。

4 結束語

本文將自調度技術引入到面向語言文字信息處理的服務網格中，并根據語言文字信息的特殊需求，對傳統的自調度算法在數據的傳輸以及子節點的執行方式上進行了優化。實驗證明，改進的自調度算法在性能上有較大的提高。而且，該改進的方法同樣可以應用到其他的具有大規模數據處理需求的服務網格中。在下一步工作中，筆者主要將研究如何縮短加載詞庫的時間及根據子節點的負載來動態分配任務。

參考文獻：

［1］

李培峰，朱巧明，支麗艷. 面向信息服務的網格資源管理器的設計[J].計算機工程，2008，34(3):4951，58.

[2]支麗艷，朱巧明，李培峰.一個應用于中文信息處理的網格系統的設計[J].計算機應用與軟件，2007，24(11):7375.

[3]ZHU Qiaoming，LI Peifeng，GONG Zhengxian，et al.ADJSA:an adaptable dynamic job scheduling approach based on historical information[C]//Proc of the 2nd International Conference on Scalable Information Systems (InfoScale 2007).Suzhou:[s.n.]，2007.

[4]TANG P，YEW P C.Processor selfscheduling for multiplenested parallel loops[C]//Proc of International Conference on Parallel Proces-sing.1986.

[5]CHRONOPOVLOSA T，BENCHE M，GROSU D.A class of loop selfscheduling for heterogeneous clusters[C]//Proc ofIEEE International Conference on Cluster Computing (CLUSTER’01).2002.

[6]POLYCHRONOPOULOS C D，KUCK D.Guided selfscheduling:a practical scheduling scheme for parallel supercomputers[J].IEEE Trans on Computers，1987，36:14251439.

[7]HUMMEL S F，SCHONBERG E，FLYNN L E.Factoring:a method for scheduling parallel loops[J].Communications of the ACM，1992，35(8):90101.

[8]CHRONOPOULOS A T，PENMATSA S，YU Ning.Scalable loop selfscheduling schemes for heterogeneous clusters[C]//Proc of IEEE International Conference on Cluster Computing ( CLUSTER’02).2002.

[9]TZEN T H，NI L M.Trapezoid selfscheduling:a practical scheduling scheme for parallel compilers[J].IEEE Trans on Parallel and Distributed System，1993，4(1):8798.