异构集群系统中实时通信信号处理调度算法

当宽带大容量数据采集进入并行计算机网络后,通过集群计算方式对强衰弱通信信号实现高增益、低延时处理,达到有效实时解译通信数据的目的。提出了一种新的动态启发式调度算法——MDS算法。该算法综合考虑任务的时间要求、系统吞吐率和负载均衡。在任务的截止期较短的情况下,MDS算法仍能保证任务具有较高的调度成功率;同时在满足任务截止期的条件下系统具有较高的吞吐率并达到负载均衡。通过实验测试,分析了一些任务参数对MDS算法的影响,并与其他算法进行了比较。实验结果表明,MDS算法优于其他算法。     

实时任务在异构集群中的自适应容错调度研究

异构集群由于良好的扩展性和可用性,逐渐成为当前并行计算的热点。在具有实时性要求的异构集群中,调度是提高系统性能的关键所在。在此提出了两种自适应调度算法SANOL和SAOL,在保证异构集群中任务的实时性和容错性的前提下,自适应地根据系统的负载情况动态地调整任务的服务级别,从而提高整个系统的灵活性、可调度性和资源利用率。通过实验将这两种算法与另外一种有效率的调度算法DYFARS算法进行比较,结果表明所提出的SAOL算法具有更好的性能。     

基于异构分布式系统的实时容错调度算法

目前文献中研究的实时容错调度算法都是基于同构分布式系统，系统中的所有处理机完全相同。该文首先建立了一个基于异构分布式系统实时容错调度模型，异构分布式系统中的各个处理机均不相同。基于该异构分布式系统模型，该文引入了可靠性代价（reliability cost）概念，并提出两种静态实时容错调度算法（RTFTNO和RTFTRC）用于调度周期性实时容错任务。算法RTFTRC在调度任务时，尽量使系统的可靠性代价最小；而算法RTFTNO在调度实时任务时，没有考虑系统的可靠性代价。该文详细讨论了两种调度算法的性能。性能模拟实验分别比较了两个算法的可靠性代价，超时比率和可调度性；并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系。实验结果表明，算法RTFTRC的性能优于算法RTFTNO。     

异构集群系统中安全关键实时应用调度研究

在集群系统中,为有安全需求的实时应用提供安全保障得到了广泛关注,但将实时应用的安全需求与调度算法相结合的研究并不多.文中提出了一种异构集群系统中安全关键实时应用的2阶段调度策略--TPSS.该策略综合考虑了任务的安全需求与时间限制.在TPSS的第1阶段,提出了一种自适应调度算法DSRF,当系统负载较重时,DSRF算法能在保证任务安全需求的基础上,通过降低新到任务和等待队列中任务的安全级别来提高任务的调度成功率.相反,当系统负载较轻时,DSRF算法能在保证系统具有较高调度成功率的基础上充分利用任务在截止期前的空闲时间提高新任务的安全级别.在TPSS的第2阶段,提出了一种新的算法FMSL,用来为所接收任务提供较为公平的安全服务,同时进一步提高了任务的整体安全级别.文中通过大量的模拟实验对TPSS策略与DSRF算法、SAEDF算法和RF算法进行了比较.实验结果表明,TPSS策略优于其它方法,使系统具有较强的安全性与灵活性.     

异构分布系统的实时任务轮转式容错调度算法

建立了一个异构分布式系统实时调度模型,对异构分布式系统中的任务及不同处理机资源进行了形式化描述.结合基版本/副版本技术,给出了用于异构分布式系统的实时任务轮转式容错调度算法.实例分析表明,该算法有效提高了异构处理机环境下的资源利用率以及整体计算性能.     

异构分布式控制系统中实时任务的调度算法

分布式控制系统是一种应用极为广泛的异构分布式实时系统，系统中同时存在有多种实时任务，如何将这些任务分配到各个处理器上并保证它们的时限是系统关键技术之一．在结合启发式任务分配算法和单处理器任务调度算法的基础上，提出了一种分布式控制系统的调度算法．该算法考虑了各个处理器的负载均衡，同时又能满足所有任务的时限．仿真结果表明了算法的有效性．     

异构集群中基于优先级的任务容错调度算法

提出一种基于任务优先级的容错调度算法,任务的优先级并不是由用户指定,而是由任务的开始时间、执行时间和截止期限决定的。该算法能够容忍异构集群系统中一个节点故障,采用主动/被动副版本相结合的执行方式和重叠技术的备份方式,提高系统资源利用率。通过实验证明了该算法在容错调度中的可靠性和高效性。     

异构分布式实时仿真系统的容错调度算法

异构分布式实时仿真系统是一类特殊的实时系统,基于改进的SP(spare processor)容错模型(checkpoint-based spare processor,简称CSP)对其容错问题进行了研究.首先,根据仿真系统的特点提出了两个命题,这是后续工作的基础;而后,基于Markov链对仿真任务的最坏反应时间进行了分析,并提出了仿真任务的可调度性分析规则;最后,基于CSP容错模型和上述可调度分析规则提出了异构分布式实时仿真系统的容错调度算法CSP-RTFT.算法的仿真结果表明:该算法较之基于SP模型的算法SP-RTFT可获得更好的稳定性、更高的任务接收率;缺点是资源利用率比PB模型下的算法要低.     

异构分布式系统中实时周期任务的容错调度算法

提出一个基于抢占性实时周期任务的可靠性调度模型,该模型与现有可靠性模型相比充分考虑了单处理机故障容错情况下的系统可靠性,因而更加接近现实和精确.在此基础上,提出一个基于异构分布式系统的实时容错调度算法IRDFTAHS,IRDFTAHS算法以提高系统的可靠性为目标来进行任务的分配,从而在不增加硬件代价的前提条件下通过调度增加了系统的可靠性.该算法同时支持主动和被动两种方式的副版本,使得容错调度算法具有更大的灵活性.最后,通过仿真实验对IRDFTAHS和现有的调度算法在几个方面进行比较.实验结果表明,IRDFTAHS算法的综合性能优于现有算法.     

可重构系统中实时任务容错调度算法

现在FPGA已被广泛的应用,但三模冗余(TMR)结构不能充分利用FPGA资源,基于主/从版本技术,提出一种实时任务容错调度算法。算法通过后向调度从版本,使得从版本在其截止期限内尽可能地推迟执行,从而同一任务的主从版本在执行时间上没有重叠或较少重叠,当任务主版本成功执行时释放任务从版本所占用的资源。仿真实验表明,与TMR相比,此方法能更有效地利用FPGA资源,提高硬件任务的接受率。     

Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters

Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints.Unfortunately,most conventional scheduling algorithms only take one or two dimensions of them into account.Motivated by this fact,this paper investigates the problem of providing multiple performance guarantees including timeliness,QoS,throughput,QoS fairness and load balancing for a set of independent tasks by dynamic ...     

三模容错多处理器动态实时调度算法

实时系统现在面临着越来越迫切的容错要求。目前流行的主副备份方式对于任务集有着特殊要求,要求时间限能够允许主副备份串行地执行,并且系统需要提供相应的硬件来检测处理器错误,因此限制了容错的应用范围。本文提出基于三模冗余比较的实时容错算法,采用了副本重载技术和主副本串并行混合调度策略。分析和实验结果表明,该算法具
有更好的适应性。     

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．     

一种实时异构系统的集成动态调度算法

提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(quality of service)降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.     

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

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

Fault-Tolerant Parallel Scheduling of Tasks on a Heterogeneous High-Performance Workstation Cluster

We propose a new approach, called cluster-based search (CBS), for scheduling large task graphs in parallel on a heterogeneous cluster of workstations connected by a high-speed network (e.g., using an ATM switch at OC-3 speed). The CBS algorithm uses a parallel random neighborhood search which works by refining multiple different initial schedules simultaneously using different workstations. The workstations communicate periodically to exchange their best solutions found thus far in order to direct the search to more promising regions in the search space. Heterogeneity of machines is exploited by the biased partitioning of the search space. The parallel random neighborhood search is fault-tolerant in that the workload of a failed workstation is automatically redistributed to other workstations so that the search can continue. We have implemented the CBS algorithm as a core function of our on-going development of SSI middleware for a Sun workstation cluster.     

具有依赖关系的周期任务实时调度方法

随着多核技术在嵌入式领域的快速发展,越来越多的功能被集成在同一个平台上,任务之间的关系越来越复杂.而当前大多数的实时周期任务的调度模型都是不考虑任务之间关系的相互独立的任务模型.文中则针对具有依赖关系的周期任务,提出了一种基于ST(Simple-Tree)的实时周期任务调度模型,通过该模型来维护任务之间的依赖关系.此外,为了有效地提高系统利用率以及降低死限丢失率,文中还提出了可延迟时间越短越优先的调度方法并和RM算法、EDF算法进行仿真实验比较,结果表明该方法具有较高的核利用率和较低的死限丢失率.