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

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

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

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

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

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

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

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

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