跳到主要內容

臺灣博碩士論文加值系統

(35.172.223.30) 您好!臺灣時間:2021/07/25 11:03
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:施俊偉
研究生(外文):Chun-Wei Shih
論文名稱:提高網格運算效能所需的排程策略之研究
論文名稱(外文):Research on the Scheduling Strategy for Improving the Performance of Grid Computing
指導教授:林作俊林作俊引用關係
指導教授(外文):Cho-Chin Lin
學位類別:碩士
校院名稱:國立宜蘭大學
系所名稱:電子工程學系碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:87
中文關鍵詞:網格計算工作排程工作指派資源媒合
外文關鍵詞:Grid computingTask schedulingTask assignmentResource matchmaking
相關次數:
  • 被引用被引用:0
  • 點閱點閱:119
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
網格計算是利用網際網路把分散在不同地理位置的電腦組織成一個虛擬
的超級電腦。為了讓分散各地的資源盡可能發揮出應有的效能, 實用且有效
率的工作排程技術就極為重要。工作排程會依據使用者的需求來尋找可用的
資源並且分配至合適的資源去執行, 這樣的動作稱為工作指派。分層工作指
派為工作指派的一種方式, 對於一個工作被切割成多個子工作來執行的情況
下, 會根據工作的分層DAG , 以分層的方式一次只針對一層的子工作進行
分配, 以順應網格環境的動態性。由於子工作間的資料相依性與工作指派的
結果, 導致運算節點上的子工作需進行轉移, 然而子工作轉移所進行的動作
就是運算節點間的資料傳遞。在本論文裡, 我們提出一個分層工作指派演算
法, 目的是在考量網格資源的動態性與異質性的情形下, 將網格的工作分配
到合適的運算節點, 以最小化工作的執行時間。我們的工作指派演算法除了
考慮降低工作的運算時間, 同時也考慮降低子工作轉移所需的通訊時間。最
後, 我們透過模擬的方式來驗證演算法的效果, 在與其他的演算法比較後,
我們的演算法是比較好。
Gird computing employs the Internet to integrate computing facilities to meet the computation requirements of many important applications. In order to achieve high performance computing, an effective and efficient task scheduling strategy is very important. According to the characteristics of a task, the task scheduler of a grid looks
for available resources and assigns the task to the proper resources for execution. This process is called task assignment. In general, the execution of a task can be divided into several steps. Each of the steps is called a layer which consists of several subtasks. Thus,
task assignment assigns the subtasks of a layer based on the available resources layer by layer in order to accommodate the dynamically changing environment. Subtasks may need to migrate from one node to another node due to the data dependency between the subtasks. Subtask migration is accomplished by communicating among the nodes.

In this thesis, we propose a novel task assignment algorithm. This algorithm is aimed to assign subtasks to adequate computing nodes for minimizing the layer execution times of grid computing environment, in which the resources are dynamic and heterogeneous. The proposed task assignment algorithm not only minimizes the computing time but also the communication time resulted form the subtask migration. Finally, we use a simulation to verify the efficiency of our algorithm. The experimental result shows that our algorithm is more efficient than other algorithms.
第一章、介紹1
1.1 背景與動機. . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 論文架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
第二章、文獻探討5
第三章、模型12
3.1 應用程式模型. . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 運算模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
第四章、通訊排程18
4.1 通訊規則. . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 通訊排程演算法. . . . . . . . . . . . . . . . . . . . . . . . 19
第五章、工作指派策略26
5.1 分層工作指派. . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2 工作指派演算法. . . . . . . . . . . . . . . . . . . . . . . . 27
第六章、實驗32
6.1 實驗環境. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.2 測試與結果. . . . . . . . . . . . . . . . . . . . . . . . . . . 34
6.2.1 測試工作1之結果. . . . . . . . . . . . . . . . . . . 37
6.2.2 測試工作2之結果. . . . . . . . . . . . . . . . . . . 52
6.2.3 測試工作3之結果. . . . . . . . . . . . . . . . . . . 67
6.3 討論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
第七章、結論與未來研究方向83
參考文獻84
[1] P. B. Bhat, V. K. Prasanna and C. S. Raghavendra, 「Adaptive communication
algorithms for distributed heterogeneous systems,」 The
Seventh International Symposium on the High Performance Distributed
Computing, pp. 310-321, 1998.
[2] D. B. Shmoys, C. Stein and J. Wein, 「Improved approximation algorithms
for shop scheduling problems,」 SIAMJ Comput, vol. 23,
no. 3, pp. 617-632, 1994.
[3] M. Kuhnemann, T. Rauber and G. Runger, 「A Source Code Analyzer
for Performance Prediction,」 The 18th International Parallel
and Distributed Processing Symposium (IPDPS』04), pp. 262b, 2004.
[4] S. Kumar, S.K. Das and R. Biswas, 「Graph partitioning for parallel
applications in heterogeneous Gridenvironments,」 Proceedings
of the International Parallel and Distributed Processing Symposium
(IPDPS』02), pp. 66-72, 2002.
[5] A. Jain, S. Sanyal, S.K. Das and R. Biswas, 「FastMap: a distributed
scheme for mapping large scale applications onto computational
grids,」 The second International Workshop on Challenges of Large
Applications in Distributed Environments (CLADE』04), pp. 66-72,
2004.
[6] P. Phinjaroenphan, S. Bevinakoppa and P. Zeephongsekul, 「A
Heuristic Algorithm for Mapping Parallel Applications on Computational
Grids,」 Advances in Grid Computing - EGC 2005, LNCS,
vol 3470, pp. 1086-1096, 2005.
[7] H. D. Kim and J. S. Kim, 「An Online Scheduling Algorithm for Grid
Computing Systems,」 Grid and Cooperative Computing - GCCC
2003, LNCS, vol 3033, pp. 34-39, 2004.
[8] W. Sun, Y. Zhang and Y. Inoguchi, 「Practical Task Flow Scheduling
for High Throughput Computational Grid,」 The 35th International
Conference on Parallel Processing Workshops (ICPPW』06), pp. 291-
297, 2006.
[9] J. M. Orduna, F. Silla and J. Duato, 「On the development of a
communication-aware task mapping technique,」 Journal of Systems
Architecture, Elsevier, vol. 50, No. 4, pp. 207-220, 2004.
[10] S. Ranka, R. V. Shankar and K. A. Alsabti, 「Many-to-many Personalized
Communication with Bounded traffic,」 Proceedings of the
Fifth Symposium on the Frontiers of Massively Parallel Computation,
pp. 20-27, 1995.
[11] T. Rauber and G. Runger, 「Anticipated distributed task scheduling
for grid environments,」 The 20th International Parallel and Distributed
Processing Symposium (IPDPS』06), pp. 25-29, 2006.
[12] P. B. Bhat and V. K. Parsanna, 「Adaptive communication algorithms
for distributed heterogeneous systems,」 Journal of Parallel
and Distributed Computing, vol. 59, No. 2, pp. 252-279, 1999.
[13] Ian Foster and Carl Kesselman, The Grid 2: Blueprint for a New
Computing Infrastructure, Morgan Kaufmann Publishers, 1998.
[14] F. Berman, High-Performance Schedulers, chapter in The Grid:
Blueprint for a Future Computing Infrastructure, edited by I. Foster
and C. Kesselman, Morgan Kaufmann Publishers, 1998.
[15] F. Dong and S. G. Akl, Scheduling Algorithms for Grid Computing:
State of the Art and Open Problems(Technical Report No. 2006-504).
School of Computing, Queen’s University, 2006.
[16] I. Bird, L. Robertson and J. Shiers, 「Deploying the LHC computing
grid - the LCG service challenges」 Local to Global Data Interoperability
- Challenges and Technologies, pp. 160 - 165, 2005.
[17] W. Hoschek, J. Jaen-Martinez, A. Samar, H. Stockinger and Kurt
Stockinger, 「Data Management in an International Data Grid
Project」 Proceedings of the First IEEE/ACM International Workshop
on Grid Computing, LNCS, pp. 77 - 90, 2000.
[18] P. Primet, 「Grid high performance networking in the DataGRID
project 」 Future Generation Computer Systems, vol. 19, No. 2, pp.
199-208, 2003.
[19] F. Gagliardi and M.-E. Begin, 「EGEE - providing a production
quality grid for e-science」 Local to Global Data Interoperability -
Challenges and Technologies, pp. 88-92, 2005.
[20] R. Berlich, M. Kunze and K. Schwarz, 「Grid computing in Europe:
from research to deployment」 Proceedings of the 2005 Australasian
workshop on Grid computing and e-research, vol. 44, pp. 88-92, 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top