基于桌面網(wǎng)格的自調(diào)度算法的.研究與應用

《基于桌面網(wǎng)格的自調(diào)度算法的.研究與應用》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、基于桌面網(wǎng)格的自調(diào)度算法的研究及應用第l章緒論1．1選題背景和意義第l章緒論隨著互聯(lián)網(wǎng)技術的迅速發(fā)展，在網(wǎng)絡上聚集了大量空閑的計算資源、存儲資源和信息資源，這些資源的閑置使得大范圍地理分布的異構計算機系統(tǒng)和資源整合在一起，形成一個大規(guī)模的計算平臺成為日益迫切的要求。因此，網(wǎng)格(Grid)Iml應運而生。網(wǎng)格的概念最早于90年代中期提出，用于表述在高端科學和工程分布式計算中的一種基礎構造形式。美國的資深科學家IanFoster將網(wǎng)格描述為：網(wǎng)格是構筑在互聯(lián)網(wǎng)上的一組新興技術，它將高速互聯(lián)網(wǎng)、高性能計算機、大型數(shù)據(jù)庫、傳感器和遠程設備等融為一體，為科技人員和普通

2、用戶提供更多的資源、功能和交互性。由于網(wǎng)格能提供如此強大的功能，目前，包括中國在內(nèi)，全世界很多國家都對網(wǎng)格投入巨大的人力物力，產(chǎn)生了很多具有里程碑意義的研究成果。在網(wǎng)格的諸多研究方向之中，對調(diào)度問題的研究無疑是最重要、最有挑戰(zhàn)性的方向之一。桌面網(wǎng)格是網(wǎng)格的一種，其中的計算資源主要是由一臺臺的桌面PC機所組成，這些資源是異構的，有自己的存儲資源和軟件資源。桌面網(wǎng)格的調(diào)度問題是根據(jù)各節(jié)點的資源狀態(tài)，把任務以合理的方式分配到相應的節(jié)點去執(zhí)行。為了發(fā)揮出各節(jié)點的潛在計算能力，一個主要的問題就是怎樣把任務分配給各節(jié)點以使各節(jié)點的負載達到平衡并使總的完成時間最小。循環(huán)是

3、科學計算領域中一個常見的、需要花費大量資源的問題【31，因此比較適合于在網(wǎng)格環(huán)境下進行并行計算。如果一個循環(huán)的各次迭代之間沒有任何關系，各次迭代就可以看作是一個任務并可被獨立的調(diào)度。傳統(tǒng)模式上對這種并行循環(huán)的調(diào)度分為靜態(tài)調(diào)度和動態(tài)調(diào)度14]兩種。靜態(tài)調(diào)度是指在編譯時進行任務的分配，因而在程序執(zhí)行前任務的大小已經(jīng)是確定的，如OpenMP、MPI等。當循環(huán)的各次迭代擁有相等的工作量時靜態(tài)調(diào)度可以發(fā)揮較高的性能，但是在處理以下幾種情況時就會顯示出不足：(1)循環(huán)的模式是不規(guī)則的；(2)循環(huán)的工作量在編譯時是不可知的；(3)系統(tǒng)是異構的。第1章緒論基于桌面網(wǎng)格的自調(diào)

4、度算法的研究及應用動態(tài)調(diào)度則是為了解決以上問題而提出來的一種可在執(zhí)行時調(diào)整具體任務的調(diào)度方式。動態(tài)調(diào)度可以實現(xiàn)不同節(jié)點間的負載平衡，因此適合于迭代次數(shù)不定以及每次迭代都花費不同時間的情況。自-N]／3芝(Self-Scheduling)ISl是一種動態(tài)、自適應的調(diào)度模式，比較適合于并行循環(huán)的調(diào)度。它是一種在應用層的調(diào)度技術，指一個任務可以分解成多個子任務，然后每個子任務分配到各個節(jié)點并行執(zhí)行，從而減少完成時間的技術。在自調(diào)度中，各個執(zhí)行服務的節(jié)點根據(jù)自己的資源狀況主動向調(diào)度節(jié)點索取任務，而不是被動地等待調(diào)度節(jié)點分配任務。在有獨立循環(huán)的計算中，如矩陣相乘、圖像

5、渲染等，自調(diào)度都取得了比較理想的效果。而在桌面網(wǎng)格環(huán)境下，由于其系統(tǒng)的異構性和動態(tài)性，使得在這之上的自調(diào)度變得復雜?？傮w來說，具有以下特點：(1)自調(diào)度是基于異構環(huán)境的。由于桌面網(wǎng)格系統(tǒng)是由分布在網(wǎng)絡上的各種PC機組成，這些資源的結(jié)構、速度或操作系統(tǒng)是異構的，因此桌面網(wǎng)格環(huán)境下的自調(diào)度必須面向異構環(huán)境；(2)自調(diào)度不干涉網(wǎng)格節(jié)點內(nèi)部的調(diào)度。自調(diào)度只是負責把任務以合理的方式、合理的大小分配給網(wǎng)格節(jié)點執(zhí)行，至于網(wǎng)格節(jié)點何時調(diào)度該任務及使用何種方式來調(diào)度是由節(jié)點內(nèi)部調(diào)度策略決定的；(3)自調(diào)度能夠動態(tài)自適應。網(wǎng)格中的資源不但是異構的而且網(wǎng)格的結(jié)構總是不停的改變：有

6、新資源加入、有資源出現(xiàn)故障等，因此自調(diào)度必須適應網(wǎng)格的這種動態(tài)性；(4)自調(diào)度必須具有通用性。提交給網(wǎng)格的作業(yè)依據(jù)占用CPU的時間及數(shù)據(jù)量的大小可以分為計算密集型、數(shù)據(jù)密集型、計算和數(shù)據(jù)均密集型三種，因此桌面網(wǎng)格環(huán)境下的自調(diào)度必須能滿足這三種應用的要求。桌面網(wǎng)格環(huán)境下自調(diào)度的目標就是以最優(yōu)的方式分割任務，在最短的時間里完成用戶的請求。具體的目標包括負載平衡、完成時間短等。(1)完成時間短。完成時間指用戶把任務提交給網(wǎng)格到網(wǎng)格把最終結(jié)果返回給用戶的這段時間。這是調(diào)度領域里一個最常見、雖普遍的目標，完成時間越短，說明調(diào)度算法越好，用戶的滿意度也越高；(2)負載平

7、衡。由于桌面網(wǎng)格環(huán)境是異構的，各節(jié)點的性能不同，因此分配任務時避免給一個性能比較差、負載比較重的節(jié)點分配過多的任務，否則會嚴重影響任務2基于桌面網(wǎng)格的自調(diào)度算法的研究及應用第1章緒論總體的完成時間。1．2研究現(xiàn)狀早期的自調(diào)度算法都是基于集群系統(tǒng)的。文獻[6】中介紹的PSS(PureSelf-Scheduling)算法每次分配一個單位的工作量給計算節(jié)點，而CSS(ChunkSelf-Scheduling)算法每次分配k個單位的工作量給計算節(jié)點，這兩種算法在整個程序的執(zhí)行過程中每次分配的任務量都是不變的。文獻【3】中的GSS(GuidedSelf-Schedul

8、ing)算法、文獻【7】中的FSS(Factorin