基于微操作的Hadoop参数自动调优方法

Hadoop作为大规模分布式数据处理框架已经在工业界得到广泛的应用，针对手动和经验调优方法中参数空间庞大和运行流程复杂的问题，提出了一种Hadoop参数自动优化的方法和分析框架。首先，对作业运行流程进行解耦，从可变参数直接影响的更细粒度的角度定义微操作，从而分析参数和单次微操作执行时间的关系；然后，利用微操作对作业运行流程进行重构，建立参数和作业运行时间关系的模型；最后，在此模型上应用各类搜索优化算法高效快速得出优化后的系统参数。在terasort和wordcount两个作业类型上进行了实验，实验结果表明，相对于默认参数情况，该方法使作业执行时间分别缩短了至少41%和30%。该方法能够有效提高Hadoop作业执行效率，缩短作业执行时间。     

Static Forecasting of the Execution Times of Complexes of Interrelated Jobs in the Multiprocessor Computer Systems

Consideration was given to a procedure of approximate forecasting of the execution times of the complexes of interrelated jobs in the multiprocessor computer systems with the Erlangian execution time of each job. This distribution is used as a tool for modeling the normal distribution. The order and parameter of the approximating Erlangian distribution are chosen from the parameters of the normal distribution.__________Translated from Avtomatika i Telemekhanika, No. 6, 2005, pp. 89–103.Original Russian Text Copyright © 2005 by Ivanov, Ignatushchenko, Mikhailov.     

Computation scheduling in multiprocessor real-time automatic control systems with constrained processor memory

For the automatic control systems with tight real time, construction of feasible schedules under the given job execution deadlines was considered, and in addition the constraints on processor memory were taken into consideration. Two methods were developed to solve this problem. The first method is based on reducing the original problem to the search of a multi-commodity flow in a special network. The second method offers a fast algorithm to determine a feasible schedule for the uniprocessor case.Translated from Avtomatika i Telemekhanika, No. 2, 2005, pp. 138–147.Original Russian Text Copyright © 2005 by Guz, Furugyan.     

分布式系统中计算作业流的均衡调度算法

分布式系统中计算作业流被映射到节点后无法进行动态调整,使关键作业无法及时执行而造成作业间等待。针对该问题,提出一种计算作业流均衡调度算法。算法对映射到分布式节点的作业根据其依赖关系得出阶位值,依据该值在分布式节点上进行动态优先值调整,使关键作业尽早完成,减少作业之间的等待,缩短计算作业流执行时间。实际系统应用表明,该算法对作业管理系统中投入的计算作业流的快速执行有较强优越性。     

A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time

This paper is about scheduling parallel jobs, i.e. which can be executed on more than one machine at the same time. Malleable jobs is a special class of parallel jobs. The number of machines a malleable job is executed on may change during its execution.In this work, we consider the NP-hard problem of scheduling malleable jobs to minimize the total weighted completion time (or mean weighted flow time). For this problem, we introduce the class of “ascending” schedules in which, for each job, the number of machines assigned to it cannot decrease over time while this job is being processed.We prove that, under a natural assumption on the processing time functions of jobs, the set of ascending schedules is dominant for the problem. This result can be used to reduce the search space while looking for an optimal solution.     

网络集群计算系统中的并行任务调度

基于多处理机并行任务调度模型，探讨网络集群计算系统中的并行任务调度问题，首先证明了一般网络集群计算系统中调度算法的可近似性难度，然后提出了三种不同的启发式算法：最大长度优先调度算法、最大宽度优先调度算法和最大面积优先调度算法；然后根据大量的模拟实验对这些算法以及文献中已提出的调度算法进行了比较分析，结果表明该文的启发式算法比文献中的算法在性能上效果更好。     

Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints

Abstract. Modern computer systems distribute computation among several machines to speed up the execution of programs. Yet, setup and communication costs, as well as parallelism constraints, bound the number of machines that can share the execution of a given application, and the number of machines by which it can be processed simultaneously . We study the resulting scheduling problem, stated as follows. Given a set of n jobs and m uniform machines, assign the jobs to the machines subject to parallelism and machine allotment constraints, such that the overall completion time of the schedule (or makespan ) is minimized. Indeed, the multiprocessor scheduling problem (where each job can be processed by a single machine) is a special case of our problem; thus, our problem is strongly NP-hard. We present a (1+ α) -approximation algorithm for this problem, where α ∈ (0,1] depends on the minimal number of machine allotments and the minimal parallelism allowed for any job. Also, we show that when the maximal number of machines that can share the execution of a job is some fixed constant, our problem has a polynomial time approximation scheme ; for other special cases we give optimal polynomial time algorithms. Finally, through the relation of our problem to the classic preemptive scheduling problem on multiple machines, we shed some fresh light on what is known in scheduling folklore as the power of preemption.     

Singularity/scattering alternative for a discrete family of static critical solutions with various numbers of unstable eigenmodes

This paper reports on the study of some solutions for a system of coupled nonlinear wave equations of a hyperbolic type, effectively dependent on one spatial (radial) variable and one time variable. This system of equations, which is a coupled system of the Yang-Mills equations with a scalar field, i.e., dilaton, belongs to the so-called class of supercritical systems, for which there exist solutions that inevitably lead to the formation of singularities at a point or even a whole region during a finite period of time at smooth initial distributions with finite energy. This system of equations has regular stationary solutions with finite energy. All such stationary solutions are unstable and can be parametrized by the number N, which is the number of their unstable eigenmodes in linear approximation, and N = 1, 2, 3, …, ∞. The self-consistent problem of the decay of such stationary solutions with N = 1, 2, 3, 4 on the independent excitation of their unstable eigenmodes was solved numerically in nonlinear regime. The corresponding initial-boundary problem was investigated numerically by means of an adaptive computation scheme based on a conservative finite-differential scheme with energy conservation. It has been found that for each considered stationary solution only the perturbation of its basic unstable eigenmode leads to the formation of the singularity/scattering alternative, the governing parameter in the choice of the alternative being the sign of the major unstable eigenmode. It is shown that the independent perturbation of all higher unstable eigenmodes necessarily leads to the formation of a singularity. It is also found that the nonlinear waves formed with the decay of the basic N = 1 solution on the perturbation of its single unstable mode may expose some properties peculiar to solitons.     

基于增强条件公式的主动规则集可终止性判定

主动规则集的可终止性判定是一个研究热点问题,现有的基于触发图和活化图的方法没有考虑触发环所有所属规则能否在同一次执行中执行;现有的条件公式判定方法只能包含不可更新或有限次更新变量,当主动规则集只包含可有限次循环执行的触发环时,现有方法不能准确判定它是可终止的。为此,提出了触发环的执行序列的概念和建立包含可更新变量的增强条件公式的方法,新的判定方法将触发环和执行语义有机地结合在一起,较现有方法可以发现更多的可终止性情形,同时给出了新算法的可终止性和正确性证明。     

Computation and communication schedule optimization for data-sharing tasks on uniprocessor

Almost every computation task requires input data in order to find a solution. This is not a problem for a centralized system because data is usually available locally. However, in a parallel and distributed system, e.g., computation grids, the data may be in remote sites and must be transferred to the local site before the computation can proceed. As a result, the interleaved sequence of data transfer and job execution has a significant impact on the overall computational efficiency. In this paper, we analyze the computational complexity of the shared-data job scheduling problem on uniprocessor, with and without consideration of the storage capacity constraint on the local site.We show that if there is an upper bound on the server capacity, the problem is NP-complete, even when each job depends on at most two data items. For the case where there is no upper bound on the server capacity, we show that there exists an efficient algorithm that can provide an optimal job schedule when each job depends on at most two data items. We also propose an efficient heuristic algorithm that can determine good schedules for cases where there is no limit on the amount of data a job may access. The reported experiment results demonstrate that this heuristic algorithm performs very well, and derives near optimal solutions.     

On the Design and Implementation of a Shared Memory Dispatcher for Partially Clairvoyant Schedulers

With the onset of distributed computing in hard real-time applications, the problem of assigning to, scheduling in, and executing jobs on processors, has received a lot of attention. Usually, real-time systems are embedded in closed loop reactive environments with uncertain behaviors and such systems take varying times to respond to such stimuli. One of the fundamental features of such systems is the presence of complex timing constraints between pairs of jobs. A secondary feature is the non-constant nature of the execution times of jobs. Real-time operating systems such as MARUTI can measure the interval within which the execution time varies (Mosse et al. In: Second IEEE Workshop on Experimental Distributed System, pp. 29–34., IEEE, 1990; Levi et al. 1989, ACM Special Interest Group Operat Syst 23(3):90–106). Partially clairvoyant scheduling was introduced in (Saksena, Parametric Scheduling in Hard Real-Time Systems. PhD thesis, University of Maryland, College Park, June 1994) to schedule jobs with varying execution times and non-trivial timing constraints. The schedulability of the job set is determined offline and a set of dispatch functions are produced from the given set of constraints if the job set is schedulable. The dispatch functions bind the start time of a job J to an interval that depends on the start and execution times of jobs sequenced before J. The online dispatcher of the system reads these dispatch functions and computes the interval within which a job can start without violating the constraints imposed on the system. In certain situations, the dispatcher fails to dispatch a job as the time to compute the dispatch functions associated with a job is greater than the interval within which the job needs to be dispatched. This phenomenon is called Loss of Dispatchability (Subramani, Duality in the Parametric Polytope and its Applications to a Scheduling Problem. PhD thesis, University of Maryland, College Park, August 2000). In this paper, we propose and implement a partially clairvoyant dispatching algorithm on a shared memory cluster with Concurrent Read Exclusive Write (CREW) architecture and contrast it with the sequential approach. For a preset number of processors, our approach has O(1) dispatch complexity while using a total of O(n ²) space, while the sequential approach requires Ω(n) time. The detailed implementation profile obtained clearly demonstrates the superiority of the multiprocessor approach to dispatching. We also address the issue of scalability of the dispatcher for increasing number of processors and show that job sets of different sizes require different number of processors. Finally, we demonstrate the effect of execution time on the dispatchability of schedules.     

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

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

A framework for adaptive execution in grids

Grids offer a dramatic increase in the number of available processing and storing resources that can be delivered to applications. However, efficient job submission and management continue being far from accessible to ordinary scientists and engineers due to their dynamic and complex nature. This paper describes a new Globus based framework that allows an easier and more efficient execution of jobs in a ‘submit and forget’ fashion. The framework automatically performs the steps involved in job submission and also watches over its efficient execution. In order to obtain a reasonable degree of performance, job execution is adapted to dynamic resource conditions and application demands. Adaptation is achieved by supporting automatic application migration following performance degradation, ‘better’ resource discovery, requirement change, owner decision or remote resource failure. The framework is currently functional on any Grid testbed based on Globus because it does not require new system software to be installed in the resources. The paper also includes practical experiences of the behavior of our framework on the TRGP and UCM‐CAB testbeds. Copyright © 2004 John Wiley & Sons, Ltd.     

Optimization of schedules with precedence logical conditions

The problem of constructing a time-optimal schedule for jobs execution with precedence logical conditions is considered. Every job is associated with a list of its direct predecessors, execution time and the number of the completed direct predecessors necessary to start execution of the job. It is shown that the problem can be solved by the methods of the cyclical games theory [1, 2]. We propose a pseudopolynomial algorithm for construction of the optimal schedule; i.e. the presented algorithm is efficient for the problems with small data arrays. The paper extends the results from [3], where AND/OR schedules are considered. A job can be started, when all its direct predecessor have been executed or when at least one of its direct predecessors has been completed.     

OpenPBS接入GT4平台的一个实现方案

根据OpenPBS与Globus Toolkit4.0不可兼容这一问题,提出了一个新的方案来解决这个问题.在Globus Toolkit4.0与OpenPBS之间增加一个中介:Globus Toolkit2.4.通过这个中介,实现网格作业的资源管理,为用户提供了一个透明的网格资源的使用方法.先介绍了这个系统的设计思想、系统结构,然后详细说明了具体实现中用到的关键技术,包括Globus Toolkit2.4上作业的执行过程、Globus Toolkit2.4与Globus Toolkit4.0间的连接问题、节点的状态检测等.     

基于蚁群算法的移动边缘服务器收益优化策略

移动边缘计算(Mobile Edge Computing,MEC)是5G的关键技术。由于MEC服务器的计算资源有限,如何对其计算资源分配以提高收益至关重要。为此,提出一种边缘服务器收益优化策略。将MEC服务器收益最大化问题建模为以服务器端任务执行次序为优化变量的最优化问题。在用户对时延和金钱偏好程度不同及子任务具有顺序执行关联性的情况下,提出基于蚁群算法的任务最优执行次序求解算法。仿真结果表明,同等条件下采用该算法获得的收益比SearchAdjust算法提高了33.6%。     

Optimal control of processing times in single-stage discrete event dynamic systems with blocking

This note concerns an optimal control problem in single-stage discrete event dynamic systems with finite buffers and blocking. The system is modeled as a deterministic queue, slated to process a finite sequence of jobs. Each job is characterized by its arrival time, service time, and due date, and has associated with it a cost function that penalizes short service times, buffer times, and lateness of completion times with respect to the due date. The sequencing (order) of the jobs at the server is given, and the variable parameter consists of the jobs' service times. Even though the cost function associated with each job is assumed to be convex, the aggregated cost functional is not convex. Therefore, much of the analysis focuses on a decomposition of the problem into a finite sequence of reduced-order convex programming problems which can be solved one at a time. This approach has been investigated in the past, but the present note provides an analysis under the most general and realistic assumptions considered to date.     

阶段感知的跨域数据分析作业保障机制

为缓解边缘计算的不稳定性,设计了适用于跨域规模的任务复制与分配机制以保障作业各阶段的完成（Geo-distributed job Insurance Mechanism,GIM）。为满足并行任务执行特征和资源限制,先将问题形式化为Min-Max多项式整数规划问题,再放松整数约束并采用feasible-point算法快速地收敛到最优解,最后基于高危任务优先原则对最优解进行取整,得到满足原问题约束的高质量任务复制与分配方案。模拟实验表明,在不同的系统负载下,相比于当前的冗余执行策略,GIM至少能够减少22%的作业平均完成时间。     

Hybrid Genetic Algorithms for a Rostering Problem

Hybrid Genetic Algorithms are described for a large-size real-life rostering problem (railway workers' job scheduling and roster optimization). The new algorithm uses an order-based representation which encodes as a chromosome the list of job units to schedule. First, a greedy algorithm is considered, which uses a randomly generated job units list, and satisfies only the constraints pertaining to the workers' job contract. Then, a genetic algorithm optimizes the global roster, minimizing its length and achieving some desired homogenizations. Finally, a second genetic algorithm (GA) is used to find the best parameter values for the first genetic algorithm. Thus, this work investigates the use of a GA together with a greedy algorithm and of a second GA to optimize the parameter values of the first GA. The results of significant tests on real data are reported. They compare favourably with the known results on Rostering Problems, both in terms of execution time and solution accuracy. This work considers a practical Rostering Problem concerning the Railway workers' rosters optimization. The size of the input data is very challenging: about 1000 duties (i.e. job-units called ‘links’) based on a large-size city location; 125 days to consider for roster optimization (summer rostering); the goal is to optimize the structure of the working-turn for any worker, and to minimize the global cost of the rosters. It should be emphasised that this is a very large problem: we will use GAs to solve the problem within an execution time in the order of a few minutes on a common workstation.     

具有时变时滞的离散系统的H∞控制

主要研究了控制输入和外部输入中带有时变时滞的离散系统的有限时间H无穷控制问题. 首先通过定义一个取值为0或1的二元变量将具有时变时滞的单通道离散系统转化为多通道定时滞离散系统, 进一步利用该系统H无穷控制与相应倒向随机系统平滑估计之间的对偶关系解决该问题,通过与原系统维数相同的Riccati差分方程给出了该问题的解,并且给出了因果与严格因果H控制器存在的充分必要条件.