处理顺序约束的信息物理融合系统静态任务表调度算法

针对异构环境并行计算的静态任务调度问题,以最小化有向无环图(Directed acyclic graph,DAG)的执行跨度为目标,改变HEFT(Heterogeneous earliest finish time)算法中任务上行权重的计算方法,获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT(Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时,分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确.确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT,CPOP(Critical-path-on-a-processor)和LDCP(Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.

基于多变异分组遗传算法的多机协同作业静态任务分配

为解决农业机械(简称农机)多机协同作业前的任务分配问题,提出了基于多变异分组遗传算法的同种农机多机协同作业静态任务分配方法。首先,根据农机合作社实际作业模式,基于农机性能参数和任务参数,综合考虑机群的作业时间、作业油耗和路程代价等因素,建立了多机协同代价函数;根据多机协同作业特点,构建了多变异分组遗传算法,设计了两段式编码、分组交叉算子和多种变异算子,并建立了农机多机协同作业静态任务分配模型;通过仿真试验对比分析了算法的性能,并采用不同的代价权重进行了任务分配仿真试验;最后,采用不同的权重对实际深松作业进行任务分配试验,对本文提出算法进行了验证。结果表明:在不同权重下,基于多变异分组遗传算法的多机协同静态任务分配的机群代价比实际作业代价降低了29.48%~55.00%,选取合理权重的静态任务分配具有较高的分配效率和分配性能,能够满足实际多机协同作业中任务分配的要求。

多核系统静态任务调度的启发式算法

在任务调度研究领域,列表类调度算法的优化研究始终备受关注,针对经典列表调度算法难以获得理想调度解的缺陷,提出一种迭代型列表调度算法。该算法采用遍历宏块拓扑序列技术,扩大任务图拓扑序列搜索空间以得到更小的任务图调度长度。理论分析表明,对于任意的任务图,该算法得到的调度长度必不大于经典列表调度算法。以4种常见类型和随机类型的任务图样本证实,迭代型列表调度算法能够有效改善调度解,尤其在平均通信计算时间比超过1的情况下,调度性能的平均提升超过14.6%,最大提升达到102.8%。

非完全互连同构系统上的静态任务调度

在分布式内存多处理机DMM（distributedmemorymultiprocessor）系统中，不同处理机上运行的任务之间的通信开销仍然很大，有时甚至抵消了多处理机并行所带来的好处．为了使并行程序在DMM系统上能得以高效的执行，必须采用合理的调度技术将任务分配给处理机．文章首先分别给出了任务调度系统中的任务模型、处理机模型以及调度问题的形式化描述，然后在此基础上研究了任务调度中3个最重要的问题，即（l）如何顺序选择参与调度的任务，（2）如何选择路由，（3）如何分配任务给处理机．其中，路由选择是按存储转发寻径与虫蚀寻径两种不同的方式来讨论的．最后，根据上述3个问题的解决策略，构造了一个非完全互连同构系统上的静态任务调度算法．

总线互连机群系统上的静态任务调度

与大规模并行处理（ＭＰＰ）系统相比，基于总线互连的机群（ｃｌｕｓｔｅｒ）系统是一种较为廉价的并行计算环境．文中提出了一个基于总线互连机群系统上的静态任务调度算法．该算法具有３个主要特点：（１）由于不同处理机之间的通信都必须通过共享总线，故在调度时将总线与处理机一样看成是资源加以分配；（２）针对总线适合于广播的特点，在调度中考虑了广播，对于某些应用而言可以大大减少通信次数；（３）在确定任务在某个处理机上的开始执行时间以及消息占用总线的开始时间时，选用了最早空闲时间空隙．最后，分别给出了Ｇａｕｓ－Ｊｏｒｄａｎ消去法与ＬＵ分解的任务图及其调度结果．

基于超立方体的静态任务调度

该文给出一个基于超立方体的静态任务调度算法 .在算法的设计中 ,首先建立了任务优先级表和处理机优先级表 ,任务在调度时总是顺次调度高优先级任务 ,然后再从处理机优先级表中选择能使该任务最早开始执行的处理机 .最后 ,分别给出了基于 LU分解的任务图与随机生成的任务图的调度结果 .

小型静态实时多任务架构

单片机已经在很多应用领域得到了普及。然而某些应用 (比如网络通信应用、前台 /后台应用等 )需要实时多任务系统的支持 ,普通单片机往往难以胜任。提出了一个基于单片机的静态实时多任务系统框架。该系统框架由一个简单的多任务内核 ,配合使用普通单片机自带的不可屏蔽中断 (NMI)和定时器功能构成。应用这个实时多任务系统框架 ,可以较好地满足一些特殊的应用需求 ,而由此带来的任务管理开销是很少的。

一种基于任务排序的单操作员控制多无人机静态注意力分配模型

在单操作员监督控制多无人机进行搜索任务的场景下,为解决操作员的静态注意力分配问题,建立基于任务排序的静态注意力分配模型,目的是将合适的任务在合适的时间分配给操作员处理,实现任务的综合回报最大化。该模型对静态任务队列进行排序,同时设定每一个任务的处理时长和任务执行后操作员的休息时长。采用MATLAB仿真实验验证,利用动态规划和免疫算法进行求解。实验结果表明,在静态任务队列的注意力分配中此模型获得的综合回报,大于基于先进先出原则的注意力分配方法获得的综合回报。

LilyTask任务并行环境中基于任务关系的初始任务分配算法

LilyTask是一个基于任务并行的并行程序设计环境,它引入了任务间关系的概念.任务间会由于这种任务依赖关系而产生等待,为了减少这种等待开销,LilyTask系统在预编译阶段分析这些数据依赖关系,并做出相应的静态任务分配.该文给出在LilyTask任务并行环境中的一族新的基于任务关系图的静态任务分配的算法——WCP算法,并在实际测试中与另外两个著名的静态分配算法ETF和MCP算法作了比较,测试结果说明WCP算法在任务计算开销与通信开销不能准确给出的情况下有更好的分配效果.

分布式系统下的启发式任务调度算法

为了提升异构分布式环境下处理具有依赖关系的任务的性能,提出一种基于关键任务和处理器选择参数的启发式任务调度算法(HCNPSV)。该算法结合表调度和任务复制调度的思想,改进了关键任务的计算方法,并按照是否为关键任务、上行权重值递减、关联任务数递增的顺序获得调度序列,资源选择阶段综合考虑了任务的最早完成时间和到出口节点的最短距离,最后将任务调度到处理器选择参数最小的资源上执行。实验结果表明,HCNPSV有效地提高了系统的调度性能。

一种多核系统任务扰动迭代算法

任务调度问题是多核处理器相关技术的一个重要组成部分。基于列表的调度算法因其低复杂度和高效率得到广泛关注,但确定任务优先级列表方法的单一性使得算法对解空间搜索不够,易陷入局部最优。为此,提出一种基于任务扰动的迭代型列表调度算法(task perturbation iteration algorithm, TPIA)。该算法通过选取任务扰动因子按照一定扰动策略进行调度列表迭代,对迭代后的列表进行贪心选择,生成更优的调度列表序列以得到更好的调度结果。通过实例和随机有向无环图(DAG)有限集对算法进行验证,结果表明算法能有效改善调度解,调度性能提升平均可达16.51%,适宜处理大规模、高出入度的复杂DAG图;针对TPIA算法在低任务总数高通讯开销情况下性能有所下降的问题,对平均任务节点数130以下的任务图进行分组测试,获得了对应的CCR上界值及其变化趋势。

并行分布计算中的静态负载分配

文章首先介绍了负载分配的几种分类,然后重点讨论了基于任务相关图的静态任务调度,最后给出了几种其它的任务调度模型。

基于动态关键路径与边消除的任务复制分配算法

当前的分布式任务调度算法中,都存在无法得到调度最优解、无法最小化处理器资源的问题。针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,提出了一种基于动态关键路径与边消除的任务复制算法。该算法依据调度长度不增加原则,发展了子节点无约束复制的调度长度不增加定理、子结点带约束复制的调度长度不增加原则、动态关键路径聚簇的调度长度不增加原则,从而缩短了任务的执行时间和占用资源的个数。整个算法流程对任务计算时间与任务间通信时间未做任何限制。通过与相关工作的比较可以看出:DDE算法在调度长度与处理器使用数目上优于其他同类算法。

带资源约束的异构多核任务复制调度算法

关键路径的确定与优化在异构多核系统的任务调度算法中占据重要地位。为解决异构多核系统调度算法常因估算关键路径时的参数选择存在局限而导致的估算结果偏差过大,调度结果不佳的问题,文章提出一种在参数计算时考虑资源约束的异构多核任务复制调度算法(task-duplication scheduling algorithm with resource constraints,TDSA-RC)。该算法通过改进布局优化方式,扩大其适用范围;同时通过筛除冗余任务,减少任务复制过程中产生的不必要的计算。通过随机生成的任务图和3种实际应用的任务图调度对比实验表明,该算法能有效缩短并行任务的调度长度,与TDCA(task-duplication based clustering algorithm)算法相比,平均性能可提升12.08%,适合处理规模大、层级少且join节点占比多的并行任务。

浅谈《展望未来》中任务的设计

本文探讨了任务型教学中任务的内涵,提出在《展望未来》的教学中,根据学生的学习情况和认知水平的发展,设计的任务应由简到繁,由易到难,层层深入,由静态任务、动态任务到抽象任务。从而使学生把所学知识与现实生活中的真实情况相结合,激发学生的创造性思维,培养他们的语言运用能力,充分发挥“任务型教学途径”的效应。

基于直接后继节点完成时间的异构调度算法

分布式环境下的异构计算系统(HCS)是大数据时代进行数据密集型计算不可或缺的,一个有效的任务调度算法可以提高整个异构计算系统的效率。在对异构环境下的任务调度进行有向无环图(DAG)建模的基础上,提出基于直接后继节点完成时间的异构调度算法(HSFT)。在计算开销和通信开销差异度较大的异构环境中,考虑两者之间的平衡,采用更为合理的以计算均值与标准方差的乘积和通信权值与任务节点出度的比值作为优先权值计算方法,并在考虑最快完成时间(EFT)的基础上,将直接后继节点完成时间(SFT)用于处理器分配策略。实验结果表明,HSFT在不增加算法时间复杂度的情况下,比HEFT、SDBATS、PEFT等算法有更短的调度长度(makespan)、更优的调度长度比和效率。

异构分布式计算环境下一种新型表调度算法

针对异构分布式环境下并行计算的静态任务调度问题,在HEFT算法的基础上,提出一种新型表调度算法IFEFT。以最小化有向无环图(DAG)的执行跨度为目的,在任务处理器分配阶段改变HEFT算法中的处理器分配策略,计算任务最早完成时间与其出口任务之间的最大通信开销,并依据两者乘积的最小值进行分配,兼顾任务对其直接后驱任务和直接前驱任务完成时间的影响,以优化处理器分配结果。通过随机生成的DAG图进行仿真,与HEFT、DLS和CPOP算法的比较结果表明,IFEFT算法具有更高的调度效率。

基于多核处理器的PLC控制程序并行执行

针对可编程逻辑控制器(Programmable Logic Controller,PLC)的编程语言不支持程序的并行编译,无法使控制程序并行执行于多核处理器的问题,根据功能块图的可拆分性,提出了用有向无环图(Directed Acyclic Graph,DAG)任务模型表示PLC控制程序的方法,并采用静态列表任务调度算法,优化DAG中的任务节点在不同CPU核上的分配调度,解决了PLC控制程序并行执行时会遇到的通信延时问题。此外,针对变量资源的竞争问题提出了使用互斥量的方法。实验结果表明,此方法能有效地将PLC控制程序并行运行在多核处理器上,大大缩短了程序的执行时间。