一个调度Out-Tree任务图的启发式算法

任务调度问题是并行分布式计算中的挑战性问题之一。大多数实际的调度算法是启发式的因而常常具有改进的余地。针对Out-Tree任务图这一基本结构提出一个基于任务复制的启发式调度算法,该算法在确保最短调度长度的同时,注重处理器的负载平衡,以达到节约处理器的目的。比较性实验的结果表明,该算法确保了最短调度长度且使用的处理器最少。因而,该算法提高了系统的利用率,避免消耗过多的资源,实际应用性更好。     

基于优先规则的空间资源约束项目调度算法

任务组占用空间资源项目调度问题需满足组内任务的序关系和人力、设备等常规资源约束,以及空间资源这一特殊资源的约束,同时任务组之间也需满足上述约束,使得该调度问题异常复杂。以船舶建造分段制造问题为背景,建立任务组占用空间资源受限的项目调度问题数学模型,基于并行调度生成方案提出基于优先规则的启发式调度算法,实现对该调度问题的综合求解。实例测试结果表明了该算法的正解性和有效性。     

并行异构系统中的一种高效任务调度算法

并行分布计算是当前计算机科学的热点之一。调度算法是影响分布式计算的关键因素,也是一个具有挑战性的课题。调度算法是将有通信关系的任务按顺序分配给不同的处理器。提出了一种基于区间插入和任务复制的高效启发式算法,通过对各种随机任务图和高斯迭代任务图进行模拟,与已有算法相比,新算法的效率有很大的提高。     

一个面向仿真程序的任务聚类算法

对仿真程序原始任务图的聚类运算是实现仿真程序并行化的关键。在研制面向仿真程序自动并行化系统AFPS的过程中,提出了一个基于状态变量一阶微分的并行任务聚类算法。使用结果表明,该算法可以最大限度地保证各处理机结点的负载均衡,减少通信次数,且易于实现通信变量的自动确定。     

树型网格计算环境下的自适应任务调度算法

提出一种基于树型计算网格的自适应调度算法,实现对小粒度独立任务和用户大作业的自适应最优调度。通过对网格环境的实时检测,给出了基于节点负载状况、节点任务执行时间、任务传输时间和任务特性的自适应调度算法,即基于最优任务分配方案的启发式任务调度算法。通过实验与其他调度算法的比较,证明了所提出的任务调度算法在负载平衡和最优跨度方面具有明显的优越性。     

基于综合优先级的并行测试调度算法设计及实现

根据并行测试实际运行环境对多测试调度策略效率的要求,借鉴实时系统调度算法研究的相关成果,提出基于综合优先级的并行测试调度算法;算法结合并行测试,尤其是导弹测试特点,综合考虑测试任务的相对截止期和空闲时间两个特征参数,讨论了测试任务综合优先级的设计方法,给出了算法实现,并对算法的性能进行了分析;该算法无须预先确定测试任务参数的典型值,可以弥补TestStand的局限性.     

负载敏感的云任务三支聚类评分调度研究

在云计算商业化的服务模式中,追求服务质量、负载均衡与经济原则的多目标优化调度。针对集群资源使用率偏低的现象,提出了三支聚类评分（three-way clustering weight,TWCW）算法,首先分析云任务的多样化需求与资源的动态特性,采用三支聚类算法对任务集合聚类划分,然后结合任务属性对类簇对象进行评分调度。基于Cloudsim实验模拟表明:相比于k-means与FCM聚类调度,三支聚类评分算法（TWCW）在任务平均响应时间与资源利用率等方面均有显著提升。     

敏捷凝视卫星密集点目标聚类与最优观测规划

针对敏捷凝视卫星密集点目标观测规划问题,提出一种快速观测任务聚类策略和启发式蚁群优化算法.首先,针对敏捷凝视卫星视场范围特点,提出基于顶点度的团划分算法,解决密集点观测任务聚类问题,形成系列团观测目标,有效提高观测效率;其次,为得到最优团目标观测序列,考虑目标可见时间窗口约束以及卫星敏捷机动能力约束,构建基于多目标观测收益和姿态机动能耗的性能指标,实现能量高效的任务规划;再次,为克服传统蚁群算法易陷入局部极小值和收敛较慢的缺点,设计一种同时考虑目标点优先级、目标可见时间窗口、目标之间卫星姿态转换时间等因素的启发式蚁群算法;最后,选取大规模密集地面目标验证所提出算法的可行性和高效性.     

任务与资源双向匹配的动态任务调度策略研究

并行测试系统中的测试任务的执行时间是不确定的,测试任务过程具有随机性。为实现测试任务优化执行的目的,建立了并行自动测试系统的动态任务调动模型,并提出了基于测试任务剩余工作量和测试资源剩余负载的启发式调度规则,并在测试任务过程Petri网模型的运行演化算法中采用该规则,实现并行测试任务的动态调度。最后通过实例仿真,验证了该策略的可行性和优越性。     

基于启发式算法降低比例公平调度开销策略

在多处理器系统中已经证明了比例公平(proportion fair, Pfair)算法是调度周期任务最优的全局调度算法。然而在该算法的最坏执行情况下,任务在每个调度时刻均产生切换或迁移,导致系统开销过大。针对这一问题,对Pfair算法进行深入研究后发现,任务的分配过程是一个重要原因。基于此,提出基于启发式算法的模拟退火比例公平(simulated annealing-proportion fair, SA-Pfair)调度算法,即在Pfair算法做出调度决策后,用启发式算法将任务分配给处理器,以弥补原算法的不足。最后,采用LITMUS-RT平台对SA-Pfair算法和以此为基础设计的调度器进行仿真。结果表明,新算法在一定程度上减少了任务的切换次数以及50%以上的任务迁移总量,且能够有效地降低调度过程中的系统开销。     

减链约束多处理器任务在三处理器中的调度

研究三个并行处理器环境中,具有递减链约束的多处理器任务的调度问题,调度目标 是最小化总处理时间,假设单项任务需单位处理时间.首先给出了减链调度问题的最优化性质 与条件,并说明了减链调度问题仍然是NP难的.随后基于两段flow-shop问题的Johnson's算 法的修正和减链调度问题最优化性质,提出了一个启发式算法,并从分析和仿真计算两方面说 明该算法是有效的和高效的.     

云计算环境下基于模糊聚类的并行调度策略研究

并行任务调度是分布式计算研究的核心问题之一,其结合大规模的石油地震勘探数据在处理过程中对高性能计算的需求,研究云计算环境下地震资料数据的并行调度问题。由于地震资料数据规模较大,因此通常将大作业进行分割,通过并行处理获得较高的处理效率。对任务进行并行处理的一个关键问题是如何将划分后的任务分配到合适的调度节点,最高效的情况是使云计算环境中的每一个资源节点都在进行计算,并且计算性能高的节点执行作业块大且复杂的任务,性能相对低的资源节点则运行对计算性能要求不高的任务或小任务,以达到整体上的负载平衡。因此基于模糊聚类思想,提出一种任务与资源混合聚类的调度优化策略,以作业与资源节点属性的匹配程度为基准,对并行作业进行聚类划分求解,在缩小任务调度规模的同时,为动态调度任务奠定基础。在划分完成后引入基于改进的贝叶斯分类调度算法,将资源节点依据其实时负载情况与队列中的作业进行快速的匹配。实验证实,此方案具有较高的执行效率。     

基于用户任务级的Web日志聚类

利用改进的用户描述计算公式和启发式聚类方法 ,进行基于用户任务级的 Web日志聚类 ,产生簇用户访问模式 ,进行有效的推荐和个性化服务 .结果表明 ,算法具有较好的聚类质量和较高的性能 .它可以成功地应用到 Web日志挖掘中 .     

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

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

嵌入式并行系统中基于任务优化的调度算法

在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关任务优化(DTO)的调度算法,通过分析已用处理机的负载和空闲时间,尽量减少系统的调度长度和处理机数目。算法分析结果表明,DTO算法在性能上优于其他算法,对嵌入式并行计算系统中的多任务调度是一个较好的选择。     

禁忌搜索方法解最小化拖期任务数的并行多机调度问题

禁忌搜索方法（ＴＳ）是一种将人工智能技术引入管理中的一种高于一般启发式算法的智能化“超启发式”算法，它能有效地解决大型组合优化问题。本文用ＴＳ方法解决最小化拖期任务数的并行多机调度问题，并同目前最好的启发式作了比较，大量实验表明了ＴＳ方法的有效性。     

基于任务复制的调度算法

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

异构系统中的综合性启发式任务调度算法

任务的单个属性常作为基于优先驱动的表调度算法的优先级,针对这种方法常出现优先级相同的情况,提出一个综合性启发式算法HCPFS。算法分三个优先级选择任务进行调度,从高到低依次为：关键路径上的任务、就绪任务到出口任务的路径长度和后继任务数。调度过程中,算法采用任务复制和空闲时间区段任务插入的方法。采用随机生成图法和任务图集进行了算法模拟和比较,实验数据表明HCPFS算法具有更好的调度性能。     

任务并行编程模型下排列熵算法的并行实现

排列熵算法随着嵌入维数的增大,运算规模将会呈平方级数增大,计算时效性问题突出,亟待解决。为此,提出一种基于任务并行编程模型的线程级并行方法,通过任务并行运行系统(StarPU)将密集型计算划分为多个独立的任务,再由调度器将任务调度到不同的CPU上执行,实现排列熵算法的并行化。基于StarPU的排列熵并行算法与串行程序相比较,加速比为23.79倍,相较于OpenMP(一种用于共享内存并行系统的并行计算方案),在分配28个线程时,加速比为1.17倍,结果表明该方法能够有效实现排列熵算法的加速执行。     

一种基于虚拟截止时间制导的改进的Min-Min元任务调度算法

在网格环境下,资源状况和用户行为相当复杂,是一个异构计算环境,元任务（meta—task）调度比传统并行调度更为复杂。如何映射一组任务到一组机器上被证明是NP问题,其目的一般是最小化任务完成时间（makespan）。为解决这一问题,已经提出一些启发式任务调度算法,例如具有代表性的MinMin元任务调度算法。本文在Min-Min元任务调度算法的基础上,通过虚拟截止时间制导的方法来改进Min-Min算法。实验结果表明,本文提出的算法具有更短的任务完成时间。