异构计算环境中启发式任务调度方法

论文摘要

异构计算环境由各种具有不同计算能力的资源构成,用以满足计算密集型应用的需要.这些应用在计算上具有不同的需求和约束.异构计算系统和计算网格使用一组地理上分布的资源来解决困难的计算问题.异构计算系统中的一个主要的挑战是如何有效地利用可用的资源.在这类系统中,系统资源被多个应用所共享,用户提出的应用具有特定的服务质量需求.一种高效利用异构计算系统或计算网格的方法是根据计算需求将应用分解为若干任务,不同的任务会适合于运行在不同的机器上.一旦应用被分解为任务,每个任务需要被分配到合适的机器上执行,从而最优化某个特定的目标函数.在异构系统中,将任务分配到机器的问题被证明是NP完全问题.因此,亟需设计启发式技术来获得近似最优解.本文主要研究异构计算系统和计算网格中任务的分配问题.为解决异构计算系统和计算网格中的任务调度问题,我们提出多种调度算法.我们提出了一种新的任务调度启发式方法,即高方差优先算法（HSTDF）.该方法将任务的期望执行时间的方差作为选择准则.任务的期望执行时间的方差表示了该任务在不同机器上执行时间的差异量.我们的方法是将具有最高方差的任务首先进行调度.直观上,具有较低方差的任务在不同机器上的执行时间相差较小,因此将这些任务延迟调度对整体完成时间的影响较小.相反,具有较高方差的任务在不同机器上的执行时间相差较大,延迟调度这些任务可能会妨碍这些任务被分配到速度更快的机器,因为这些机器可能己经被之前调度过的任务占据了,这种情况将导致任务整体完成时间的增加.因此,具有最高方差的任务优先进行调度.我们进行了大量的实验来检验该启发式方法在各种情况下的有效性.实验结果表明该方法优于现有的方法.因此,将任务的期望执行时间的方差作为选择准则有助于提高调度的效率.此外,我们还提出了一种新的网格计算中的服务质量导向的任务调度算法.服务质量在不同的应用背景下具有不同的含义.例如,网络中的服务质量表示应用所期望的带宽. CPU的服务质量表示所需要的速度,如FLOPS,或对潜在CPU性能的利用.我们的研究考虑一种一维服务质量.我们将网络的服务质量表示为它的带宽.在现有的网格任务调度中,具有不同级别服务质量要求的任务会请求不同的资源.没有服务质量要求的任务可以在高服务质量的资源上执行也可在低服务质量的资源上执行.然而,带有高服务质量请求的任务只能在高服务质量资源上执行.因此,让低服务质量任务占据高服务质量资源,同时让高服务质量要求的任务等待是不可行的,因为低服务质量资源仍然空闲.为克服这些不足,我们提出了一种新的调度算法.该算法将服务质量匹配考虑进任务调度决策中.为了在异构计算系统中进行任务调度,人们提出了大量启发式方法.每种启发式方法都建立在不同的假设基础上,从而给出近似最优解,然而对于一组特定的任务,选择哪种方法进行调度却没有被研究过.为解决这个问题,我们对多种启发式方法进行了大量实验研究,并考察哪个方法能够给出最小的任务完成时间.我们实现、分析、并系统地比较了16种贪心式启发方法,其中7种是新提出的方法.比较实验所使用的数据模型由基于coefficient-of-variation的模型实现.大量的模拟实验指出了在某种贪心启发方法优于其他15种方法的情况.

论文目录

• 摘要
• Abstract
• List of Figures
• List of Tables
• Acronym
• Chapter 1 Heterogeneous Computing: Introduction & Overview
• 1.1 Motivation
• 1.2 Applications of Heterogeneous Computing
• 1.2.1 Distributed Supercomputing
• 1.2.2 High-Throughput Computing
• 1.2.3 On-Demand Computing
• 1.2.4 Data-Intensive Computing
• 1.2.5 Collaborative Computing
• 1.3 Characteristics of HC Systems and Computational Grids
• 1.3.1 Heterogeneity at Multiple Levels
• 1.3.2 Unpredictable Structure
• 1.3.3 Dynamic Behavior
• 1.3.4 Multiple Administrative Domains
• 1.4 Research Challenges for HC
• 1.4.1 Programming Model and Tools
• 1.4.2 Resource Management
• 1.4.3 Network Protocols and Infrastructure
• 1.4.4 Security
• 1.4.5 Task Scheduling
• 1.5 Task Scheduling: Background and Related Work
• 1.5.1 A Motivational Example
• 1.5.2 NP-Completeness of Mapping Problem
• 1.5.3 Scheduling Taxonomies
• 1.6 Contributions
• 1.7 Structure of Thesis
• Chapter 2 Determining Efficient Task Scheduling Algorithm
• 2.1 Introduction
• 2.2 Simulation Model
• 2.3 Task Scheduling Heuristics Descriptions
• 2.3.1 Preliminary Definitions
• 2.3.2 Minimum Execution Time
• 2.3.3 Opportunistic Load Balancing
• 2.3.4 Minimum Completion Time
• 2.3.5 Minmin
• 2.3.6 Maxmin
• 2.3.7 Heaviest Task First
• 2.3.8 WMTGMin
• 2.3.9 Sufferage
• 2.4 Results and Discussion
• 2.5 Summary
• Chapter 3 Heuristic Algorithm for Task Scheduling in Heterogeneous Computing Environment
• 3.1 Introduction
• 3.2 Problem Definition
• 3.3 High Standard Deviation First Heuristic
• 3.4 Results and Discussion
• 3.4.1 Dataset
• 3.4.2 Comparative Performance Evaluation
• 3.4.3 Inconsistent ETCs
• 3.4.3.1 Fixed machine heterogeneity & variable task heterogeneity
• 3.4.3.2 Fixed machine heterogeneity & variable task heterogeneity
• 3.4.4 Consistent ETCs
• 3.4.4.1 Fixed machine heterogeneity & variable task heterogeneity
• 3.4.4.2 Fixed task heterogeneity & variable machine heterogeneity
• 3.4.5 Partially-consistent ETCs
• 3.4.5.1 Fixed machine heterogeneity & variable task heterogeneity
• 3.4.5.2 Fixed task heterogeneity & variable machine heterogeneity
• 3.5 Summary
• Chapter 4 QoS Guided Scheduling Algorithm
• 4.1 Introduction
• 4.2 QoS Guided Scheduling Model
• 4.3 Proposed QoS Algorithm
• 4.3.1 Terminology
• 4.4 Simulation and Results
• 4.5 Summary
• Chapter 5 Task Partitioning Based Heuristic Algorithms
• 5.1 Introduction
• 5.2 Problem Definition
• 5.3 Task Partitioning Heuristic
• 5.3.1 Heuristics Notation
• 5.4 Experimental Results and Analysis
• 5.4.1 Dataset
• 5.4.2 Comparative Performance Evaluation
• 5.5 Algorithm to Find Best Heuristic
• 5.6 Summary
• Conclusions
• References
• Publications
• Declaration
• Acknowledgments
• Resume