Abstract

Many multicore processors are capable of decreasing the voltage and clock frequency to save energy at the cost of an increased delay. While a large part of the theory oriented literature focuses on local dynamic voltage and frequency scaling (local DVFS), where every core’s voltage and clock frequency can be set separately, this article presents an in-depth theoretical study of the more commonly available global DVFS that makes such changes for the entire chip. This article shows how to choose the optimal clock frequencies that minimize the energy for global DVFS, and it discusses the relationship between scheduling and optimal global DVFS. Formulas are given to find this optimum under time constraints, including proofs thereof. The problem of simultaneously choosing clock frequencies and a schedule that together minimize the energy consumption is discussed, and based on this a scheduling criterion is derived that implicitly assigns frequencies and minimizes energy consumption. Furthermore, this article studies the effectivity of a large class of scheduling algorithms with regard to the derived criterion, and a bound on the maximal relative deviation is given. Simulations show that with our techniques an energy reduction of 30% can be achieved with respect to state-of-the-art research.
Original languageUndefined
Pages (from-to)1742-1754
Number of pages13
JournalIEEE transactions on computers
Volume64
Issue number6
DOIs
StatePublished - Jun 2015

Fingerprint

Clocks
Energy utilization
Scheduling
Scheduling algorithms
Voltage scaling
Dynamic frequency scaling

Keywords

  • EWI-25452
  • CAES-EEA: Efficient Embedded Architectures
  • Heuristic Methods
  • Energy aware-systems
  • METIS-312460
  • IR-93272
  • Multi-core/single-chip multiprocessors
  • Global Optimization
  • Convex programming
  • Scheduling

Cite this

@article{9ce83cf1eec946d685a4e7607cf2d72e,
title = "On the interplay between global DVFS and scheduling tasks with precedence constraints",
abstract = "Many multicore processors are capable of decreasing the voltage and clock frequency to save energy at the cost of an increased delay. While a large part of the theory oriented literature focuses on local dynamic voltage and frequency scaling (local DVFS), where every core’s voltage and clock frequency can be set separately, this article presents an in-depth theoretical study of the more commonly available global DVFS that makes such changes for the entire chip. This article shows how to choose the optimal clock frequencies that minimize the energy for global DVFS, and it discusses the relationship between scheduling and optimal global DVFS. Formulas are given to find this optimum under time constraints, including proofs thereof. The problem of simultaneously choosing clock frequencies and a schedule that together minimize the energy consumption is discussed, and based on this a scheduling criterion is derived that implicitly assigns frequencies and minimizes energy consumption. Furthermore, this article studies the effectivity of a large class of scheduling algorithms with regard to the derived criterion, and a bound on the maximal relative deviation is given. Simulations show that with our techniques an energy reduction of 30% can be achieved with respect to state-of-the-art research.",
keywords = "EWI-25452, CAES-EEA: Efficient Embedded Architectures, Heuristic Methods, Energy aware-systems, METIS-312460, IR-93272, Multi-core/single-chip multiprocessors, Global Optimization, Convex programming, Scheduling",
author = "Gerards, {Marco Egbertus Theodorus} and Hurink, {Johann L.} and Jan Kuper",
note = "eemcs-eprint-25452",
year = "2015",
month = "6",
doi = "10.1109/TC.2014.2345410",
volume = "64",
pages = "1742--1754",
journal = "IEEE transactions on computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "6",

}

TY - JOUR

T1 - On the interplay between global DVFS and scheduling tasks with precedence constraints

AU - Gerards,Marco Egbertus Theodorus

AU - Hurink,Johann L.

AU - Kuper,Jan

N1 - eemcs-eprint-25452

PY - 2015/6

Y1 - 2015/6

N2 - Many multicore processors are capable of decreasing the voltage and clock frequency to save energy at the cost of an increased delay. While a large part of the theory oriented literature focuses on local dynamic voltage and frequency scaling (local DVFS), where every core’s voltage and clock frequency can be set separately, this article presents an in-depth theoretical study of the more commonly available global DVFS that makes such changes for the entire chip. This article shows how to choose the optimal clock frequencies that minimize the energy for global DVFS, and it discusses the relationship between scheduling and optimal global DVFS. Formulas are given to find this optimum under time constraints, including proofs thereof. The problem of simultaneously choosing clock frequencies and a schedule that together minimize the energy consumption is discussed, and based on this a scheduling criterion is derived that implicitly assigns frequencies and minimizes energy consumption. Furthermore, this article studies the effectivity of a large class of scheduling algorithms with regard to the derived criterion, and a bound on the maximal relative deviation is given. Simulations show that with our techniques an energy reduction of 30% can be achieved with respect to state-of-the-art research.

AB - Many multicore processors are capable of decreasing the voltage and clock frequency to save energy at the cost of an increased delay. While a large part of the theory oriented literature focuses on local dynamic voltage and frequency scaling (local DVFS), where every core’s voltage and clock frequency can be set separately, this article presents an in-depth theoretical study of the more commonly available global DVFS that makes such changes for the entire chip. This article shows how to choose the optimal clock frequencies that minimize the energy for global DVFS, and it discusses the relationship between scheduling and optimal global DVFS. Formulas are given to find this optimum under time constraints, including proofs thereof. The problem of simultaneously choosing clock frequencies and a schedule that together minimize the energy consumption is discussed, and based on this a scheduling criterion is derived that implicitly assigns frequencies and minimizes energy consumption. Furthermore, this article studies the effectivity of a large class of scheduling algorithms with regard to the derived criterion, and a bound on the maximal relative deviation is given. Simulations show that with our techniques an energy reduction of 30% can be achieved with respect to state-of-the-art research.

KW - EWI-25452

KW - CAES-EEA: Efficient Embedded Architectures

KW - Heuristic Methods

KW - Energy aware-systems

KW - METIS-312460

KW - IR-93272

KW - Multi-core/single-chip multiprocessors

KW - Global Optimization

KW - Convex programming

KW - Scheduling

U2 - 10.1109/TC.2014.2345410

DO - 10.1109/TC.2014.2345410

M3 - Article

VL - 64

SP - 1742

EP - 1754

JO - IEEE transactions on computers

T2 - IEEE transactions on computers

JF - IEEE transactions on computers

SN - 0018-9340

IS - 6

ER -