基于任务图的并行调度MEWFM算法

随着多核处理器体系结构在计算机领域的广泛应用,如何合理地对计算任务进行调度成为人们广泛讨论的问题。目前已经有针对多处理器的任务调度算法,但是这些算法在执行时要经过多次迭代,执行效率比较低。提出一种改进的波前调度算法MEWFM,它是一种执行时间短,加速比接近处理器核数的一种算法。这种算法主要包括任务图分层,层内调度和误差下降调度三个子算法。详细分析了这些算法的特点和执行流程。实验评测表明,算法在多处理器环境下的任务调度方面具有执行速度快,性能高等优势。

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

任务调度是影响工作站网络效率的关键因素之一.Fork-Join任务图可以代表很多并行结构,但其他已有调度Fork-Join任务图算法忽略了在非全互连工作站网络环境中通信之间不能并行执行的问题,有些效率高的算法又没有考虑节省处理器个数的问题.因此,专门针对该任务图,综合考虑调度长度、非并行通信和节省处理器个数问题,提出了一个基于任务复制的静态调度算法TSA_FJ.通过随机产生任务的执行时间和通信时间,生成了多个Fork-Join任务图,并且采用TSA_FJ算法和其他调度算法对生成的任务图进行调度.结果表明,TSA_FJ算法的调度长度最短、使用的处理器个数最少,它更适合于非全互连的NOW环境.

一个调度Fork-Join任务图的最优算法(英文)

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

相关任务图的均衡动态关键路径调度算法

表调度 (list scheduling)法是解决任务调度问题的较为有效的方法 .该文对两个典型的表调度算法——MCP算法和 ETF算法进行了分析 ,发现它们均存在着一定的不足 .文中提出了一个更好的表调度算法 BDCP,它采用动态关键路径技术并均衡考虑关键路径结点和非关键路径结点 ,使得对相关任务图调度长度影响最大的就绪结点能够被优先调度 ,从而极大地缩短了任务图的调度长度 .分析和实验结果表明 ,BDCP算法要优于

DAG任务图的一种调度算法

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

调度Fork-Join任务图的贪心算法

任务调度算法的目标是把组成并行程序的一组任务分配到多个处理器以使得程序的完成时间最短,这是一个NP完全问题。虽然许多算法在任务满足某些条件时能产生最优调度,但大多都忽略了节省处理器个数和最小化程序总的完成时间等问题。Fork-Join结构是一种并行处理的基本结构。因此,专门针对Fork-Join任务图,提出了一个能产生最优调度的新的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为2,其中,表示任务集中任务的个数。实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理器数较少。

任务图模型中实时任务设计

仿真技术的进步推动了实时系统(如核反应堆、军事战场和fly-by-wire系统)的深入研究.用仿真方法解决实时问题,必须首先给出实时系统描述模型.TGM(task graph model)模型是实时系统描述模型之一,其模型最重要的成员是实时任务.使用量化仿真方法定义了实时任务的4种参数,并细分任务为子任务.此方法更易描述实时应用系统,更易构造TGM的执行模型,其层次化的结构更容易进行研究和软件实现.TGM模型及其任务设计已成功地应用于分布式三星实时侦察仿真系统.

异构环境中Fork-Join任务图的调度算法

目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低。因此,对Fork-Join任务图的调度问题进行研究,提出了一个基于异构环境的贪心调度算法,该算法具有高的加速比和总体效率,其时间复杂度为2,其中,表示任务集中任务的个数。实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性。

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。

带时间约束实时任务图模型上可调度性分析算法研究

带时间约束的实时任务图(TCDRT)模型具有接近于时间自动机的丰富表达性,但是其关联的可调度性分析(SA)问题却是强NP困难的.目前的研究仅关注一类约束个数为常数K的易解模型:K-TCDRT,且局限于SA问题的图转换求解方法.这种间接求法使得问题的计算复杂度随约束宽度呈指数倍增长.该文研究TCDRT模型上可调度性分析问题的直接求解方法,为两个核心子问题给出新的理论结果:第一,针对需求上界函数(DBF)的计算问题,提出了考虑时间约束的路径需求结构,并据此设计了新的动态规划算法,其时间复杂度与约束宽度无关;第二,对于可调度分析上界T的限定问题,从理论上证明了该问题是伪多项式时间可解的,且计算复杂度不再与K指数相关,这使得文中算法性能较已有结果有指数级提升.更进一步地,该文方法还蕴含着一类新的TCDRT易解模型.该类模型突破了约束个数必须为常数的局限,其分析难度也较K-TCDRT有指数倍地下降.

利用层次任务图和多种群遗传算法的可重构计算任务划分

为实现可重构计算中软硬件任务的自动划分,提出一种基于层次任务图模型和采用遗传算法作为搜索算法的任务划分算法.首先设计了一个层次任务图模型,其不同于基于有向非循环图(DAG)的模型,可以在任务划分时动态改变任务颗粒度,进而得到不同任务粒度下的最优解;其次设计了一个考虑了时间、功耗、资源和通信代价的适应度函数,并根据任务数量不固定的特点对遗传算法进行了改进.对文中算法在FPGA上进行实验验证和分析的结果表明,该算法的结果优于基于DAG任务图模型的任务划分.

基于异构环境的Out-Tree任务图的调度算法

分布式应用程序的有效调度是异构计算系统中的一个关键问题。目前已有的Out-Tree任务图的调度算法大多基于同构环境而开发,未考虑处理机的异构性,导致调度的效率较低。针对异构计算环境,提出一个基于列表和任务复制的Out-Tree任务图的静态启发式贪心调度算法,其时间复杂度为O(hv2 p),其中h、v和p分别表示任务图的高度、任务个数和调度使用的处理机个数。实验结果表明,相比其他算法,该算法能提供调度长度较短、处理机使用较少的有效调度,其应用性更强。

同构环境中Join任务图的一个调度算法

任务调度问题是一个NP完全问题。Join结构是一种并行处理的基本结构,虽然许多算法对Join任务图能产生最优调度,但大多都忽略了节省处理机个数和最小化程序总的完成时间等问题。因此,专门针对Join任务图,提出一个能产生最优调度的同构贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数。实验结果表明,相比其他算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少。

异构任务图的实现模型

任意异构程序映射到任意异构系统上执行 ,是并行程序计算最复杂的情况 .为此提出了异构任务图的定义 ,它是异构程序直观和有效描述方法 .还研究了异构任务图的实现模型 ,它是异构计算环境中软件和硬件的桥梁 .分别给出了任务图的分簇算法、系统图的分簇算法和映射算法及应用实例 .利用该模型可设计出可移植的并行程序 。

广义Fork-Join任务图的调度问题研究

Fork-Join结构是一种并行处理的基本结构。为处理传统方法难以解决的复杂和非线性问题,缩短整个程序的总完成时间,针对广义Fork-Join任务图提出了基于遗传算法的调度算法,该算法将遗传算法和任务复制相结合,有效地缩短了得到最优结果的时间。实验结果表明,与其他算法相比,该算法具有较短的调度长度。

基于通信竞争的Fork-Join任务图的调度算法

Fork-Join任务图是一种并行处理的基本结构,目前已有的Fork-Join任务图的调度算法大多没有考虑实际应用中通信链路的竞争及延迟以及节省处理机的问题,导致算法在具体应用中效率较低。因此,针对Fork-Join任务图,提出一个基于通信竞争的贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(vlogv),其中v表示任务集中任务的个数。实验结果表明,该算法相比其它算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性。

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

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

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

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

基于任务图的一种并行程序设计方法（Ⅰ）──任务图的设计

本文提出一种基于任务图的并行程序设计方法．首先分析欲解的问题，产生数据流程图，并以此设计出表示并行算法的任务图，然后根据任务图选择合适的系统拓扑结构，最后完成并行程序的设计．该方法思路清晰，富有条理，产生的并行程序质量较高．

一个新的Fork任务图的调度算法

针对Fork任务图的结构特点,提出了基于任务复制的调度算法。在对算法基础、术语、新的Fork任务图的调度算法-NSF进行了介绍的基础上,运用实例对调度进行了分析比较。该算法在保证得到最优调度长度的前提下,减少了使用处理机的个数。实验结果表明,该算法综合性能优于其它算法。