分布式存儲結(jié)構(gòu)下時延動態(tài)負(fù)載平衡系統(tǒng)的穩(wěn)定性分析.pdf

1、負(fù)載平衡是并行計算中的一個重點研究領(lǐng)域，節(jié)點間負(fù)載的不平衡會嚴(yán)重影響并行計算的效率。負(fù)載平衡算法按照調(diào)度時可用資源信息和任務(wù)運行狀態(tài)的即時性可劃分為靜態(tài)和動態(tài)兩種，其中動態(tài)負(fù)載平衡算法由于其靈活性和處理非規(guī)則問題時所具有的優(yōu)勢逐漸成為研究的熱點。時延現(xiàn)象在并行計算環(huán)境中是普遍存在的，尤其在分布式存儲結(jié)構(gòu)情況下，在動態(tài)負(fù)載平衡的過程中，并行系統(tǒng)為了保持信息的準(zhǔn)確性及實現(xiàn)過量負(fù)載的遷移不可避免地要進(jìn)行大量的通信和傳輸，在這類過程中均會產(chǎn)生不

2、同程度的時延。時延給準(zhǔn)確地收集和管理負(fù)載信息帶來了困難，很容易引起動態(tài)負(fù)載平衡算法的一些不穩(wěn)定的振蕩現(xiàn)象，從而嚴(yán)重地影響并行計算的效率。因此，如何有效地分析及減少時延所帶來的影響成為動態(tài)負(fù)載平衡中亟待解決的重要問題之一。針對此情況，本文采用了控制論中的線性時延系統(tǒng)理論對分布式存儲結(jié)構(gòu)下的時延動態(tài)負(fù)載平衡(DDLB: Delay Dynamic Load balancing)系統(tǒng)進(jìn)行建模和穩(wěn)定性分析，并以此為依據(jù)，通過使用適當(dāng)?shù)姆答佋鲆鎭?/p>

3、減少時延所帶來的影響。
　　首先，針對并行環(huán)境下的DDLB系統(tǒng)，本文在前人工作的基礎(chǔ)上，提出了一個更貼近實際的頻域模型，并在其基礎(chǔ)上給出了一個與之等價的異構(gòu)時域模型。兩類模型充分地考慮了實際并行環(huán)境下任務(wù)的不可劃分性和負(fù)載隊列的非負(fù)性，描述了現(xiàn)實環(huán)境中影響DDLB系統(tǒng)穩(wěn)定性的外界干擾因素。同時，負(fù)載平衡閾值的引入增加了模型的靈活性，使其能夠在負(fù)載平衡質(zhì)量與負(fù)載平衡速度之間做出一個符合實際要求的折中。最后，根據(jù)控制論中的穩(wěn)定性理論，

4、本文提出了一些符合實際環(huán)境的假設(shè)和定義，并在其基礎(chǔ)上將所提出的時域模型轉(zhuǎn)換為便于時域分析的標(biāo)準(zhǔn)形式，為后續(xù)的理論分析工作奠定基礎(chǔ)。
　　其次，針對所提出的頻域模型，本文提出了DDLB系統(tǒng)穩(wěn)定性的充分必要條件。采用了頻域分析方法對DDLB系統(tǒng)的同構(gòu)模型進(jìn)行穩(wěn)定性分析，通過laplace變換及一系列矩陣變換推導(dǎo)出系統(tǒng)的傳遞函數(shù)矩陣，并根據(jù)Routh-Hurwitz判據(jù)，通過分析時DDLB系統(tǒng)的閉環(huán)極點得出了系統(tǒng)漸近穩(wěn)定的充分必要條件，

5、從而找到了時延、系統(tǒng)規(guī)模及負(fù)載平衡增益之間較為直觀的近似關(guān)系。同時，在所得出DDLB系統(tǒng)穩(wěn)定性的充分必要條件的基礎(chǔ)上，提出了一種基于局部優(yōu)化的自適應(yīng)控制策略，與原有局部優(yōu)化方法相比，本文所提出的方法在對實際控制增益進(jìn)行優(yōu)化調(diào)節(jié)的同時，還保證了DDLB系統(tǒng)的穩(wěn)定性，在一定程度上彌補了傳統(tǒng)局部優(yōu)化自適應(yīng)控制方法的不足，使得本文所提出方法更加接近實際應(yīng)用。
　　再次，為了清晰地揭示各類時延對動態(tài)負(fù)載平衡穩(wěn)定性的影響，本文提出了常數(shù)時延條

6、件下DDLB系統(tǒng)穩(wěn)定性的充分條件。在常數(shù)時延情況下采用了時域分析方法對DDLB系統(tǒng)的異構(gòu)模型進(jìn)行了穩(wěn)定性分析。通過選取適當(dāng)?shù)腖yapunov-Krasovskii泛函，使用Newton-Leibniz公式、Moon不等式及矩陣的Schur補性質(zhì)得出了系統(tǒng)漸進(jìn)穩(wěn)定的充分條件，拓展了分析結(jié)果的理論適用范圍，并通過引入指數(shù)穩(wěn)定的概念提高系統(tǒng)的收斂速度，所得出結(jié)論適用于時延變化較小的動態(tài)負(fù)載平衡系統(tǒng)。
　　同時，針對時延變化較大的異構(gòu)動態(tài)

7、負(fù)載平衡系統(tǒng)，本文提出了時變時延條件下DDLB系統(tǒng)穩(wěn)定性的充分條件。通過選取適當(dāng)?shù)腖yapunov-Krasovskii泛函，使用積分的基本性質(zhì)、Jenssen不等式及矩陣的Schur補性質(zhì)得出了時變時延情況下系統(tǒng)指數(shù)穩(wěn)定的充分條件，該條件適用于時延在一定區(qū)間內(nèi)變化且其變化率有界的動態(tài)負(fù)載平衡系統(tǒng)。另外，在上述穩(wěn)定性分析工作的基礎(chǔ)上，本文將幾類穩(wěn)定性條件轉(zhuǎn)換為標(biāo)準(zhǔn)的LMI優(yōu)化問題，并通過使用Matlab中的LMI工具箱對動態(tài)負(fù)載平衡系統(tǒng)

8、的理論增益值進(jìn)行求解。
　　最后，針對實際DDLB系統(tǒng)，本文給出了一種基于多線程的離散事件模擬方法，并其基礎(chǔ)上對理論分析中的各類情況進(jìn)行了模擬驗證。實驗結(jié)果表明，DDLB系統(tǒng)的最優(yōu)負(fù)載平衡增益與傳輸及通信時延成反比，與系統(tǒng)規(guī)模及負(fù)載平衡時延成正比，通信、傳輸時延、系統(tǒng)規(guī)模及信息確定化程度對動態(tài)負(fù)載平衡系統(tǒng)的穩(wěn)定性均有較大的影響，通過選擇適當(dāng)?shù)膭澐植呗约柏?fù)載平衡增益可以有效地減少這一類影響。本文所提出的理論與方法對尋找到DDLB系統(tǒng)