异构Hadoop集群下的负载自适应反馈调度策略

随着基于Hadoop平台的大数据技术的不断发展和实践的深入,Hadoop YARN资源调度策略在异构集群中的不适用性越发明显。一方面,节点资源无法动态分配,导致优势节点的计算资源浪费、系统性能没有充分发挥;另一方面,现有的静态资源分配策略未考虑作业在不同执行阶段的差异,易产生大量资源碎片。基于以上问题,提出了一种负载自适应调度策略。监控集群执行节点和提交作业的性能信息,利用实时监控数据建模、量化节点的综合计算能力,结合节点和作业的性能信息在调度器上启动基于相似度评估的动态资源调度方案。优化后的系统能够有效识别集群节点的执行能力差异,并根据作业任务的实时需求进行细粒度的动态资源调度,在完善YARN现有调度语义的同时,可作为子级资源调度方案架构在上层调度器下。在Hadoop 2.0上实现并测试该策略,实验结果表明,作业的自适应资源调度策略显著提高了资源利用率,集群并发度提高了2到3倍,时间性能提升了近10%。     

A biased random‐key genetic algorithm for scheduling heterogeneous multi‐round systems

A divisible load is an amount W of computational work that can be arbitrarily divided into independent chunks of load. In many divisible load applications, the load can be parallelized in a master–worker fashion, where the master distributes the load among a set P of worker processors to be processed in parallel. The master can only send load to one worker at a time, and the transmission can be done in a single round or in multiple rounds. The multi‐round divisible load scheduling problem consists in (a) selecting the subset of workers that will process the load, (b) defining the order in which load will be transmitted to each of them, (c) defining the number m of transmission rounds that will be used, and (d) deciding the amount of load that will be transmitted to each worker at each round , so as to minimize the makespan. We propose a heuristic approach that determines the transmission order, the set of the active processors and the number of rounds by a biased random‐key genetic algorithm. The amount of load transmitted to each worker is computed in polynomial time by closed‐form formulas. Computational results showed that the proposed genetic algorithm outperformed a closed‐form state‐of‐the‐art heuristic, obtaining makespans that are 11.68% smaller on average for a set of benchmark problems.     

异构集群系统的可分负载多轮调度算法

针对更实际的异构集群计算环境,充分考虑处理机具有不同的计算速度、通信能力和存储容量的特性,通过允许计算和通信操作重叠执行,采取多次并行分配计算任务的方法,设计一种可分负载多轮调度算法。实验结果表明,该算法不但能获得与均匀多轮调度(UMR)算法相当的渐近最优调度时间长度,并且能够处理更大规模的应用负载,实用性更强。     

基于节点分组的异构集群负载均衡算法*

首先根据排队论理论给出了一个理想的负载均衡模型。针对该模型的系统开销问题,提出了一种基于节点分组的异构集群负载均衡算法。实验结果表明,相比于轮转法和加权轮转法这两种普遍采用的负载均衡算法,该算法可以提供更加稳定的请求响应时间,并在负载波动较大时明显提高集群的吞吐率。     

异构机群系统上并行计算双序列的最长公共子序列*

针对处理机节点具有不同计算速度、不同通信能力的情况,考虑计算和通信启动开销,给定处理机分配顺序,基于可分负载理论,提出一种存储受限异构机群系统的序列串最优分配线性规划模型,给出相应的序列串最优分配方法。实验结果表明,基于最优序列串分配方法的双序列最长公共子序列并行算法优于平均分配序列串算法,获得了较好的加速,并具有良好的可扩展性。     

Consensus of heterogeneous first‐ and second‐order multi‐agent systems with directed communication topologies

In this paper, we consider the consensus problem for heterogeneous multi‐agent systems composed of some first‐order and some second‐order dynamic agents in directed communication graphs. Consensus protocols are proposed for the second‐ and first‐order dynamic agents, respectively. Under certain assumptions on the control parameters, for fixed communication topologies, necessary and sufficient conditions for consensus are given, and the consensus values of all agents are established. For switching topologies, sufficient conditions are given for all agents to reach consensus. Finally, simulation examples are presented to demonstrate the effectiveness of the proposed methods. Copyright © 2013 John Wiley & Sons, Ltd.     

Adaptive robust consensus tracking for nonlinear second‐order multi‐agent systems with heterogeneous uncertainties

This paper addresses the consensus tracking problem for a class of heterogeneous nonlinear second‐order multi‐agent systems with parametric uncertainties, unmodeled dynamics, and bounded external disturbances. By linearly parameterizing the control input of the leader, two distributed adaptive robust consensus tracking control protocols with dynamic and fixed coupling gains are constructed based on the relative information from neighboring agents. The global tracking errors are shown to be guaranteed to exponentially converge to a ball with a constant radius at a prescribed rate of convergence under external disturbances. Finally, a numerical example is provided to verify the theoretical results. Copyright © 2017 John Wiley & Sons, Ltd.     

Sensor allocation with guaranteed exponential stability for linear multi‐rate sampled‐data systems

This paper addresses sensor allocation with guaranteed exponential stability for linear multi‐rate sampled‐data systems. It is assumed that a continuous‐time linear plant is exponentially stabilized by a continuous‐time linear controller. Given sensors with incommensurate sampling rates, the objective is to allocate each state to a sensor such that the resulting multi‐rate sampled‐data system remains exponentially stable. The main contributions of this paper are twofold. First, we propose sufficient Krasovskii‐based conditions to partition the state vector among sensors such that exponential stability of the closed‐loop system is guaranteed. Second, the problem of finding a partition that guarantees exponential stability is cast as a mixed integer program subject to linear matrix inequalities. The theoretical results are successfully applied to two robotic problems: path‐following in unicycles and hovering in quadrotors. Copyright © 2015 John Wiley & Sons, Ltd.     

TLA: Temporal look-ahead processor allocation method for heterogeneous multi-cluster systems

In a heterogeneous multi-cluster (HMC) system, processor allocation is responsible for choosing available processors among clusters for job execution. Traditionally, processor allocation in HMC considers only resource fragmentation or processor heterogeneity, which leads to heuristics such as Best-Fit (BF) and Fastest-First (FF). However, those heuristics only favor certain types of workloads and cannot be changed adaptively. In this paper, a temporal look-ahead (TLA) method is proposed, which uses an allocation simulation process to guide the decision of processor allocation. Thus, the allocation decision is made dynamically according to the current workload and system configurations. We evaluate the performance of TLA by simulations, with different workloads and system configurations, in terms of average turnaround time. Simulation results indicate that, with precise runtime information, TLA outperforms traditional processor allocation methods and has up to an 87% performance improvement.     

Resource brokering using a multi‐site resource allocation strategy for computational grids

Grid computing employs heterogeneous resources which may be installed on different platforms, hardware/software, computer architectures, and perhaps using different computer languages to solve large‐scale computational problems. As many more Grids are being developed worldwide, the number of multi‐institutional collaborations is growing rapidly. However, to realize Grid computing's full potential, it is expected that Grid participants must be able to share one another's resources. This paper presents a resource broker that employs the multi‐site resource allocation (MSRA) strategy and the dynamic domain‐based network information model that we propose to allocate Grid resources to submitted jobs, where the Grid resources may be dispersed at different sites, and owned and governed by different organizations or institutes. The jobs and resources may also belong to different clusters/sites. Resource statuses collected by the Ganglia, and network bandwidths gathered by the Network Weather Service, are both considered in the proposed scheduling approach. A dynamic domain‐based model for network information measurement is also proposed to choose the most appropriate resources that meet the jobs' execution requirements. Experimental results show that MSRA outperformed the other tested strategies. Copyright © 2010 John Wiley & Sons, Ltd.     

Distributed loop‐scheduling schemes for heterogeneous computer systems

Distributed computing systems are a viable and less expensive alternative to parallel computers. However, a serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. Some distributed scheduling schemes suitable for parallel loops with independent iterations on heterogeneous computer clusters have been designed in the past. In this work we study self‐scheduling schemes for parallel loops with independent iterations which have been applied to multiprocessor systems in the past. We extend one important scheme of this type to a distributed version suitable for heterogeneous distributed systems. We implement our new scheme on a network of computers and make performance comparisons with other existing schemes. Copyright © 2005 John Wiley & Sons, Ltd.     

Consensus of a class of second‐order nonlinear heterogeneous multi‐agent systems with uncertainty and communication delay

In this paper, a consensus problem is studied for a group of second‐order nonlinear heterogeneous agents with non‐uniform time delay in communication links and uncertainty in agent dynamics. We design a class of novel decentralized control protocols for the consensus problem whose solvability is converted into stability analysis of an associated closed‐loop system with uncertainty and time delay. Using an explicitly constructed Lyapunov functional, the stability conditions or the solvability conditions of the consensus problem are given in terms of a set of linear matrix inequalities apart from a small number of scalar parameters that appear nonlinearly. Furthermore, the linear matrix inequalities are theoretically verified to be solvable when the communication delay is sufficiently small. The effectiveness of the proposed control protocol is illustrated by numerical examples. Copyright © 2016 John Wiley & Sons, Ltd.     

Jcluster: an efficient Java parallel environment on a large‐scale heterogeneous cluster

In this paper, we present Jcluster, an efficient Java parallel environment that provides some critical services, in particular automatic load balancing and high‐performance communication, for developing parallel applications in Java on a large‐scale heterogeneous cluster. In the Jcluster environment, we implement a task scheduler based on a transitive random stealing (TRS) algorithm. Performance evaluations show that the scheduler based on TRS can make any idle node obtain a task from another node with much fewer stealing times than random stealing (RS), which is a well‐known dynamic load‐balancing algorithm, on a large‐scale cluster. In the performance aspects of communication, with the method of asynchronously multithreaded transmission, we implement a high‐performance PVM‐like and MPI‐like message‐passing interface in pure Java. The evaluation of the communication performance is conducted among the Jcluster environment, LAM‐MPI and mpiJava on LAM‐MPI based on the Java Grande Forum's pingpong benchmark. Copyright © 2005 John Wiley & Sons, Ltd.     

Event‐triggered output synchronization of heterogeneous multi‐agent systems

This paper proposes a control architecture that employs event‐triggered control techniques to achieve output synchronization of a group of heterogeneous linear time‐invariant agents. We associate with each agent an event‐triggered output regulation controller and an event‐triggered reference generator. The event‐triggered output regulation controller is designed such that the regulated output of the agent approximately tracks a reference signal provided by the reference generator in the presence of unknown disturbances. The event‐triggered reference generator is responsible for synchronizing its internal state across all agents by exchanging information through a communication network linking the agents. We first address the output regulation problem for a single agent where we analyze two event‐triggered scenarios. In the first one, the output and input event detectors operate synchronously, meaning that resets are made at the same time instants, while in the second one, they operate asynchronously and independently of each other. It is shown that the tracking error is globally bounded for all bounded reference trajectories and all bounded disturbances. We then merge the results on event‐triggered output regulation with previous results on event‐triggered communication protocols for synchronization of the reference generators to demonstrate that the regulated output of each agent converges to and remains in a neighborhood of the desired reference trajectory and that the closed‐loop system does not exhibit Zeno solutions. Several examples are provided to illustrate the advantages and issues of every component of the proposed control architecture. Copyright © 2016 John Wiley & Sons, Ltd.     

Scheduling multi‐component applications with mobile agents in heterogeneous distributed systems

In grid computing environment, several classes of multi‐component applications exist. These types of applications may often require additional resources of different types that go beyond what is available in any of the sites making up the grid resource composition. The heterogeneity nature of both the user application and the computing environment makes this a challenging problem. However, the current off‐the‐shelf scheduling software can hardly cope with these diversities in distributed computing application frameworks. Therefore, there is the need for an adequate scheduling system that would grant simultaneous or coordinated access to application of multi‐component nature that requires resources of possibly multiple types, in multiple locations, managed by different resource providers. The main focus of this paper is to develop a mobile agent scheduling model that addresses the aforementioned challenge. A scheduling policy that pertains to job scheduling and resource allocation is proposed. The scheduling policy treats different multi‐component applications requiring diverse heterogeneous resources fairly. The policy is used by mobile agents to schedule user applications and to also find available and suitable distributed resource that are capable of executing user application at a very minimal time. Copyright © 2015 John Wiley & Sons, Ltd.     

Energy‐efficient scheduling algorithms for batch‐of‐tasks (BoT) applications on heterogeneous computing systems

One of the major design constraints of a heterogeneous computing system is optimal scheduling, that is, mapping of tasks on the processing nodes in order to optimize the QoS parameters. Because of the huge energy consumption by computing resources, negative environmental effects and reduced system reliability, energy has unavoidably been added as a new parameter to the list of QoS parameters. Energy optimization in scheduling strategies along with makespan makes it an even more challenging combinatorial optimization problem. This work proposes two energy‐aware scheduling algorithms G1 and G2 to schedule a batch‐of‐tasks, made of a collection of independent tasks, on heterogeneous processors in order to minimize the makespan and the energy consumption. The proposed algorithms schedule tasks based on weighted aggregation cost function to the appropriate processors followed by task migration phase designed to further minimize the makespan and the energy consumption. The study evaluates the performance of the proposed algorithms with some of the peers, that is, MinMin, MINSuff on account of makespan, energy consumption, flowtime, and utilization. An experimental study reveals that the proposed algorithm (G2) consistently performs better under various test conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

带负载均衡的混合算法求解分布式异构作业车间调度问题

针对以最小化最大完工时间为目标的分布式异构作业车间调度问题(DHJSP), 本文提出了一种新的混合遗传禁忌搜索算法. 首先, 综合考虑工厂的工件总负载与最大机器负载, 提出了一种新的工厂负载表达方式. 其次, 针对DHJSP总工序数不定的特性, 提出以最小化最大工厂负载为目标快速确定初始工件分配方案, 并验证了方法的高效性. 然后, 新设计了两种考虑负载均衡的单工件转移邻域结构, 根据工序调度的结果对工件分配方案进行局部搜索. 最后, 因DHJSP缺少标准算例和相关算法, 在分布式同构作业车间调度问题(DJSP)上与现有算法进行对比, 所提算法在TA算例的480个问题上更新了420个问题的最优解, 其余60个问题取得了同等最优解. 在随机生成的3个不同规模的异构算例中, 所提算法也均取得了较好解, 验证了所提方法的优越性.     

TRINI: an adaptive load balancing strategy based on garbage collection for clustered Java systems

Nowadays, clustered environments are commonly used in high‐performance computing and enterprise‐level applications to achieve faster response time and higher throughput than single machine environments. Nevertheless, how to effectively manage the workloads in these clusters has become a new challenge. As a load balancer is typically used to distribute the workload among the cluster's nodes, multiple research efforts have concentrated on enhancing the capabilities of load balancers. Our previous work presented a novel adaptive load balancing strategy (TRINI) that improves the performance of a clustered Java system by avoiding the performance impacts of major garbage collection, which is an important cause of performance degradation in Java. The aim of this paper is to strengthen the validation of TRINI by extending its experimental evaluation in terms of generality, scalability and reliability. Our results have shown that TRINI can achieve significant performance improvements, as well as a consistent behaviour, when it is applied to a set of commonly used load balancing algorithms, demonstrating its generality. TRINI also proved to be scalable across different cluster sizes, as its performance improvements did not noticeably degrade when increasing the cluster size. Finally, TRINI exhibited reliable behaviour over extended time periods, introducing only a small overhead to the cluster in such conditions. These results offer practitioners a valuable reference regarding the benefits that a load balancing strategy, based on garbage collection, can bring to a clustered Java system. Copyright © 2016 John Wiley & Sons, Ltd.     

Fault‐tolerant adaptive control allocation schemes for overactuated systems

This paper presents a fault‐tolerant adaptive control allocation scheme for overactuated systems subject to loss of effectiveness actuator faults. The main idea is to use an ‘ad hoc’ online parameters estimator, coupled with a control allocation algorithm, in order to perform online control reconfiguration whenever necessary. Time‐windowed and recursive versions of the algorithm are proposed for nonlinear discrete‐time systems and their properties analyzed. Two final examples have been considered to show the effectiveness of the proposed scheme. The first considers a simple linear system with redundant actuators and it is mainly used to exemplify the main properties and potentialities of the scheme. In the second, a realistic marine vessel scenario under propeller and thruster faults is treated in full details. Copyright © 2010 John Wiley & Sons, Ltd.     

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

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