一种采用消息模型的多集群作业管理方案设计

文中针对多集群环境资源异构且地域分散、网络环境不可靠以及面向用户需求的特点,提出了一种采用消息模型的多集群作业管理方案。该方案采用全局一局部的层次调度方法,基于发布一订阅的消息模型,根据当前网络环境、用户作业的资源需求、各集群自身负载情况进行综合统一调度管理。实践证明,采用该方案设计实现的多集群作业管理系统实现了多集群环境下的资源监控、资源管理、作业调度、作业控制、数据管理等功能,有效解决了在资源异构及网络环境不可靠条件下的系统稳定性问题,显著提高了多集群系统作业吞吐能力。     

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

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

一种基于流作业的网格作业调度研究

在基于网格环境的一些网格应用中,用户需要提交一种作业类型,该作业可以被分解为逻辑上独立的元作业,这些元作业不存在依赖和通讯关系,并且它们的执行需要大量的数据移动。针对这种作业类型,本文提出了一种基于流作业的网格调度模型。在该模型中,这些独立的元作业像"流"一样自主地流向各个计算节点去执行,各计算节点接收的流量取决于其计算能力,并避免"断流"问题。同时,该模型还分离了作业流和数据流,实现了作业逻辑控制和数据控制的分离,提高了调度的灵活性。本文将该调度模型应用于药物虚拟筛选应用中,该模型能够充分利用计算节点的计算能力。     

计算密集型与数据密集型混合网格作业调度算法

针对计算密集型作业与数据密集型作业混合情况,在一个作业有时间限制的动态环境中,对传统的网格作业调度方法进行扩展,提出了三种网格作业调度启发式算法:Emin min、Ebest、Esufferage。并在一个由多个Cluster组成的、通过高速网络连接的网格模型上,对三种算法进行验证。与Min min算法的比较结果显示：三种算法均优于Min min算法。与ASJS算法比较结果显示：Emin min减少了等待时间与作业的makespan; Esufferage算法以减少作业完成量为代价,减少了作业的等待时间及makespan; Ebest在完成作业数量上与ASJS基本保持一致,但却增加了作业的等待时间与makespan。总体上,Emin min具有比较大的优势。     

Scheduling parallel jobs to minimize the makespan

We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen. List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.     

IMPROVED RESOURCE UTILIZATION WITH BUFFERED COSCHEDULING

We present buffered coscheduling, a new methodology to multitask parallel jobs in a message-passing environment and to develop parallel programs that can pave the way to the efficient implementation of a distributed operating system. Buffered coscheduling is based on three innovative techniques: communication buffering, strobing, and non-blocking communication. By leveraging these techniques, we can perform effective optimizations based on the global status of the parallel machine rather than on the limited knowledge available locally to each processor

The advantages of buffered coscheduling include higher resource utilization, reduced communication overhead, efficient implementation of flow-control strategies and fault-tolerant protocols, accurate performance modeling, and a simplified yet ;.till expressive parallel programming model which offloads many resource-management tasks to the operating system. Preliminary experimental results show that buffered coscheduling is very effective in increasing the overall performance in the presence of load imbalance and communication-intensive workloads and is relatively insensitive to the local process scheduling strategy.     

Context‐aware scheduling in MapReduce: a compact review

It is a fact that the attention of research community in computer science, business executives, and decision makers is drastically drawn by big data. As the volume of data becomes bigger, it needs performance‐oriented data‐intensive processing frameworks such as MapReduce, which can scale computation on large commodity clusters. Hadoop MapReduce processes data in Hadoop Distributed File System as jobs scheduled according to YARN fair scheduler and capacity scheduler. However, with advancement and dynamic changes in hardware and operating environments, the performance of clusters is greatly affected. Various efforts in literature have been made to address the issues of heterogeneity (i.e., clusters consisting of virtual machines and machines with different hardware), network communication, data locality, better resource utilization, and run‐time scheduling. In this paper, we present a survey to discuss various research efforts made so far to improve Hadoop MapReduce scheduling. We classify scheduling algorithms and techniques proposed in the literature so far based on their addressing areas and present a taxonomy. Furthermore, we also discuss various aspects of open issues and challenges in the scheduling of MapReduce to improve its performance. Copyright © 2015 John Wiley & Sons, Ltd.     

Hadoop MapReduce短作业执行性能优化

Hadoop MapReduce并行计算框架被广泛应用于大规模数据并行处理.近年来,由于其能较好地处理大规模数据,Hadoop MapReduce也被越来越多地使用在查询应用中.为了能够处理大规模数据集,Hadoop的基本设计更多地强调了数据的高吞吐率.然而在处理对短作业响应性能有较高要求的查询应用时,Hadoop MapReduce并行计算框架存在明显不足.为了提升Hadoop对于短作业的执行效率,对原有的Hadoop MapReduce作出以下3点优化：1)通过优化原有的setup和cleanup任务的执行方式,成功地缩短了作业初始化环境准备和作业结束环境清理的时间;2)将首次任务分配从“拉”模式转变为“推”模式;3)将作业执行过程中JobTracker和TaskTrackers之间的控制消息通信从现有的周期性心跳机制中分离出来,采用即时传递机制.最后,采用一种典型的基于MapReduce并行化的查询应用BLAST,对优化工作进行了评估.各种不同类型BLAST作业的测试实验表明,与现有的标准Hadoop相比,优化后的Hadoop平均执行性能提升约23%.     

网络并行计算系统中基于多处理机任务的资源调度模型

简要描述了网络并行计算系统中任务调度问题和经典的多处理机任务调度研究现状,并将两者结合到一起建立网络并行计算系统中的新型调度模型,较详细地论述了多处理机任务的定义,然后还讨论了该模型求解的近似调度策略及其近似优化问题,给出了其特例Pm｜fix｜Cmax问题的最优调度的时间跨度下界。     

面向高性能计算环境的作业优化调度模型的设计与实现

高性能计算环境聚合了多个分布在不同地域、不同组织机构的高性能计算资源,面向用户提供统一的访问入口和使用方式,由系统中间件根据用户作业请求匹配合适的高性能计算资源。随着环境应用编程接口的开放以及作业请求数量的大幅增加,面对高并发作业提交请求时,目前采用的即时调度模型会由于网络等原因导致一定数量的请求处理失败,同时缺乏灵活性。针对此问题,优化了环境作业调度模型,引入作业环境队列,细化了作业系统层状态,增加了作业调度策略可配置性,并基于环境中间件SCE实现了系统原型。经测试,在单核心服务每分钟处理近200个作业提交请求的工作负载下,无因系统和网络原因引起的作业提交出错现象;在共计1 000个作业中,近500个作业提交命令请求在0.3s以内完成,800余个作业提交命令请求在0.5s以内完成。     

基于LSTM的集群用户作业执行时间预测模型

为提升服务质量,数据中心需要确保在规定的截止时间前完成用户作业,因此必须根据实时的系统资源对作业进行有效的调度。提出了一种作业调度算法,根据预测的作业执行时间进行批作业调度,以最小化批作业的完成时间。作业执行时间预测模型基于长短期记忆LSTM网络,根据用户作业类型、作业量、作业需要的CPU核数和内存数量,以及作业需要的资源在系统总资源中的占比,对用户作业的执行时间进行预测。预测结果用于判断集群是否有能力按时完成用户作业,同时为合理安排各作业的执行顺序提供依据。通过实验确定了影响LSTM时间预测模型性能的各超参数取值,如迭代次数、学习率和网络层数等。实验表明,与SVR模型、ARIMA模型和BP模型相比,基于LSTM的作业执行时间预测模型的决定系数R²分别有2.97%,2.34%和5.66%的提升效果,且预测的平均误差仅为0.78%。     

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

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

On construction of a well-balanced allocation strategy for heterogeneous multi-cluster computing environments

With the rapid increment of the heterogeneity of hardware devices, cluster computing has to encounter the problem of handling heterogeneous resources for exploiting the utilization of system resources. This paper introduces a new job allocation strategy based on multi-clusters in diskless environments. By adopting Ganglia as the resource monitor and Condor as the queue system, a heterogeneous multi-cluster system is also constructed with and without storage devices for evaluating the system performance. The proposed algorithm is called the Well-Balanced Allocation Strategy (WBAS) in which the scheduler dispatches MPI-based jobs to appropriate resources across multi-clusters. The strategy focuses on dispatching jobs to nodes with similar performance, thus equalizing execution times among all the required nodes. The WBAS is implemented on the constructed heterogeneous multi-cluster system to evaluate the performance of the scheduling strategy. The experimental results show that the proposed strategy performs well and could efficiently improve the system performance.     

Integrating Computing Resources on Multiple Grid-Enabled Job Scheduling Systems Through a Grid RPC System

We present a framework for a parallel programming model by remote procedure calls, which bridge large-scale computing resource pools managed by multiple Grid-enabled job scheduling systems. With this system, the user can exploit not only remote servers and clusters, but also the computing resources provided by Grid-enabled job scheduling systems located on different sites. This framework requires a Grid remote procedure call (RPC) system to decouple the computation in a remote node from the Grid RPC mechanism and uses document-based communication rather than connection-based communication. We implemented the proposed framework as an extension of the OmniRPC system, which is a Grid RPC system for parallel programming. We designed a general interface to easily adapt the OmniRPC system to various Grid-enabled job scheduling systems, including XtremWeb, CyberGRIP, Condor and Grid Engine. We show the preliminary performance of these implementations using a phylogenetic application. We found that the proposed system can achieve approximately the same performance as OmniRPC and can handle interruptions in worker programs on remote nodes. Yoshihiro Nakajima is a Research Fellow of the Japan Society for the Promotion of Science     

一种基于DAG的网络流量调度器

在如今的数据中心中,各种分布式任务往往会对各种不同的资源进行竞争,特别是网络资源.如果没有有效的网络调度,那么这种竞争就会降低整个数据中心的运行效率.以往的网络资源调度研究由于忽视了任务里计算与网络需求之间的具体关系,对于任务性能的提升十分有限.因此,旨在探索如何通过网络调度来缩短数据中任务的完成时间(job completion time, JCT),从而提升数据中心的整体效率.通过对基于有向无环图(directed acyclic graph, DAG)的分布式任务的深度分析,发现可以在降低它们的网络占用的同时,却不影响它们的JCT.根据这个发现,提出了一个利用计算图来加速任务执行的网络调度器JIT.为了实现JIT,首先将调度问题建模成为一个整数线性规划问题(integer linear programming, ILP),然后证明了这个ILP可以通过一个等价的线性规划模型(linear programming, LP)来快速求解.此外,通过一些合理的简化,将求解时间降低到了1s.与其他调度器的比较实验结果说明了JIT可以取得1.55倍的整体加速效果,从而有效提升数据中心的工作效率.     

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

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

Algorithms for scheduling incompatible job families on single batching machine with limited capacity

Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively.     

Job design,employment practices and well-being: a systematic review of intervention studies

Abstract

There is inconsistent evidence that deliberate attempts to improve job design realise improvements in well-being. We investigated the role of other employment practices, either as instruments for job redesign or as instruments that augment job redesign. Our primary outcome was well-being. Where studies also assessed performance, we considered performance as an outcome. We reviewed 33 intervention studies. We found that well-being and performance may be improved by: training workers to improve their own jobs; training coupled with job redesign; and system wide approaches that simultaneously enhance job design and a range of other employment practices. We found insufficient evidence to make any firm conclusions concerning the effects of training managers in job redesign and that participatory approaches to improving job design have mixed effects. Successful implementation of interventions was associated with worker involvement and engagement with interventions, managerial commitment to interventions and integration of interventions with other organisational systems.

Practitioner Summary: Improvements in well-being and performance may be associated with system-wide approaches that simultaneously enhance job design, introduce a range of other employment practices and focus on worker welfare. Training may have a role in initiating job redesign or augmenting the effects of job design on well-being.     

Design and implementation of an adaptive job allocation strategy for heterogeneous multi‐cluster computing systems

Cluster computing is an attractive approach to provide high‐performance computing for solving large‐scale applications. Owing to the advances in processor and networking technology, expanding clusters have resulted in the system heterogeneity; thus, it is crucial to dispatch jobs to heterogeneous computing resources for better resource utilization. In this paper, we propose a new job allocation system for heterogeneous multi‐cluster environments named the Adaptive Job Allocation Strategy (AJAS), in which a self‐scheduling scheme is applied in the scheduler to dispatch jobs to the most appropriate computing resources. Our strategy focuses on increasing resource utility by dispatching jobs to computing nodes with similar performance capacities. By doing so, execution times among all nodes can be equalized. The experimental results show that AJAS can improve the system performance. Copyright © 2011 John Wiley & Sons, Ltd.     

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

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