基于延迟调度策略的Reduce调度优化算法

在大规模的Hadoop集群中,良好的任务调度策略对提高数据本地性、减小网络传输开销、减少作业执行时间以及提高集群的作业吞吐量都有着重要的影响。本文针对Hadoop架构中Reduce任务的数据本地性较低问题,提出了一种基于延迟调度策略的Reduce任务调度优化算法,通过提高Reduce任务的数据本地性来减少作业执行时间以及提高作业吞吐量,该算法在Hadoop架构的Early Shuffle阶段,使用多级延迟调度策略来提高Reduce任务的数据本地性。最后重写原生公平调度器代码实现了该调度算法,并与原生公平调度器进行了对比实验分析,实验结果表明该算法明显减少了作业执行时间,提高了集群的作业吞吐量。     

基于蚁群优化算法的服务网格的作业调度

提出了利用蚁群算法来优化服务网格的作业调度系统的方法和一个两层的作业调度模型，该模型可以在网格的动态和异构环境下实现对作业执行时间的预测，然后根据作业的预测执行时间并利用蚁群优化算法使适应函数取得最小值，从而得到最优化的作业调度。基于开发的校园网格实验床，通过实验显示该方法可以优化服务网格的性能，减少作业的平均执行时问，提高系统的吞吐率。     

Hadoop平台下基于加权轮转算法的改进任务调度算法

为提高Hadoop作业调度的效率,增加云平台的吞吐率,提出了一种基于Hadoop云计算平台的作业调度算法。该算法在加权轮转调度算法的基础上,针对MapReduce的运行特点,增加了改进map任务本地性调度的因素,使得作业调度仍然保持了相对的公平性,并通过提高轮转周期内的map任务数据本地性,减少了任务的执行时间。实验结果证明,该调度算法与加权轮转调度算法相比,较好地提高了任务本地执行的比例,缩短了云计算系统内作业的总执行时间。     

一种作业弹性与截止时间感知的作业调度算法

针对采用MapReduce模型的大数据分析作业的调度问题进行深入研究，并分析现有任务调度算法的缺陷，现有算法没有考虑资源分配对于作业截止时间的影响，也未考虑不同类型作业截止时间的敏感性问题。因作业的完成时间随着分配资源的不同而改变，故称之为弹性作业，截止时间敏感性是指不同类型作业对截止时间要求的严格程度不同。针对以上问题，提出一种截止时间感知的弹性作业调度算法（DA）。该算法将作业依据截止时间敏感程度进行分类，在基于作业整体执行时间预测的基础上，通过调控不同的资源分配策略来改变作业完成时间，同时结合用户对于截止时间的需求及作业预执行的收益来提前规划作业的资源分配及调度次序使得整体收益最大化。将算法在仿真拥有210个物理节点的集群中进行实验，实验表明该算法满足了截止时间的限制并使得作业整体收益值平均提高了2.37倍。     

基于推测的无响应任务自适应容错调度算法

已有的 基于静态的执行失败判定时间阈值 的无响应任务容错调度算法,不能适应大数据处理中心动态的集群负载。针对该问题,提出判定无响应任务执行失败时间阈值自适应调整方法。基于该模型,设计了自适应的无响应任务容错调度算法(AFTS)。AFTS算法通过分析作业规模、单个任务大小和剩余作业推测执行时间等参数,自适应地调整无响应任务判定执行失败的时间阈值,以减少无响应任务对整体作业执行效率的影响,降低作业响应时间。基于开发的原型系统,验证了自适应判定方法,测试了算法的性能。实验结果表明,AFTS算法在作业响应时间等方面优于已有的无响应任务容错调度算法。     

一个基于偏序的定时投入关联网络作业调度算法

基于偏序的定时投入关联网络作业调度算法在一个大型作业管理系统中得到了应用，它的基本思想是对定时投入的关联网络作业找到一个最佳执行序列，以便减少互相关联的网络作业在执行时的等待时间，该算法首先将同时请求投入的多个有关联关系的网络作业按照偏序关系进行排序，形成关联作业，然后推算出网络作业的阶位值，最后产生一个最优的投入序列，从而大大提高关联作业执行时间，实际系统应用表明，此算法对作业管理系统中定时投入关联网络作业的快速执行有很强的优越性。     

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

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

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

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

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

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

Hadoop下资源匹配最大集作业调度算法

针对目前层级队列作业调度算法中资源占比高的作业执行效率低的问题,提出一种资源匹配最大集算法。该算法分析作业特征,引入完成度、等待时间、优先级、重调度次数为紧迫值因子,优先考虑资源占比高或等待时间长的作业,以改善作业公平性;采用双队列结构在可用资源总量内优先选择高紧迫值作业,在不同资源占比作业集比较中选择作业数最大集,以实现调度平衡。在与最大最小公平(Max-min fairness)算法的实例对比中发现,该算法可降低作业集平均等待时间、提高资源利用率。实验对比结果表明,该算法可将不同资源占比的单一类型作业集执行时间缩短18.73%,其中资源占比高的作业执行时间缩短27.26%;在混合型作业集中对应的执行时间可分别缩短22.36%与30.28%。所提算法能有效减少资源占比高作业的等待,提高作业整体执行效率。     

Adaptive Execution of Jobs in Computational Grid Environment

In a computational grid, jobs must adapt to the dynamically changing heterogeneous environment with an objective of maintaining the quality of service. In order to enable adaptive execution of multiple jobs running concurrently in a computational grid, we propose an integrated performance-based resource management framework that is supported by a multi-agent system (MAS). The multi-agent system initially allocates the jobs onto different resource providers based on a resource selection algorithm. Later, during runtime, if performance of any job degrades or quality of service cannot be maintained for some reason (resource failure or overloading), the multi-agent system assists the job to adapt to the system. This paper focuses on a part of our framework in which adaptive execution facility is supported. Adaptive execution facility is availed by reallocation and local tuning of jobs. Mobile, as well as static agents are employed for this purpose. The paper provides a summary of the design and implementation and demonstrates the efficiency of the framework by conducting experiments on a local grid test bed.     

校园网格的资源评估算法研究

针对校园网格主要应用于科学计算的特点,面向应用提出并实现了一种评估资源是否适宜分配作业的算法,指导校园网格应用合理分配作业,实现校园网格系统中作业运行时间短和资源负载平衡.重点阐述了网格资源的作业适宜分配度算法,包括网格资源的初始权重算法、信誉度算法和动态负载算法,完善了网格资源评估体系.最后通过仿真实验对资源评估算法完成了验证,证明所提出的算法是可行并有效的.     

一种支持服务网格的动态负载平衡系统

为了实现服务网格系统内负载的均衡分布，提高资源利用率和系统的吞吐率，设计并实现了一种基于服务网格环境的动态负载平衡系统。提出了层次式负载平衡调度模式，给出了本系统结构形式，设计并实现了一种综合考虑各局部代理作业数和各个局部代理性能以及当前的负载情况的动态双阈值作业分配算法。实验结果表明，此算法能有效地基于负载分派作业，达到了提高网格内分布资源的利用率和减少作业调度时间的目的。     

计算网格中动态负载平衡的分布调度模式

网格计算下对资源进行有效的管理和调度可以提高系统的利用率.在对现有若干调度方法的研究和分析基础上,针对计算网格中的负载平衡问题,提出了一种分布式网格作业调度模型,并给出相关算法.算法通过建立主从模式的负载信息收集机制,提供给节点全局负载信息,加速重负载节点的负载转移速度.通过有效的负载平衡模式,解决资源调度中负载平衡及其可靠性问题.     

多QoS约束网格作业调度问题的多目标演化算法

针对网格计算中的多QoS约束网格作业调度问题，以独立作业为研究对象，将其规约为多目标组合最优化问题．通过深入剖析多目标最优化理论及其演化算法，结合网格作业调度自然特征，提出了一种解决多QoS约束网格作业调度问题的多目标演化算法．该算法求解多个QoS维度效用函数指标的非劣解集，尝试解决多管理域间网格用户、资源管理者等网格实体的多目标协同问题．仿真结果表明，在时间维度、可靠性维度、安全性维度QoS效用值等用户级QoS指标，以及丢弃作业数等系统级指标方面该算法与QoS-Min-min和QoS-Sufferage等同类算法相比具有较好的综合性能．     

Adaptive Task Checkpointing and Replication: Toward Efficient Fault-Tolerant Grids

A grid is a distributed computational and storage environment often composed of heterogeneous autonomously managed subsystems. As a result, varying resource availability becomes commonplace, often resulting in loss and delay of executing jobs. To ensure good grid performance, fault tolerance should be taken into account. Commonly utilized techniques for providing fault tolerance in distributed systems are periodic job checkpointing and replication. While very robust, both techniques can delay job execution if inappropriate checkpointing intervals and replica numbers are chosen. This paper introduces several heuristics that dynamically adapt the above mentioned parameters based on information on grid status to provide high job throughput in the presence of failure while reducing the system overhead. Furthermore, a novel fault-tolerant algorithm combining checkpointing and replication is presented. The proposed methods are evaluated in a newly developed grid simulation environment dynamic scheduling in distributed environments (DSiDE), which allows for easy modeling of dynamic system and job behavior. Simulations are run employing workload and system parameters derived from logs that were collected from several large-scale parallel production systems. Experiments have shown that adaptive approaches can considerably improve system performance, while the preference for one of the solutions depends on particular system characteristics, such as load, job submission patterns, and failure frequency.     

面向运行时间预测和容错感知的网格资源分配

提出与描述了一种面向任务运行时间预测和容错感知（Fault-Aware）的网格资源分配策略,采用主动容错的方式,在资源出错之前尽量提前避免它出错或异常的情况发生。该策略把网格中任务的运行时间（runtime）预测和资源的在线时间（uptime）预测结合起来,相对于普通的调度策略具有比较高的资源利用率。在具体的CoBRA网格中间件中实现了该容错感知调度,描述了实现该容错感知调度策略模块的功能。测试过程中选择了睡眠任务技术,划分四种不同的场景进行实验,把该容错感知资源分配与普通的FCFS调度策略进行比较,结果证明在可变化的资源可用性的情况下系统可以加快应用的整体执行时间,具有很小的偏差。     

Observing the effect of interprocess communication in auto controlled ant colony optimization‐based scheduling on computational grid

Computational grids allow the sharing of geographically distributed computational resources in an efficient, reliable, and secure manner. Grid is still in its infancy, and there are many problems associated with the computational grid, namely job scheduling, resource management, information service, information security, routing, fault tolerance, and many more. Scheduling of jobs on grid nodes is an NP‐class problem warranting for heuristic and meta‐heuristic solution approach. In the proposed work, a meta‐heuristic technique, auto controlled ant colony optimization, has been applied to solve this problem. The work observes the effect of interprocess communication in process to optimize turnaround time of the job. The proposed model has been simulated in Matlab. For the different scenarios in computational grid, results have been analyzed. Result of the proposed model is compared with another meta‐heuristic technique genetic algorithm that has been applied for the same purpose. It is found that auto controlled ant colony optimization not only gives better solution in comparison to genetic algorithm, but also converges faster because initial solution itself is good because of constructive and decision‐based policy adapted by the former. Concurrency and Computation: Practice and Experience, 2012.© 2012 Wiley Periodicals, Inc.     

网格作业自适应迁移模型

作业迁移是实现网格作业服务质量保证和系统高效能的重要方法。该文在分析传统进程迁移技术的基础上,根据网格系统的特点,提出一种全局作业与局部进程相结合的网格作业自适应迁移模型,给出网格作业自适应迁移策略、迁移对象选定原则、迁移时机确定机制和自适应迁移实现算法。试验结果以及在某校园计算网格中的应用验证了该模型的有效性。