基于服务属性区分的可重构任务调度研究
Research on Scheduling Reconfigurable Tasks Based on Service Attribute Differentiated
可重构器件内部的资源规模越来越大,并提供了实时部分动态可重构(Run-Time Partial Reconfiguration, RTPR)功能,支持运行任务在器件中的动态切换过程.利用可重构任务调度系统对器件资源进行有效管理,为任务确定合适的切换时机和布局区域,将使更多任务在器件中并行运行,有利于提高器件的资源利用率,因而可重构任务调度系统对发挥可重构计算性能至关重要.本论文依托"十一五"国家863计划项目《可重构路由器构件组研制》课题,分析了现有的可重构任务调度系统,并得出以下结论:基于任务自身时空属性的调度和布局过程,无法反映前后任务之间服务属性差异,包括紧迫度和依赖关系等服务属性.本文提出了基于服务属性区分的可重构任务调度系统模型,并对该调度系统提出了一种离散预约调度算法;分析了对预约任务进行抢占调度的可行性,并结合任务之间的紧迫度差异,提出了一种支持紧迫度属性区分的预约抢占调度算法;针对存在依赖属性的相依性任务集合,提出了一种基于依赖区分排序的调度算法,并通过提前任务的配置起始时刻,加快任务集合的运行结束时间.本文的主要研究内容包括以下几个方面:1.分析了现有的可重构任务调度系统及其调度算法,指出现有的调度系统以布局器为中心,对任务都采用统一的FCFS(First Come First Served)调度模式,忽略了不同任务之间的服务属性差异;现有的基本调度(Basic Scheduling, BS)算法和预约调度(Planning Scheduling, PS)算法,由于各任务的调度过程相互独立,不但无法反映前后任务的服务属性差异,而且带来任务调度行为的自私性和盲目性,不利于对可重构资源的整体优化利用.2.提出了一种区分服务属性的可重构任务调度系统模型,并给出了本模型的基本组成单元及功能描述.不同于现有的可重构任务调度系统,本系统以调度器为核心,布局器和资源管理器分别在调度器控制下实现任务布局和资源维护过程.基于时域资源切片组成的紧凑型资源管理器,为后续提出的离散预约调度算法提供了前提条件;调度器支持对调度结果的再处理功能,为后续研究预约抢占调度提供了支撑环境.3.提出一种弹性化离散预约(Elastic Discrete Planning, EDP)调度算法.对连续时刻切片组成的资源管理器,证明了对其引入离散预约调度的可行性;对由时域资源切片组成的资源管理器,证明了只需在各切片的初始时刻进行布局;针对孤立的运行启动事件,证明了在调度时可跳过在该事件发生时刻的布局过程.相对于在各活动时刻都布局的Stuffing算法,EDP算法通过对松弛度内的时域资源切片进行分类,生成了潜在布局时刻表(Potential Placing Time List, PPTL),在基于PPTL表的预约调度过程中,避免了在松弛度的所有活动时刻都进行布局.4.提出一种支持紧迫度区分的预约抢占调度(Preemptive Scheduling based on Urgency Differentiated, PSUD)算法.通过对预约抢占的可行性分析,并结合对任务引入的紧迫度定义,采用最大紧迫度优先(Maximum Urgency First, MUF)策略对预约任务进行抢占调度.在抢占调度过程中,利用资源优先策略、建立抢占阈值和失效恢复机制,减少了失效任务再调度次数,从而提高了抢占调度效率.实验表明,相对于BS和PS调度算法,PSUD算法提高了任务调度的整体成功率;在支持抢占调度过程中,EDP算法不但与Stuffing算法的调度效果相同,并缩短了任务的预约调度开销.5.对依赖关系与资源限制下的相依性任务集合,提出一种基于依赖区分排序(Dependance Differentiatting Sequence, DDS)的调度算法.利用有向无环图(Direct Acyclic Graph, DAG)描述任务间的复杂依赖关系,说明了依赖区分排序策略的必要性.基于任务的依赖区分排序,建立了针对相依性任务的三维资源模型,证明了基于PPTL-E表的离散预约算法对相依性任务调度同样有效.实验表明,DDS算法避免了发生任务调度死锁;通过提前任务的配置起始时刻,将有效加快任务集合的运行结束时间.
- 作者：
- 黄万伟
- 学位授予单位：
- 解放军信息工程大学
- 专业名称：
- 通信与信息系统
- 授予学位：
- 博士
- 学位年度：
- 2009年
- 导师姓名：
- 汪斌强
- 中图分类号：
- TP393.05
- 关键词：
- 可重构任务调度；调度系统模型；预约调度；抢占调度；有向无环图
- Reconfigurable Task Scheduling；Scheduling System Module；Planning Scheduling；Preemptive Scheduling；Direct Acyclic Graph