(3.239.33.139) 您好!臺灣時間:2021/03/08 16:31
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:魏家鑫
研究生(外文):Wei Chia-Hsin
論文名稱:異質計算系統中工作配置與排程之探討
論文名稱(外文):Task Matching and Scheduling in Heterogeneous Computing Systems
指導教授:莊博任
指導教授(外文):Chuang Po-Jen
學位類別:碩士
校院名稱:淡江大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:81
中文關鍵詞:異質計算系統基因遺傳演算法模擬退火演算法工作排程
外文關鍵詞:Heterogeneous Computing SystemGenetic AlgorithmSimulated Annealing AlgorithmTask scheduling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:279
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:9
  • 收藏至我的研究室書目清單書目收藏:1
工作配置與排程問題(Task Matching and Scheduling)關係著系統效能是否能有效發揮,若此問題能獲得解決則可用最少的成本獲得最大的效益,否則功能再強大的系統也無法發揮它的效能。目前已有許多的研究提出不同策略的演算法來解決工作配置與排程問題,這些演算法大多僅將焦點置於只考慮處理器的計算能力,對系統中其他資源的統合應用並未一併探討。而異質計算系統(Heterogeneous Computing System)是藉由網路將系統中的資源結合在一起,除了處理器的計算能力外,網路傳輸成本亦是重要的考量,因此目前解決工作配置與排程的方法並不完全適用於異質計算系統。
為了有效解決異質計算系統中工作配置與排程問題,我們重新定義此一問題,並定義相關公式以計算目標函數。在異質計算系統中,執行某一應用程式時,可能需要讀取檔案伺服器中的檔案才能使程式順利執行完畢,因此在我們的定義中,藉由加入考慮檔案存取的方式以適當反映傳輸成本。此時若將工作分配到執行時間最短的處理器上執行,並不一定能有效縮短排程長度,因為此舉可能使得至檔案伺服器中讀取檔案的時間增長。在此情況下,工作配置與排程問題必須根據系統整體情況做全盤考量,而不只考慮處理器的計算能力。
我們首先應用基因遺傳演算法(Genetic Algorithm),模擬退火演算法(Simulated Annealing Algorithm)及導引演進模擬退火演算法(Guided Evolutionary Simulated Annealing Algorithm) 來求解最佳工作配置與排程方式。再將我們所提出的基因退火演算法(Genetic Annealing Algorithm)與前述三種演算法比較。
我們所提出的基因退火演算法與其他三種演算法最大的差別在於1.演算法流程簡單明確易於實現2.只使用攪動運算操作方式簡單卻更具保留優良基因的效果3.藉由攪動運算完成退火過程是一種全新的溫度退火觀念。
基因退火演算法是由四個參數來控制由兩個for所組成的巢狀迴圈及攪動運算,因此只要適當設定此四個參數的值即可有效控制整個演算法的流程與攪動運算的變化。整個基因退火演算法的詳細演算流程、搜尋方式、攪動運算如何操作、與其他演算法的優缺點比較等,將於文中詳細說明。
我們模擬評估的項目有1.Speedup 2.Running Time 3.Cost 4.Complexity。我們所提出的基因退火演算法在四項評估項目中均有不錯的表現,足以證明含有退火過程的攪動運算確實更能有效保留優良基因。整體流程簡單明確,不需設定收斂條件,因此能有效降低程式執行時間與演算法整體複雜度。由模擬結果亦可看出各項系統參數對評估項目的影響程度及四種演算法的優劣與特色。

A major challenge in the Heterogeneous Computing Systems is to make effective use of the shared resources to optimize global objectives. The goal of task matching and scheduling is to assign application tasks to suitable resources and to order task executions in time to optimize a specific objective function. Over the past few years, a considerable number of studies have been made on this problem. Various algorithms have been devised for matching applications in the Heterogeneous Computing System, but most focus only on computing resources.
The purpose of this research is to redefine the task matching and scheduling problem in a Heterogeneous Computing System and to use our novel Genetic Annealing Algorithm (GAA) to solve this problem. The resources of a Heterogeneous Computing System are interconnected by networks. It is important that we should not overlook the transmission cost. Some assumptions are made carefully to define or redefine the problem under investigation so that the defined problem can be closer to the real situation and hence the solution obtained can be more practical and useful. In our problem tasks need to access files and transmission cost is taken into consideration. By merely assigning a task to the processor that gives its best estimated computation time, performance can also be poor due to the cost of retrieving the required input file from an improper file server.
Our Genetic Annealing Algorithm and three other optimization techniques, i.e., the Genetic Algorithm (GA), the Simulated Annealing (SA) and the Guided Evolutionary Simulated Annealing (GESA), are employed and applied to get the optimal solution to our carefully defined problem. The three advantages with our Genetic Annealing Algorithm are: (1) the algorithm itself is short and simple, (2) only the stir operation is involved, and (3) the stir operation is a novel idea with the annealing concept. Our proposed Genetic Annealing Algorithm can solve not only the task matching and scheduling problem but also any other problems that need optimal solutions. The details of the Genetic Annealing Algorithm and the stir operation are to be shown in this thesis.
Four metrics are used to compare the performance of our proposed algorithm and of the previous approaches. Extensive simulation runs are conducted and the results are collected for comparison between our approach and the others. As the simulation results indicate, our GAA yields constantly favorable performance over the other approaches.

目 錄
第一章簡介....................1
第二章異質計算系統中工作配置與排程問題
2.1 異質計算系統............... 5
2.2 方向性非循環圖.............. 7
2.3 工作配置與排程問題............ 9
2.4 系統模型與公式定義............ 11
第三章最佳化演算法介紹
3.1 基因遺傳演算法.............. 20
3.2 模擬退火演算法.............. 26
3.3 導引演進模擬退火演算法.......... 31
3.4 本文所提出之基因退火演算法........ 35
3.5 應用四種演算法尋找最佳解......... 46
第四章 模擬結果................ 54
4.1 增速................... 57
4.2 程式執行時間............... 67
4.3 成本................... 72
4.4 複雜度.................. 74
第五章 結論................... 76
參考文獻...................... 80

參考文獻
[1] R. Freuncd and H. J. Siegel “Guest editors’ introduction: Heterogeneous processing” IEEE Computer, Vol. 26, No. 6, June 1993, pp. 13-17
[2] L. Wang, H. J. Siegel, V. P. Roychowdhury, and A. A. Maciejewski “Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach” Journal of Parallel and Distributed Computing, Vol. 47, No. 1, Nov. 1997, pp. 8-22
[3] T. D. Braun, et. al., “A taxonomy for describing matching and scheduling heuristics for mixed-machine heterogeneous computing system” Proc. 7th IEEE Symposium on Reliable Distributed Systems, 1998, pp. 330-335
[4] Y.-K. Kwok and I. Ahmad “Benchmarking the task graph scheduling algorithms” Proc. 1st Merged Int’l Parallel Processing Symp. and Symp. on Parallel and Distributed Processing, 1998, pp. 531 —537
[5] Z.-P. Lo and B. Bavarian “Job scheduling on parallel machines using simulated annealing” Proc. 1991 IEEE Int’l Conf. on Systems, Man, and Cybernetics, Vol. 1, 1991, pp. 391-396
[6] C.-Y. Shen, Y.-H. Pao, and P. Yip, Proc “Scheduling Multiple Job Problems with Guided Evolutionary Simulated Annealing Approach” 1st. IEEE Conf. on Evolutionary Computation, Vol. 2,1994, pp. 702 —706
[7] Ahmad, Y.-K. Kwok, and M.-Y. Wu “Analysis, evaluation, and comparison of algorithms for scheduling task graphs on parallel processors” Proc. 2nd Int’l Symp. on Parallel Architectures, Algorithms, and Networks, 1996, pp. 207 —213
[8] S.-H. Woo, S.-B. Yang, and S.-D. Kim “Task scheduling in distributed computing systems with a genetic algorithm” Proc. HPC Asia '97, 1997 , pp. 301 —305
[9] A.H. Alhusaini, V. K. Prasanna, and C. S. Raghavendra “A unified resource scheduling framework for heterogeneous computing environments” Proc. 8th Heterogeneous Computing Workshop, 1999, pp. 156-165
[10] A.H. Alhusaini, V. K. Prasanna, and C. S. Raghavendra “A framework for mapping with resource co-allocation in heterogeneous computing systems”Proc. 9th Heterogeneous Computing Workshop, 2000, pp. 273 —286
[11] E. S. H. Hou, N. Ansari, and R. Hong “A Genetic Algorithm for Multiprocessor Scheduling” IEEE Trans. on Parallel and Distributed Systems, Vol. 5, No. 2, Feb. 1994, pp. 113-120
[12] H. Topcuoglu, S. Hariri, and M.-Y. Wu “Task scheduling algorithms for heterogeneous processors” Proc. 8th Heterogeneous Computing Workshop, 1999, pp. 3 —14

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔