学位论文 > 优秀研究生学位论文题录展示

基于提前预留的backfill并行调度优化模型和算法研究

作　者: 李丽娟
导　师: 李波
学　校: 云南大学
专　业: 通信与信息系统
关键词: 网格计算并行调度提前预留算法实验仿真
分类号: TP393.01
类　型: 硕士论文
年　份: 2011年
下　载: 10次
引　用: 0次
阅　读: 论文下载

内容摘要

网格计算环境为实现各种资源的共享提供了条件。提前预留是网格资源预留机制的重要组成部分。通过采用提前预留方法,可以使作业在未来某个时间段内获得协定的资源和服务质量。随着高性能计算技术的不断发展,单处理机由于受到自身计算速度的限制,已经无法满足那些对计算速度有较高要求的应用问题,对于比较复杂的大型工程计算问题和实时性上有较高要求的应用问题,必须在并行处理机上通过并行算法才能求解,所以并行调度显得越来越重要。本文在现有支持预留的网格资源管理和调度技术的基础上,研究了并行调度过程中常用的Easy backfill算法和Conservative backfill算法,并提出新的backfill策略和backfill预留策略,建立了相应的调度优化模型一二维装箱模型。无论是Easy backfill算法还是Conservative backfill算法,都包括backfill策略和backfill预留策略。现有的backfill策略每次只选择一个作业进行回填,没有考虑多个作业的组合,也没有考虑回填作业与当前可用资源的匹配情况。针对以上backfill策略的不足,本文中提出了新的backfill策略—JCO策略,该策略每次选择多个作业进行回填,并根据当前空闲区域的大小来选择回填作业。原有的backfill预留策略都是选择作业能够开始执行的最早时间预留资源,这样的预留策略没有考虑预留作业对空闲资源的影响,会产生很多资源碎片,导致系统的利用率很低。针对以上backfill预留策略的不足,本文提出了新的backfill预留策略—OSTP策略,该策略充分考虑了backfill预留作业对空闲资源的影响,总是选择最佳的时间点预留作业。通过实验仿真验证了backfill策略的可行性,分析了不同预留深度对资源平均利用率、作业平均等待时间和作业平均减缓的影响,比较了各种backfill策略在不同性能参数下的差异。

全文目录

摘要  3-4
Abstract  4-6
目录  6-8
第一章绪论  8-13
  1.1 研究背景和现状  8-10
    1.1.1 研究背景  8
    1.1.2 研究现状  8-10
  1.2 课题的提出、目的和意义  10-11
  1.3 研究目标和研究内容  11-12
    1.3.1 研究目标  11
    1.3.2 研究内容  11-12
  1.4 论文的组织结构  12-13
第二章综述  13-25
  2.1 并行调度的研究现状  13-15
  2.2 提前预留的研究现状  15-19
    2.2.1 严格请求的提前预留  15-16
    2.2.2 非严格请求的提前预留  16-17
      2.2.2.1 支持松弛时间的提前预留  16
      2.2.2.2 弹性预留  16-17
      2.2.2.3 模糊请求的提前预留  17
    2.2.3 提前预留算法  17-19
  2.3 维装箱问题的研究现状  19-21
    2.3.1 分层算法  19-20
    2.3.2 不分层算法  20-21
    2.3.3 其他的算法  21
  2.4 网格计算中的装箱模型  21-23
  2.5 小结  23-25
第三章基于提前预留的backfill调度优化模型和算法  25-38
  3.1 问题的描述  25-26
  3.2 二维装箱模型  26-27
  3.3 支持资源预留的backfill调度算法  27-37
    3.3.1 支持资源预留的Easy backfill调度算法  27-28
    3.3.2 支持资源预留的Conservative backfill调度算法  28-29
    3.3.3 作业组合优化backfill策略  29-34
    3.3.4 最优开始时间点backfill预留策略  34-37
  3.4 小结  37-38
第四章实验仿真  38-44
  4.1 实验仿真环境介绍  38-40
    4.1.1 仿真平台体系结构  38-39
    4.1.2 仿真实体  39
    4.1.3 性能参数  39-40
  4.2 实验结果及分析  40-43
    4.2.1 不同backfill策略的资源平均利用率  40-41
    4.2.2 不同backfill策略的作业平均等待时间  41-42
    4.2.3 不同backfill策略的作业平均减缓  42-43
  4.3 小结  43-44
第五章总结和展望  44-46
  5.1 总结  44
  5.2 展望  44-46
参与项目情况与主要研究成果  46-47
参考文献  47-51
致谢  51

基于提前预留的backfill并行调度优化模型和算法研究

内容摘要

全文目录

相似论文