检索结果-南通市图书馆

异构系统中DAG任务调度的双螺旋结构遗传算法

在线全文

学校读者我要写书评

暂无评论

计算机研究与发展 2014年第6期51卷 1240-1252页

作者：徐雨明朱宁波欧阳艾嘉李肯立湖南大学信息科学与工程学院长沙410082

任务调度问题是一个NP完全问题,基于启发式的方法通常被用来求解次优解,其性能在很大程度上依赖启发的成效,在复杂问题时可能会产生不理想的结果.鉴于此,根据染色体双螺旋结构模型,提出了一种异构计算系统中依赖任务调度的双螺旋结构遗... 详细信息

任务调度问题是一个NP完全问题,基于启发式的方法通常被用来求解次优解,其性能在很大程度上依赖启发的成效,在复杂问题时可能会产生不理想的结果.鉴于此,根据染色体双螺旋结构模型,提出了一种异构计算系统中依赖任务调度的双螺旋结构遗传算法.算法将遗传算法和启发式方法有机地结合,首先针对任务图的数据依赖关系,采用启发式方法,控制遗传算法的交叉与变异操作合理改变一个染色体主链结构,以产生较佳的任务调度优先队列;然后模仿碱基互补配对方法,利用启发式异构环境下最早完成时间算法,实现从一个染色体主链(任务集)到另一个染色体主链(异构处理机集)的映射,以提高算法的有效性和收敛速度.随机任务图和真实问题任务图的仿真实验表明,所提出的算法在调度性能上明显优于启发式算法,最大完成时间平均减少10.1%.

关键词： NP完全问题遗传算法双螺旋结构 DAG任务调度调度长度

在线全文

学校读者我要写书评

暂无评论

基于动态关键任务的多处理器任务分配算法

计算机学报 2007年第3期30卷 454-462页

作者：兰舟孙世新电子科技大学计算机科学与工程学院成都610054

多处理器调度问题是影响系统性能的关键问题,基于任务复制的调度算法是解决多处理器调度问题较为有效的方法.文中分析了几个典型的基于任务复制算法,提出了基于动态关键任务(DCT)的多处理器任务分配算法.DCT算法以克服贪心算法不足为要... 详细信息

多处理器调度问题是影响系统性能的关键问题,基于任务复制的调度算法是解决多处理器调度问题较为有效的方法.文中分析了几个典型的基于任务复制算法,提出了基于动态关键任务(DCT)的多处理器任务分配算法.DCT算法以克服贪心算法不足为要点,调度过程中动态计算任务时间参数,准确确定处理器的关键任务,以关键任务为核心优化调度,逐步改善调度结果,最终取得最优的调度结果.分析和实验证明,DCT算法优于现有其它同类算法.

关键词：调度长度任务复制多处理器系统任务分配并行计算同构系统

在线全文

学校读者我要写书评

暂无评论

基于动态任务优先级的网格任务调度算法研究

大连理工大学学报 2012年第2期52卷 277-284页

作者：孟宪福闫玲玲刘伟伟大连理工大学计算机科学与技术学院辽宁大连116024

网格环境下的任务调度是一个NP完全问题.为了确保每一步都能优先调度影响调度长度最大的就绪任务,提出一种采用动态任务优先级策略的任务调度算法.在进行任务调度的过程中,通过动态计算任务图DAG的关键路径并有效地利用处理器的空闲时... 详细信息

网格环境下的任务调度是一个NP完全问题.为了确保每一步都能优先调度影响调度长度最大的就绪任务,提出一种采用动态任务优先级策略的任务调度算法.在进行任务调度的过程中,通过动态计算任务图DAG的关键路径并有效地利用处理器的空闲时间段来复制任务,使任务节点之间的通信开销尽可能降低,进而缩短整个任务图的完成时间.大量的模拟实验结果表明,所提的算法在任务完成时间上明显优于HEFT算法和DDS算法.

关键词：网格环境任务调度动态任务优先级任务复制调度长度

TSA-OT:一个调度Out-Tree任务图的算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2001年第4期24卷 390-394页

作者：刘振英方滨兴张毅哈尔滨工业大学计算机科学与工程系哈尔滨150001 哈尔滨理工大学电气与电子工程系哈尔滨150040

对于把一个任务群调度到多个处理器的问题 ,人们往往只注重找到一个调度路径最短的算法 ,却忽略了要节省处理器 .由于 Out- Tree任务图代表分治算法的一大类问题 ,因此 ,文中专门针对该任务图 ,给出了一个基于任务复制的算法 TSA- OT.... 详细信息

对于把一个任务群调度到多个处理器的问题 ,人们往往只注重找到一个调度路径最短的算法 ,却忽略了要节省处理器 .由于 Out- Tree任务图代表分治算法的一大类问题 ,因此 ,文中专门针对该任务图 ,给出了一个基于任务复制的算法 TSA- OT.它首先分配关键路径上的任务结点 ,然后在不改变调度长度的情况下 ,把非关键路径上的结点尽可能分配到已用的处理器上 .并且 ,该算法将 Out- Tree任务图中的所有通信都化为零 .TSA- OT算法与近几年所提出的 TDS,CPFD,DCP算法之间的比较表明 ,TSA- OT算法不仅调度长度最短 ,而且采用了更少或相当个数的处理器 .

关键词：任务调度调度长度 DAG TSA-0T算法 DCP算法多处理器

异构网络化汽车电子系统中多DAG离线任务调度

在线全文

学校读者我要写书评

暂无评论

通信学报 2013年第12期34卷 20-32页

作者：谢国琪李仁发杨帆黄卫红湖南大学嵌入式与网络计算湖南省重点实验室湖南长沙410082

公平性和通信开销已成为影响调度性能的主要瓶颈,首先在任务优先级排序阶段,提出基于通信开销权值的轮转调度的公平排序标准;在处理器选择阶段,提出在插入法的基础上将任务分配到具有最小选择值的选择标准;综合上述2个阶段,提出以降低... 详细信息

公平性和通信开销已成为影响调度性能的主要瓶颈,首先在任务优先级排序阶段,提出基于通信开销权值的轮转调度的公平排序标准;在处理器选择阶段,提出在插入法的基础上将任务分配到具有最小选择值的选择标准;综合上述2个阶段,提出以降低调度长度和减少通信开销为目标的多DAG离线公平任务调度(MDOFTS,multiple DAGs off-line and fairness task scheduling)算法。异构网络化汽车电子系统是一个典型的混合关键级嵌入式系统,既要确保实时性又要降低调度长度,提出了以满足安全关键DAG的多DAG离线优先级任务调度(MDOPTS,multiple DAGs off-line and Priority task scheduling)算法。综合MDOFTS和MDOPTS,提出多DAG离线自适应任务调度(MDOATS,multiple DAGs off-line and adaptive task scheduling)算法,在满足实时性的基础上提高调度性能。实例分析和实验结果表明,提出的算法在调度长度、通信开销、不公平性、最差响应时间和实时性上都优于其他算法。

关键词：异构网络化汽车电子系统多DAG 通信开销调度长度实时性

在线全文

学校读者我要写书评

暂无评论

多层次分布实时仿真系统的静态调度策略

系统仿真学报 2011年第1期23卷 85-88,94页

作者：潘玉林陈勇姚新宇黄柯棣国防科技大学机电工程与自动化学院长沙410073

针对多层次分布实时仿真系统环境的特点,为了解决任务静态调度问题,提出了一种基于实时性分层的调度策略。该算法结合任务分层和启发式列表调度算法,在映射中同时考虑任务节点计算负载和通信开销映射到系统节点的等效负载,并映射当前最... 详细信息

针对多层次分布实时仿真系统环境的特点,为了解决任务静态调度问题,提出了一种基于实时性分层的调度策略。该算法结合任务分层和启发式列表调度算法,在映射中同时考虑任务节点计算负载和通信开销映射到系统节点的等效负载,并映射当前最小总等效量到相应的系统节点上,从而获取较小的调度长度。实验结果表明,与交互优先算法相比该算法能提供较优的调度结果;相对于不考虑实时性而言,在调度中存在着一定的"不平衡"。

关键词：多层次分布实时仿真分层单向性调度长度

在线全文

学校读者我要写书评

暂无评论

一种实时异构嵌入式系统的任务调度算法

软件学报 2004年第4期15卷 504-511页

作者：邱卫东陈燕李洁萍彭澄廉复旦大学计算机与信息技术系上海200433

异构分布式系统已被广泛应用在实时嵌入式系统中,而调度算法是在进行嵌入式系统综合时,确保系统实现性能目标的一个关键问题,这是一个NP-完全问题.现有的算法主要是启发式算法,性能还有待提高.提出了一个异构分布式系统的动态BLevel优先... 详细信息

异构分布式系统已被广泛应用在实时嵌入式系统中,而调度算法是在进行嵌入式系统综合时,确保系统实现性能目标的一个关键问题,这是一个NP-完全问题.现有的算法主要是启发式算法,性能还有待提高.提出了一个异构分布式系统的动态BLevel优先(dynamic BLevel first,简称DBLF)算法,算法选择就绪任务中动态BLevel值最大的任务进行调度,用插入法为任务分配处理器,遵循以下3个插入原则:满足任务先后顺序关系;任务的最早完成时间(earliest-finish-time,简称EFT)最小;在EFT相等时,优先分配到利用率较低的处理器上.与现有算法比较可以看出,DBLF算法可以有效降低调度长度.

关键词：异构系统列表调度调度长度动态关键路径通信资源访问最早完成时间

在线全文

学校读者我要写书评

暂无评论

嵌入式并行系统中基于任务优化的调度算法

计算机工程 2008年第2期34卷 11-13,49页

作者：刘勇尹增山杨根庆上海微小卫星工程中心上海200050 中国科学院上海微系统与信息技术研究所上海200050

在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关... 详细信息

在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关任务优化(DTO)的调度算法,通过分析已用处理机的负载和空闲时间,尽量减少系统的调度长度和处理机数目。算法分析结果表明,DTO算法在性能上优于其他算法,对嵌入式并行计算系统中的多任务调度是一个较好的选择。

关键词：嵌入式系统任务调度调度长度相关任务

在线全文

学校读者我要写书评

暂无评论

异构集群下的任务调度算法研究

计算机应用研究 2014年第1期31卷 80-84页

作者：刘莉姜明华武汉纺织大学数学与计算机学院武汉430073 武汉纺织大学研究生处武汉430073

针对异构集群下高效节能的任务调度算法进行了研究,提出了一种基于复制的任务调度算法,在任务初始分配的基础上,分别从能源感知和性能—能源平衡两个角度考虑任务的复制。建立了由计算和通信造成的能源消耗的数学模型,并进行了大量的实... 详细信息

针对异构集群下高效节能的任务调度算法进行了研究,提出了一种基于复制的任务调度算法,在任务初始分配的基础上,分别从能源感知和性能—能源平衡两个角度考虑任务的复制。建立了由计算和通信造成的能源消耗的数学模型,并进行了大量的实验。实验结果表明,与已有的BEATA算法相比,该算法能明显地减少异构集群处理并行应用的调度长度和能耗。分析结果发现,任务复制的方法在减少调度长度的同时会增加相应的能耗,能同比优化调度长度和能耗的任务调度方法是今后的研究方向。

关键词：任务调度任务复制异构性调度长度能源消耗