分布式存儲結構下時延動態(tài)負載平衡系統的穩(wěn)定性分析.pdf

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

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

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

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

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

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

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

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