物联网环境下具有顺序约束关系的静态任务表调度算法

针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。     

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

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

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

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

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

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

一种基于任务全局迁移的静态调度算法

任务调度是分布实时系统中的一个关键问题.TDS等典型算法在优化条件下可得到该问题调度长度上的最优解.但是TDS等算法在节点分配时存在节点选择范围和节点执行时间范围的局限,无法最小化算法所需处理器数目.任务全局迁移调度算法GTT（global task-transferring）在保证调度长度最优的前提下,从全局范围内选择并调度任务节点,有效利用了处理器,可最小化调度所需处理器数目.优化条件下对各种算法的调度实验表明,GTT算法在加速比和效率上比TDS等同类算法有显著提高.GTT算法的时间复杂度是O（d ｜ V｜^ 2）.这里｜V｜是DAG图中的节点数,d是图中各节点入度或出度的最大值.     

异构计算平台静态任务调度算法综述

异构计算平台由通过总线或者高速网络互联的各种处理器组成,通常应用于计算密集型应用.高效的任务调度一直是异构计算平台中实现高性能计算的关键问题之一.通常,应用可以划分为一组具有依赖关系的任务集合,可以通过有向无环图DAG模型表示.本文首先介绍了基于DAG的静态任务调度模型,然后给出了相关任务调度算法的分类及其概述,最后总...     

LSA_IT:一种In-Tree任务图的分层调度算法

In-Tree任务图可用来求解归并排序、求和等分治问题的并行。针对该类任务图,提出了一种分层调度算法——LSA_IT。它对任务图逐层调度。调度中,根据优先级,保证任务的最优前驱被优先调度,并在不影响调度长度的同时,将任务尽可能地调度到其已调度兄弟所在处理器上。实验表明,与TDS、DCP、MCP算法相比,LSA_IT的调度性能最优。     

一种异构计算环境下基于复制的调度算法

提出了一种异构环境下的基于复制的调度算法（TDNH）,并与同为异构环境下的HEFT算法进行了比较,结果证明TDNH算法减小了时间跨度。最后通过实验证明了TDNH算法能够得到比较好的结果。     

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

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

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

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

一种改进的优先级列表任务调度算法

异构多核处理器任务调度是高性能计算领域的重要问题。针对优先级列表调度算法中存在的优先级排序方法失当、调度结果不理想的问题,提出一种改进的优先级列表任务调度算法。该算法对传统优先级列表任务调度中以任务执行时间平均值作为参数的优先级计算方式进行优化,提出一种基于异构核性能差异性、依赖任务特征加权优先级的排序方式。在此基础上,以当前格局下每个任务的向后关键路径执行时间为权值作为任务分配到处理器内核的依据,克服贪心思想在内核选择中带来的局部最优解问题。此外,在任务分配阶段利用任务复制和区间插入技术,缩短任务最早开始时间,提高处理器利用率。实例分析和模拟实验结果表明,该算法可有效降低任务的执行时间,能发挥异构多核处理器优势。     

概率构造算法与遗传算法融合的可重构计算系统硬件任务划分

提出一种概率构造算法与遗传算法融合的算法,通过引入表示划分结果多样性的度量方法,利用概率构造算法产生具有多样性的较优的初始群体,并在此基础上利用遗传算法寻求最优解.实验结果表明,该算法能够获得比已有的基于列表的划分算法更优的划分结果,比采用完全随机初始群体的遗传算法缩短了运行时间.     

云计算环境下基于路径优先级的任务调度算法

为了最小化云计算系统的任务调度长度,结合表启发式调度技术和任务复制的思想提出基于路径优先权的任务调度算法.采用一种新方法计算DAG图中任务节点及边的权值,从最高优先权的路径开始依次选择任务进行调度,并通过有选择性地复制任务节点的父任务来减少任务间信息传送的时间花费,最后将任务安排到使其执行完成时间最早的虚拟机上.通过随机产生的DAG图与HEFT算法进行对比分析,实验结果表明了该算法能获得较短的调度长度.     

网格环境下的静态启发式任务调度算法

针对网格环境中应用程序常为复杂的计算密集型的并行分布式应用程序,提出了一个新的基于复制和插入的启发式任务调度算法(duplication-and-insertion-based scheduling,DIBS),可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载.实验结果表明,该算法更加符合网格的复杂环境,能够更好地满足不同用户的实际需要.     

同构计算环境中一种新的静态任务调度算法

延伸了TTIG模型并提出新的算法．在模拟实验中，将此算法与MATE和其它同构环境中基于DAG的调度算法，在不同测试条件下进行了比较，结果显示该算法性能明显优于MATE，与基于DAG模型的调度算法比较而言，在性能方面各有千秋，但在算法时间复杂度方面具有显著的优势．     

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

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