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

基于LRSS的可重构任务调度算法研究

作　者: 曹晓磊
导　师: 程东年
学　校: 解放军信息工程大学
专　业: 通信与信息系统
关键词: 可重构任务调度状态切片资源预约相关任务
分类号: TP393.05
类　型: 硕士论文
年　份: 2010年
下　载: 18次
引　用: 0次
阅　读: 论文下载

内容摘要

支持实时动态可重构(Run-Time Partial Reconfigurable, RTPR)功能的可重构器件,具有重复编程和配置特点,不仅能满足多个任务的并行运行,还能使不同的任务以时分复用方式在器件上运行。由于可重构资源规模限制,任务之间对资源的需求存在着竞争关系,为了降低因任务资源分配不合理而造成的对系统吞吐量和任务处理时间等性能的影响,设计高效的资源管理模型及任务调度算法是解决上述问题的有效途径之一。本论文以“十一五”国家863计划项目“可重构路由器构件组研制”为依托,简要回顾了可重构技术历史和发展现状;介绍了任务调度系统的组成、资源模型和任务模型以及调度算法的性能评价指标;重点分析了已有资源管理模型和调度算法的思想及其存在的问题,并得出如下结论:(1)无法实现对资源状态的有效管理;(2)资源预约自私性和调度的盲目性;(3)“重调度轻布局”的调度方式带来较大的调度时延。针对上述问题,分别提出了资源状态切片链表(List of Resource State Slice, LRSS)管理模型、基于离散时间距的任务调度算法和一种相关任务模型的启发式列表调度算法;最后通过仿真实验进行对比,验证了算法的有效性。本文以资源管理模型及任务调度算法为研究内容,主要包括以下几个部分: 1建立了基于事件驱动的LRSS资源管理模型。主要思想是,在将逻辑资源进行矩阵映射的基础上,通过分析任务事件与资源状态关系,定义了状态切片的概念和结构并生成LRSS链表。LRSS中各状态切片以时间顺序排列,并根据任务事件实时更新。系统通过查询切片的状态和时间点来为任务进行预约操作。LRSS管理模型实现了资源状态的离散化表示,不仅有利于降低状态存储冗余,提高匹配查找效率,同时还为后续算法在调度效率上的改进提供了模型基础。2提出了基于离散时间距(Discrete Time-Interval, DTI)的任务调度算法。主要思想是,为了避免任务因FCFS方式预约资源带来的自私性,引入任务紧迫度作为调度决策函数参数,确保紧迫度高的任务优先获取资源。通过计算任务最早结束时间设定调度启动计时器,结合LRSS中切片状态确定调度布局启动时机和预约区域,避免了任务调度的盲目性。仿真实验表明,DTI调度算法在任务的调度成功率及调度效率上取得了较好的改进效果。3提出了一种支持相关任务模型的启发式列表调度算法。算法主要思想是,在以有向无环图描述任务之间约束关系基础上,以路径长度t_level、b_level复合值和任务面积为参数进行加权,计算调度优先级。任务调度过程中,遵循有约束关系任务之间前驱任务优先调度,无约束关系任务之间优先级高的任务优先调度的原则,优化任务调度顺序。仿真实验表明,调度算法在有效避免调度死锁情况下,能够缩短整体任务运行时间,最大可减少15.4%的时间长度。本文从资源管理模型和调度决策函数两方面考虑,对可重构任务调度进行了研究。通过上述分析和仿真实验,基于LRSS资源模型的任务调度算法在降低状态存储冗余、提高任务调度效率和成功率以及缩短整体任务运行时间上取得了较好的改进效果。

全文目录

摘要  9-11
ABSTRACT  11-13
第一章绪论  13-22
  1.1 课题研究背景  13-15
    1.1.1 可重构技术概述  13-14
    1.1.2 课题研究背景  14-15
  1.2 研究现状  15-18
    1.2.1 支持ITM 的调度算法  15-17
    1.2.2 支持RTM 的调度算法  17-18
  1.3 存在的问题  18
  1.4 论文主要工作及结构  18-22
    1.4.1 本文研究思路及主要工作  18-20
    1.4.2 论文组织结构  20-22
第二章可重构任务调度相关技术介绍  22-27
  2.1 可重构任务调度系统  22-23
  2.2 资源模型  23-24
  2.3 任务模型  24-25
    2.3.1 任务模型分类  24-25
    2.3.2 任务调度布局约束准则  25
  2.4 调度算法性能评价指标  25-26
  2.5 本章小结  26-27
第三章基于事件驱动的LRSS 资源管理模型  27-38
  3.1 引言  27-29
  3.2 相关问题分析  29-30
  3.3 LRSS 资源管理模型  30-36
    3.3.1 基本概念  30-31
    3.3.2 LRSS 主要思想  31-33
    3.3.3 状态切片的管理  33-34
    3.3.4 资源匹配实现  34-35
    3.3.5 性能分析  35-36
  3.4 本章小结  36-38
第四章基于离散时间距的任务调度算法  38-50
  4.1 引言  38-39
  4.2 相关问题分析  39-40
    4.2.1 FCFS 调度存在问题  39-40
    4.2.2 “跳跃式”调度布局的可行性分析  40
  4.3 基于DTI 的任务调度算法  40-45
    4.3.1 基本概念  41
    4.3.2 DTI 算法思想  41-45
    4.3.3 DTI 算法步骤  45
  4.4 仿真及性能评估  45-49
    4.4.1 调度成功率  46-48
    4.4.2 算法运行时间对比  48-49
  4.5 本章小结  49-50
第五章一种支持相关任务模型的启发式列表调度算法  50-58
  5.1 引言  50-51
  5.2 问题分析  51-53
    5.2.1 任务模型的DAG 描述  51
    5.2.2 关键路径对调度时延的影响  51-52
    5.2.3 任务大小对调度时延的影响  52-53
  5.3 HPL 调度算法  53-56
    5.3.1 基本定义  53-54
    5.3.2 任务调度决策函数  54
    5.3.3 HPL 调度算法思想  54-55
    5.3.4 算法流程  55-56
  5.4 仿真实验  56-57
    5.4.1 实验设计  56
    5.4.2 实验结果分析  56-57
  5.5 本章小结  57-58
结束语  58-60
参考文献  60-63
作者简历攻读硕士学位期间完成的主要工作  63-64
致谢  64

相似论文

ABC支持型智能QoS保证机制的设计与仿真实现,TP393.02
具有QoS保障的异构网络系统设计与资源预留机制的改进,TN929.5
基于IEEE 802.11的Ad Hoc网络服务质量研究,TN929.5
基于蚁群算法的分层生产调度模型研究与设计,TP311.52
OBS边缘节点调度模块硬件设计与实现,TN929.1
光突发交换网络数据调度算法研究及NS仿真,TN929.1
异构多域环境的全局资源调度技术研究与实现,TP393.07
基于网格的分布式计算环境设计,TP393
移动无线因特网中资源预约机制的研究与仿真实现,TP393.4
网格资源管理中的协同分配问题研究,TP393.01
OBS及LOBS网络边缘节点和核心节点FPGA设计,TN929.1
基于资源容器技术的虚拟机技术研究与实现,TP316
基于预测与预约机制的网格任务调度中间件研究,TP311.52
基于服务属性区分的可重构任务调度研究,TP393.05
多路串口服务器的设计与实现,TP393.05
基于Linux集群系统的负载均衡算法研究及在Webgis中的应用,TP393.05
EIB家庭网关的研究与设计,TP393.05
基于DM6467的视频服务器设计与实现,TP393.05
跨服务器消息发布与推送机制的研究,TP393.05
基于TR-069配置管理的网关的研究与设计,TP393.05
基于TILE Pro64多核处理器的3G服务器视频转码软件设计,TP393.05