Abstract In the rapidly expanding field of parallel processing, job schedulers are the “operating systems” of modern big data architectures and supercomputing systems. Job schedulers allocate computing resources and control the execution of processes on those resources. Historically, job schedulers were the domain of supercomputers, and job schedulers were designed to run massive, long-running computations over days and weeks. More recently, big data workloads have created a need for a new class of computations consisting of many short computations taking seconds or minutes that process enormous quantities of data. For both supercomputers and big data systems, the efficiency of the job scheduler represents a fundamental limit on the efficiency of the system. Detailed measurement and modeling of the performance of schedulers are critical for maximizing the performance of a large-scale computing system. This paper presents a detailed feature analysis of 15 supercomputing and big data schedulers. For big data workloads, the scheduler latency is the most important performance characteristic of the scheduler. A theoretical model of the latency of these schedulers is developed and used to design experiments targeted at measuring scheduler latency. Detailed benchmarking of four of the most popular schedulers (Slurm, Son of Grid Engine, Mesos, and Hadoop YARN) is conducted. The theoretical model is compared with data and demonstrates that scheduler performance can be characterized by two key parameters: the marginal latency of the scheduler t s and a nonlinear exponent α s . For all four schedulers, the utilization of the computing system decreases to 90 for all four of the schedulers that were tested.
Next we must address related work within the scheduling function. There are a number of papers that focus on comparing the queue management and scheduling algorithms within schedulers, including discussion of support for first-come, first-served (FCFS) [ @cite_71 ], fairshare [ @cite_21 ], backfill [ @cite_23 , and gang scheduling [ @cite_37 , @cite_26 ]. These papers includes comparisons of how jobs are prioritized within queues and how jobs are matched to resources to most effectively execute them. These articles make comparisons among the various schedulers available within Apache Hadoop YARN [ @cite_61 ]; within PBS [ @cite_16 ], within the Maui scheduler [ @cite_17 , and among several of the HPC schedulers [ @cite_54 , @cite_44 , @cite_5 ].
@cite_61 @cite_37 @cite_26 @cite_54 @cite_21 @cite_44 @cite_23 @cite_71 @cite_5 @cite_16 @cite_17
2276177172 1513326124 2003346154 1991173480
To solve the limitation of Hadoop on scalability, resource sharing, and application support, the open-source community proposes the next generation of Hadoop's compute platform called Yet Another Resource Negotiator YARN by separating resource management functions from the programming model. This separation enables various application types to run on YARN in parallel. To achieve fair resource sharing and high resource utilization, YARN provides the capacity scheduler and the fair scheduler. However, the performance impacts of the two schedulers are not clear when mixed applications run on a YARN cluster. Therefore, in this paper, we study four scheduling-policy combinations SPCs for short derived from the two schedulers and then evaluate the four SPCs in extensive scenarios, which consider not only four application types, but also three different queue structures for organizing applications. The experimental results enable YARN managers to comprehend the influences of different SPCs and different queue structures on mixed applications. The results also help them to select a proper SPC and an appropriate queue structure to achieve better application execution performance. Copyright © 2016 John Wiley & Sons, Ltd. The Maui scheduler has received wide acceptance in the HPC community as a highly configurable and effective batch scheduler. It is currently in use on hundreds of SP, O2K, and Linux cluster systems throughout the world including a high percentage of the largest and most cutting edge research sites. While the algorithms used within Maui have proven themselves effective, nothing has been published to date documenting these algorithms nor the configurable aspects they support. This paper focuses on three areas of Maui scheduling, specifically, backfill, job prioritization, and fairshare. It briefly discusses the goals of each component, the issues and corresponding design decisions, and the algorithms enabling the Maui policies. It also covers the configurable aspects of each algorithm and the impact of various parameter selections. It is well known that head-of-line blocking limits the throughput of an input-queued switch with first-in-first-out (FIFO) queues. Under certain conditions, the throughput can be shown to be limited to approximately 58.6 . It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used, then it is possible to achieve 100 throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm. We introduce two maximum weight matching algorithms: longest queue first (LQF) and oldest cell first (OCF). Both algorithms achieve 100 throughput for all independent arrival processes. LQF favors queues with larger occupancy, ensuring that larger queues will eventually be served. However, we find that LQF can lead to the permanent starvation of short queues. OCF overcomes this limitation by favoring cells with large waiting times. We study the following online preemptive scheduling problem: given a set of jobs with release times, deadlines, processing times and weights, schedule them so as to maximize the total value obtained. Unlike traditional scheduling problems, partially completed jobs can get partial values proportional to their amounts processed. Recently gave improved lower and upper bounds (1.236, 1.8) on the competitive ratio for this problem, the upper bound being achieved by using timesharing to simulate two equal-speed processors. In this paper we (1) give a new algorithm MIXED-k with competitive ratio 1 (1 − (k (k + 1)) k ) which approaches e (e−1) ≈ 1.582 when k →∞ , by using timesharing to simulate k equal-speed processors; (2) give an equivalent but much more practical algorithm MIX, which is e (e − 1)-competitive (independent of k), by timesharing the processor with different speeds (depending on the job weights), and use its interesting properties to devise an efficient implementation; (3) improve the lower bound to 1.25 by showing an identical lower bound for randomized algorithms; and (4) prove a lower bound of 1.618 on the competitive ratio when timesharing is not allowed, thus answering an open problem raised by Chang and Yap, showing that timesharing provably helps in giving better algorithms for this problem.