Two-level utilization-based processor allocation for scheduling moldable jobs

  • PDF / 2,160,618 Bytes
  • 28 Pages / 439.37 x 666.142 pts Page_size
  • 45 Downloads / 176 Views

DOWNLOAD

REPORT


Two‑level utilization‑based processor allocation for scheduling moldable jobs Ying‑Jhih Wu1 · Shuo‑Ting Yu1 · Kuan‑Chou Lai1 · Amit Chhabra2 · Hsi‑Ya Chang3 · Kuo‑Chan Huang1

© Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract Most modern parallel programs are written with the moldable property. However, most existing parallel computing systems treat such parallel programs as rigid jobs for scheduling, resulting in two drawbacks. The first is inflexibility and inefficiency in processor allocation, leading to resource fragmentation and thus poor performance. The second is about usage inconvenience, requiring users to figure out the best number of processors for executing a job. As HPC as a service emerges, moldable job scheduling has become an important research issue for achieving both high performance and user convenience. This paper presents our research work on developing new processor allocation approaches for moldable job scheduling based on two-level resource utilization calculation, preemptive job execution, and dual-criteria iterative improvement. A series of simulation experiments have been conducted to evaluate the proposed approaches and compare them to previous methods. The experimental results demonstrate significant performance improvement in terms of average turnaround time. Keywords  Resource utilization · Processor allocation · Moldable job scheduling · HPC as a service

1 Introduction Parallel jobs, according to their flexibility in parallelism, can be classified into four types [1]: (1) rigid, (2) moldable (3) evolving, and (4) malleable. A rigid job can only run with a specific number of processors specified by the user upon job submission. Moldable jobs are flexible in the number of processors to use, but the number cannot be changed during execution. Malleable and evolving jobs are similar to moldable jobs in that they all have the potential to run with different parallelisms in * Kuo‑Chan Huang [email protected] Extended author information available on the last page of the article

13

Vol.:(0123456789)



Y.-J. Wu et al.

contrast to rigid jobs. However, they are even more flexible, being able to change the number of used processors dynamically during execution. While both evolving and malleable jobs can change their processor requirements during execution, the change is application initiated for evolving jobs, but system initiated for malleable jobs [2, 3]. Most modern parallel programs are written with the moldable property. For example, the famous benchmark program HPL,1 used for ranking the top 500 supercomputers in the world,2 has the moldable property, so that it can be used for evaluating the performance of various parallel computers of different scales easily without modifying its source code. Another example is a dynamic moldable tree search (DMTS) framework proposed for solving the Boolean satisfiabilitϕy problem in [4]. The DMTS framework was designed to run on various parallel computing infrastructures, including clusters, computational grids,