基于关键路径和任务复制的多核调度算法

针对目前大多数多核处理器任务分配优化算法没有考虑关键路径上节点对任务完成时间的重要影响,导致任务完成总时间延迟的问题,提出了基于关键路径和任务复制(CPTD)的单任务调度算法。CPTD算法通过复制任务图中fork节点的方式将任务图转化为与之相对应的产品加工树;再在生成的产品加工树中找到关键路径,并采取使关键路径上节点的紧前节点尽早调度的方式,使关键路径上节点尽早开始执行,进而使产品加工树中节点完成时间得以提前,达到缩短任务执行总时间的目的。理论分析表明,CPTD算法能够实现应用程序在多核上充分并行处理,并能缩短任务完成时间。

基于任务复制的分簇与调度算法

针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法.改进了粒度的定义,证明了对任意DAG,算法有优于前人的性能下界.实验结果优于典型任务复制算法,特别是对经典EZ算例的解(调度长度为8)好于前人认为的理论最优解(调度长度为8.5),并证明了新的解为最优解.定义了DAG的补图,讨论了不允许任务复制时树型DAG的2-优度算法.

基于任务复制的调度算法

任务调度是并行分布式计算系统中最具挑战性的NP完全问题之一。基于任务复制的调度是一种有效的调度方法。在通信开销较小的情况下,现已有许多算法能产生最优调度。但其最优条件要么比较苛刻,要么比较复杂。因此,针对这些算法存在的问题,提出一个新的基于任务复制的聚集调度(TDCS)算法,不仅其最优条件简单、宽松,而且该算法具有更小的时间复杂度O(log),其中,和分别表示任务集中任务的个数和最大入度。

一种基于多处理器任务复制的分簇调度算法

任务调度的优劣是决定并行分布式计算机系统性能好坏的重要因素之一。为优化任务调度,基于一些典型算法(如LG、PPA算法等),提出了一种新的任务调度算法。该算法一方面复制满足条件的前驱任务来缩短调度长度;另一方面合理地复制其他前驱任务和合并冗余簇来减少所需处理器的数目。实验表明,该算法在调度长度和所需处理器的数目上优于以上典型算法,并具有更小的时间复杂度,对并行计算机系统性能的提升具有一定的意义。

基于任务复制的多关键路径任务调度算法

高效的任务调度算法使多核处理器的资源分配和并行计算能力更加高效。通过研究关键路径对任务调度算法的重要性后提出TDMCP算法。对DAG上关键任务的确定采用一种多关键路径选取的方法,使得关键路径上信息在任务调度的每一步都是实时更新的;保证调度的每一步优先执行紧迫性高的任务;对首任务采用任务复制技术,使得后续任务的调度更加的高效,从整体上提高任务调度效率。和两个经典任务调度算法进行实验性能的比较,比较结果表明TDMCP算法在任务调度时间和算法执行效率方面都要优于两种经典算法。

一种基于任务复制调度算法研究

分布式计算系统中任务调度是NP完全问题,调度算法可以分为任务复制和无任务复制两类.本文在简述了传统TDS算法的缺陷后,提出了一种改进的TDS任务调度算法-M TDS.该算法基于异构计算系统的特点,采用动态DAG图,尽可能的提前每个任务的执行时间,缩短所有任务完成的执行时间;并且避免出现在某一个执行序列中由于某一任务执行时间过长,而影响整个程序的执行时间.

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

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

基于任务复制的网格任务调度算法

网格中资源之间存在着通信延迟,通过任务复制的冗余,可以减少任务之间的通信开销,缩短整个计算程序的计算时间。目前网格中的任务调度算法基本上是没有考虑任务复制的;而基于任务复制调度算法往往会产生过多的复制任务,增大系统开销,甚至有可能延迟计算时间。由于基于任务复制的任务调度是一个NP问题,因此本文提出了一种基于任务复制的网格资源调度算法,以减少调度长度为主要目标、减少任务复制量和资源占用量为次要目标。该算法在调度长度和任务复制数量以及占用资源数量方面都等于或优于其它算法。

基于任务复制的处理器预分配算法

基于任务复制的调度算法比无任务复制的调度算法具有较好的性能 .文章在分析了基于任务复制的几个典型算法 (如TDS ,OSA等算法 )及其假设条件后 ,提出了以使调度长度最短作为主要目标、减少处理机数目作为次要目标的处理器预分配算法PPA .该算法对任务计算时间与任务间通信时间未做任何限制 (即不考虑任务粒度 ) .通过与相关工作的比较可以看出 :PPA算法在调度长度与处理器使用数目上均优于其它算法或与其它算法相当 ,同时 ,该算法具有与TDS ,OSA相同的时间复杂度 .这对嵌入式实时分布系统具有重要的意义 .

基于任务复制与冗余消除的多核调度算法

在分布式计算中常把任务之间的协同和通信关系转换为任务图模型,而任务调度是决定分布式计算性能的关键因素之一。为解决OSA、TDCS、RECS等传统经典算法处理器个数消耗多且存在大量冗余任务等问题,提出一种改进的任务图调度算法。该算法基于贪心策略复制任务的前驱以及前驱的前驱,减少调度长度和处理器空闲时间,并在不增加调度长度的前提下,通过合并簇及减少冗余任务降低处理器个数和处理器的负载。实验结果表明,该算法在处理器个数、加速比以及冗余任务比率上都有一定程度的优化,能提升分布式计算性能。

基于任务复制的多维QoS云计算任务调度

为了满足云计算环境下用户服务质量(QoS)需求和提高虚拟资源空闲时间段的利用率,提出了一种基于任务复制的多维QoS任务调度策略。首先,构建云资源模型和用户QoS模型,然后根据虚拟资源的利用情况和QoS的满意度对虚拟机进行性能测评,选择综合性能更高的虚拟资源进行任务的分配;在任务执行时为了缩短任务的完成时间,在调度过程中引入了在空闲时间段复制父任务的方式。通过仿真实验将该算法与HEFT、CPOP进行比较,实验结果显示:当用户偏好可靠性执行时,该算法平均可靠性比HEFT和CPOP高;当用户偏好完成时间和费用花费执行时,该算法平均完成时间比HEFT和CPOP少;当用户无偏好执行时,该算法平均完成时间和平均花费均比HEFT和CPOP少。结果表明该算法能有效提高资源利用率和用户的满意度。

一种改进的基于任务复制的多核调度算法

在多核系统中,任务调度是决定系统性能的关键因素之一。为优化任务调度,基于一些典型的任务调度算法(如PPA,徐成提出的算法等),提出了一种新的任务调度算法。该算法一方面合理确定前驱任务复制的先后顺序,而且进行两个阶段的复制,从而可以复制更多的前驱任务以减少调度长度和处理器上空余时间;另一方面,通过去除不影响任务系统调度长度的冗余簇,然后进行簇之间的合并,以减少处理机的数目和调度长度。实验表明,改进后的算法在任务调度的性能上优于典型算法。

一种基于可重构多FPGA的任务调度与任务复制方法

在可重构多现场可编程逻辑门阵列(FPGA)系统中,任务调度是一个极其重要的研究方向。参照同构与异构计算领域的调度算法,结合可重构多FPGA计算模型的自身特点,在现有的调度算法的基础上,将任务复制方法引入到可重构多FPGA系统计算领域,如果任务余图最长路经上的父子节点不在同一FPGA上,通过寻找FPGA上的复制空间,提出的算法将父节点尽可能复制在子节点所在的FPGA上,减小了任务之间的通信开销。实验结果表明,对于任务调度有向无环图,提出方法的调度长度优于或等于前人方法的性能下界,而且,FPGA利用率有所提高。

基于任务复制的静态调度算法研究

任务调度是分布实时系统中的一个关键问题。基于任务复制的静态调度算法是任务调度问题中的研究热点。通过概括任务复制静态调度算法的算法模型以及基本术语后,详细分析比较了几种典型算法。还考虑了优化条件、调度长度、处理器数目以及时间复杂度等研究方向。最后,结合国内外研究现状,提出以减少处理器数目为研究目标。

基于任务复制的进化调度算法

并行程序任务调度是NP完全问题.已有的进化调度算法不能很好利用任务复制这一重要手段.为此,利用染色体直接编码和间接编码的优点,并结合任务图的知识,使进化调度算法的搜索能力得到增强,同时染色体的解码过程也得到简化.通过与同类算法的性能比较,表明了本算法在调度问题中的有效性.

一种基于任务复制方法的网格调度算法

根据Internet上存在大量空闲主机的情况,结合流行的P2P的思想给出了一种基于资源代理的网格系统模型,该模型能提供超级计算能力给一般的用户。针对在像网格这样的大规模系统中部署大量监控组件的困难性,设计了一种基于任务复制的调度算法。该算法无需任何有关环境的预测信息,仅需知道任务的相对长度,就可在执行过程中自动地适应网格的动态性,并且具有容错功能。

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

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

一种基于复制的高效任务调度算法

近年来,对于拥有高性能计算功能的多处理器(包括多核处理器)系统的研究已逐渐成熟,并且在很多并行系统中已经开始采用多处理器架构。但是现在针对多处理器平台的任务调度算法尚未成熟,在满足最大化并行执行各个任务时难以兼顾任务间的通信延迟。基于此,提出了一个新的算法,采用选择复制特定任务的方法来减少任务间的通信时间并提高处理器的利用率,以达到使整个任务的执行时间最短的目标。算法的核心是基于待调度任务,分别计算其在有限个处理器下复制与不复制关键父任务的完成时间,并在之中找到符合条件的完成时间,基于该完成时间,将待调度任务调度到相应的处理器上。该调度算法采用了选择复制的方式进行调度,在增加了处理器利用率的同时,有效地减少了任务之间的通信时间,使整个任务的调度时间变短,调度时间相比对比算法平均缩短2%。这对于结构复杂、参数随机的有向无环图(Directed Acyclic Graph,DAG)任务模型来说,具有高效的调度性能。

网格环境下基于复制的能耗有效依赖任务调度研究

随着能耗管理成为可靠和绿色计算的重要课题,能耗感知调度方法以其低成本和可行性引发关注.目前,网格环境下依赖任务的能耗感知调度研究具有极大的挑战性,其需要平衡应用的优先约束性、海量数据传输、系统的异构性和不同性能指标的冲突性的关系.提出的网格依赖任务的能耗有效调度(energy-efficient scheduling of grid dependent tasks,ESGDT)算法旨在优化应用执行时间的前提下降低应用执行能耗,能有效解决上述问题.通过任务复制和渐进比例因子减少通信时间和通信能耗,同时兼顾应用复杂的数据依赖关系;适应芯片微型化和多核技术的发展趋势,采用动态电源管理技术减少任务执行的静态能耗;任务复制条件、渐进比例因子和微调原则均适时兼顾时间和能耗两个相互冲突的调度指标,并提出自适应和动态映射方法适应异构计算环境.模拟实验表明,较HEFT,EETDS和HEADUS算法,ESGDT算法不仅没有影响调度的时间性能,还可进一步降低应用执行能耗.

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

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