On solving the unrelated parallel machine scheduling problem: active microrheology as a case study
- PDF / 1,321,172 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 115 Downloads / 231 Views
On solving the unrelated parallel machine scheduling problem: active microrheology as a case study F. Orts1 · G. Ortega1 · A. M. Puertas2 · I. García3 · E. M. Garzón1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Modern computational platforms are characterized by the heterogeneity of their processing elements. Additionally, there are many algorithms which can be structured as a set of procedures or tasks with different computational cost. Balancing the computational load among the available processing elements is one of the main keys for the optimal exploitation of such heterogeneous platforms. When the processing time of any procedure executed on any of the available processing elements is known, this workload-balancing problem can be modeled as the well-known scheduling on unrelated parallel machines problem. Solving this type of problems is a big challenge due to the high heterogeneity on both, the tasks and the machines. In this paper, the balancing problem has been formally defined as a global optimization problem which minimizes the makespan (parallel runtime) and a heuristic based on a Genetic Algorithm, called Genetic Scheduler (GenS), has been developed to solve it. In order to analyze the behavior of GenS for several heterogeneous clusters, an example taken from the field of statistical mechanics has been considered as a case study: an active microrheology model. Given this type of problem and a heterogeneous cluster, we seek to minimize the total runtime to extend and analyze in depth the case of study. In such context, a task consists of the simulation of a tracer particle pulled into a cubic box with smaller bath particles. The computational load depends on the total number of the bath particles. Moreover, GenS has been compared to other dynamic and static scheduling approaches. The experimental results of such a comparison show that GenS outperforms the rest of the tested alternatives achieving a better distribution of the computational workload on a heterogeneous cluster. So, the scheduling strategy developed in this paper is of potential interest for any application which requires the execution of many tasks of different duration (a priori known) on a heterogeneous cluster. Keywords Parallel scheduling · Heterogeneous cluster · Unrelated machines · Genetic Algorithm * G. Ortega [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
F. Orts et al.
1 Introduction Modern computational systems consist of heterogeneous clusters which are composed by the interconnection of Processing Units (PUs) with different computational power, such as CPU-cores, GPUs and so on [1]. Algorithms developed for this kind of platforms have to treat such heterogeneity to efficiently exploit the different resources on modern computers. To this effect, the programmer is responsible for explicitly selecting the devices and mapping the tasks among PUs. So, scheduling techniques become one of the most challenging problems, having
Data Loading...
