一种MapReduce实时调度算法设计及实现

MapReduce是云计算中重要的批数据处理框架,多任务共享MapReduce机群并满足任务实时性要求是调度算法急需解决的问题。提出两阶段实时调度算法,将调度划分为任务间调度和任务内调度。对于任务间调度,使用抽样法和经验值法确定子任务执行时间,利用该参数建立资源分配模型,动态确定任务优先级进行调度;对于子任务使用延迟调度策略进行调度,保证计算的本地性。实验结果显示,两阶段实时调度算法相比公平调度算法和FIFO算法,在保证吞吐量的同时能够满足任务实时性要求。     

满足实时云任务需求的主动响应式工作流调度模型

为了改善云平台中多工作流调度时的执行代价和资源利用率,提出一种满足实时云任务需求的主动响应式工作流调度算法.该算法可以分别针对新工作流的到达、任务完成后的虚拟机资源提供、紧迫任务到达等做出主动的实时响应调度策略,从而充分利用虚拟机资源的空闲时槽和更大化的任务并行程度,以混合形式调度来自不同工作流的任务.在确保截止期限约束的同时,有效满足实时云任务的调度需求.大量实时工作流的仿真测试表明,与另外几种同类型算法相比,该算法不仅可以降低任务执行代价,而且可以得到更高的资源利用率,实现算法预期效果.     

基于局部关键路径与截止期限分配的云工作流调度算法

为了解决云计算中截止期限约束下的工作流调度代价优化问题,提出一种基于局部关键路径和截止期限分配的工作流任务调度算法。为了满足期限约束,并最小化执行代价,算法将工作流任务的调度过程划分为两个阶段:期限分配阶段和调度资源选择阶段。期限分配阶段定义工作流的局部关键路径,并以递归的方式在局部关键路径上的任务间进行子期限分配;调度资源选择阶段在满足任务子期限的同时,为每个任务选择执行代价最低的资源进行任务调度,以实现调度代价优化。分析算法的时间复杂度,并通过一个算例对算法的实现思路进行了详细阐述。通过科学工作流结构的仿真实验,证明了算法不仅可以满足截止期限约束,而且可以降低工作流任务的执行代价。     

通用调度框架的改进及其在Linux中的实现

在嵌入式Linux实时系统中,要求内核对不同时问约束的任务采用不同的调度算法.但目前Linux内核采用单一的实时调度模式,不能灵活地执行多种调度算法,也就无法满足实时系统中实时任务的时间约束.引入了一种能够在Linux内核调度中执行多种调度算法的框架,即通用调度框架(GSF),并改进了其中的多算法调用机制,从而更好地在Linux内核中实现GSF.     

一种多重约束下确保成功率的云工作流调度方法

为提高多重约束下的调度成功率,提出一种满足期限和预算双重约束的云工作流调度算法。将可行工作流调度方案求解分解为工作流结构分层、预算分配、期限分配、任务选择和实例选择。工作流结构分层将所有工作流任务划分层次形成包任务,以提高并行执行程度;预算分配对整体预算在层次间进行分割;期限分配将全局期限在不同层次间分割;任务选择基于任务最早开始时间确定优先级,得到任务调度次序;实例选择根据时间和代价均衡因子,获取任务执行最佳实例。仿真结果证明,该算法在调度成功率、同步优化工作流执行时间与执行代价上相较对比算法更好。     

实时异构系统中的积极复制容错调度算法

在设计实时异构系统中的容错调度算法时,既要考虑到实时性的约束,又要最大化系统的可靠性.此外,异构系统中的并行应用调度问题已经被证明了是NP完全问题.现有的容错调度算法大多采用复制技术来提升系统的可靠性,但是任务的多次执行会导致应用执行时间变长,系统实时性下降.为此,提出了一个基于积极复制技术的容错调度算法,该算法连续的复制任务集中对当前系统实时性影响最小的任务,然后将任务集中的所有任务调度至最早完成的处理器,用以在满足实时性约束的同时,提升系统的可靠性.实验表明,相比于同样着眼于实时异构系统的DB-FTSA算法,该算法在实时性约束严格的情况下,可靠性有较大提升.     

多目标最优化云工作流调度进化遗传算法

为了实现云环境中科学工作流调度的执行跨度和执行代价的同步优化,提出了一种多目标最优化进化遗传调度算法MOEGA。该算法以进化遗传为基础,定义了任务与虚拟机映射、虚拟机与主机部署间的编码机制,设计了满足多目标优化的适应度函数。同时,为了满足种群的多样性,在调度方案中引入了交叉与变异操作,并使用启发式方法进行种群初始化。通过4种现实科学工作流的仿真实验,将其与同类型算法进行了性能比较。结果表明,MOEGA算法不仅可以满足工作流截止时间约束,而且在降低任务执行跨度与执行代价的综合性能方面也优于其他算法。     

基于裁剪的弱硬实时调度算法

针对当前弱硬实时调度算法无法保证超过窗口长度的执行序列的满足率达到一定比例的问题,基于(m~-,p)弱硬实时约束,提出了一种基于裁剪的调度算法(cut-down based scheduling,简称CDBS).由于判断(m~-,p)约束是否满足需要遍历任务的整个执行序列,因此判断复杂度很大.为此,提出一种高效的裁剪执行序列的算法,同时证明其正确性,并利用适当的数据结构,使得计算复杂度与序列长度无关,通过实验说明其降低计算复杂度的有效性.进一步与其他经典实时调度算法(EDF(earliest deadline first),DBP(distance-based priority),DWCS(dynamic window constraint schedule))进行比较,验证该算法与其他算法具有相当的性能.     

基于遗传算法的多模式资源约束项目调度问题研究*

为解决多模式资源约束项目调度问题,提出了一种混合遗传算法的求解方法。该算法采用二维编码方法来表示问题的解,基因的值表示任务的优先权和执行模式,每条染色体对应一个满足逻辑关系约束的可行任务排序,根据染色体所对应的任务调度顺序和执行模式序列可以获得一个满足资源约束的项目调度方案。应用该编码方法进行选择、交叉和变异等遗传操作,能够使搜索范围遍及整个问题解空间。实际应用表明,该算法能快速求得问题的最优解或近似最优解。     

FF现场总线系统中实时任务的建模与调度

本文研究了单网段 FF现场总线系统中具有时间约束和次序约束的实时任务，即 功能块任务和通信任务的建模与调度．首先，将功能块任务和通信任务等视为相同的任务， 在只考虑任务间次序约束的情况下，提出了基于紧凑模式的任务模型，以保证每个作业被尽 可能早地完成．其次，考虑单网段通信任务共享一个传输介质而引起的通信超时，提出了基 于作业速率单调优先级算法的扩展紧凑模式的任务调度算法，以满足实时任务的时间约束 和次序约束．最后，通过一个应用实例来描述实时任务的调度过程．     

Average-case performance analysis of scheduling random parallel tasks with precedence constraints on mesh connected multicomputer systems

We investigate the problem of scheduling parallel tasks with precedence constraints on mesh connected multicomputer systems. It is still an open problem on whether there exists an approximation algorithm with finite asymptotic worst-case and/or average-case performance bound for this scheduling problem. As an early attempt to solve our problem, we propose and analyze the performance of a level-by-level scheduling algorithm LL. In fact, we solve a special case of the problem when all tasks request for square submeshes and run on a square mesh system whose size is a power of 2. There are three basic techniques in algorithm LL, i.e., the level-by-level scheduling strategy for handling precedence constraints, the largest-task-first algorithm for scheduling tasks in the same level, and the two-dimensional buddy system for system partitioning and processor allocation. Algorithm LL does not have a finite worst-case performance bound; however, it has quite acceptable average-case performance. The main contribution of the paper is to show that under the assumptions that task sizes are independent and identically distributed (i.i.d.) random variables with a common probability distribution, and that task execution times are i.i.d. random variables with finite mean and variance, and that the probability distributions of task sizes and execution times are independent of each other, for wide task graphs and typical task size distributions, algorithm LL has an asymptotic average-case performance bound about two for all probability distributions of task execution times.     

异构分布式系统中一种新型主副版本调度算法

针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，提出一种新型高可靠性主副版本调度算法（HRPB）。任务模型以有向无环图（DAG）表示，该算法共计调度主、副两个版本的任务。在任务优先级排序阶段，根据任务执行时间及截止时限来制定新指标平均最晚开始时间（ALST）进行排序；在任务处理器分配阶段，采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，并且改进了副版本调度时的可靠性指标计算方法。通过随机生成DAG图进行算法仿真测试，实验结果表明，HRPB比eFRD具有更优的副版本调度成功率、更高的系统可靠性。     

On a parallel machine scheduling problem with precedence constraints

We characterize a nontrivial special case with a polynomial-time algorithm for a well-known parallel machine scheduling problem with precedence constraints, with a fixed number of machines, and with tasks of unit length. The special case is related to instances with given maximum path length and maximum degree of the task precedence graph. The method is based on the observation that the number of tasks is either small and bounded by a constant depending on the maximum path length and maximum degree, or alternatively, the number of tasks is large, giving a “dense” schedule.     

Hardware-software co-synthesis of hard real-time systems with reconfigurable FPGAs

Real-time systems cover a wide application domain. This paper presents an efficient heuristic algorithm for enforcing the schedulability of aperiodic hard real-time tasks arriving simultaneously with precedence constraints and individual deadlines. The proposed co-synthesis algorithm integrates partitioning and non-preemptive scheduling. Reconfigurable FPGAs are incrementally added when schedulability suffers in a uniprocessor system. Initially, a schedule that minimizes the maximum lateness and satisfies the precedence constraints is made. If individual timing constraints are not met in this schedule, some tasks are selected and transferred to dynamically reconfigured FPGAs. The proposed algorithm was implemented and tested with a large number of task graphs with task size as high as 700 nodes. The algorithm could not only achieve schedulability but also could reduce the total completion time of the task graph. Moreover, incremental addition of reconfigurable FPGAs yielded a cost effective solution.     

一种面向部分可重构FPGA的混合实时调度算法

在CPU/FPGA平台上运行的实时任务通常由软/硬件子任务组成并存在优先约束关系。提出了一种软/硬件混合实时任务调度算法。在截止期限错失时刻,通过分析系统的运行情况,推导出实时任务可调度的充分条件。每个实时任务的硬件子任务分成多组,每组硬件子任务重叠配置到FPGA上。通过手工布局硬件子任务端口和总线端口,使得硬件子任务可动态的连接到系统总线上。实验表明,该算法能够满足任务的实时性,充分利用FPGA资源。     

具有优先次序的多媒体流调度和资源共享

文章讨论了在分布式多媒体系统中有优先次序约束的任务调度和资源共享问题.通过建立任 务优先次序的偏序关系,定义准正态调度概念,提出了任务调度算法QNES(quasi-normality －EDF－scheduler).该算法基于PCP(priority ceiling protocol)或SRP(stack resour ce policy)协议访问共享资源,具有抢占式、能处理任务的优先次序约束和访问共享资源的 特点,适合单机系统多媒体流的任务调度.     

Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization

An efficient method based on particle swarm optimization (PSO) is developed to solve the Multiprocessor Task Scheduling Problem (MPTSP). To efficiently execute parallelized programs on a multiprocessor environment, a scheduling problem must be solved to determine the assignment of tasks to the processors, the execution order of the tasks, and the starting time of each task, such that some optimality criteria are met. The scheduling problem is known as an NP-complete problem even when the target processors are fully connected and no communication delay is considered among the tasks in the task graph. The complexity of the scheduling problem depends on the number of tasks (N), the number of processors (M), the task processing time and the precedence constraints. The Directed Acyclic Graph (DAG) was exploited to represent the tasks and their precedence constraints. The proposed algorithm was compared with the Genetic Algorithm (GA) and the Duplication Scheduling Heuristic (DSH). We also provide a systematic investigation on the effect of varying problem settings. The results show that the proposed algorithm could not outperform the DSH while it could outperform the GA in some cases.     

云计算平台中非定期任务并行调度仿真

由于云计算平台的动态不确定性和非定期任务调度本身的复杂性,使得非定期任务调度过程中的耗时长和负载不均等问题很难得到有效解决。针对上述问题,提出一种非定期任务并行调度方法,并应用到云计算中。通过多方面考虑云平台客户非定期任务的截止时间底线、调度估算等并行调度约束条件和各种可用资源的性能参数,对非定期任务调度的多目标约束条件进行量化建模。基于建模生成的隶属度函数将非定期任务多目标约束的调度优化问题转变成单一目标约束问题,采用模拟退火算法对该问题进行求解,最终实现对非定期任务的并行调度。分析实验结果可知,与传统方法相比,所提方法能够有效减少非定期任务的传输时间,并且能够均衡节点负载,表明所提方法具有有效性。     

云中多媒体应用中基于混合DAG的最优任务调度研究

云计算的平台优势使得它在多媒体应用中得到广泛使用。由于多媒体服务的多样性和异构性,如何将多媒体任务有效地调度至虚拟机进行处理成为当前多媒体应用的研究重点。对此,研究了云中多媒体最优任务调度问题,首先引入有向无环图来模拟任务中的优先级及任务之间的依赖性,分别对串行、并行、混合结构任务调度模型进行任务调度研究,根据有限资源成本将关键路径中任务节点融合,提出一种实用的启发式近似最优调度方法。实验结果表明,所提调度方法能够以最短的执行时间在有限的资源成本下完成最优的任务分配。     

一种面向同构集群系统的并行任务节能调度优化方法

节能调度算法设计是高性能计算领域中的一个研究热点.复制调度算法能够减少后继任务等待延时,缩短任务总体调度时间,但是耗费了更多的能量.为此,作者提出一种启发式处理器合并优化方法 PRO.该方法按照任务最早开始时间和最早结束时间查找处理器时间空隙,将轻负载处理器上的任务重新分配到其它处理器上,从而减少使用的处理器数目,降低系统总体能耗.实验结果表明,和已有的复制任务调度算法TDS、EAD和PEBD相比,优化后的调度算法在不增加调度时间的条件下,能够明显减少使用的处理器数和系统总体能耗,从而更好地实现性能和能耗之间的平衡.