基于計(jì)算智能的并行分布式系統(tǒng)任務(wù)調(diào)度算法研究.pdf

1、并行與分布式處理一直是當(dāng)前科技研究、發(fā)展與應(yīng)用的熱點(diǎn)領(lǐng)域，是天氣預(yù)報(bào)、核爆炸模擬、電子碰撞模擬、風(fēng)洞雷諾數(shù)值計(jì)算以及金融服務(wù)等科學(xué)計(jì)算與數(shù)據(jù)服務(wù)處理領(lǐng)域的重要解決手段。資源共享與管理是并行分布式系統(tǒng)的核心和關(guān)鍵技術(shù)之一，任務(wù)調(diào)度對(duì)于資源的有效利用起到非常關(guān)鍵的作用，是幾十年來(lái)學(xué)術(shù)界研究的重點(diǎn)之一。
　　調(diào)度是一個(gè)NP難問(wèn)題，目前的很多啟發(fā)式方法在尋優(yōu)能力等方面仍存在缺陷。隨著人工智能的發(fā)展和成熟，其中一個(gè)重要分支——計(jì)算智能理論得

2、到廣泛的應(yīng)用。應(yīng)用計(jì)算智能已解決了環(huán)境、經(jīng)濟(jì)、管理等領(lǐng)域的諸多復(fù)雜問(wèn)題，該方法模擬人類和生物智能行為的計(jì)算方法，為搜索、分類等提供了新的求解方式。本文將部分經(jīng)典的計(jì)算智能方法引入到并行與分布式系統(tǒng)的調(diào)度策略設(shè)計(jì)中，以期突破傳統(tǒng)方法在自適應(yīng)、組合優(yōu)化等方面的局限性，本文的主要研究工作如下:
　　(1)針對(duì)并行分布式系統(tǒng)中的多用戶網(wǎng)絡(luò)應(yīng)用，將任務(wù)和資源動(dòng)態(tài)性質(zhì)轉(zhuǎn)化為隨機(jī)分布，基于排隊(duì)論將調(diào)度問(wèn)題定義為一個(gè)非線性規(guī)劃問(wèn)題。但是該方法只能

3、用于特定分布，缺乏適應(yīng)性。因此引入機(jī)器學(xué)習(xí)方法到調(diào)度中，將調(diào)度定義為馬爾可夫決策過(guò)程，提出了一種能適應(yīng)任務(wù)到達(dá)和資源性能動(dòng)態(tài)性的調(diào)度算法。相比于第一種方法，此方法通過(guò)學(xué)習(xí)能夠主動(dòng)適應(yīng)分布式系統(tǒng)中存在的不確定性，從而提高調(diào)度性能。提出的算法具有較好的魯棒性，其較強(qiáng)的適應(yīng)能力使得調(diào)度之后任務(wù)的平均響應(yīng)時(shí)間較小。
　　(2)上述集中式調(diào)度方法適用于小規(guī)模的并行分布式系統(tǒng)，在大規(guī)模系統(tǒng)中，分布式調(diào)度更為普遍，根據(jù)資源特性建立了一個(gè)分層的多

4、角色的任務(wù)調(diào)度框架。在分布式調(diào)度中，調(diào)度器不僅需要適應(yīng)任務(wù)到達(dá)的隨機(jī)性和系統(tǒng)負(fù)載的動(dòng)態(tài)性，而且還需要適應(yīng)其他調(diào)度器分配策略的影響。對(duì)于其中的合作型調(diào)度問(wèn)題，基于任務(wù)流之間存在相互關(guān)系將其定義為馬爾可夫決策過(guò)程，并且基于強(qiáng)化學(xué)習(xí)提出了相應(yīng)的調(diào)度算法，使得調(diào)度器能夠主動(dòng)學(xué)習(xí)任務(wù)到達(dá)和執(zhí)行的相關(guān)知識(shí)，以及適應(yīng)相鄰調(diào)度器分配策略。對(duì)于自利型調(diào)度問(wèn)題，建立了一個(gè)非合作博弈模型，并提出了納什均衡聯(lián)合調(diào)度策略的分布式學(xué)習(xí)算法，該算法在任務(wù)的期望響應(yīng)時(shí)

5、間和公平性方面均有較好的性能。
　　(3)上述兩個(gè)算法的調(diào)度模型中沒(méi)有考慮數(shù)據(jù)本地化對(duì)調(diào)度的影響，而網(wǎng)格中數(shù)據(jù)密集型應(yīng)用在計(jì)算時(shí)需要頻繁地訪問(wèn)存儲(chǔ)資源，計(jì)算和存儲(chǔ)資源調(diào)度的協(xié)同成為調(diào)度的關(guān)鍵。針對(duì)網(wǎng)格中數(shù)據(jù)密集型應(yīng)用，提出了融合計(jì)算和存儲(chǔ)資源的調(diào)度模型。該模型將傳統(tǒng)的調(diào)度器分為三層，且在每一層扮演不同的角色:在第一層中，為一個(gè)總的調(diào)度器，它負(fù)責(zé)收集信息。第二層和第三層中各包含了多個(gè)小的調(diào)度單元，使得應(yīng)用程序的調(diào)度能夠并行執(zhí)行。在此

6、調(diào)度模型基礎(chǔ)上，提出了并行的遺傳算法和并行的禁忌搜索算法用于解決分布式系統(tǒng)中任務(wù)調(diào)度和存儲(chǔ)資源選擇問(wèn)題，從而達(dá)到減小應(yīng)用完成總時(shí)間的目的。
　　(4)資源的異構(gòu)性是調(diào)度模型中另一個(gè)不可忽視的元素，現(xiàn)有并行分布式系統(tǒng)中資源具有不同的可用性是一個(gè)重要的特點(diǎn)，在這種情況下，如何提升系統(tǒng)的可用性，滿足更多應(yīng)用的可用性需求是調(diào)度面臨的新問(wèn)題。針對(duì)可用性需求，提出了makespan（調(diào)度長(zhǎng)度）和可用性雙目標(biāo)優(yōu)化問(wèn)題。首先，建立了系統(tǒng)的任務(wù)完成