基于最佳并行度的任务依赖图调度

基于最佳并行度的任务依赖图调度策略充分利用编译时刻所得到的全局信息,采用横向和纵向任务合并,处理节点预分配,静态调度和动态调度相结合、集中式调度和分层调度相结合等措施,是一种简单的、具有较高效率的实用化调度方案.该调度方案能够在尽量压缩调度长度的情况下节约系统资源.     

基于选择性复制前驱任务的DAG调度算法

针对异构环境下相关任务的静态调度问题,以最小化调度长度为主要目标,结合表调度与基于复制的调度思想提出了选择性任务复制调度算法.在任务调度过程中,利用处理器的空闲时间,通过有选择地复制能提前当前任务开始执行时间的父任务来减少任务之间信息传递的通信延迟,有利于后续任务的及时调度,从而缩短整个任务图的并行完成时间.实验结果表明,文中算法在通信量比较大的情况下在时间上优于复杂度相同的HEFT,HNDP及DDS算法,且随着任务图中通信时间/计算时间比值的增加,其优越性也越来越明显.     

DAG任务图的一种调度算法

并行程序的调度技术是开发并行计算机系统的计算潜能的关键问题。本文讨论了4种典型的调度算法的缺陷，提出了一种新的调度算法CPFMBF，它采用的策略是：优先调度关键路径节点，其次调度b-level值大的节点，再次调度节点的关键路径影响度大的节点。对照分析及在几种具代表性的工程应用任务图上的实验结果证明CPFMBF算法的调度性能普遍好于其它算法。     

Scalable and Structured Scheduling

Scheduling a program (i.e. constructing a timetable for the execution of its operations) is one of the most powerful methods for automatic parallelization. A schedule gives a blueprint for constructing a synchronous program, suitable for an ASIC or VLIW processor. However, constructing a schedule entails solving a large linear program. Even if one accepts the (experimental) fact that the Simplex is almost always polynomial, the scheduling time is of the order of a large power of the program size. Hence, the method does not scale well. The present paper proposes two methods for improving the situation. First, a large program can be divided into smaller units (processes), which can be scheduled separately. This is structured scheduling. Second, one can use projection methods for solving linear programs incrementally. This is specially efficient if the dependence graph is sparse.     

TSA—OT：一个调度Out—Tree任务科的算法

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

数字化机步旅抢修任务动态调度框架研究

针对一体化机动进攻作战中战场抢修任务动态分配缺乏定量化确定方法的问题,对数字化机步旅抢修任务动态调度的框架结构进行了研究;借鉴Hall三维结构方法论,从对象维、过程维和技术维3个维度建立了抢修任务动态调度的框架结构,并以此为基础,分析梳理出了抢修任务动态调度的7个核心子问题,总结了这些核心子问题的自身特性,为抢修任务动态调度的后续研究提供了宏观规划和微观指导。     

基于DAG图解-重构的机群系统静态调度算法

机群系统静态任务调度是NP-完全问题,通常的算法是通过一些启发式算法得到多项式次优 解.该文提出的图解-子图重构算法实现了对分布在有向无环图(directed acyclic graph, 简称DAG)上的并行任务的快速有效调度.该算法的复杂性为O(log^|V|×(|V|+| E|)),采用递归方法实现了对任务图的有效分解和子图重构,生成任务群,完成任务调度,并 且初步实现了对处理机的优化.通过实例分析以及与其他启发式调度算法的性能比较,证明该 算法是一种快速、有效、可     

一种调度In-Tree任务图的算法

In-Tree任务图可用来表示归并、求和等分治算法的很多问题,该文针对这种任务图提出一种分层调度算法,利用队列存放被调度的任务,在同层任务调度中,优先把前驱不为空的任务调度到其一个前驱处理器上执行,只有前驱为空的任务才考虑是否分配新的处理器。实验表明,与以前的算法相比,该算法在调度长度相当的情况下,使用了更少的处理器。     

一个调度Out-Tree任务图的新算法

Out-Tree任务图代表分治算法的一大类问题。本文专门针对该类任务图,提出了一个新的调度算法。它利用fork结构的最优调度为各任务定义优先级,准确的反映了任务对调度的影响,保证了任务的正确调度顺序,得到优的调度长度。并在不改变调度长度的情况下,将结点尽可能地分配到已用处理器上,节省了处理器。实验表明,本文算法的调度性能优于现有同类算法。     

一种批优化调度策略的实时异构系统的集成动态调度算法

针对实时异构多任务调度的特点,提出了软、硬实时任务形式化描述非精确计算的统一任务模型,在此基础上,提出了一种基于批优化调度策略的实时异构系统的集成动态调度算法.该算法以启发式搜索为基础,引入软实时任务服务质量降级策略,在每次扩充当前局部调度时,按制定的规则选取一批任务,计算其在各处理器上运行的目标函数,采用指派问题解法对任务优化分配.模拟实验表明,该算法与同类算法相比,提高了调度成功率.     

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

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

多维动态规划在对地观测卫星调度中的应用

对地观测卫星调度问题是指如何利用有限卫星资源,在时间、空间等多约束条件下提高对地观测任务执行效率,是一个多约束条件下的目标满足问题.多维动态规划是针对多维约束任务将有限资源进行合理分配、高效调度的有效方法.它以缩短任务完成时间为目标,通过先求解一系列子问题,再处理子问题间关系求得问题最终解,避免了计算的复杂性,又满足了时效性要求.针对卫星对地观测任务约束变量多的特点,将多维动态规划应用到对地观测卫星调度问题中,是解决该问题在时效性要求条件下的有效方法,其可行性通过想定任务在文章中得到证明.     

Scheduling Functions for Spatiotemporal Mapping of d-Dimensional Algorithms with Homogeneous Dependences on (d-2)-Dimensional Parallel Architectures

A formalized method is proposed for construction of scheduling functions for spatiotemporal mapping of d-dimensional algorithms represented by systems of homogeneous recurrence equations on (d-2)-dimensional parallel architectures. Basic operations of the algorithms are scheduled separately by means of functions with rational coefficients.     

融合遗传算法和蚁群算法动态网格任务调度算法研究

网格计算是当今计算机科学领域最新兴起的一项有很高学术价值和应用价值的研究课题。未来互联网的发展方向是将网络中众多闲置的计算资源、存储资源以及科学仪器等可用资源充分合理的加以利用。如何高效地使用网格资源,即网格调度问题也随之成为研究的重点,虽然在传统的分布式并行计算中有很多成熟的任务调度算法,但由于网格的新特性,使得必须研究新的算法来解决一些新出现的问题,如调度问题的NP安全性,调度算法的高效性,资源的异构性以及资源分配决策的并行性和分布性等。     

一种基于DAG图划分的网格关联任务调度算法

网格计算中的大型应用程序往往被分解为多个关联任务.对于这类应用,任务间的依赖是一个不可忽略的因素.传统算法只能将其视为元任务来考虑,限制了对任务粒度的进一步划分,从而大大降低了任务调度的性能.本文提出一种基于DAG图划分的关联任务调度算法.它优先调度关键路径上的任务,同时利用任务复制的方法充分利用资源上的时间碎片,保证依赖关系及时得到满足.仿真结果表明,对于网格环境下的大规模关联任务,该算法有效地提高了作业执行速度和资源使用效率.     

基于最小化传输和完成时间的多DAG调度

针对云计算环境下多个有向无环图(DAG)工作流的调度问题,提出一种基于最小化数据传输时间和任务完成时间(LTCT)的算法,用于处理具有相同优先级的多个DAG工作流之间的调度问题。在多个DAG优先级各不相同时的情况下,给出多优先级多DAG的混合调度算法。实验结果表明,LTCT算法较E-Fairness算法在保证多DAG调度公平性的基础上,能避免额外的数据传输开销,有利于缩短整个工作流的执行Makespan,提高资源的利用率。     

含过程任务图的调度

我们在Ｆｏｒｔｒａｎ程序并行转换系统ＨＺＰＡＲＡ－Ⅱ的研究中遇到了含过程任务图的情形，对此我们提出了一种有效的调度方法。该方法可在Ｏ（ｎ＊ｅ）的时间内完成调度，调度结果可以与ＣＰ调度法相比     

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

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

基于图匹配的多处理机调度算法

本文对具有高通讯延迟的多处理机系统（机群系统）上的任务调度算法进行了研究，与以往算法主要考虑任务图的关键路径不同，本文给出了任务图的调度与其偶图匹配的对应关系，并由此提出了一种新的启发式算法，通过模拟试验显示本算法具有较好的调度效果。     

一个调度Fork-Join任务图的最优算法

Fork-Join任务图是一种并行处理的基本结构.虽然许多算法在任务满足某些条件时能产生最优调度,但往往没有考虑节省处理器个数和减少任务集的总完成时间,从而降低算法的加速比和效率.因此,提出一种基于任务复制的平衡调度算法,其时间复杂度为O(vq+vlogv),v和q分别表示任务集中任务的个数和使用的处理器个数.通过分析已用处理器的负载和空闲时间段,把任务尽量分配到已用的处理器上以均衡负载,从而提高其利用率.实验结果表明,该算法的加速比和总体效率优于其他算法.因此,该算法对于高性能应用程序的调度是一个较好的选择.