An Algorithm for Task Scheduling in a Heterogeneous Computing Environment

论文摘要

网格计算一直到80年代后期开始研究。现在它已成为一个非常重要的计算模式,尤其是有关科学,工程问题,企业和那些需要密集计算等领域。存在许多成功应用网格计算的系统。网格计算创建了一个非常强大的计算环境,同时也带来了许多挑战,通常在平常的计算方式中是不不存在的。其中最大的问题是调度。如何把一个大的问题划分成小的问题并且分配到网格计算系统的各个计算终端上就是网格计算系统所管理的。因此,调度的问题就成了非常重要的挑战,如果这个问题解决得话,那么整个的网格计算系统就能成功的运行。映射独立任务到异构计算系统,到整个系统中最后完成得任务所需要的时间就是所谓的跨度,这是已经被证明的NP-完全问题。因此,许多文献中存在解决这个问题的启发式算法。其中,HLTF（The Heterogeneous Largest Task First）和Segmented Min-Min有较好的低复杂度的跨度。在这份文件中,我们提出Heterogeneous Priority for Avoidance of Largest Penalty （HPALP）算法,它通过解决HLTF在异构计算环境中的问题和在异构的计算环境中Segmented Min-Min没有一个清晰的分段来实现在HLTF和Segmented Min-Min中的启发式。新提出的启发式和几个相关的已在基于simjava的模拟异构计算（HC）的环境中实现,实验结果表明,我们的启发式算法比传统的算法性能更优

论文目录

• Acknowledgements
• ABSTRACT
• 摘要
• Table of Contents
• List of Tables
• List of Figures
• 1 Introduction
• 1.1 Grid Computing
• 1.2 Types of Grids
• 1.2.1 Computational Grids
• 1.2.2 Scavenging Grids
• 1.2.3 eScience Grids
• 1.2.4 Data Grids
• 1.2.5 Enterprise Grids
• 1.3 Heterogeneous Grid computing
• 1.4 Scheduling:An important Grid mechanism
• 1.5 Types of Scheduling in Grids
• 1.5.1 Independent Scheduling
• 1.5.2 Grid workflows
• 1.5.3 Centralized,hierarchical and decentralized scheduling
• 1.5.4 Static vs. dynamic scheduling
• 1.5.5 Immediate vs. batch mode scheduling
• 1.5.6 Adaptive Scheduling
• 1.5.7 Economy-based scheduling
• 1.6 Our Proposal
• 2 Computation Models
• 2.1 Expected Time To Compute model
• 2.2 Modeling heterogeneity and consistency of computing
• 2.3 Some existing heuristics
• 2.4 ETC Matrix Characterization
• 3 Introducing Hasse Diagram
• 3.1 Definitions
• 3.2 Hasse Diagram
• 3.2.1 Usage Of Hasse Diagram in our heuristic
• 4 Our New Heuristic for Task Scheduling in Heterogenous Environments
• 4.1 TPD↓-MinCT-MinCT
• 4.2 Our Proposed HPALP Heuristic
• 4.2.1 HPALP Heuristic discussed in detail
• 5 Experiments and Results
• 5.1 Generating Data Related to the Experiment
• 5.2 Simulation Platform for the Experiment
• 5.2.1 Construction of our Experiment
• 5.2.2 Some parameters chosen for the experiement
• 5.2.3 Experimental Results
• 6 Conclusion
• 6.1 Summary
• 6.2 Future Work
• References