资源不均衡Spark环境任务调度优化算法研究

由于硬件资源的更新换代,集群中各个节点的计算能力会变得不一致。集群异构的出现导致集群计算资源不均衡。目前Spark大数据平台在任务调度时未考虑集群的异构性以及节点资源的利用情况,影响了系统性能的发挥。构建了集群节点的评价指标体系,提出利用节点的优先级来表示其计算能力。提出的节点优先级调整算法能够根据任务执行过程中节点的状态动态调整各个节点的优先级。基于节点优先级的Spark动态自适应调度算法(SDASA)则根据实时的节点优先级值完成任务的分配。实验表明,SDASA能够缩短任务在集群中的执行时间,从而提升集群整体计算性能。     

GPU/CPU异构系统任务节能调度方法仿真

研究GPU/CPU异构系统任务调度的节能问题.与传统同构体系结构相比,异构系统任务调度呈现较大的随机性和不定性,GPU/CPU异构系统中时间间隙片段呈现了较大的随机性,导致传统调度方法很难建立规则的描述时间片段的模型,调度能耗较高.为解决上述问题,提出了一种改进功耗优化的GPU/CPU异构环境下的任务调度算法,将任务关系图按照依赖关系计算量拆分,并分配到计算节点.在计算节点内根据权重法的思想,统计所有计算节点的处理情况,进而将节点内的子任务调度到合适的处理器.实验结果表明,在不影响应用性能的前提下,降低了异构系统的能耗开销,优化效果明显.     

基于异构Flink集群的节点优先级调度策略

Flink流处理系统默认的任务调度策略在一定程度上忽略了集群异构和节点可用资源,导致集群整体负载不均衡。研究分布式节点的实时性能和集群作业环境,根据实际作业环境的异构分布情况,设计结合异构Flink集群的节点优先级调整方法,以基于Ganglia可扩展分布式集群资源监控系统的集群信息为依据,动态调整适应当前作业环境的节点优先级指数。基于此提出Flink节点动态自适应调度策略,通过实时监测节点的异构状况,并在任务执行过程中根据实时作业环境更新节点优先级指数,为系统任务找到最佳的执行节点完成任务分配。实验结果表明,相比于Flink默认的任务调度策略,基于节点优先级调整方法的自适应调度策略在WorldCount基准测试中的运行时间约平均减少6%,可使异构Flink集群在保持集群低延迟的同时,节点资源利用率和任务执行效率更高。     

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

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

考虑通信竞争的任意处理机网络表调度算法

任务调度是高性能计算系统中的基本问题之一。解决此类NP难问题的经典启发式算法都假定目标处理机全互连,调度任务时可忽略节点间通信,这显然与实际计算环境不符。为此,文中提出一种在调度任务时同时考虑通信边调度的表调度算法。在边调度时,提出了一种基于最短路径搜索算法的最早通信完成路径查找算法(EFCS),并采用插入式链路策略实现通信边的动态调度,而对处理机网络异构环境下的任务优先级计算问题,受HEFT算法启发,提出异构系统递归优先权计算方法,按非升序排列获得各任务优先级。为了降低算法的执行时间,文中还提出了理论加速比为O(PPE)的并行算法。以随机产生程序任务图和DSP应用程序实例为数据源,在两类不同任意处理机网络目标系统上进行的模拟实验结果表明:本算法明显优于考虑通信竞争的静态表调度算法和不考虑通信竞争的表调度算法,特别是在高通信率应用程序中优势更明显。     

虚拟计算环境中的多机群协同调度算法

基于虚拟计算环境的核心机理,提出由自主调度单元、域调度共同体、元调度执行体为核心的多机群协同系统框架.剖析多机群任务并发运行性能模型,设计了多机群协同调度算法框架,提出最大空闲节点优先、最小网络拥塞优先、最小异构因子优先与最小异构空闲节点优先4种启发式资源选择策略.实验验证了协同调度模型与算法在任务集完成时间与系统平均利用率的测度上的有效性.     

异构云环境下的密码服务调度方法

针对云计算环境下存在密码服务请求算法种类多、资源需求差异化和节点性能异构等问题。为了提高系统的可靠性,保证服务质量,综合考虑用户请求任务和处理节点等多种因素,在作业包截止时间的基础上,通过任务映射策略完成密码服务的一级调度。设计一个基于用户优先级和任务等待时间的任务优先级调度算法实现二级调度,从而构造一种同时支持多种密码服务请求和任务动态可调整的调度系统框架,以保证云环境下任务的时效性。仿真结果表明,该系统有较好的执行效率和负载分布效果,达到设计目标。与随机法和遗传算法相比,其执行效率分别提高了17%和11%左右。     

一种高回报的最小空闲时间优先实时调度改进算法

信号任务调度算法是提高信息物理系统执行效能的关键,而最小空闲时间优先算法(LSF)、最早截止时间优先算法(EDF)和最大价值优先算法(HVF)在系统满载的情况下无法很好地完成任务调度并且系统能耗很高。为此,提出一种改进型调度算法。将任务能耗、任务完成价值和任务紧迫程度相结合,通过引入任务调度优先级和任务实际调度优先级的形式,实现任务的动态调度。实验结果表明,对于同一个任务集,在完成相同调度任务数量的情况下,改进算法的系统能耗小于采用LSF算法和EDF算法的系统能耗。系统满载时,在完成任务总价值相同的情况下,采用改进算法的系统所需要的能耗比HVF算法更少。     

面向节点异构GPU集群的能量有效调度方案

GPU集群已经成为高性能计算(HPC)领域的主流组件。随着处理单元的发展和集群节点的拓展,GPU集群将在节点层面趋于异构化。提出一套针对异构任务在节点异构GPU集群上的能量有效调度方案。形式化地描述其任务和资源模型以及能耗评估模型。通过特定的节点选择策略,减少空闲状态的能耗损失。通过任务类型划分和组合分配以及DVFS,增加CPU资源利用率。该方案从系统层面着手,能够与现有的算法和指令层面的优化方法兼容。     

一种基于DAG的MapReduce任务调度算法

Hadoop已成为研究云计算的基础平台,MapReduce是其大数据分布式处理的计算模型。针对异构集群下MapReduce数据分布、数据本地性、作业执行流程等问题,提出一种基于DAG的MapReduce调度算法。把集群中的节点按计算能力进行划分,将MapReduce作业转换成DAG模型,改进向上排序值计算方法,使其在异构集群中计算更精准、任务的优先级排序更合理。综合节点的计算能力与数据本地性及集群利用情况,选择合理的数据节点分配和执行任务,减少当前任务完成时间。实验表明,该算法能合理分布数据,有效提高数据本地性,减少通信开销,缩短整个作业集的调度长度,从而提高集群的利用率。     

异构集群中基于优先级的任务容错调度算法

提出一种基于任务优先级的容错调度算法,任务的优先级并不是由用户指定,而是由任务的开始时间、执行时间和截止期限决定的。该算法能够容忍异构集群系统中一个节点故障,采用主动/被动副版本相结合的执行方式和重叠技术的备份方式,提高系统资源利用率。通过实验证明了该算法在容错调度中的可靠性和高效性。     

一种基于两级DAG模型的MapReduce工作流异构调度算法

MapReduce编程模型被广泛应用于大数据处理平台,而一个有效的任务调度算法对模型的运行效率至关重要。将MapReduce工作流的Map和Reduce阶段分别拆解为若干个有先后序限定关系的作业,每个作业再拆解为多个任务。之后基于计算集群的可用资源和任务异构性,构建面向作业和任务的2级有向无环图(DAG)模型,同时提出基于2级优先级排序的异构调度算法2-MRHS。算法的第1阶段进行优先级排序,即对作业和任务分别进行优先权值计算,再汇总得到任务的调度队列;第2阶段进行任务分配,即基于最快完成时间将每个任务所包含的数据块子任务分配给最适合的计算结点。采用大批量随机生成的DAG模型进行实验,结果表明与其他相关算法相比,本文算法有更短的调度长度(makespan)且更加稳定。     

多核嵌入式系统总线冲突避免的节能调度综述

在多核嵌入式系统中,避免总线冲突并在时间限制下调度通信任务和计算任务来降低能量消耗是非常重要的,有效节能调度可以避免总线冲突并在时间限制下实现有效节能。由于任务的粒度、优先级、通信任务和计算任务的协同调度对此类算法的节能有着重要影响,概述了这三个方面的研究现状,指出总线冲突避免的节能调度算法设计中有待解决的问题,并给出了多核嵌入式系统总线冲突避免的节能调度算法的发展方向。     

基于优先级和优化完成时间的网格调度算法

网格由大量的异构资源组成，具有复杂性、动态性和自治性特点。高效的网格调度算法可以充分利用网格系统资源，提高网格处理应用程序的能力。Min min算法是一个简单、快速、有效的调度算法，但由于总是先分配小任务而不能确保负载平衡。文中首先对网格系统中任务的数据传输和执行进行分析，计算并优化Min min算法的任务完成时间，再根据任务需求赋予任务优先级，通过优先级安排任务调度，提高算法负载平衡能力，最后在上述分析基础上提出POTE Min min(Priority and Overlap Transmission and Execution Min min)调度算法。     

异构系统中一种基于可用性的抢占式任务调度算法*

针对大多数现有的异构系统调度算法没有考虑由多类任务特别是抢占式任务所引起的可用性需求的不足,在现有基于可用性的非抢占式任务调度算法的基础上,通过计算任务的平均等待时间来确定优先级等级,对异构系统中多类抢占式任务的可用性约束的调度问题进行了探索,提出了一种基于可用性的抢占式优先调度算法P-SSAC。该算法在不增加硬件代价的前提条件下通过调度增加了系统的可用性,缩短了任务的平均等待时间,同时该算法可对抢占式的任务进行有效调度。仿真实验结果表明,该算法有效实现了异构系统可用性和任务等待时间之间的折中。     

AUV协同设计平台中多任务流调度算法研究

对AUV协同设计平台中多个任务流的调度问题进行建模,将其转换为分布式计算环境下的独立任务在线调度问题。针对系统异构和任务流具有优先级属性的特殊性,提出了一种基于预测的多任务流调度算法,采用统计和预测的方法评估各工作站执行任务的效用,并设计优先级策略和暂停调度策略,保证具有较高优先级的任务流较早分配和执行。实验结果表明,该算法在参数选取适当的情况下,性能优于传统的MCT和MET任务调度算法。     

基于有向无环图网格独立任务调度算法*

提出了基于有向无环图多约束网格环境下独立任务的调度模型,为其建立多约束线性规划模型,通过求解模型节点的优先级,获得网格各计算节点最优任务调度数;然后基于多约束最优任务调度方案,提出多约束带宽优先启发式算法(MCOPBHATS)和多约束计算速度优先启发式算法(MCOPCHATS)。实验结果表明,在多约束异构的网格环境下实现大量独立任务调度时, MCOPBHATS和MCOPCHATS算法的性能优于基于多约束最优任务调度方案的MinMin 算法。     

云计算中基于优先级和费用约束的任务调度算法

针对云计算中的服务质量保证问题,提出一种基于优先级和费用约束的任务调度算法。该算法通过计算任务优先级和资源服务能力,分别对任务和资源进行排序和分组,并根据优先级高低和服务能力强弱建立任务组和资源组间的调度约束关联;再通过计算任务在关联资源组内不同资源上的完成时间和费用,将任务按优先级高低依次调度到具有任务完成时间和费用折中值最小的资源上。与Min-Min和QoS-Guided-Min算法的对比实验结果表明,该算法具有良好的系统性能和负载均衡性,并降低了服务总费用。     

一种适于异构环境的任务调度算法

针对异构环境独立任务调度问题提出两个调度原则,并基于Min-min算法提出优先级最小最早完成时间算法(Priority min-min,PMM).该算法将任务在各处理机上执行时间的标准误差作为任务的优先级.选取最早完成时间较小的k个任务,优先调度其中优先级最高的一个.在实验基础上分析了参数$k$对PMM算法性能的影响. PMM算法克服了min-min算法单纯追求局部最优的局限性,更适合于异构环境.实验数据表明PMM算法能有效地降低调度跨度,其性能比min-min算法有明显提高.     

异构重构计算系统应用任务调度的性能分析

异构重构计算是目前高性能计算的研究热点.由于应用任务的异构性,以及体系结构的可重构性,导致异构重构计算的性能分析非常困难,现有的并行计算性能分析方法不再适用.本文提出一种基于应用任务调度的性能分析方法,该方法以异构重构计算系统模型和应用任务模型为基础,利用异构匹配、重构耦合矩阵,实现应用任务和处理部件的优化选择和耦合匹配,通过调度算法求出应用任务在异构重构计算系统中的完成时间,并进行了实例分析.