面向系统负载的分段式实时调度算法及其实现

实时调度算法是实时系统中的关键技术,实时任务能否在规定的时限内完成主要依赖于调度算法的优劣.本文提出了一种分段式实时调度算法SS(Sectional Scheduling),此算法根据系统负载强度的不同将系统负载划分为三种情况:正常负载,超载和严重超载,每一种情况采用不同的调度算法.模拟实验表明,在所有负载条件下该算法相对于典型的EDF(Earliest Deadline First)算法,HVF(Highest Value First)算法与HVDF(Highest Value Density First)算法都有很大的性能改进.     

单步预测的单机调度算法及其仿真分析

调度问题中在线算法只能够利用已经到达的工件信息进行调度,但在实际生产中,往往有可能预知即将到达的未来工件信息,并且利用信息进行决策.针对经典单机加权完工时间调度问题,根据预测控制的思想,提出了一种单步预测调度的算法,并且分别在理论证明和仿真两方面进行了分析.对单步预测调度算法进行了性能分析,在理论上证明了预测调度算法的竞争比下界为2,对于一般的情况进行了大鼍的仿真比较,由于在调度中增加了未来信息,单步预测调度算法的调度结果优于在线调度算法.     

可重构系统中的实时任务在线调度与放置算法

有效的任务调度与放置是发挥可重构计算性能优势的重要因素.针对实时任务在二维可重构器件上的在线调度问题,定义了调度算法完全识别的概念,即算法不会拒绝能够成功调度的任务.提出了新的实时在线调度与放置算法,充分利用了任务的时间信息,实现了完全识别的调度.实验表明,与已有的算法相比,新算法显著地改善了调度效果,而运行开销没有明显增加.     

一种基于EDF算法的多处理器实时调度算法

多处理器系统实时调度理论是目前实时系统研究的热点问题。EDF调度算法是目前流行的实时调度算法,有很多优点,但在多处理器系统应用中存在问题。论文研究了EDF调度算法在多处理器系统中的调度理论,在此基础上,提出了一种基于EDF算法的优先级驱动实时调度算法,算法充分利用了EDF调度算法的优点,较大程度地克服了EDF算法在多处理器系统中的调度缺点,并提供了较好的实时调度性能。     

RM及其扩展可调度性判定算法性能分析

可调度性判定是实时调度算法的关键问题·单调速率算法RM(ratemonotonic)及其扩展是应用广泛的实时调度算法,大量文献讨论了实时任务在这些算法下的可调度性判定,给出了相应的判定算法·但迄今为止,对这些判定算法的性能分析都是理论上的定性分析或者只是少数几种判定算法之间的简单比较,这不利于实时系统的开发·归纳了RM及其扩展的可调度性判定算法,通过测试平台,系统地测试和分析了各算法的性能和适用场合,讨论了各种条件和实现方式对算法性能和可调度性的影响·     

一种实时进程调度算法的研究

在实时系统中,进程调度算法性能的好坏直接对系统的实时性起着决定性的作用。因此,该文介绍实时调度和进程调度算法的相关定义,对常见的动态优先级调度算法和静态优先级调度算法的不足之处进行了解析。据此提出了一种基于优先级的动态分配策略(Dynamic allocation strategy based on priority)的进程调度算法。     

软件容错模型中的容错实时调度算法

在软件容错模型的容错实时调度算法中,主部分可执行性的预测精度是影响调度算法性能的关键.针对此问题提出了DPA(deep-prediction based algorithm)和EDPA(EDF-based DPA)算法.算法考虑当前时间至替代部分通知时间之间的任务执行情况,通过构建预测表对待执行主部分的可执行性进行精确预测.当主部分不发生错误时算法根据预测表调度任务. DPA依照预测表中通知时间的先后顺序调度主部分,而EDPA则按照EDF算法调度预测表中的主部分.模拟结果表明,DPA和EDPA较目前同类算法可获得更多的主部分执行时间,降低CPU的消耗.当软件错误率较低、任务周期较短时,算法能够以较小的调度开销获得较高的调度性能.     

混合型实时容错调度算法的设计和性能分析

以往文献中研究的实时容错调度算法都只能调度单一的具有容错需求的任务.该文建立了一个混合型实时容错调度模型,提出一种静态实时容错调度算法.该算法能同时调度具有容错需求的实时任务和无容错需求的实时任务.该文还提出了一个求解最小处理机个数的算法,用于对静态实时容错调度算法的性能进行模拟分析.为了提高静态调度算法的调度性能,提出了一种动态调度算法.最后,通过模拟实验分析了静态和动态调度算法的性能.实验表明,调度算法的性能与实时任务的个数、任务的计算时间、周期和处理机个数等系统参数相关.     

带等级约束的多重工件在线(半在线)排序问题

论文提出了带等级约束的多重工件排序问题,每个客户提交多个加工时间和等级相同的工件。目标是寻找一个调度方案,使得机器的最大完工时间最小。当客户的信息未知时,论文设计了一个竞争比为5/3的在线算法。当所有工件的加工时间总和已知时,论文设计了一个竞争比为3/2的半在线算法。这些结论对经典带等级约束的两台平行机排序问题进行了推广。     

温度感知的Linux多核调度算法研究

多核处理器温度升高会影响芯片的稳定性和性能的发挥,硬件层面的DTM(Dynamic Thermal Management)方法以牺牲处理器性能为代价来降低功耗,提出了在一种软件层面的温度感知调度算法,它可以在线实时获取处理器性能计数器的值并计算各个执行核温度,根据各执行核的温度状况在各个核上合理分配进程,给出了温度感知的启发式方法。基于ATMI温度仿真器的仿真表明,温度感知调度算法较无温度感知的算法可以创建更均匀的功率密度图,且带MST启发式方法的温度感知调度算法能明显减少进程的迁移次数。     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。     

Adaptively scheduling parallel loops in distributed shared-memorysystems

Using runtime information of load distributions and processor affinity, the authors propose an adaptive scheduling algorithm and its variations from different control mechanisms. The proposed algorithm applies different degrees of aggressiveness to adjust loop scheduling granularities, aiming at improving the execution performance of parallel loops by making scheduling decisions that match the real workload distributions at runtime. They experimentally compared the performance of the algorithm and its variations with several existing scheduling algorithms on two parallel machines: the KSR-1 and the Convex Exemplar. The kernel application programs used for performance evaluation were carefully selected for different classes of parallel loops. The results show that using runtime information to adaptively adjust scheduling granularity is an effective way to handle loops with a wide range of load distributions when no prior knowledge of the execution can be used. The overhead caused by collecting runtime information is insignificant in comparison with the performance improvement. The experiments show that the adaptive algorithm and its five variations outperformed the existing scheduling algorithms     

基于扩展的随机DAG的EST估算与任务调度

针对DAG调度算法中采取多次执行后的平均值估算任务的EST值问题,通过对DAG调度中常用的调度算法ETF算法进行分析提出基于扩展的随机DAG的调度方法SETF,给出扩展的随机DAG中节点的EST计算方法,以标准方差和平均值之和的数学期望表示,并以ETF算法为例进行实验模拟。实验结果表明,SETF算法相对于ETF算法,减少并行任务执行时间,并能更精确地预测任务调度的平均执行时间。     

三台机并行工件排序问题的改进的下界

与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。     

DAG任务图的一种调度算法

并行程序的调度技术是开发并行计算机系统的计算潜能的关键问题。本文讨论了4种典型的调度算法的缺陷，提出了一种新的调度算法CPFMBF，它采用的策略是：优先调度关键路径节点，其次调度b-level值大的节点，再次调度节点的关键路径影响度大的节点。对照分析及在几种具代表性的工程应用任务图上的实验结果证明CPFMBF算法的调度性能普遍好于其它算法。     

异构并行平台的Caffe推理速度提升方法

随着计算机硬件性能的提高,目前在个人终端上也开始出现使用预训练机器学习模型进行推理的运用.Caffe是一款流行的深度学习框架,擅长图像分类等任务,但是在默认状态下只能单核运行,无法充分发挥异构并行计算设备的计算能力.深度学习对于计算性能的要求较高,如果能并行化以充分使用所有计算设备,就能提升计算速度和使用体验.由于CPU和GPU的计算性能之比在不同模型下存在差异,因此不能简单将任务均分到多个计算设备.而任务拆分过多或者需要等待多设备完成任务后同步的调度算法会引入更多开销.因此,还需要设计合适的调度算法减少设备空闲时间,才能获得更好的性能.已有一些提高Caffe并行表现的方法,但是对于具体平台有限制且使用难度较高,无法简单充分利用异构并行计算设备的计算能力.本文将Caffe接口扩展,使得自定义程序可以调用异构并行平台的多核或多计算设备使用Caffe进行深度学习推理.接着将目前已有的多种调度算法运用到此类任务上并考察了运行效果.为了减少已有调度算法的同步开销,本文提出了先进先出调度和快速分块调度两种新的算法.测试表明,使用快速分块调度算法结合异构并行计算设备,Caffe的推理速度相比只使用单个CPU核心或者单个GPU都大幅提升.而且,相比已有调度算法中表现最好的HAT算法,本文提出的快速分块调度算法在MNIST和Cifar-10两个数据集上分别减少了7.4%和21.0%的计算性能浪费.     

Optimizing layer‐based scheduling algorithms for parallel tasks with dependencies

Programming with parallel tasks leads to task graphs with dependencies representing a parallel program. Scheduling algorithms are employed to find an efficient execution order of the parallel tasks. A large variety of scheduling algorithms exist, including layer‐based scheduling algorithms for homogeneous target platforms that build consecutive layers of independent parallel tasks and schedule each layer separately. Although these scheduling algorithms provide good results in terms of scheduling algorithm runtime and schedule execution time, the resulting schedules leave room for optimization. This article proposes an optimization for arbitrary layer‐based scheduling algorithms, which is called Move‐blocks algorithm. Given a layer‐based schedule of the parallel tasks, this algorithm moves blocks of parallel tasks into preceding layers in order to reduce the overall execution time of a task‐based application. Suitable blocks of parallel tasks are identified by the algorithm Find‐blocks, which is employed together with the Move‐blocks algorithm. The algorithm Move‐blocks is applied to four well‐known scheduling algorithms. A detailed evaluation for a wide range of test cases is given. Copyright © 2010 John Wiley & Sons, Ltd.     

Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems

Earliness/tardiness scheduling problems with undetermined common due date which have wide application background in textile industry, mechanical industry, electronic industry and so on, are very important in the research fields such as industry engineering and CIMS. In this paper, a kind of genetic algorithm based on sectional code for minimizing the total cost of assignment of due date, earliness and tardiness in this kind of scheduling problem is proposed to determine the optimal common due date and the optimal scheduling policy for determining the job number and their processing order on each machine. Also, simulated annealing mechanism and the iterative heuristic fine-tuning operator are introduced into the genetic algorithm so as to construct three kinds of hybrid genetic algorithms with good performance. Numerical computational results focusing on the identical parallel machine scheduling problem and the general parallel machine scheduling problem shows that these algorithms outperform heuristic procedures, and fit for larger scale parallel machine earliness/tardiness scheduling problem. Moreover, with practical application data from one of the largest cotton colored weaving enterprises in China, numerical computational results show that these genetic algorithms are effective and robust, and that especially the performance of the hybrid genetic algorithm based on simulated annealing and the iterative heuristic fine-tuning operator is the best among them.     

Competitive online adaptive scheduling for sets of parallel jobs with fairness and efficiency

We study online adaptive scheduling for multiple sets of parallel jobs, where each set may contain one or more jobs with time-varying parallelism. This two-level scheduling scenario arises naturally when multiple parallel applications are submitted by different users or user groups in large parallel systems, where both user-level fairness and system-wide efficiency are of important concerns. To achieve fairness, we use the well-known equi-partitioning algorithm to distribute the available processors among the active job sets at any time. For efficiency, we apply a feedback-driven adaptive scheduler that periodically adjusts the processor allocations within each set by consciously exploiting the jobs’ execution history. We show that our algorithm achieves asymptotically competitive performance with respect to the set response time, which incorporates two widely used performance metrics, namely, total response time and makespan, as special cases. Both theoretical analysis and simulation results demonstrate that our algorithm improves upon an existing scheduler that provides only fairness but lacks efficiency. Furthermore, we provide a generalized framework for analyzing a family of scheduling algorithms based on feedback-driven policies with provable efficiency. Finally, we consider an extended multi-level hierarchical scheduling model and present a fair and efficient solution that effectively reduces the problem to the two-level model.