一个新的基于通信竞争的任务调度算法

任务调度是并行处理的一个非常关键的方面。目前的调度算法大多假定处理器完全互连、可以并行接收数据,而没有考虑实际应用中通信链路的竞争及延迟,进而导致调度算法在具体应用中效率较低。论文研究异构计算环境下具有依赖关系任务的边调度问题,结合传统任务调度问题中的有效策略,提出一种新的调度算法,该算法通过串行化通信边使通信竞争集成化。实验结果表明,与各种经典调度方案相比,该算法显著地改善了精确性和效率。     

基于同构多核处理器的任务调度

随着现代应用对计算机性能要求的提高,计算机主频不断提升。由于功耗和半导体工艺的限制,仅靠提高单核主频难以继续维持“摩尔定律”,同构多核处理器（Homogeneous Multi-core）应运而生。在同构多核处理器的支持下,一个芯片汇集多个地位对等、结构相同的通用处理器核,以最小的代价满足了提高系统性能、负载均衡、处理器容错的需要。并行体系结构需要结合与之适应的软件实现性能效益的倍增。本文从操作系统层面,针对处理器结构的变化,研究并实现多核任务调度。系统采用混合调度策略,簇间独立调度,簇内统一调度。从调度模式、调度算法、分配算法、调度时机等方面详细分析了多核调度的原理和实现机制。最后通过模拟实验证明功能正确性及算法可调度性。     

并行嵌入式系统中具有通信竞争任务调度问题的高级列表调度方法

现代嵌入式系统正在向使用多核或多处理器进行并行处理的方向发展.针对并行嵌入式系统中具有通信竞争情况下的任务调度问题,文中提出3项高级技术以提高列表调度方法的性能.首先使用5组(已存在的两组和新提出的3组)节点等级作为节点优先权来生成节点列表;然后使用关键子节点技术来改善调度过程中处理器的选择;最后使用通信延迟技术扩大通信连接线上的空闲时间区间.文中还给出了组合使用这3项技术的高级动态列表调度方法.实验结果表明,在中等通信代价和高通信代价的情况下,组合高级动态方法能够有效地缩短调度长度,可以在通信代价很高时通过优化使用硬件资源使调度结果加速高达80%.     

同构计算环境中DAG任务图的调度算法

在并行多处理机系统中,任务调度算法是保证整个系统性能的关键.通常用有向无环图(DAG)表示任务间的依赖关系.将粒子群算法应用于组合优化领域,构造了求解任务调度问题的离散粒子群算法.算法采用基于分组的思想对粒子进行直接编码,借鉴遗传算法的思想,将粒子个体最优及全局最优解分别采用交又操作作用到当前粒子位置上,使粒子不断向最优位置逼近;同时在每次迭代过程中引入变异操作以提高粒子群体多样性.实验结果表明,算法在不同规模的任务调度问题中均取得了良好的效果.     

通信竞争环境中Join任务图的一个调度算法

Join任务图是一种并行处理的基本结构。目前已有的Join任务图的调度算法大多忽略了通信链路的竞争、延迟以及节省处理机的问题,导致算法在实际应用中效率较低。针对这一问题,提出一个基于通信竞争的Join任务图的调度算法,该算法通过对各通信边的串行化而在任务调度中集成通信竞争,其时间复杂度为O(vlogv),其中v表示图中的任务数。实验结果表明,相比其他算法,该算法就调度长度、使用的处理机数、加速比和效率而言为优,具有更强的实用性。     

同构计算环境中一种新的静态任务调度算法

延伸了TTIG模型并提出新的算法．在模拟实验中，将此算法与MATE和其它同构环境中基于DAG的调度算法，在不同测试条件下进行了比较，结果显示该算法性能明显优于MATE，与基于DAG模型的调度算法比较而言，在性能方面各有千秋，但在算法时间复杂度方面具有显著的优势．     

元计算环境中任务调度的深入分析

文章主要对元计算环境中任务调度进行了深入分析与研究。先概述了元计算系统对于科学领域的贡献,分析了元计算环境的特点;然后对元计算环境中的调度算法进行了分类说明,并对几种典型的调度算法行了具体的分析,评价了其特点与不足之处;最后分析了新兴的元计算环境—校园级元计算环境面临的挑战,借鉴各种调度算法,提出了与之相适应的任务调度策略,对其可行性进行了分析,并简要概括了其创新性。     

基于通信和计算开销的网格任务调度算法的研究

在计算密集型的异构网格环境中,有效的任务调度是一个关键的问题,这是一个完全NP问题,针对这一问题提出了一种基于通信和计算开销的启发式网格任务调度算法,这一算法考虑了不同的节点计算能力、任务大小和网络带宽,最后给出了相应的实验及相关算法的比较结果,表明了该算法对于异构环境具有更优的性能。     

异构环境下独立任务调度算法的研究

本文基于Min-min算法和Sufferage算法提出了基于任务调度损失的最小最早完成时间算法(Sufferage Min-min,SMM).该算法将任务调度损失引入Min-min算法,选取最早完成时间较小的k个任务,再优先对其中任务调度损失最大的一个进行调度.SMM算法克服了Min-min算法单纯追求局部最优而缺少全局意识的缺点.测试表明,SMM算法可以做到调度跨度低与平均等待时间小的统一,在综合性能上较Min-min算法有所提高.     

同构计算环境中一种快速有效的静态任务调度算法

快速有效的调度任务是多处理器计算环境中的一个关键问题. 目前任务调度算法中刻画任务依赖关系最流行的模型是DAG. 在以前的文献中, 提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境). 延伸了TTIG模型, 并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2). GBHA以组的形式尽量消除图中回路,因而能获得任务图的全局信息,具有更好的调度性能. 在模拟实验中,将此算法与MATE和其他同构环境中基于DAG的有效调度算法,在不同测试条件下进行了比较,结果显示GBHA在性能上明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势.     

一个有效的Join任务图的调度算法

已有的Join任务图的调度算法大多不是基于通信竞争的环境而开发,且未考虑节省处理机的问题,使算法的应用效果不佳.因此,针对Join任务图,提出一个通信竞争环境的调度算法,该算法因串行通信边而改善其调度效率,时间复杂度为O(vlogv),其中,v为图中任务的个数.实验结果表明,与其他算法相比,该算法的调度长度较短且使用的...     

独立任务调度的启发式算法

任务调度是一个NP-hard问题,而且是并行与分布式计算中一个必不可少的组成部分,特别是在网格计算环境下任务调度更加复杂。该文提出了满足负载均衡的一个启发式任务调度算法。给出了选择处理机和任务的方法,以提高算法的效率。实验表明该算法是一个高效率的调度算法,并且几乎总是找到了最优调度方案。     

一种基于改进蚁群算法的网格任务调度算法

在网格计算中,任务调度是影响系统性能和服务质量的重要问题。文章在考虑截止时间和花费两项用户QoS需求的基础上,提出了一种基于蚁群算法的网格任务调度算法。该算法先采用GC（Greedy Cost-Time Distribution）算法求解,将所得解转化为蚁群算法的初始信息素分布,然后利用蚁群算法获得调度解。模拟实验结果表明：在网格环境下,该调度算法具有明显的优势。     

基于深度学习的动态优先级任务调度算法

工业互联网中设备任务的处理需要大量计算资源,有低时延需求的任务显著增多.边缘计算将算力等资源放置到靠近需求一侧,为任务处理提供有效支撑.但由于边缘计算资源有限,无法同时满足设备任务的低时延和高完成率需求.如何确定合理的卸载决策与任务调度,仍然存在巨大挑战.针对以上问题,本文提出了一种基于深度学习的动态优先级任务调度算法DPTSA,首先根据动态优先级选择待处理任务,通过神经网络产生任务调度决策,然后通过交叉变异等操作产生一组可行解,再筛选最优解存储到经验缓冲区,最后通过经验缓冲区样本优化神经网络参数.基于Google的Brog任务调度数据集的实验结果表明,相比于4种基准算法, DPTSA在任务等待时间和任务完成率方面都有出色表现.     

基于联系数的网格任务动态调度算法

针对传统网格任务调度模型将每个任务的预期执行时间设定为一个确定常量,无法表达其不确定性的问题,利用一种新的软计算方法——集对分析联系数来表示并处理网格任务预期执行时间的综合不确定性。提出基于联系数的不确定性网格动态调度模型,在线动态调度算法OUD_MCT和批模式动态调度算法BUD_Surferage。数值仿真结果表明,该类算法能较好地描述网格任务预期执行时间的动态性和不确定性,使传统网格调度方法成为其特例,在动态和不确定网格环境中具有良好的理论意义和实用价值。     

一种异构计算系统中考虑通信冲突的有效任务调度算法

任务调度是异构计算的核心问题之一 .现有的异构计算系统的任务调度算法基本上没有考虑任务通信时可能在同一通道中发生冲突的情况 ,因而造成任务调度的结果与实际运行结果之间的差异 .本文提出了一种异构计算系统中的基于表调度 (list scheduling)的启发式任务调度算法 ,该算法考虑了任务通信中通道冲突的情况 ,在不提高算法复杂度的同时提高了任务调度的性能 .文中还通过实例结果的比较说明了该算法的有效性     

控制系统中一种新的周期性任务模型及其优化调度算法

分析了控制系统中的周期任务特性 ,给出了控制系统周期性任务的一种新任务模型 - -周期性任务分解模型 ,它将系统中的控制回路分解为几个子任务 .给出适合此任务模型的调度算法——双优先级调度算法 ,引入了辅助优先级 .该算法能够控制子任务执行顺序和降低控制输入输出延迟 .分析了任务集的可调度性 ,给出了任务集可调度的充分必要条件 .最后讨论了系统性能优化的问题 ,给出了系统性能优化的调度算法     

云计算环境下基于用户和资源约束的免疫效用均衡任务调度算法

针对云计算中的任务调度问题, 提出了一种免疫均衡效用任务调度算法. 该算法将云计算环境下任务调度问题建模为一个多目标优化模型, 同时兼顾了用户任务的时间跨度和虚拟化资源的负载均衡. 仿真结果表明, 该任务调度算法提高了用户满意度的同时减少了任务的完成时间, 是云平台下一种有效的任务调度策略.