1 Introduction
2 Related surveys
3 Modeling and notation
3.1 Task models
3.2 Processor models for speed scaling
3.3 Sleep modes
3.4 Problem notation and qualification
-
\(\mathfrak a\): The system field describes the architecture of the system. This includes the number of processors (or devices), whether speed scaling (ss) and/or sleep modes (sl) are used, and properties of the system with respect to speed scaling and/or sleep modes (see Table 1). The entries nonunif, disc, and global all imply speed scaling (ss) to keep the notation concise.
-
\(\mathfrak b\): The second field contains the task characteristics like arrival time, deadline, restrictions on the ordering of timing constraints of tasks (agree, prec, lami), and scheduling properties (migr, pmtn, prio, sched). E.g., when \(a_n\) occurs in this field, it means that tasks have arrival times, otherwise \(a_n{=}0\) (for all n) is implied. As we focus on energy minimization under deadline constraints, \(d_n\) always occurs in \(\mathfrak b\) and implies that deadlines must be met.
-
\(\mathfrak c\): The third field contains the scheduling objective. In the context of this article, the field \(\mathfrak c\) only contains “E” to denote that the energy should be minimized, but we maintain this field to preserve compliance with Graham’s notation.
Field | Entry | Meaning |
---|---|---|
\(\mathfrak a\)
| 1 | Single processor |
\(P_M\)
|
M parallel processors | |
\(\mathrm {ss}\)
| Speed scaling is supported | |
\(\mathrm {nonunif}\)
| A nonuniform power function is used (\(\mathrm {ss}\) implied) | |
\(\mathrm {disc}\)
| Discrete speed scaling is used (\(\mathrm {ss}\) implied) | |
\(\mathrm {global}\)
| Global speed scaling is used (\(\mathrm {ss}\) implied) | |
\(\mathrm {sl}\)
| Sleep modes supported | |
\(\mathfrak b\)
|
\(a_n\)
| Arrival time |
\(a_n{=}a\)
| Same arrival time a for all tasks | |
\(d_n\)
| Deadline constraint | |
\(d_n{=}d\)
| Same deadline constraint d for all tasks | |
\(w_n{=}w\)
| All tasks have workload w
| |
\(\mathrm {agree}\)
| Agreeable deadlines (\(a_n \le a_m \Leftrightarrow d_n \le d_m\)) | |
\(\mathrm {lami}\)
| Laminar instances | |
(\([a_i,d_i] \subset [a_j,d_j] \vee [a_j,d_j] \subset [a_i,d_i] \vee [a_i,d_i] \cap [a_j,d_j] = \emptyset \)) | ||
\(\mathrm {prec}\)
| Tasks have precedence constraints | |
\(\mathrm {pmtn}\)
| Preemptions are allowed | |
\(\mathrm {prio}\)
| Tasks have a fixed priority | |
\(\mathrm {migr}\)
| Task migration is allowed | |
\(\mathrm {sched}\)
| A schedule is given | |
\(\mathfrak c\)
|
E
| Minimize the energy consumption |
4 Fundamental results
4.1 Constant speed
4.2 Nonconvex power function
4.3 Critical speed
4.4 Discrete speed scaling as a linear program
4.5 Relation between continuous and discrete speed scaling
4.6 Power equality
4.7 Nonuniform power
Section | Problem | Papers |
---|---|---|
General tasks (Sect. 5.1) |
\(1;\mathrm {ss} \vert a_n;d_n;\mathrm {pmtn} \vert E\)
| |
\(1;\mathrm {disc} \vert a_n;d_n;\mathrm {pmtn} \vert E\)
| ||
\(1;\mathrm {ss} \vert a_n;d_n;\mathrm {pmtn};\mathrm {prio} \vert E\)
|
Quan and Hu (2003) | |
\(1;\mathrm {ss} \vert a_n;d_n \vert E\)
| ||
\(1;\mathrm {ss} \vert a_n;d_n;w_n=1 \vert E\)
|
Huang and Ott (2014) | |
\(1;\mathrm {ss};\mathrm {nonunif} \vert a_n;d_n;\mathrm {pmtn} \vert E\)
|
Kwon and Kim (2005) | |
\(1;\mathrm {ss};\mathrm {nonunif};\mathrm {disc} \vert a_n;d_n \vert E\)
|
Kwon and Kim (2005) | |
\(1;\mathrm {sl} \vert a_n;d_n;\mathrm {pmtn} \vert E\)
|
Baptiste et al. (2012) | |
\(1;\mathrm {ss};\mathrm {sl} \vert a_n;d_n;\mathrm {pmtn} \vert E\)
| ||
Agreeable deadlines (Sect. 5.2) |
\(1;\mathrm {ss} \vert a_n;d_n;\mathrm {agree} \vert E\)
| |
\(1;\mathrm {sl} \vert a_n;d_n;\mathrm {agree} \vert E\)
|
Angel et al. (2014) | |
\(1;\mathrm {sl};\mathrm {ss} \vert a_n;d_n;\mathrm {agree} \vert E\)
|
Bampis et al. (2012a) | |
Laminar instances (Sect. 5.3) |
\(1;\mathrm {ss} \vert a_n;d_n;\mathrm {pmtn};\mathrm {lami} \vert E\)
|
Li et al. (2006) |
\(1;\mathrm {ss} \vert a_n;d_n=d;\mathrm {pmtn} \vert E\)
|
Li et al. (2006) | |
\(1;\mathrm {ss} \vert a_n=a;d_n;\mathrm {pmtn} \vert E\)
|
Li et al. (2006) | |
\(1;\mathrm {ss} \vert a_n;d_n;\mathrm {lami} \vert E\)
|
Huang and Ott (2014) |
4.8 Flow problems
4.9 Sleep modes
5 Uniprocessor problems
5.1 General tasks
Task | Arrival time | Deadline | Workload |
---|---|---|---|
\(T_1\)
| 0 | 30 | 30 |
\(T_2\)
| 5 | 10 | 10 |
\(T_3\)
| 15 | 55 | 10 |
\(T_4\)
| 25 | 35 | 10 |
Interval | Iteration 1 | Iteration 2 | Iteration 3 | |||
---|---|---|---|---|---|---|
\(g(I_{i,j})\)
|
\(g(I_{i,j})\)
|
\(g(I_{i,j})\)
| ||||
\(I_{1,1}\)
|
\(\frac{40}{30}\)
|
\(\approx 1.333\)
|
\(\frac{30}{25}\)
|
\( = 1.2\)
| ||
\(I_{1,2}\)
|
\(\frac{10}{10}\)
|
\(= 1\)
| ||||
\(I_{1,3}\)
|
\(\frac{50}{55}\)
|
\(\approx 0.909\)
|
\(\frac{50}{50}\)
|
\( = 1\)
| ||
\(I_{1,4}\)
|
\(\frac{50}{35}\)
|
\(\approx 1.429\)
|
\(\frac{40}{30}\)
|
\(\approx 1.333\)
| ||
\(I_{2,1}\)
|
\(\frac{10}{25}\)
|
\(= 0.4\)
| ||||
\(I_{2,2}\)
|
\(\frac{10}{5}\)
|
\(=2\)
| ||||
\(I_{2,3}\)
|
\(\frac{30}{50}\)
|
\(=0.6\)
| ||||
\(I_{2,4}\)
|
\(\frac{20}{30}\)
|
\(\approx 0.667\)
| ||||
\(I_{3,1}\)
| 0 | 0 | ||||
\(I_{3,2}\)
| 0 | |||||
\(I_{3,3}\)
|
\(\frac{20}{40}\)
|
\(=0.5\)
|
\(\frac{20}{40}\)
|
\(=0.5\)
|
\(\frac{10}{20}\)
|
\(=0.5\)
|
\(I_{3,4}\)
|
\(\frac{10}{20}\)
|
\(=0.5\)
|
\(\frac{10}{20}\)
|
\(=0.5\)
| ||
\(I_{4,1}\)
| 0 | 0 | ||||
\(I_{4,2}\)
| 0 | |||||
\(I_{4,3}\)
|
\(\frac{10}{30}\)
|
\(\approx 0.333\)
|
\(\frac{10}{30}\)
|
\(\approx 0.333\)
| ||
\(I_{4,4}\)
|
\(\frac{10}{10}\)
|
\(=1\)
|
\(\frac{10}{10}\)
|
\(=1\)
|
5.2 Agreeable deadlines
5.3 Laminar instances
6 Multiprocessor problems
Section | Problem | Papers |
---|---|---|
General tasks (Sect. 6.1) |
\(P_M;\mathrm {ss} \vert a_n=a;d_n=d \vert E\)
| |
\(P_M;\mathrm {ss} \vert a_n;d_n;\mathrm {pmtn};\mathrm {migr} \vert E\)
| ||
\(P_M;\mathrm {ss} \vert a_n;d_n;\mathrm {pmtn} \vert E\)
| ||
\(P_M;\mathrm {ss} \vert a_n;d_n \vert E\)
| ||
Agreeable deadlines (Sect. 6.2) |
\(P_M;\mathrm {ss} \vert a_n;d_n;w_n=1;\mathrm {agree} \vert E\)
|
Bampis et al. (2015) |
Tasks with precedence constraints (Sect. 6.3) |
\(P_M;\mathrm {ss} \vert a_n=a;d_n=d;\mathrm {prec} \vert E\)
|
Li (2012) |
\(P_M;\mathrm {global} \vert d_n=d;\mathrm {prec} \vert E\)
|
Gerards et al. (2015) | |
\(P_M;\mathrm {global} \vert a_n;d_n;\mathrm {sched};\mathrm {prec} \vert E\)
|
Gerards et al. (2014) |