异构分布式系统中能量感知的并行应用调度算法研究

论文摘要

处理器上能量感知的任务调度一直是计算机系统（例如,异构分布式计算系统）中的热门话题。给定一个包含N个任务n1,n2,...,n|N|的应用G,以及一个包含处理器集合U=u1,u2,...,u|U|的计算系统,能耗感知的任务调度通常是指为应用中的每个任务ni找到合适的处理器和处理频率,以确保所有任务都能被有效的完成,同时能够优化系统能耗,保证应用执行的整个过程中消耗的能量在控制范围内。围绕绿色计算的主题,本文的主要目标是研究在异构分布式计算系统中,对于考虑任务优先级的并行应用,如何在有能耗约束的前提下最小化应用的调度长度。本文中调度长度是指从启动第一个任务开始到完成最后一个任务之间的时间间隔。对于此问题,现有工作采用的策略是预先为每个未调度的任务分配其最小能耗以满足能耗限制,然后使用启发式算法最小化调度长度。然而,我们通过分析发现,这种预分配策略可能会使调度结果对任务优先级敏感,优先级低的任务在调度时不能得到足够的能量资源,并因此导致最终的调度长度不够乐观。基于此,本文提出了一个新的任务调度算法ISAECC,该算法设计了一种基于权重的分配机制来为任务预分配能耗,最大程度减小因能耗分配不公平对调度结果的影响,并提供了严格的数学证明来验证其可行性。本文基于两个真实的并行应用做了多组实验,和多个传统优秀算法进行对比,结果一致表明,本文提出的算法有更好的性能。除此之外,本文从能耗约束的并行应用调度长度最小化问题出发,基于解决此问题的基本思想进行扩展,又研究了另外两个能量感知的调度问题:（1）在异构分布式系统中,对于有任务优先级约束的并行应用,考虑在有能耗约束的前提下,最大化其可靠性。本文中可靠性是指系统在执行应用的过程中不发生故障的概率。受最小化调度长度问题启发,本文通过将此问题分解为两个子问题来解决,并提出ISAECC*算法;（2）在异构分布式系统中,对于有任务优先级约束的并行应用,同时考虑应用的截止时间约束和能耗约束,最大化可靠性。本文提出MRDECC算法来解决此问题,将其分为两个阶段,先利用ISAECC算法最小化调度长度,在此基础上为最大化可靠性对任务进行重新分配。针对上面两个扩展问题,本文分别给出了充分的实验来证明所提方法的有效性。

论文目录

摘要

Abstract

第1章绪论

1.1 研究背景及意义

1.1.1 能耗问题

1.1.2 调度长度和可靠性

1.1.3 任务调度

1.2 国内外研究现状

1.2.1 调度长度相关的任务调度

1.2.2 可靠性相关的任务调度

1.3 本文主要工作

1.4 本文的组织结构

第2章模型及问题描述

2.1 相关模型

2.1.1 系统模型

2.1.2 应用模型

2.1.3 功率模型

2.2 最小化调度长度问题描述

2.3 本章小结

第3章能耗约束下最小化调度长度

3.1 MSLECC算法及其局限性

3.1.1 MSLECC算法

3.1.2 MSLECC算法的局限性

3.2 改进的最小化调度长度算法

3.2.1 基于权重机制的预分配策略

3.3 权重机制的可行性

3.4 算法描述

3.5 ISAECC调度应用示例

3.6 实验结果及分析

3.6.1 实验设置

3.6.2 实验结果及分析

3.7 本章小结

第4章能耗约束下最大化可靠性

4.1 可靠性模型

4.2 问题描述

4.3 最大化可靠性算法

4.4 应用示例调度

4.5 实验结果与分析

4.5.1 实验设置

4.5.2 实验结果及分析

4.6 本章小结

第5章时间和能耗约束下最大化可靠性

5.1 问题描述

5.2 时间和能耗约束下最大化可靠性

5.3 应用示例调度

5.4 实验结果及分析

5.4.1 实验设置

5.4.2 实验结果及分析

5.5 本章小结

结论

参考文献

附录A 发表论文和参加科研情况说明

致谢

文章来源

类型: 硕士论文

作者: 叶婷

导师: 全哲

关键词: 异构系统,能耗,并行应用,任务调度,调度长度,可靠性

来源: 湖南大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机硬件技术

单位: 湖南大学

分类号: TP332;O224

DOI: 10.27135/d.cnki.ghudu.2019.002059

总页数: 69

文件大小: 1990K

下载量: 8

异构分布式系统中能量感知的并行应用调度算法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢