基于动态优先级策略的最优软非周期任务调度算法

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向 通过定义“调度”和“逆调度” ,对实时周期任务集在使用EDF算法调度时的可挪用时间进行分析 ,求出了周期任务集在使用EDF调度时的最大可挪用时间 在此基础上 ,提出用于缩短非周期任务响应时间和周转时间的调度算法———ISA(idlestealingalgorithm) ISA算法充分使用最大可挪用时间 ,在保证周期任务满足最后期限的同时能取得非周期任务的最优响应时间和周转时间 证明了ISA算法的最优性 ,并使用仿真实验进行了性能验证     

多处理器环境中基于节能及容错的实时动态调度算法

当前处理器由于较高的能量消耗,导致处理器热量散发的提高及系统可靠性的降低,同时任务实际运行中的错误也降低了系统的可靠性.因此同时满足节能性及容错性已经成为目前计算机领域较为关心的问题.提出的调度算法针对实时多处理器计算环境,以执行时间最短的任务优先调度为基础,结合其他有效技术(共享空闲时间回收及检查点技术),使得实时任务在其截止期内完成的同时,能够动态地降低整个系统的能量消耗及动态容错.针对独立任务集及具有依赖关系的任务集,提出两种算法:STFBA1及STFBA2(shortest task first based algorithm).通过实验与目前所知的有效算法相比,算法具有更好的性能(调度长度及能量消耗)及较低的通信时间复杂度.     

一种高回报的最小空闲时间优先实时调度改进算法

信号任务调度算法是提高信息物理系统执行效能的关键,而最小空闲时间优先算法(LSF)、最早截止时间优先算法(EDF)和最大价值优先算法(HVF)在系统满载的情况下无法很好地完成任务调度并且系统能耗很高。为此,提出一种改进型调度算法。将任务能耗、任务完成价值和任务紧迫程度相结合,通过引入任务调度优先级和任务实际调度优先级的形式,实现任务的动态调度。实验结果表明,对于同一个任务集,在完成相同调度任务数量的情况下,改进算法的系统能耗小于采用LSF算法和EDF算法的系统能耗。系统满载时,在完成任务总价值相同的情况下,采用改进算法的系统所需要的能耗比HVF算法更少。     

混合粒子群算法在ETV调度优化中的应用

为了提高机场货运区(Elevating Transfer Vehicle,ETV)转运效率,建立以最小化任务集调度时间为优化目标的调度模型,提出一种混合的粒子群算法对ETV调度问题求解。算法对加速因子采取动态的自适应调整策略;采用混沌序列替代标准粒子群中的随机数;建立平均粒距、适应度方差和汉明距离相结合的早熟判断机制并采用混沌算子扰动微粒的位置来跳出局部最优。通过实例验证和遗传算法、模拟退火等经典的优化算法以及非线性学习因子粒子群、混沌粒子群等改进的粒子群算法相比,该算法在ETV调度最优序列的求解中收敛速度快,全局寻优能力强,稳定性好;和传统的链式调度算法相比,平均调度任务时间减少了15.6%,较好地解决了ETV转运效率低的问题。     

一种基于优先级表的实时调度方法

针对单处理器实时系统动态调度问题进行了研究,分析任务的到达时间、执行时间、截止时间和空闲时间等任务属性的敏感度和影响度,提出了一种基于优先级表的调度算法PTBM,使相对截止期越小、空闲时间越大的任务优先级越高。对关于实时任务属性敏感度和影响度的结论验证和与传统的EDF、LLF和PTD算法的对比进行仿真实验,仿真结果表明基于优先级表设计的实时调度算法PTBM具有较高的调度成功率。该方法可应用于实时系统的实时任务的动态调度中。     

众核处理器系统核资源动态分组的自适应调度算法

针对众核处理器系统的核资源优化使用问题,提出了一种支持核资源动态分组的自适应调度算法CASM(core-partitioned adaptive scheduling for many-core systems).该算法通过对任务簇的拆分与合并,动态构建可弹性分区的核逻辑组,实现核资源的隔离优化访问.为了平衡核资源利用率及任务调度效率,CASM算法针对任务簇间和簇内的不同特点,分别采用公平性较好的均衡调度算法和资源利用率较高的自适应调度算法.在线竞争理论分析表明,CASM算法的任务执行时间在线竞争比为常数2,其性能可扩展性较好.实验结果表明,与WS(work-stealing),AGDEQ(adaptive greedy dynamicequi-partitioning)和EQUI°EQUI算法相比,CASM算法使任务集运行时间分别减少了近46％,32％和15％.在相同能耗情况下,CASM算法大幅度地提升了系统吞吐量.     

多机异构相关任务集的调度优化研究

本文首先介绍了异构相关任务集的概念,在实现子任务优化调度的前提下,基于相同处理机(identical processors)并根据多目标优化策略,提出了AOSA调度算法,构成多机相关任务集的优化调度方法。实验表明:(1)AOSA方法优于随机非AOSA方法对异构任务集的调度;(2)理论准则与实验结果一致。     

基于辅助队列的硬实时混合任务节能调度算法

节能调度是当今实时系统研究的一个重要领域,其中混合实时任务节能调度技术研究刚刚起步.OLDVS算法是非常简洁的硬实时系统在线节能调度算法,但存在以下不足:不适应任务执行的动态变化,不能有效利用动态松弛时间,过于保守以致节能效果并不理想.据此,提出一种新的基于辅助队列的硬实时混合任务节能调度算法(OLDVS-AQ).通过引入一个额外的数据结构即辅助队列(Assisted Queue,AQ)来计算任务的最大完成时间,能够更有效地利用动态松弛时间进一步降低能耗.证明了该算法的可调度性,仿真实验结果表明,OLDVS-AQ算法始终优于OLDVS算法.平均提高约10%的节能效果.     

具有温度感知特性的实时调度研究

处理器温度的上升严重危害着处理器的性能。DTM（Dynamic Thermal Management）是一种硬件层面的热管理机制,它会带来一定的性能损失。提出了一种操作系统层面的针对实时任务的动态热管理机制——LTEDF（Low Thermal Early Deadline First）。LTEDF通过在线实时获取性能计数器的值,计算处理器当前温度来动态调度队列中的线程,提出了MST（Maximum Scheduling Threshold）启发式方法。基于HotSpot温度模型对算法进行了仿真实验,结果显示,该算法不仅可以满足任务的时间限制而且可以满足温度限制,并且较传统的EDF（Early Deadline First）LTEDF算法可以创建更加统一的功率密度图,MST启发式算法可以明显减少线程迁移带来的开销。     

物联网环境下具有顺序约束关系的静态任务表调度算法

针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。     

基于网格的两级动态负载平衡算法

网格系统具有异构性、动态性和分布性的特点,且资源数量巨大,这使得网格中的任务调度十分复杂.针对网格的特点,在两级树型网格结构的基础上,设计了一种基于该结构的两级负载平衡算法,针对传统的负载平衡算法考虑资源因素单一,难以满足复杂的网格环境的要求,该算法使用了多种负载参数来衡量网格节点的负载状况.     

网络管理中多agent的半在线调度算法

多agent调度算法在基于多agent的网络管理中对任务执行效率起着至关重要的作用.现有的多agent调度算法由于缺乏考虑任务间的依赖关系,使得面对复杂任务系统时会产生大量的网络负载和等待时间.为此,在建立一个适合网络管理任务特点的多agent调度框架的基础上,提出了一种基于任务依赖关系的多agent半在线调度算法.理论分析和测试结果表明,这种半在线调度算法优于已有的全在线调度算法,其性能更接近离线最优调度算法,从而为网络管理任务中多agent的动态调度提供了一种新的途径.     

基于分类矩阵的决策树算法

为了提高决策树分类的速度和精确率,提出了一种基于分类矩阵的决策树算法.介绍了ID3算法的理论基础,定义了一种分类矩阵,指出了ID3算法的取值偏向性并利用分类矩阵给出了证明.在此基础上,引入了一个权重因子,抑制了原有算法的取值偏向,并利用分类矩阵给出相应证明,同时根据基于分类矩阵增益的特点,提出了新的决策树分类方案,旨在运算速率上进行优化,与原有算法进行了实验比较.对实验结果分析表明,优化后的方案在性能上有明显改善.     

嵌入式并行系统中基于任务优化的调度算法

在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关任务优化(DTO)的调度算法,通过分析已用处理机的负载和空闲时间,尽量减少系统的调度长度和处理机数目。算法分析结果表明,DTO算法在性能上优于其他算法,对嵌入式并行计算系统中的多任务调度是一个较好的选择。     

多核系统中基于Global EDF 的在线节能实时调度算法

随着多核系统能耗问题日益突出,在满足时间约束条件下降低系统能耗成为多核实时节能调度研究中亟待解决的问题之一.现有研究成果基于事先已知实时任务属性的假设,而实际应用中,只有当任务到达之后才能够获得其属性.为此,针对一般任务模型,不基于任何先验知识提出一种多核系统中基于Global EDF在线节能硬实时任务调度算法,通过引入速度调节因子,利用松弛时间,结合动态功耗管理和动态电压/频率调节技术,降低多核系统中任务的执行速度,达到实时约束与能耗节余之间的合理折衷.所提出的算法仅在上下文切换和任务完成时进行动态电压/频率调节,计算复杂度小,易于在实时操作系统中实现.实验结果表明,该算法适用于不同类型的片上动态电压/频率调节技术,节能效果始终优于Global EDF算法,最多可节能15％～20％,最少可节能5％～10％.     

实时异构系统的动态分批优化调度算法

提出了一种实时异构系统的动态分批优化调度算法,该算法采用的是在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上的运行综合各种因素构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都分配一个处理器或为每个处理器分配一项任务,使得这种分配具有最好的“合适性”,以增大未被调度任务的可行性.这种方法有效地提高了算法调度成功率.同时,为了评估该算法的性能,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与老算法的调度成功率进行了比较.模拟结果显示,新算法优于老算法.     

Energy aware fixed priority scheduling in mixed-criticality systems

Most of studies about energy management for MC systems are based on dynamic priority scheme. The disadvantages of dynamic priority scheme are high system overhead and poor predictability. Unlike previous studies, we focus on the problem of scheduling mixed-criticality (MC) periodic tasks with minimizing energy consumption in MC systems based on fixed priority scheme. Firstly, we explain a criticality rate monotonic scheduling (CRMS) and propose the sufficient schedulability condition of CRMS. Secondly, we compute the energy minimization uniform scaled speed and present an optimal static solution algorithm based on CRMS. The extra workload of the high criticality level (HI) task executes with the maximum processor speed in the high criticality mode (HI-mode). But this algorithm does not exploit the slack time generated from the HI task in the low criticality mode (LO-mode). For energy efficiency, we propose a dynamic fixed priority energy minimization algorithm which exploits the slack time generated from the HI task in LO-mode to save energy. In addition, it combines a dynamic voltage and frequency scaling technique and a dynamic power management technique to reduce energy consumption. Finally, the experiments are applied to evaluate the performance of the proposed algorithm and the experimental results show that the proposed algorithm can save up 23.89% energy compared with other existing algorithms.     

基于多片FPGA的双优先级动态调度算法

针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法。根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段; 对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度。实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率。     

Finding Optimal Ordering of Sparse Matrices for Column-Oriented Parallel Cholesky Factorization

In this paper, we consider the problem of finding fill-preserving sparse matrix orderings for parallel factorization. That is, given a large sparse symmetric and positive definite matrix A that has been ordered by some fill-reducing ordering, we want to determine a reordering that is appropriate in terms of preserving the sparsity and minimizing the cost to perform the Cholesky factorization in parallel. Past researches on this problem all are based on the elimination tree model, in which each node represents the task for factoring a column, and thus, can be seen as a coarse-grained task dependence model. To exploit more parallelism, Joseph Liu proposed a medium-grained task model, called the column task graph, and showed that it is amenable to the shared-memory supercomputers. Based on the column task graph, we devise a greedy reordering algorithm, and show that our algorithm can find the optimal ordering among the class of all fill-preserving orderings of the given sparse matrix A.