Bleuse et al. (EuroPar 2018) [1] introduced a general model for interference-aware scheduling in large scale parallel platforms. They considered two different types of communications: the flows induced by data exchanges during computations and the flows related to Input/Output operations. Rather than taking into account these communications explicitly, they restrict the possible allocations of a job by external topological constraints. In their work, jobs are considered to be rigid: a job requires a specific number of machines as well as a prespecified Input/Output processor in order to be executed. Here, we propose to adopt the same framework for the platform and the aforementioned topological constraints, but to extend their study by taking explicitely into account the energy consumption. For that, we plan to adopt the speed scaling model. In the speed scaling model [2], the speed of the processor (machine) may be dynamically changed over time. When a processor runs at speed s, then the rate with which the energy is consumed (i.e., the power) is f(s) with f a non-decreasing function of the speed. The energy is the integral of the power over time. According to the well-known cube-root rule for CMOS devices, the speed of a device is proportional to the cube-root of the power and hence f(s) = s3, but in the literature, many works consider that the power is f(s) = sα where α > 1 is a constant, or an arbitrary convex function. Many scheduling problems have been studied in this model and recently, Kononov and Kovalenko [3] considered the case of rigid parallel jobs. We propose to first extend his study by introducing Input/Output nodes as in the model of Bleuse et al. [1].
The student will have to first study the related bibliography and then to design and evaluate efficient algorithms for the problem. The evaluation may be either analytical and/or using simulations.
Stage effectué dans le cadre de l'ANR Energumen.
References
[1] Raphaël, Bleuse Konstantinos Dogeas, Giorgio Lucarelli, Gr ́egory Mouni ́e, Denis Trystram, Interference- Aware Scheduling Using Geometric Constraints. 205-217 2018 Euro-Par
[2] F. Frances Yao, Alan J. Demers, Scott Shenker, A Scheduling Model for Reduced CPU Energy. 374-382 FOCS, 1995
[3] Alexander V. Kononov, Yulia V. Kovalenko Approximation algorithms for energy-efficient scheduling of parallel jobs. 693-709 2020 23 J. Sched.