基于预算受限的网格工作流调度算法研究

发布时间：2018-02-03 20:12

本文关键词： 网格网格工作流调度预算受限蚁群算法　出处：《南京大学》2014年硕士论文　论文类型：学位论文

【摘要】：网格作为一种新型计算模式,已经成为新一代电子科研的计算基础设施,世界各地学者为其巨大潜力所吸引,投入大量精力并取得了丰硕成果。作为网格环境中一项重要的基本服务,网格工作流对网格应用的构建、执行调度和管理监控有着重要意义,极大地提高了网格应用的自动化程度与效率。网格工作流调度是网格工作流系统的核心部分之一,也是网格高性能计算的重要支撑。它将工作流中的活动(计算任务)分配到合适的网格资源上执行(计算),协调各个活动的执行以达到最好的目标。网格工作流调度已被证明为NP困难问题,却吸引着广大工作流问题研究者。由于研究人员的突出贡献,网格工作流调度已获得重要进展,出现了如Min-Min、Max-Min、HEFT、表调度、聚簇调度等经典的启发式调度算法,也引进了如遗传算法、模拟退火算法、蚁群算法等元启发式搜索算法。工作流调度者在使用网格资源执行活动时,往往需要付出与执行时间成正比的费用。对于某些场景,用于支付资源所需的费用是有限的,这就形成了预算受限的网格工作流。上述经典或元启发式算法都是性能驱动的调度算法,并不适用于预算受限的网格工作流。本文提出了一种基于蚁群优化的算法以解决预算受限网格工作流调度问题。在应用蚁群算法的过程中,为排除无效解对解空间的负面影响和对求解速度的干扰,本文创造性地提出了奢侈资金和奢侈率的概念,并给出了一种全新的计算节点之间距离的公式,综合考虑预算的限制以及活动前驱的完成时间、数据通信时间、活动本身的执行时间,使算法的求解质量有了较大提升：经本算法调度,计算密集型工作流的完工时间降低了约8%,而通信密集型工作流的完工时间则降低了约11%。
[Abstract]:Grid, as a new computing model, has become the computing infrastructure of the new generation of electronic scientific research, and scholars around the world are attracted by its great potential. As an important basic service in grid environment, grid workflow plays an important role in the construction, execution, scheduling and management of grid applications. Grid workflow scheduling is one of the core parts of grid workflow system. It is also an important support for grid high performance computing, which assigns the activities (computing tasks) in the workflow to the appropriate grid resources to execute (compute). Grid workflow scheduling has been proved to be a NP hard problem, but it attracts a large number of workflow problem researchers. Due to the outstanding contributions of researchers. Grid workflow scheduling has made important progress, such as Min-Min-Max-Min-HEFTT, table scheduling, clustering scheduling and other classical heuristic scheduling algorithms, such as genetic algorithms have been introduced. Simulated annealing algorithm, ant colony algorithm and other meta-heuristic search algorithms. Workflow schedulers often have to pay a cost proportional to the execution time when using grid resources to execute activities. For some scenarios. The cost required to pay for resources is limited, which results in a grid workflow with budget constraints. The classical or meta heuristic algorithms mentioned above are both performance-driven scheduling algorithms. This paper proposes an ant colony optimization algorithm to solve the scheduling problem of budget constrained grid workflow. In order to eliminate the negative effect of invalid solution on solution space and the interference of solution speed, this paper creatively puts forward the concepts of luxury capital and luxury rate, and gives a new formula to calculate the distance between nodes. Considering the limitation of the budget, the time of completion of the activity precursor, the time of data communication, and the execution time of the activity itself, the solution quality of the algorithm has been greatly improved: the algorithm is scheduled by this algorithm. The completion time of computationally intensive workflow is reduced by about 8 percent, while that of communication intensive workflow is reduced by about 11 percent.
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02

【相似文献】