ENES: Energy-Efficient Scheduling

• Applicant: Professorin Dr. Susanne Albers
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 254856932

• Final Report Year: 2019

Final Report Abstract

In the project, over a period of four years, we have worked on a spectrum of algorithmic problems in energy-efficient computation. Specifically, the investigated problems address modern and timely scheduling environments. The results contribute towards an efficient processing of large data sets on the system and device level. A major part of our research has focused on "dynamic speed scaling", a relatively new and effective technique to save energy in microprocessor systems. Many modern microprocessors can run at variable speed. The higher the speed, the higher the required power is. Obviously, energy is power integrated over time. We investigated the most fundamental scheduling problem in this context, where jobs with release times, deadlines and processing volumes must be processed. In our research we conducted the first comprehensive study of dynamic speed scaling in multiprocessor environments with heterogeneous processors. Such systems naturally arise in data and compute centers. For the offline problem, where job sets are known in advance, we have developed polynomial time algorithms that work for arbitrary, continuous non-decreasing power functions. We have also devised combinatorial algorithms that work for general simple polynomial power functions. Additionally, we have examined the online setting, where jobs arrive over time, and have extended known strategies that were proposed for single-processor settings. For dynamic speed scaling we have also studied the scenario that job preemption is not allowed. We have been able to present significantly improved approximations guarantees. Finally, we have examined throughput maximization problems, given a certain energy budget. Moreover, in the project we have investigated "power-down mechanisms", which transition idle systems into low-power stand-by or sleep states. Prior work has focused on a single device. In our research we have initiated the study of power-down mechanisms in multiprocessor environments with power-heterogeneous processors. Such mechanisms are particularly relevant in data centers where servers are utilized only 20 - 40% of the time on average. When idle and in active mode, they still consume half of their peak power. We have introduced new power management problems that dynamically right-size the pool of active servers depending on the current workload. We have developed algorithms based on min-cost flow and multi-commodity min-cost flow that compute optimal or provably good approximate solutions.

Publications

• Speed-scaling with no preemptions. Proc. 25th International Symposium on Algorithms and Computation (ISAAC’14), Springer LNCS 8889, 259–269, 2014
  E. Bampis, D. Letsios and G. Lucarelli
  
• A duality based 2-approximation algorithm for maximum agreement forest. Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP’16), LIPIcs 55, Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 70:1-70:14, 2016
  F. Schalekamp, A. van Zuylen and S. van der Ster
  
• Throughput maximization for speed scaling with agreeable deadlines. Journal of Scheduling, 19(6):619–625, 2016
  E. Angel, E. Bampis, V. Chau and D. Letsios
  
• Minimizing worst-case and average-case makespan over scenarios. Journal of Scheduling, 20(6):545–555, 2017
  E. Feuerstein, A. Marchetti-Spaccamela, F. Schalekamp, R. Sitters, S. van der Ster, L. Stougie and A. van Zuylen
  
• On energy conservation in data centers. Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’17), 35–44, 2017
  S. Albers
  
• Online market intermediation. Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP’17), LIPIcs 80, Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 47:1-47:14, 2017
  Y. Giannakopoulos, E. Koutsoupias and P. Lazos
  
• Scheduling on power-heterogeneous processors. Information and Computation, Vol. 257. 2017, pp. 22-33.
  S. Albers, E. Bampis, D. Letsios, G. Lucarelli and R. Stotz
  
• Scheduling on powerheterogeneous processors. Information and Computation, 257:22–33, 2017
  S. Albers, E. Bampis, D. Letsios, G. Lucarelli and R. Stotz