支持优先级约束任务的容错调度算法

为了解决异构分布式系统中可靠调度问题,提出一种考虑处理机链路通信竞争的,支持优先级约束任务的容错调度(FSPCT)算法。该算法使用通信竞争模型描述处理机之间通信,在备份成本最小化和备份任务最早完成之间寻求平衡点。对主副版本任务的最早开始时间进行分析,并限定了所执行的处理机,在处理机出现故障后任务可以顺利执行。实验结果表明FSPCT算法的综合性能优于现有一些算法。     

考虑释放时间和调度顺序的可分任务调度模型

针对处理机具有任意释放时间的异构并行与分布式系统,通过寻找最优的处理机调度顺序和任务分配方案,使得任务的完成时间达到最短.首先,在给定处理机调度顺序的情况下,分析了处理机释放时间对任务完成时间的影响,得到了任务分配方案关于处理机调度顺序和时序约束条件的解析解;然后,以调度顺序和时序约束条件为变量,以任务的最短完成时间为目标,建立了一种新的可分任务调度模型;最后,设计了高效的全局优化遗传算法求解该模型.仿真结果表明所提算法比已有算法完成任务的时间更短.     

一种可调节动态任务调度算法

提出了适于异构环境独立任务调度的可调节动态调度算法(AS算法)。该算法以任务与处理机的执行时间和完成时间作为参数共同构造任务调度顺序的衡量值,其中二者所占的比重能进行适当调整。AS算法克服了Min-min算法单纯追求局部最优的局限性,更适合异构环境。实验结果表明AS算法可以有效地降低调度跨度,其性能比Min-min算法有所提高。     

异构系统中带可用性约束的性能优化调度算法

针对可用性约束以及任务响应时间不同给异构系统中实时任务调度分配带来的处理机节点难选取的问题,提出了一种带可用性约束的性能优化调度算法(PO-SSAC)。该算法将异构系统内处理机节点、实时任务以及带可用性约束的实时任务调度过程进行数学建模,通过考虑可用性成本与任务平均响应时间的折中,引入系统综合开销的概念,根据实时任务的可用性需求为其分配系统综合开销最少的处理机节点调度执行,达到系统调度资源合理利用的目的。实验结果表明,在实时任务调度可用性方面,与SSAC算法相比,PO-SSAC算法提升了3.4%,与MinMin算法相比,提升了76.9%,与Sufferage算法相比,提升了76.5%;与Sufferage算法相比,PO-SSAC算法的系统综合开销减少了约30%,优化了异构系统的实时任务调度性能。     

一种基于任务竞争力的工作流调度算法

网格计算聚集了大量的异构分布式的计算或存储资源,为科学研究提供了一个高性能环境.然而,网格资源的异构性和自治性特征使得任务调度变得极其复杂.针对DAG表示的科学工作流调度问题,根据任务可用资源率确定任务调度的优先级,以任务竞争力刻画任务对资源的最佳匹配度,基于分层调度策略提出了一种基于任务竞争力的工作流调度算法.采用GridSim模拟实验表明该算法相对于其他两个算法,具有更小的执行时间.     

多处理机系统的高效实时容错调度算法

在容错调度算法副版本后调度算法（ＢＫＣＬ）的基础上,提出一种高效实时容错调度算法（ＥＢＫＣＬ）．对于具有容错需求的实时任务而言,由实时容错调度算法所产生的调度可保证在多处理机实时系统中一个处理机失效时,实时任务仍然可在截止时限内完成．在ＥＢＫＣＬ算法中,如果两个实时任务的基版本分配在不同的处理机Ｐｉ和Ｐｊ上,且这两个实时任务的副版本被调度到同一个处理机Ｐ上,则两个副版本之间允许有时间上的重叠．模拟实验证明,使用多个实时任务副版本之间的时间重叠技术,ＥＢＫＣＬ大大提高了调度的性能     

网络控制系统中任务与信息的优化调度

为了提高网络控制系统性能,解决网络控制系统中信息和任务相互约束的问题,设计了同时调度网络控制系统中任务与信息的算法.采用遗传算法优化调度序列,减小系统采样周期和端端延时,优化了系统整体性能.最终形成同步异构系统一个周期内的调度表,确定了系统每个子任务的执行时间和占用资源,解决了不同控制回路资源冲突问题和相同控制回路任务与信息执行顺序的约束问题,并且保证了每个子任务的实时性.仿真表明该算法是有效的.     

异构分布式实时系统中容错调度模型的研究

研究了基于异构分布式系统的实时容错调度算法 ,同构分布式系统中的处理机完全相同 ,而在异构分布式系统中各个处理机均不相同 ,各个处理机有不同的处理能力和不同的健壮性 .提出了可靠性成本概念 ,建立了一个基于异构分布式系统实时容错调度模型 .基于该模型 ,设计了一种实时容错调度算法 ,算法在不增加系统硬件成本的情况下 ,提高了实时分布式系统的可靠性 .     

基于Anytime算法的模型预测控制器的优化反馈调度

模型预测控制器可以实现为具有Anytime算法特征的模型预测控制（MPC）任务，它允许在执行时间和控制性能之间进行折衷．文中针对一组MPC任务，提出一种优化反馈调度算法（FS-CBS），在有限处理器时间约束范围内使全局控制性能最大化．该算法为每个MPC任务分配了一个恒定带宽服务器（CBS），并对CBS所预定的处理器时间进行动态调节，同时通过约束条件保证整个任务集的可调度性和各组分的稳定性．仿真结果表明，该算法对MPC运行时的执行时间变化不敏感，明显优于基本的CBS算法．     

基于权值比例和服务时间误差的动态调度算法

针对动态网格计算中的需求调度问题,提出了 一种基于权值比例和服务时间误差的调度算法.首先,构建出一个由多个动态独立执行的任务和多个具有相应计算能力的多处理器系统构成的动态网格模型;然后,对于一个给定的由多个任务构成的任务集来说,按照任务集中每个任务的权值比例对队列中的全部任务进行降序排序,并得到每个任务的服务时间误差;最后,根据每个任务的服务时间误差值来分配计算资源给任务,以使服务时间误差值最小化.性能仿真结果表明,相比于网格计算中常用的FCFS调度算法和轮询调度算法,提出的调度算法在平均计算成本、总的任务完成时间以及服务时间误差值性能方面都具有较大的优势.     

多处理机系统的高效实时容错调度算法

在容错调度算法副版本后调度算法的基础上,提出一种高效实时容错调度算法。对于具有容错需求的实时任务而言,由实进容错调度算法所产生的调度可保证在多处理机实时系统中一个处理机失效时,实时任务仍然可在截止时限内完成。在ＥＢＫＣＬ算法中,如何两个实时任务的基版本分配在不同的处理机Ｐｉ和Ｐｊ上,且这两个实时任务的副版本被调度到同一个处理机Ｐ’上,则两个副版本之间允许有时间上的重叠。     

考虑处理机时间窗口的可分任务调度优化模型

针对异构分布式系统下处理机具有时间窗口约束的可分任务调度问题,通过寻找最优的任务分配方案和最优的处理机调度顺序,可以使得任务的完成时间最短。首先,在已有模型上引入处理机时间窗口的概念,使得所建模型更加贴切实际;然后,建立了一个新的考虑处理机时间窗口可分任务调度的非阻塞优化模型,同时设计了一种基于全局优化的遗传算法来求解模型;最后,为了快速、高效地求解模型,所提算法同时对处理任务量和调度顺序进行编码,利用不同的交叉算子来优化调度顺序和任务分配量,设计了合理的修正算子来修正不满足处理机时间窗口的任务分配方案,并且设计了高效的局部搜索算子来加快算法的收敛速度。仿真实验结果表明,在处理机时间窗口约束下,与已有算法相比,所提算法至少提升了20%以上的性能,从而证明了所提算法的正确性和有效性。     

面向GPU异构集群的自学习负载均衡调度算法

由于GPU的高性能计算能力,越来越多地被用于集群系统中,但同时也给集群带来节点级的异构问题,使原来适用于同构集群的调度算法在异构集群中性能大大降低。为使异构节点间的负载均衡,降低总的作业执行时间,提出了一个面向GPU异构集群的自学习负载均衡调度算法。首先对Torque调度器进行扩展,使其支持GPU作业调度,然后将提出的自学习调度算法在Rocks操作系统及Torque调度器软件中实现。真实物理集群上的实验结果表明,扩展后的Torque调度器很好地支持GPU任务的调度,自学习调度算法较原来的Torque调度算法能达到更好的负载均衡。     

异构分布式实时系统中容错调度模型的研究

研究了基于异构分布式系统的实时容错调度算法,同构分布式系统中的处理机完全相同,而在异构分布式系统中各个处理机均不相同,各个处理有不同的处理能力和不同的健壮性。提出了可靠性成本概念,建立了一个基于异构分布式系统实时容错调度模型。基于该模型,设计了一种实时容错调度算法,算法在不增加系统硬件成本的情况下,提高了实时分布式系统的可靠性。     

异构分布式系统中实时可任意切分任务调度算法

针对异构分布式系统中最大化实时可分任务服务收益和最小化任务完成时间的任务调度问题进行了研究.为在保持较高任务接受率条件下最大化服务收益,提出了三种有效策略:(1)同时考虑服务收益和任务完成截止时间的任务接受/拒绝判断策略;(2)从等待队列里移除任务的策略;(3)考虑收益的最小松弛度优先的排序策略.为最小化任务的完成时间,设计了能够充分利用处理机空闲时间的调度算法以对接受的任务进行调度.仿真实验结果表明,提出的算法能够获得更多的服务收益、任务接受率和较小的任务完成时间.     

异构环境下基于任务交互图的调度算法

针对异构环境下任务图为TIG（task interaction graph）的问题，利用松弛标记法善于利用邻居属性处理大量约束的特点，提出一种任务调度算法．算法把任务看作目标对象，处理器单元看作待分配标记，根据对象间所有可能关系，逐渐排除不相关的处理器单元，选择计算和通信综合性能较好的处理器单元．在兼顾任务执行的计算和通信需求的情况下，能够合理分配资源、提高处理速度、缩短整个应用程序的执行时间．实验结果与用穷举法得出的最优结果比较显示，本算法能较理想地解决异构环境下基于任务交互图的调度问题．     

分布式计算系统下可分任务的周期性多趟调度

针对已有单趟任务调度模型因无法充分利用分布式平台的并行特性导致系统利用率和任务完成效率较低的问题,提出了一种新的周期性多趟任务调度优化模型。在给定处理机调度顺序的情况下,推导得到了分布式系统最优任务分配方案的解析解;通过分析任务完成时间关于调度趟数和服务器数的变化曲线,设计了一种启发式算法寻求最优的调度趟数和参与计算的服务器数;为了获得最优的服务器调度顺序,提出了一种高效的全局优化进化算法。实验结果表明:与已有调度算法相比,所提算法能够在分布式平台下最小化任务的完成时间,对于小规模和大规模任务,任务完成时间分别降低了至少25%和43%。     

面向异构集群的作业调度与资源分配研究

提出一种面向异构集群的作业调度与资源分配策略,在异构资源实时监控的基础上,实现了作业的有效调度,进而在作业执行阶段,采用基于二部图的最小权匹配的资源分配算法,实现异构资源到执行任务的合理部署与配置.以医学科学计算为背景,搭建了异构云计算环境,并进行了仿真实验.实验结果显示:提出的算法实现了预期的目标,有效弥补了现有同构作业调度算法的缺陷与不足.     

星载计算机系统高优先级恢复容错调度算法

为了在星载异构容错计算机上调度星载任务，在给出了星载计算机系统的容错调度模型的基础上，提出了一种星载计算机系统高优先级恢复容错调度算法（OHFSA），该算法通过引进可靠性代价量化了容错系统在维护容错调度时所需要的开销，并在调度过程中充分考虑了容错调度的实时性和低可靠性代价．同时，采用高优先级恢复机制可及时响应紧急时限下的恢复任务，从而提高了星载任务的整体实时性能．实验验证表明，OHFSA随着计算时间的增加，其所需的可靠性代价也相应增大．仿真结果表明，在任务负载不断增加的情况下，OHFSA的执行时间比目前算法减少20%～30%，特别是在恢复任务优先级比其主任务提高1个级别时，响应时间可减少近8．7%．     

异构计算系统的表调度式任务映射与调度算法

研究了在异构计算系统（ＨＣＳ）中利用表调度式算法进行任务映射与调度．给出两种异构静态优先级表调度式任务映射算法（ＨＳＰ和ＧＨＳＰ）,以及一种异构动态优先级表调度式任务映射算法（ＢＨＤＰ）．实验结果表明,ＧＨＳＰ算法对于粗中粒度ＤＡＧ的调度效果稍好于ＨＳＰ算法,而ＢＨＤＰ算法对于粗粒度和细粒度ＤＡＧ的调度效果均明显优于ＨＳＰ和ＧＨＳＰ算法．