基于Hadoop的三队列作业调度算法

Hadoop集群单队列作业调度会产生短作业等待、资源利用率低的问题;采用多队列调度可兼顾公平、提高执行效率,但会带来手工配置参数、资源互占、算法复杂等问题。针对上述问题,提出三队列作业调度算法,利用区分作业类型、动态调整作业优先级、配置共享资源池、作业抢占等设计,达到平衡作业需求、简化一般作业调度流程、提升并行执行能力的目的。对短作业占比高,各作业占比均衡以及一般作业为主,偶尔出现长、短作业三种情况与先进先出(FIFO)算法进行了对比实验,结果三队列算法的运行时间均比FIFO算法要少。实验结果表明,在短作业聚集时,三队列算法的执行效率提升并不显著;但当各种作业并存且分布均衡时,效果很明显,这符合了算法设计时短作业优先、一般作业简化流程、兼顾长作业的初衷,提高了作业整体执行效率。     

基于节点集计算能力差异的Hadoop自适应任务调度算法

针对异构集群任务推测式执行算法存在的任务进度比例固定、落后任务被动选取等问题,提出基于快慢节点集计算能力差异的自适应任务调度算法。该算法量化节点集计算能力差异实现分集调度,并通过节点与任务速率的动态反馈及时更新快慢节点集,提高节点集资源利用率与任务并行度。在两节点集中,利用动态调整任务进度比例判别落后任务,主动选择采用替代执行方式为落后任务执行备份任务的快节点,从而提升任务执行效率。与最长近似结束时间(LATE)算法的实验对比结果表明,该算法在短作业集、混合型作业集、出现节点性能下降的混合型作业集执行时间上比LATE算法分别缩短了5.21%、20.51%、23.86%,启用的备份任务数比LATE算法明显减少。所提算法可使任务主动适应节点差异,在减少备份任务的同时有效提高作业整体执行效率。     

异构环境下改进的LATE调度算法

针对异构环境下LATE算法在选择备份任务及执行节点时的不足,提出一个改进的IR-LATE调度算法。算法通过计算为剩余完成时间最长、最需要备份的慢任务启动备份,并将其按负载不同进行分类,结合轮询算法,将备份任务分配到负载最小且成功/负载比高的节点上执行。实验结果表明,该算法与LATE算法比较,有效的将作业完成时间缩短了30%左右,提高了执行效率,进而促进系统的负载均衡。     

Hadoop平台的多队列作业调度优化方法研究

对Hadoop平台的作业调度算法进行了研究, 提出了支持作业类型区分的多队列调度优化算法。优化算法支持根据节点当前的负载情况分配不同类型的作业, 以提高节点的资源利用率; 允许作业队列的资源在闲置时被其他作业队列占用; 在原作业队列需要时可以被即时回收, 即回收过程支持任务抢占; 采用共享队列列表和非共享队列列表的逻辑划分来防止乒乓效应。Hadoop平台的性能测试结果表明, 优化算法相比系统默认算法在作业调度的执行效率、执行平稳性等方面都有了显著的提升。     

气象环境下的云计算调度算法

针对气象计算的特点,提出气象计算的云模型,在这个模型之上,提出气象云计算（Weather Cloud）的启发式调度算法。调度算法对气象作业按照时间紧迫型、CPU紧迫型、内存紧迫型和硬盘空间紧迫型进行分类,计算资源综合紧迫指数,相应地赋予不同调度优先权限。与CMMS（Cloud Min min Scheduling）、AFCFS（Adaptive First Come First Service）、Fair的调度算法对比表明,Weather Cloud的调度算法不但减少了计算的等待时间,而且增加了完成的指令数量。     

基于奖惩共存收益模式的大数据作业调度器

为满足服务商获得最大收益、达到平台资源利用率最大的要求，提出一种基于奖惩共存收益模式的大数据作业调度器，该调度器中包括基于任务执行时间的确定轮数算法(TRN)和基于最大轮数的作业调度算法(MRNS)。TRN确定作业在不同奖惩阶段的Map和Reduce的最大轮数组合以及最大标准时间；MRNS选择具有局部最大收益的作业和该作业的任务最大轮数方案，制定出基于任务的作业调度策略。实验结果表明，提出的作业调度器对比已有的调度器，作业平均完成时间缩短了13.5%～25.9%、服务商收益提高了16.3%～26.4%,平台资源利用率平均提高了7.8%～10.3%,故该大数据作业调度器具有一定的高效性和可用性。     

Hadoop平台下计算模型中调度策略的研究

针对Hadoop平台下默认调度算法FIFO、计算能力调度算法以及公平调度算法在调度过程中遵守严格的队列顺序,导致一些任务被调度到不满足数据本地性节点上的问题,提出一个基于本地性的调度算法——延时调度。该算法在维护公平性原则的同时,当一个被调度的作业无法启动一个本地的任务时,让这个任务等待一小段时间,调度其他作业先执行。实验结果表明,此调度算法缩短了作业平均响应时间,有效增加了集群系统的吞吐量,提高了集群资源利用率。     

基于混合GA算法的工作流作业调度队列优化

工作流作业的调度效率是评价工作流管理系统整体表现的重要指标。众所周知,工作流作业的调度问题是一个NP-hard问题,而异构的计算环境使得问题更加棘手。分层基因算法LGA将启发式算法与GA算法相结合,利用GA算法来优化经过正向分层之后的工作流作业调度队列,显著地减少了工作流作业的执行时间。该算法根据作业的分层优先级来产生作业队列,把队列中的同层作业从整体上看作是一位基因来处理,有效地对算法的进化方向进行规划,并通过对杂交和变异流程的改进,增强算法的搜索深度和广度。实验表明,相比于其他混合GA算法,经LGA算法优化之后的工作流作业调度队列,所需的执行时间更少。     

集群中基于资源可用度的作业调度

提出一种基于资源可用度的集群作业调度算法,综合考虑资源的历史记录和当前的资源信息。基于资源可用度评价方法,改进原有的Min-Min算法。采用GridSim对算法进行模拟实验,并与Min-Min算法进行了对比。模拟实验结果显示,基于可用度的作业调度算法提高了集群的效率和作业的完成效率,缩短了作业的平均完成时间。     

基于集群拓扑结构的工作流调度研究

针对MapReduce的默认调度策略先进先出(FIFO)在执行任务时考虑本地性调度带来的任务等待时间长、资源利用率不高和没有考虑任务的优先级等问题,提出一种基于集群拓扑结构的工作流实时调度算法。MapReduce在对工作流进行Map处理时,首先根据taskTracker的计算能力和数据大小对map阶段工作流的完成时间进行估计,得到一个完成时间隶属函数,然后再利用集群的拓扑结构,得到taskTracker在集群中的距离隶属函数,根据这两个隶属函数来对集群中的taskTracker在工作流处理时间和数据传输时间进行综合性能评估,这样可以有效地缩短任务的等待时间并提高资源的利用率。同时该算法采用对作业进行优先级划分的方式,满足不同类型作业的需求。大量的实验结果表明:该优化策略在平均完成时间和平均等待时间方面要优于FIFO算法,可以有效提高工作流处理的实时性。     

多租户集群中基于服务水平目标的调度机制

针对多租户集群中无法保证作业服务水平目标(SLO)的问题,提出了一种多租户场景下基于SLO的调度机制,其中包括优先调度算法和资源抢占算法。优先调度算法区别考虑超额使用资源的租户和未超额使用资源的租户,赋予后者的作业更高的优先级,在此前提下选择紧急度最高的作业,优先为其分配资源;资源抢占算法在资源受限的情况下,选择紧急度超过阈值的作业实施资源抢占,并根据租户的资源使用情况,在相应的运行作业范围内选择紧急度最低的作业,抢占其资源。实验结果表明,与现有保证公平的多租户调度器Capacity Scheduler相比,该调度机制可以在兼顾作业执行效率和租户间公平的前提下,显著提高作业的截止时间保证率,从而保证业务的服务水平目标。     

数据密集作业在GPU集群上的调度算法研究

数据密集型作业包含大量的任务,使用GPU设备来提高任务的性能是目前的主要手段.但是,在解决数据密集型作业之间的GPU资源公平共享以及降低任务所需数据在网络间的传输代价方面,现有的研究方法没有综合考虑资源公平与数据传输代价的矛盾.分析了GPU集群资源调度的特点,提出了一种基于最小代价最大任务数的GPU集群资源调度算法,解决了GPU资源的公平分配与数据传输代价较高的矛盾.将调度过程分为两个阶段：第1阶段为各个作业按照数据传输代价给出自己的最优方案;第2阶段为资源分配器合并各个作业的方案,按照公平性给出全局的最优方案.首先,给出了GPU集群资源调度框架的总体结构,各个作业给出自己的最优方案,资源分配进行全局优化;第二,给出了网络带宽估计策略以及计算任务的数据传输代价的方法;第三,给出了基于GPU数量的资源公平分配的基本算法;第四,提出了最小代价最大任务数的资源调度算法,描述了资源非抢夺、抢夺以及不考虑资源公平策略的实现策略;最后,设计了6种数据密集型计算作业,对所提出的算法进行了实验.通过实验验证,最小代价最大任务数的资源调度算法对于资源公平性能够达到90%左右,同时亦能保证作业并行运行时间最小.     

A new window-based job scheduling scheme for 2D mesh multicomputers

Allocating submeshes to jobs in mesh-connected multicomputers in a FCFS fashion can lead to poor system performance (e.g., long job waiting delays) because the job at the head of the waiting queue can prevent the allocation of free submeshes to other waiting jobs with smaller submesh requirements. However, serving jobs aggressively out-of-order can lead to excessive waiting delays for jobs with large allocation requests. In this paper, we propose a scheduling scheme that uses a window of consecutive jobs from which it selects jobs for allocation and execution. This window starts with the current oldest waiting job and corresponds to the lookahead of the scheduler. The performance of the proposed window-based scheme has been compared to that of FCFS and other previous job scheduling schemes. Extensive simulation results based on synthetic workloads and real workload traces indicate that the new scheduling strategy exhibits good performance when the scheduling window size is large. In particular, it is substantially superior to FCFS in terms of system utilization, average job turnaround times, and maximum waiting delays under medium to heavy system loads. Also, it is superior to aggressive out-of-order scheduling in terms of maximum job waiting delays. Window-based job scheduling can improve both overall system performance and fairness (i.e., maximum job waiting delays) by adopting large lookahead job scheduling windows.     

一种面向BSP系统的多等待队列作业调度算法

在以往的BSP（Bulk Synchronous Parallel）系统中,作业调度都是采用基于单队列的优先级调度策略.它的优点是实现简单,但作业队列维护开销大,低优先级作业存在无限等待的问题.论文提出了面向BSP系统基于多等待队列的按优先级作业调度算法,以高响应比优先级队列为作业组织方式,并加入了作业优先级的动态调整策略,避免了低优先级作业因长期得不到执行而废弃的情况.目前,论文所提算法已成功运行于BC-BSP系统中.文中通过实验进一步证明,融合了作业优先级调整策略的基于多等待队列的作业调度算法较传统的单队列优先级调度算法在队列维护方面,能降低30％～50％的维护代价.另外,在兼顾作业的初始优先级的同时,能够减少低优先级作业的等待时间,避免低优先级作业的无限等待问题.     

分布式环境中的多作业执行调度策略与优化

分布式大数据计算引擎是科研机构、互联网企业和政府部门处理大规模数据必不可少的工具,它们的使用和推广促进了各个领域的快速发展,为社会进步做出了巨大贡献.但是,在多作业处理的情况下,目前主流的大数据计算引擎在资源分配和作业调度方面仍有许多不足之处,它们通常对多作业平均划分内存资源并以先进先出FIFO的方式调度作业,这样简单...     

大型高能物理计算集群资源管理方法的评测

高能物理数据由物理事例组成,事例之间没有相关性。可以通过大量作业同时处理大量不同的数据文件,从而实现高能物理计算任务的并行化,因此高能物理计算是典型的高吞吐量计算场景。高能所计算集群使用开源的TORQUE/Maui进行资源管理及作业调度,并通过将集群资源划分成不同队列以及限制用户最大运行作业数来保证公平性,然而这也导致了集群整体资源利用率非常低下。SLURM和HTCondor都是近年来流行的开源资源管理系统,前者拥有丰富的作业调度策略,后者非常适合高吞吐量计算,二者都能够替代老旧、缺乏维护的TORQUE/Maui,都是管理计算集群资源的可行方案。在SLURM和HTCondor测试集群上模拟大亚湾实验用户的作业提交行为,对SLURM和HTCondor的资源分配行为和效率进行了测试,并与相同作业在高能物理研究所TORQUE/Maui集群上的实际调度结果进行了对比,分析了SLURM及HTCondor的优势和不足,探讨了使用SLURM或HTCondor管理高能物理研究所计算集群的可行性。     

面积最大优先调度的预约回填算法

传统backfilling算法是在先来先服务基础上,将小作业回填到空闲CPU,以提高CPU利用率。该算法偏向小作业,大作业也会因为长期等待出现饥饿现象。当空闲CPU数无法满足算法中小作业回填要求时,系统仍有部分CPU闲置,难以更好地提高CPU利用率。本文中提出的算法以作业所需CPU数及预估运行时间构成的二维面积作为优先调度的条件,引入二级优先级和预约算法消除大作业的饥饿现象,减少回填作业CPU数,相应增加预估运行时间,更好提高CPU利用率。实验证明,该算法比传统backfilling算法在保证用户公平性,缩短作业平均响应时间及CPU利用率方面有所提高。     

Job scheduling algorithm based on Berger model in cloud environment

Considered the commercialization and the virtualization characteristics of cloud computing, the paper proposed for the first time an algorithm of job scheduling based on Berger model. In the job scheduling process, the algorithm establishes dual fairness constraint. The first constraint is to classify user tasks by QoS preferences, and establish the general expectation function in accordance with the classification of tasks to restrain the fairness of the resources in selection process. The second constraint is to define resource fairness justice function to judge the fairness of the resources allocation. We have expanded simulation platform CloudSim, and have implemented the job scheduling algorithm proposed in this paper. The experimental results show that the algorithm can effectively execute the user tasks and manifests better fairness.