異構總線網絡中實時可分性負載調度算法

摘要：針對異構總線網絡提出了一種動態實時可分性負載調度方法。首先，根據可分性負載調度最優性原理，分析了網絡中處理器負載分配的最優次序以及參與計算的處理器數目；然后，針對實時任務的截止期限約束提出一種動態負載分配算法，該算法可以利用網絡中最少的處理器數目，保證實時任務在其截止期限之前計算完成。理論分析和仿真測試都驗證了所提出算法的有效性。

關鍵詞：負載分配；異構總線網絡；實時任務；可分性負載理論

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2008)03－0729－03

近年來隨著海量任務計算處理的需要，如大規模信號處理、圖像/視頻處理、科學計算、密碼破譯、組合優化等，使得多處理器系統得到了廣泛應用，而其中對計算負載的有效分配調度方法是研究者一直關注的焦點。傳統的負載分配方法對于多數應用問題的求解都是NPhard，因此只能給出一些基于啟發式規則的近似求解方法。即便如此這些方法仍然只是對一些特殊應用背景和多處理器拓撲結構有效，其問題的求解還是十分復雜[1]。

可分性負載理論為上述問題的求解給出了一種可行的思路。該理論最早由Cheng和Robertazzi提出[2]，其假設處理負載對于多處理器系統是任意可分，通過對系統參數進行合理的線性假設，可以得出最優負載分配的顯性數學表達式。因此，該理論在近年來引起了各國學者的廣泛關注，分別針對bus總線網絡[3]、star(singlelevel tree)星型網絡[4]和tree樹型網絡[5]給出了不同的負載分配最優解形式。文獻[6]還針對多處理器網絡參數未知的情況，通過估計網絡參數來進行最優的負載分配。

可分性負載理論所求解的主要問題是對給定的處理任務和多處理器網絡系統，而網絡中對任務數據的傳輸有一定延遲。那么如何通過在各個處理器之間的最優負載分配，使得處理網絡對給定任務的計算時間最小化。

傳統的可分性負載理論所考慮的計算任務為非實時任務，優化目標是最小化任務處理時間。處理實時任務時，

由于實時任務有截止期限的約束，只要在其截止期之前完成即可。此時的負載調度一方面要考慮到滿足任務實時性的要求；另一方面還要使得所消耗的計算資源最小化。文獻[7]考慮了一種完全同構網絡的實時任務分配方法。在此基礎上本文著重分析異構總線網絡中實時任務的負載分配策略，最終目的是在滿足實時任務截止期限的同時，使得系統消耗的計算資源最少化。

1問題描述

假設如圖1所示的異構總線網絡。其中p0為控制節點，負責將待處理的可分性任務分為若干份，并發送到各個處理節點pi(i=1，2，…，N)進行處理。每個處理節點接收到控制節點發送的任務后立刻開始計算，并將任務處理的最終結果返回給控制節點。控制節點和所有的處理節點通過總線連接。總線網絡的拓撲結構表明：網絡帶寬固定；網絡對各個處理節點共享。這里重點考慮的是控制節點對處理任務的負載分配。假設每個處理節點計算完成后的結果數據量很小，可以忽略將處理結果返回給控制節點的時間延遲。

假設待處理的實時任務模型為task=(L，D)。其中：L={Tcp，Tcm}為任務的負載；D為該實時任務的相對截止期。任務負載參數Tcp表示該任務處理的負載量，定義為單位處理器計算該任務所需要的時間長度；Tcm表示任務傳輸的負載量，定義為單位網絡帶寬傳輸該任務所需要的時間長度。

現在需要解決的問題是如何在1~N處理節點之間分配負載，使得在滿足該實時任務截止期限的約束條件下，參與計算的處理節點數最小化。為此需要解決三個子問題：按照何種次序給參與計算的處理節點分配負載；選擇哪些處理節點參與計算；給這些參與計算的處理節點分配多少負載。這三個問題存在內在的相關性，下面針對這三個問題來求解實時任務的最優負載分配。

2實時任務可分性負載調度

2．1任務處理總時間

首先針對異構總線網絡進行如下參數定義：wi(i=1，2，…，N)為處理節點pi計算單位負載所需要的時間，等效于處理器計算速度的倒數；Z為總線網絡傳輸單位負載所需要的時間，等效于網絡通信速度的倒數；對于任務負載L={Tcp，Tcm}，處理節點pi單獨處理需要時間為wiTcp，總線網絡傳輸全部負載需要時間為ZTcm。假設網絡中控制節點分配其中的n個處理節點來計算任務task=(L，D)，不妨記為pi(i=1，2，…，n)。令αi為控制節點分配給處理節點pi的負載量占總負載的比例（0≤αi≤1，i=1，2，…，N）。定義Ti為處理節點pi處理完成的時間，T為多處理器網絡對整個實時任務處理完畢的總時間，它等于參與計算的各個處理節點中最后一個處理節點的完成時間。整個任務調度的時序如圖2所示。由此可以得出

式(13)表明，對于第n個處理節點，選取其比所有未參與計算的處理節點具有更快的處理速度，將會帶來更小的處理總時間。進一步，根據前n個處理節點的次序對處理總時間無影響的結論可以得出，若所有參與計算的處理節點都比未參與計算的處理節點運算速度快，會使處理總時間最小化；否則，可以通過對前n個處理節點中任意一個與第n個處理節點互換，再將第n個處理節點與未參與計算處理的但比其計算速度更快的節點交換處理，這樣的任務分配調度會帶來更優異的網絡處理性能。

2．3處理節點的最優數目

對于實時任務的處理，必須要滿足其截止期限的約束條件。因此處理節點數目n的選擇原則就是使得任務的處理總時間不大于該實時任務的相對截止期限，即

T≤D(14)

對于異構總線網絡，根據式(5)可得出

(ZTcm+w1Tcp)/(1+n-1i=1ij=1kj， j+1)≤D (15)

式(15)為實時任務調度處理時，處理節點數目需要滿足的條件。對于完全同構網絡這一特殊情況，式(15)可進一步化簡為一個顯性表達式，由w1=w2=…=wn=w得

k1=k2=…=kn-1=wTcp/(ZTcm+wTcp)

(16)

此時的任務處理總時間為

T′=(ZTcm+wTcp)/(1+n-1i=1ij=1k)=(ZTcm+wTcp)(1-k)/(1-kn)=ZTcm/{1-[wTcp/(ZTcm+wTcp)]n} (17)

由實時任務截止期限的約束條件，可得

ZTcm/{1-(wTcp/(ZTcm+wTcp))n}≤D(18)

即

n≥log(1-ZTcm/D)/log(wTcp/(ZTcm+wTcp))(19)

由式（19）即可得出需要參與計算的處理節點數目至少為

n=log(1-ZTcm/D/log(wTcp/ZTcm+wTcp))」+1(20)

其中：x」表示不大于x的最小整數。由此得出參與計算的處理節點數目n。如果n＞N則表明該多處理器網絡無法保證實時任務的有效計算，需要增加網絡的計算能力，如增加新的處理節點、更換更高性能的處理器或提高網絡傳輸速度等。

3負載調度算法的實現

根據前面的分析可以看出，實時任務的調度過程主要有兩個關鍵性步驟：其一是對所有處理節點按照處理速度從大到小排序，后續的調度是按照該次序進行負載分配；其二是確定出參與計算的處理節點數目，再結合前一步的排序，就可以完全確定出哪些處理節點參與任務計算。由此可以得出任務調度算法的實現流程，如圖3所示。

需要指出的是，上述任務分配過程中相當于有一個一維遍歷的過程，但是每一步只需要根據式(15)進行簡單的數學計算。如果需要進一步提高分配算法的速度，則可以采用類似牛頓二分法等更快速的查找方法。

4仿真測試

仿真中針對具有固定負載量的實時可分性任務，測試在不同截止期限下算法對異構總線網絡中處理節點的負載分配效果。假定給定的實時可分性任務task={L，D}。其中：L={Tcp=100，Tcm=20}。異構總線網絡中包含10個處理節點，其參數Z=5，w分別為[1．0，1．2，1．8，2．0，2．2，2．4， 2．5，2．8，3．1，3．5]。

該實時任務的相對截止期限D從101．8逐步增大到200。圖4給出了利用本文算法所確定出參與計算的處理節點數目以及相應的處理總時間。從圖4中可以看出，當實時任務的截止期限較大時，只需要少量的處理節點即可滿足該任務的處理需求。剩余的處理節點可以分配給其他任務進行處理。這樣就可以大大提高系統的處理能力。

針對上述實時任務選取四個特定的截止期限D=[102，105，115，140]，得出本文算法與傳統的利用全部處理節點進行最優負載分配，以及利用全部處理節點進行負載平均分配方法的性能比較，如表1所示。從表1中可以看出，利用全部處理節點同時進行最優的負載分配方法雖然可以得到最短的任務完成時間，但是其并不能隨任務進行自適應調整，整個處理網絡中的所有處理節點總是參與計算處理，這會增加系統計算資源的消耗；而利用全部處理節點進行平均負載分配方法性能較差，雖然利用了所有的處理節點，但是其性能與本文方法利用網絡中的兩個處理節點進行計算的效果相當。

從上述仿真分析可以得出如下結論：可分性負載理論與平均負載分配方法相比可以大大提高系統的處理能力；本文提出的實時任務可分性負載調度方法可以在滿足實時任務有效執行的條件下，顯著降低系統計算資源的消耗。

5結束語

針對實時任務處理，本文研究了異構總線網絡的可分性負載調度問題，給出了最優負載分配方法，包括參與計算的處理節點數目、處理節點的分配次序以及最佳的負載分配份額。然而，針對實時可分性負載的最優化調度問題的研究剛剛起步，推廣到一般的網絡拓撲結構以及考慮任務計算的啟動開銷和傳輸啟動開銷下的最優負載分配，都是值得進一步研究的問題。

參考文獻：

［1］ROBERTAZZI T G.Ten reasons to use divisible load theory[J].IEEE Computer，2003，36(5):63－68.

[2]CHENG Y C，ROBERTAZZI T G.Distributed computation with communication delays[J].IEEE Trans on Aerospace and Electronic Systems，1988，24(6):700712.

[3]SOHN J，ROBERTAZZI T G.Optimal divisible job load sharing for bus networks[J].IEEE Trans on Aerospace and Electronic Systems，1996，32(1):34－40.

[4]BHARADAWJ V，GHOSE D，MANI V.Optimal sequencing and arrangement in distributed singlelevel tree networks with communication delays[J].IEEE Trans on Parallel and Distributed Systems，1994，5(9):968－976.

[5]KIM H J，JEE G I，LEE J G.Optimal load distribution for tree network processors[J].IEEE Trans on Aerospace and Electronic Systems，1996，32(2):607－612.

[6]GHOSE D，KIM H J，KIM T J.Adaptive divisible load scheduling strategies for workstation clusters with unknown network resources[J].IEEE Trans on Parallel and Distributed Systems，2005，16(10):897－907.

[7]LIN X，LU Y，DEOGUN J，et al.Realtime divisible load scheduling for cluster computing，RUNLCSE2006 0016[R].[S.l.]:University of NebraskaLincoln，2006.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”