# Power Optimization of Multimode Mobile Embedded Systems with Workload-Delay Dependency

Authors: Hoeseok Yang; Soonhoi Ha
Journal: Mobile Information Systems
 (2016)

---

## Abstract

This paper proposes to take the relationship between delay and workload into account in the power optimization of microprocessors in mobile embedded systems. Since the components outside a device continuously change their values or properties, the workload to be handled by the systems becomes dynamic and variable. This variable workload is formulated as a staircase function of the delay taken at the previous iteration in this paper and applied to the power optimization of DVFS (dynamic voltage-frequency scaling). In doing so, a graph representation of all possible workload/mode changes during the lifetime of a device, Workload Transition Graph (WTG), is proposed. Then, the power optimization problem is transformed into finding a cycle (closed walk) in WTG which minimizes the average power consumption over it. Out of the obtained optimal cycle of WTG, one can derive the optimal power management policy of the target device. It is shown that the proposed policy is valid for both continuous and discrete DVFS models. The effectiveness of the proposed power optimization policy is demonstrated with the simulation results of synthetic and real-life examples.


---

## Body

## 1. Introduction

Today’s mobile embedded systems often interact with physical processes or external environments, referred to as Cyber-Physical Systems (CPSs). Such systems are usually modeled with interactions between the physical world and the devices [1]. For instance, handheld or stationary embedded systems need to continuously interact with environments in the example of smart building [2]. The system performs a computational task and responds through an actuator to the physical side, while the resulting change at the physical side, in turn, makes a variation on the input (sensor) of the device. In order not to make this control loop unstable, it is common that the embedded system has a real-time constraint within which all the computation should be completed.In a class of applications, the computational workload of the embedded systems depends on the variation of the sampled input value, while the computation delay, in turn, affects the input variation of the next iteration. Usually, if it invests more time at one iteration for processing information, it would have more work to do at the next iteration. One example of such delay-workload dependency can be found in an object tracking which is frequently used in drone, surveillance camera, or augmented reality [3–5]. The image obtained from the camera is processed by the object tracker to follow an object. As the object may continuously change its position meanwhile, the object tracker should reactively take an image from the adjusted position/angle to make the next decision. The more time the object spends in the tracker, the more distance the object will move by.Such workload-delay relations can be popularly found in modern mobile embedded systems, which rely on computer vision algorithms to capture what happens in the external world. In those applications, it is typical that thecurrent internal state is maintained to figure out thedifference caused by what happened in the external world. The examples of such internal states range from a simple snapshot of a sensor reading to a complicated model of the scene obtained from camera. No matter what the model is, it is generally true that the longer execution delay between two consecutive invocations of the algorithm results in the larger workload in the successive iteration as the degree of the heterogeneity gets bigger.The workload-delay dependency can also be found in many different types of applications. Real-time pattern matching over event streams [6], for instance, exhibits similar behavior: the queries can be handled either by small amount (shorter delay, less workload) or in an aggregated manner (longer delay, more workload). Similarly, haptic rendering in Human-Computer Interface (HCI) uses adaptive sampling techniques to deal with the stringent real-time constraint [7] and the rendering algorithm can be warm-started to exploit the temporal coherence [8]. In essence, applications which exploit temporal coherence have possible workload-delay dependencies. That is, any iterative algorithms that can be warm-started can lead to one.Nowadays, most modern microprocessors used in mobile embedded systems support dynamic voltage-frequency scaling (DVFS) [9] for power-efficient operations. Generally, delay and energy in the systems with DVFS are in a tradeoff relationship for a given workload. That is, given a certain amount of work to be handled, a faster solution (with a higher frequency) is less energy efficient. Considering this control knob with the aforementioned delay-workload dependency, the power optimization problem gets very challenging. Conventionally, it has just been understood that “working as slow as possible” within the real-time constraint is the best discipline in terms of minimizing the power dissipation. However, with the existence of the workload-delay dependency, it is no longer valid since a slower execution may cause a bigger workload at the next iteration. On the other hand, “as fast as possible” is not optimal either, as the power consumption is a strong function of the operating speed [10].The workload-delay dependency has been firstly modeled and applied to the DVFS optimization in [11]. It is assumed that the workload is a continuous and monotonically increasing function of the delay, under which a simple yet effective power management technique has been proposed. Specifically, it has been shown that staying in a certain DVFS mode is better than alternating between different DVFS modes dynamically. Later, the optimization is generalized to various power models and formally proven to be optimal [12].This work differs from our previous work [12] in that we take different optimization approach tailored for discrete workload levels. We observed that the continuity assumption does not always hold true in reality. Rather, there are a number of applications that have discrete levels of workload. For instance, recall that many image or signal processing algorithms handle input data in the unit of macroblock or frame. In such application domains, the workload tends to grow in a discrete manner. In this paper, the workload is modeled as a staircase function of the delay taken in the previous iteration. Since the solution obtained by the previous work [11, 12] is no longer optimal or nonexisting at all in the staircase model, a new power management technique is proposed. The contributions of this paper can be summarized as follows:(i)
The workload-delay dependency is modeled in a staircase function generalizing the previous model and validated with a real-life example.
(ii)
A novel data structure, Workload Transition Graph (WTG), is proposed to represent all possible operation workload/mode changes of a device.
(iii)
Based on WTG, a power management policy is derived and shown to be optimal.


## 2. Related Work

Bogdan and Marculescu [13] observed that workloads from physical processes tend to be nonstationary but exhibit some systematic relationship in space and time. They proposed a workload characterization approach based on statistical physics and showed how the workload-awareness can improve the design of electronic systems. Zhang et al. [14] studied the relationship between the control stability and workload in inverted pendulum control. While enlarged invocation periods may lower the degree of stability, more inverted pendulums can be controlled by a system as the lengthened invocation periods lower the utilization of the algorithm. This can be seen as trading off the control stability for resource efficiency. In other words, they proposed to sacrifice the stability to accommodate more workload in a system. The proposed technique also deals with variable workload in electronic systems but differs from the above-mentioned works in that the effect of execution delay on workload is systematically considered.Recently, Pant et al. [15] proposed a codesign of computation delay and control stability based on anytime algorithm. Anytime algorithm is a kind of algorithms that can be stopped at any point in time but still provides a decent solution. Typically, the quality of the solution is increasing function of the computation delay. In their work, it is the duty of the control algorithm to adaptively change the real-time deadline constraint and error bound (quality of control). On the contrary, the relationship between execution delay and workload is formally described in the form of workload-delay function; thus no explicit runtime monitoring/control is required in the proposed technique.A design guideline for flexible delay constraints in distributed embedded systems was proposed by Goswami et al. [16], where some of the samples are allowed to violate the given delay deadline. They presented the applicability of the proposed approach using the FlexRay dynamic segment as a communication medium. This work is similar to the proposed approach in the sense that they do not stick to a given fixed real-time deadline. While they could avoid the resource overprovisioning by trading off the hard real-time constraints, the workload dependency to the delay has not been considered. Moreover, from a real-time standpoint, the proposed work is more rigorous as it allows no real-time constraint violations.


## 3. Problem Definition

This section presents the system model assumed in this paper, which is followed by the formulation of the power optimization problem.


### 3.1. System Model

#### 3.1.1. Dynamic Voltage-Frequency Scaling

In this paper, we assume that a system has multiple operation modes due to DVFS feature, where the operating frequency and voltage can be modulated. For simplicity, we first assume that there are infinitely many operation modes available, among which one is chosen at each iteration. It will be shown that the proposed technique can be applied to a discrete DVFS as well in Section5. The operation mode at the ith iteration is represented with the speed scaling factor k
i ranging from k
m
i
n to k
m
a
x
=
1 (k
m
i
n
≤
k
≤
k
m
a
x
=
1). Then, the operating frequency of the ith iteration, f
i, is(1)
f
i
=
k
i
·
f
m
a
x
,where f
m
a
x is the maximum frequency of the microprocessor.


#### 3.1.2. Workload

The workload is defined to be a number of clock cycles elapsed to complete the given computation. We denote the number of cycles elapsed to handle the workload of theith iteration at the full speed of the microprocessor (k
i
=
1) as t
r
e
f
,
i. That is,(2)
w
i
=
t
ref
,
i
=
k
i
·
t
i
.Note that the elapsed time t
i increases as the speed is scaled down (k
i
<
1). Then, the delay t
i is automatically determined when a speed scaling factor k
i is chosen for the given workload (t
i
=
w
i
/
k
i).


#### 3.1.3. Real-Time Constraint

The delayt
i cannot be unboundedly long as the system is associated with real-time constraint T. For all iterations, the elapsed time should be no more than T: (3)
t
i
≤
T
,
∀
i
.


#### 3.1.4. Delay-Workload Dependency

As stated earlier, the workload is dependent upon the previous execution delay. Usually, the workload is not a continuous function of the delay variation. Rather, the changes happen in a discrete manner. Therefore, the workload at theith iteration is a monotonically increasing staircase function of the delay of the previous iteration, t
i
-
1: w
i
=
W
(
t
i
-
1
). If the given system has n workload levels, the workload function W can be formulated as follows: (4)
W
t
=
wl
1
if
0
<
t
≤
th
1
wl
2
if
th
1
<
t
≤
th
2
⋮
wl
n
-
1
if
th
n
-
2
<
t
≤
th
n
-
1
wl
n
if
th
n
-
1
<
t
,in which the workload levels are wl
1
<
wl
2
<
⋯
<
wl
n and the delay thresholds (workload changing moments) are th
1
<
th
2
<
⋯
<
th
n
-
1.


#### 3.1.5. Execution Trace

At theith iteration, the speed scaling factor k
i uniquely defines an executionmode as the delay is fixed accordingly by (2). The initial workload is assumed to be given as w
1. Then, an execution trace t
r of length L is defined to be a sequence of the speed scaling factors of L iterations:(5)
t
r
≔
k
1
,
k
2
,
…
,
k
L
.


#### 3.1.6. Average Power Consumption

The dynamic power consumption of CMOS circuits isc
v
d
d
2
f, where c, v
d
d, and f are capacitance, operating voltage, and frequency, respectively. As the operating frequency is proportional to (
v
d
d
-
v
th
)
2
/
v
d
d [10], the power consumption is an increasing function of f. It is worth noting that the proposed model is not dependent upon any specific DVFS model. We denote the energy consumption of a unit workload at the full speed (k
=
1) as C
e and assume that energy dissipation grows linearly to the size of workload. Then, the reference energy of a workload w
i at the full speed is C
e
·
w
i. Given a DVFS energy model S as a function of the speed scaling factor k, the energy consumption at the ith iteration EG
i is formulated as follows:(6)
EG
i
=
C
e
·
w
i
·
S
k
i
,in which S
(
0
)
=
0 and S
(
1
)
=
1. Then, the average power consumption of a trace t
r can be formulated as follows:(7)
AVG
t
r
=
∑
i
=
1
t
r
EG
i
∑
i
=
1
t
r
t
i
.It is worthwhile to mention that the proposed technique is not specific to a certain workload-energy model. While we adopt linear model for the workload-energy relation for ease of presentation, any, possibly nonlinear, model can be used in (6).


### 3.2. Problem Formulation

Our objective is to minimize the average power consumption of a given system as follows:Given the modeling constantC
e, DVFS energy modeling function S, workload function W, and the real-time constraint T, determine an execution trace t
r such that the average power consumption formulated in (7) is minimized.


## 3.1. System Model

### 3.1.1. Dynamic Voltage-Frequency Scaling

In this paper, we assume that a system has multiple operation modes due to DVFS feature, where the operating frequency and voltage can be modulated. For simplicity, we first assume that there are infinitely many operation modes available, among which one is chosen at each iteration. It will be shown that the proposed technique can be applied to a discrete DVFS as well in Section5. The operation mode at the ith iteration is represented with the speed scaling factor k
i ranging from k
m
i
n to k
m
a
x
=
1 (k
m
i
n
≤
k
≤
k
m
a
x
=
1). Then, the operating frequency of the ith iteration, f
i, is(1)
f
i
=
k
i
·
f
m
a
x
,where f
m
a
x is the maximum frequency of the microprocessor.


### 3.1.2. Workload

The workload is defined to be a number of clock cycles elapsed to complete the given computation. We denote the number of cycles elapsed to handle the workload of theith iteration at the full speed of the microprocessor (k
i
=
1) as t
r
e
f
,
i. That is,(2)
w
i
=
t
ref
,
i
=
k
i
·
t
i
.Note that the elapsed time t
i increases as the speed is scaled down (k
i
<
1). Then, the delay t
i is automatically determined when a speed scaling factor k
i is chosen for the given workload (t
i
=
w
i
/
k
i).


### 3.1.3. Real-Time Constraint

The delayt
i cannot be unboundedly long as the system is associated with real-time constraint T. For all iterations, the elapsed time should be no more than T: (3)
t
i
≤
T
,
∀
i
.


### 3.1.4. Delay-Workload Dependency

As stated earlier, the workload is dependent upon the previous execution delay. Usually, the workload is not a continuous function of the delay variation. Rather, the changes happen in a discrete manner. Therefore, the workload at theith iteration is a monotonically increasing staircase function of the delay of the previous iteration, t
i
-
1: w
i
=
W
(
t
i
-
1
). If the given system has n workload levels, the workload function W can be formulated as follows: (4)
W
t
=
wl
1
if
0
<
t
≤
th
1
wl
2
if
th
1
<
t
≤
th
2
⋮
wl
n
-
1
if
th
n
-
2
<
t
≤
th
n
-
1
wl
n
if
th
n
-
1
<
t
,in which the workload levels are wl
1
<
wl
2
<
⋯
<
wl
n and the delay thresholds (workload changing moments) are th
1
<
th
2
<
⋯
<
th
n
-
1.


### 3.1.5. Execution Trace

At theith iteration, the speed scaling factor k
i uniquely defines an executionmode as the delay is fixed accordingly by (2). The initial workload is assumed to be given as w
1. Then, an execution trace t
r of length L is defined to be a sequence of the speed scaling factors of L iterations:(5)
t
r
≔
k
1
,
k
2
,
…
,
k
L
.


### 3.1.6. Average Power Consumption

The dynamic power consumption of CMOS circuits isc
v
d
d
2
f, where c, v
d
d, and f are capacitance, operating voltage, and frequency, respectively. As the operating frequency is proportional to (
v
d
d
-
v
th
)
2
/
v
d
d [10], the power consumption is an increasing function of f. It is worth noting that the proposed model is not dependent upon any specific DVFS model. We denote the energy consumption of a unit workload at the full speed (k
=
1) as C
e and assume that energy dissipation grows linearly to the size of workload. Then, the reference energy of a workload w
i at the full speed is C
e
·
w
i. Given a DVFS energy model S as a function of the speed scaling factor k, the energy consumption at the ith iteration EG
i is formulated as follows:(6)
EG
i
=
C
e
·
w
i
·
S
k
i
,in which S
(
0
)
=
0 and S
(
1
)
=
1. Then, the average power consumption of a trace t
r can be formulated as follows:(7)
AVG
t
r
=
∑
i
=
1
t
r
EG
i
∑
i
=
1
t
r
t
i
.It is worthwhile to mention that the proposed technique is not specific to a certain workload-energy model. While we adopt linear model for the workload-energy relation for ease of presentation, any, possibly nonlinear, model can be used in (6).


## 3.1.1. Dynamic Voltage-Frequency Scaling

In this paper, we assume that a system has multiple operation modes due to DVFS feature, where the operating frequency and voltage can be modulated. For simplicity, we first assume that there are infinitely many operation modes available, among which one is chosen at each iteration. It will be shown that the proposed technique can be applied to a discrete DVFS as well in Section5. The operation mode at the ith iteration is represented with the speed scaling factor k
i ranging from k
m
i
n to k
m
a
x
=
1 (k
m
i
n
≤
k
≤
k
m
a
x
=
1). Then, the operating frequency of the ith iteration, f
i, is(1)
f
i
=
k
i
·
f
m
a
x
,where f
m
a
x is the maximum frequency of the microprocessor.


## 3.1.2. Workload

The workload is defined to be a number of clock cycles elapsed to complete the given computation. We denote the number of cycles elapsed to handle the workload of theith iteration at the full speed of the microprocessor (k
i
=
1) as t
r
e
f
,
i. That is,(2)
w
i
=
t
ref
,
i
=
k
i
·
t
i
.Note that the elapsed time t
i increases as the speed is scaled down (k
i
<
1). Then, the delay t
i is automatically determined when a speed scaling factor k
i is chosen for the given workload (t
i
=
w
i
/
k
i).


## 3.1.3. Real-Time Constraint

The delayt
i cannot be unboundedly long as the system is associated with real-time constraint T. For all iterations, the elapsed time should be no more than T: (3)
t
i
≤
T
,
∀
i
.


## 3.1.4. Delay-Workload Dependency

As stated earlier, the workload is dependent upon the previous execution delay. Usually, the workload is not a continuous function of the delay variation. Rather, the changes happen in a discrete manner. Therefore, the workload at theith iteration is a monotonically increasing staircase function of the delay of the previous iteration, t
i
-
1: w
i
=
W
(
t
i
-
1
). If the given system has n workload levels, the workload function W can be formulated as follows: (4)
W
t
=
wl
1
if
0
<
t
≤
th
1
wl
2
if
th
1
<
t
≤
th
2
⋮
wl
n
-
1
if
th
n
-
2
<
t
≤
th
n
-
1
wl
n
if
th
n
-
1
<
t
,in which the workload levels are wl
1
<
wl
2
<
⋯
<
wl
n and the delay thresholds (workload changing moments) are th
1
<
th
2
<
⋯
<
th
n
-
1.


## 3.1.5. Execution Trace

At theith iteration, the speed scaling factor k
i uniquely defines an executionmode as the delay is fixed accordingly by (2). The initial workload is assumed to be given as w
1. Then, an execution trace t
r of length L is defined to be a sequence of the speed scaling factors of L iterations:(5)
t
r
≔
k
1
,
k
2
,
…
,
k
L
.


## 3.1.6. Average Power Consumption

The dynamic power consumption of CMOS circuits isc
v
d
d
2
f, where c, v
d
d, and f are capacitance, operating voltage, and frequency, respectively. As the operating frequency is proportional to (
v
d
d
-
v
th
)
2
/
v
d
d [10], the power consumption is an increasing function of f. It is worth noting that the proposed model is not dependent upon any specific DVFS model. We denote the energy consumption of a unit workload at the full speed (k
=
1) as C
e and assume that energy dissipation grows linearly to the size of workload. Then, the reference energy of a workload w
i at the full speed is C
e
·
w
i. Given a DVFS energy model S as a function of the speed scaling factor k, the energy consumption at the ith iteration EG
i is formulated as follows:(6)
EG
i
=
C
e
·
w
i
·
S
k
i
,in which S
(
0
)
=
0 and S
(
1
)
=
1. Then, the average power consumption of a trace t
r can be formulated as follows:(7)
AVG
t
r
=
∑
i
=
1
t
r
EG
i
∑
i
=
1
t
r
t
i
.It is worthwhile to mention that the proposed technique is not specific to a certain workload-energy model. While we adopt linear model for the workload-energy relation for ease of presentation, any, possibly nonlinear, model can be used in (6).


## 3.2. Problem Formulation

Our objective is to minimize the average power consumption of a given system as follows:Given the modeling constantC
e, DVFS energy modeling function S, workload function W, and the real-time constraint T, determine an execution trace t
r such that the average power consumption formulated in (7) is minimized.


## 4. Proposed Technique

In this section, we describe the proposed operation management policy as an answer to the problem defined in the previous section. In doing so, we first derive the condition for feasible and schedulable systems. Then, we study when the workload changes and how it affects the power dissipation. Based on that, we propose a novel graph representation that captures all possible workload transitions in the power-optimal operation. Finally, we derive the power-optimal operation policy with the given workload functionW.


### 4.1. Feasibility

In this subsection, we examine under which condition a given system is feasible. First, the system should be schedulable within the given real-time constraintT at every iteration.Theorem 1 (schedulability).
Given the workload functionW and the real-time constraint T, the system isnot schedulable if W
(
t
)
/
t
>
1, ∀
t
∈
(
0
,
T
].Proof.
Suppose that the delay at theith iteration is t
i. Then, w
i
+
1
=
W
(
t
i
)
>
t
i and w
i
+
1
=
k
i
+
1
·
t
i
+
1. Since k
i
+
1
≤
1, t
i
<
t
i
+
1. That is, the delay is increasing as iteration goes by and will eventually reache the real-time constraint: t
j
=
T. At the next iteration, the system becomes unschedulable even with the full speed, as W
(
t
j
=
T
)
=
1
·
t
j
+
1
>
T requires t
j
+
1
>
T.Once the workload gets bigger thanT, the system is trivially not schedulable afterwards even with the full speed, k
i
=
1. Thus, the workload must not be bigger than T at any time. Moreover, once the workload reaches T, k should remain the full speed k
=
1 afterwards. We can make the upper bound of workload even tighter if there exists t
′ such that W
(
t
)
>
t for all t
∈
(
t
′
,
T
]. In this case, the workload larger than W
(
t
′
) is not allowable as it makes the execution delay longer and longer, eventually violating the deadline.Given the workload functionW and the initial workload w
1, one can calculate the lower bound of the workload as well. If a value t
~ exists which satisfies W
(
t
~
)
=
t
~ and W
(
t
~
)
<
w
1, the workload will never become smaller than W
(
t
~
). In other words, even with the full speed, the execution delay never goes below t
~.Then, the valid workload levels and the execution delay range during the lifetime of a given system can be formulated as below.Definition 2 (valid ranges).
Given the workload functionW and the initial workload w
1, the minimum and maximum workload levels of a system are defined to be(8)
wl
m
i
n
=
W
max
⁡
t
~
s.t.
t
~
=
W
t
~
<
w
1
if
∃
t
~
wl
1
otherwise
,
(9)
wl
m
a
x
=
W
min
⁡
t
′
s.t.
W
t
>
t
,
∀
t
∈
t
′
,
T
if
∃
t
′
W
T
otherwise
.Then, the valid range of the execution delay is formulated as [
t
m
i
n
,
t
m
a
x
] according to wl
m
i
n and wl
m
a
x with(10)
t
m
i
n
=
min
⁡
t
~
s.t.
W
t
~
=
wl
m
i
n
,
t
m
a
x
=
min
⁡
T
,
max
⁡
t
′
s.t.
W
t
′
=
wl
m
a
x
.


### 4.2. Workload Transitions

In this subsection, we examine when a workload transition between valid workload levels possibly occurs and how it affects the system.As presented in (4), workload is a function of the delay taken at the previous iteration. If the delay taken at an iteration is t and th
l
-
1
<
t
≤
th
l. Then, if the system works fast enough to result in a shorter delay, t
′
≤
th
l
-
1, the next workload will get smaller than wl
l. Similarly, in case that the delay gets longer (t
′
>
th
l), the system will need to handle a larger workload than wl
k at the successive iteration.However, such workload transitions can occur only within limited ranges. Figure1 depicts valid and invalid transitions from one workload level. Figure 1(a) shows two transitions from a workload level wl
p to lower ones wl
q and wl
r (r
<
q
<
p). To make the next workload level wl
q, the delay should be in the range of (
th
q
-
1
,
th
q
]. Given the current workload wl
p, the speed scaling factor should be larger than or equal to wl
p
/
th
q from (2). If wl
p
/
th
q
≤
k
m
a
x
=
1, this workload transition can possibly occur. In contrast, if wl
p
/
th
r
>
1 for another workload level wl
r, the transition from wl
p to wl
r never happens because the delay never goes below th
r even with the full processing speed.Figure 1
Examples of workload transitions: (a) transitions to lower workload levels and (b) transitions to higher workload levels. The transitions fromwl
p to wl
q are valid, while the ones from wl
p to wl
r are not.
(a)
(b)The same principle is also applied to the transition from a workload level to higher ones. If the delay can be lengthened properly with a speed scaling factor within the range[
k
m
i
n
,
k
m
a
x
], the transitions are valid. Figure 1(b) illustrates that the transition from wl
p to wl
q is valid, while the one to wl
r is not. One can tell if a transition can happen or not with the following definition.Definition 3 (valid transition).
A workload transition fromw
l
o to w
l
n is said to bevalid if w
l
o
/
t
h
n
≤
k
m
a
x
=
1 and w
l
o
/
t
h
n
-
1
≥
k
m
i
n.


### 4.3. Workload Transition Graph

The essential difficulty of the presented power optimization problem lies in the fact that two conflicting forces should be handled at the same time. In order to minimize the power, on one hand, it tries to scale down the speed (thus lengthen the delay) as much as possible as described in (2) and (6). On the other hand, the lengthened delay is not desirable as it imposes a bigger workload in the successive iteration, as shown in (4).Therefore, no one simple intuition can be exploited to solve the problem. Rather, we need to compare different modes in a comprehensive way. In order to be able to explore all possible execution modes and quantify their effects, we need to devise a data structure that includes elementary information on how workload transitions change the system status and power dissipation. In line with that purpose, we propose a graph representation of the workload evolution, Workload Transition Graph (WTG), which captures all possible transition scenarios of the workload changes during the lifetime of a system.A valid workload transition from one workload level to another can be caused by any delay within the corresponding range. A transition fromw
l
p to w
l
q in Figure 1(a), for instance, can be caused by any delay within the range of (
t
h
q
-
1
,
t
h
q
]. In other words, when handling a workload of w
l
p, any scaling factor within the range of [
w
l
p
/
t
h
q
,
w
l
p
/
t
h
q
-
1
) can cause the transition. In the power-optimal execution trace, however, only one specific scaling factor is always chosen for a certain transition even though it happens many times. We show this in the next theorem.Theorem 4 (optimal scaling factor).
In the power-optimal tracet
r
=
(
k
1
,
k
2
,
…
,
k
t
r
), if the workload level handled by k
i is w
l
o and the next workload level is w
l
n,(11)
k
i
=
min
⁡
w
l
o
t
h
n
,
k
m
i
n
.Proof.
We prove this by contradiction. Let us suppose that there exists a power-optimal tracet
r where k
i (which results in the transition from w
l
o to w
l
n) is not equal to min
⁡
(
w
l
o
/
t
h
n
,
k
m
i
n
). Then, we make a new execution trace t
r
′ from t
r by replacing k
i with k
i
′
=
min
⁡
(
w
l
o
/
t
h
n
,
k
m
i
n
). Note that all other execution modes in t
r
′ are the same as in t
r. That is,(12)
tr
⁡
j
=
tr
′
⁡
j
,
∀
j
≠
i
.By the definition of the scaling factor,(13)
k
i
≥
k
m
i
n
,
k
i
≥
w
l
o
t
h
n
,since the transition is from w
l
o to w
l
n. Thus,(14)
tr
⁡
i
=
k
i
>
tr
′
⁡
i
=
k
i
′and accordingly we obtain(15)
S
k
i
>
S
k
i
′
.Then, from (6) and (7), the average power in t
r
′ is lower than that of t
r and this contradicts the proposition.From Theorem4, we know that only one speed scaling factor is associated with all transitions of a certain type in the power-optimal operation scenario. So, we define a scaling factor of a valid transition as follows.Definition 5 (scaling factor of a transition).
The scaling factor of a valid workload transition fromw
l
o to w
l
n is(16)
s
f
w
l
o
,
w
l
n
=
max
⁡
w
l
o
min
⁡
t
h
n
,
T
,
k
m
i
n
.Now, we define WTG.Definition 6 (Workload Transition Graph).
WTG is defined to be a graph(
V
,
E
), where V and E are the sets of vertices and edges, respectively. Each valid workload level forms a vertex(17)
V
=
v
i
=
w
l
i
∣
w
l
min
⁡
≤
w
l
i
≤
w
l
m
a
x
,while a valid transition from a workload level to another forms an edge between vertices. That is, there exists an edge from v
i to v
j corresponding to a valid transition from w
l
i to w
l
j:(18)
E
=
v
i
,
v
j
∣
∃
valid  transition  from
w
l
i
to
w
l
j
.We denote the source and destination vertices of an edge e
∈
E as src
(
e
) and dst
(
e
), respectively.With these definitions, a power-optimal execution tracet
r
=
(
k
1
,
k
2
,
…
,
k
t
r
) can be represented as a walk (a sequence of vertices where any pair of consecutive vertices are connected through an edge) of length t
r
+
1 in WTG. In a different form, the execution trace is a sequence of edges in WTG of length t
r
(
e
1
,
e
2
,
…
,
e
t
r
), where the workload transition from src
⁡
e
i to dst
⁡
e
i is caused by the execution mode sf
⁡
(
src
⁡
e
i
,
dst
⁡
e
i
)
=
k
i.Algorithm1 shows how WTG is generated out of the given workload function W and the initial workload w
1. After the initialization, all valid workload levels are added as vertices in lines  (
5
)
-
(
6
). Then, for each permutation of two workload levels (lines (
7
)
-
(
8
)), it is checked if the in-between transition is valid or not in line (
9
). If valid, it is added as an edge in line (
10
).Algorithm 1:Generation of WTG.
(1)procedure
G
e
n
e
r
a
t
e
W
T
G
(
W
,
w
1
)
(2)w
l
m
i
n
← equation (8);      ⊳ Initializations
(3)w
l
m
a
x
← equation (9);
(4)V
←
ϕ, E
←
ϕ;
(5)for all
w
l
m
i
n
≤
w
l
≤
w
l
m
a
x
do     ⊳ Vertices
(6)V
←
V
∪
w
l;
(7)for all
w
l
m
i
n
≤
w
l
1
≤
w
l
m
a
x
do     ⊳ Edges
(8)for all
w
l
m
i
n
≤
w
l
2
≤
w
l
m
a
x
do
(9)if
∃ valid transition from w
l
1 to w
l
2
then
(10)E
←
E
∪
w
l
1
,
w
l
2Let us take Figure2 as an example of workload function W. Once given the initial workload, one can easily get the valid workload levels according to (8) and (9). When w
1
=
wl
2, for instance, w
l
m
i
n
=
w
l
2 and w
l
m
a
x
=
w
l
6. Figure 3(b) illustrates the corresponding WTG of the workload function shown in Figure 2 with the initial workload of w
l
2. It is not a complete graph as some pairs of vertices cannot be connected directly since it is notvalid according to Definition 3.Figure 2
A workload staircase function example with six workload levels.Figure 3
The corresponding WTG of the workload functionW shown in Figure 2 with the initial workload of (a) w
l
1, (b) w
l
2 or w
l
3, and (c) w
l
4, w
l
5, or w
l
6.
(a)
(b)
(c)The feasible delay range to handle workloadw
l
4 is highlighted in Figure 2, justifying that vertex w
l
4 has three outgoing edges to w
l
6, w
l
5, and itself. To be more specific, when the workload is given as w
l
4, the shortest possible delay is the case when the speed is chosen as k
m
a
x. Then, the delay (x coordinate of the cross point of y
=
w
l
4 and y
=
k
m
a
x
t) is between t
h
3 and t
h
4 as shown in Figure 2. This means that the lowest possible workload in the next iteration is w
l
4. Similarly, the biggest possible workload can also be calculated as w
l
6 as the biggest possible delay is between t
h
5 and T. Note also that some of the vertices may not have an edge directed to itself (self-loop) such as vertex w
l
3. It has outgoing edges only to higher workload levels. This means that the computation burden of that state is so big that it only results in higher workload levels at the next iteration even with the full speed.Different initial workload levels may result in different WTGs as shown in Figures3(a)–3(c). The WTG derived from the initial workload level of w
l
1 is illustrated in Figure 3(a). In contrast to Figure 3(b), vertex w
l
1 is included in the graph. The WTG derived from higher initial workload levels, w
l
4, w
l
5, and w
l
6, is shown in Figure 3(c). Note that the WTGs in Figures 3(a) and 3(c) are notstrongly connected. Vertex w
l
2 in Figure 3(b), for example, is not reachable from w
l
4. However, from the definition of valid workload levels, all vertices are reachable from the initial workload level. This property is important for deriving the optimal operation policy that will be presented in the next subsection.


### 4.4. Proposed Operation Policy

In this subsection, we present the proposed operation policy that compromises the energy-delay tradeoff caused by the delay-workload dependency.As stated earlier, a power-optimal execution tracet
r can be represented as a walk of WTG. Then, we have the following definition.Definition 7 (corresponding walk).
Given the power-optimal execution tracet
r
=
(
k
1
,
k
2
,
…
,
k
t
r
) and its initial workload w
1, the corresponding walk of the trace is denoted as (19)
cw
t
r
,
w
1
=
e
1
,
e
2
,
…
,
e
t
r
,where src
⁡
(
e
1
)
=
w
1 and sf
⁡
(
src
⁡
(
e
i
)
,
dst
⁡
(
e
i
)
)
=
k
i (for simplicity, we also denote it as sf
⁡
(
e
i
)
=
sf
⁡
(
src
⁡
(
e
i
)
,
dst
⁡
(
e
i
)
)
=
k
i for the rest of the paper). The average power consumption of the walk can be formulated as follows:(20)
A
V
G
cw
t
r
,
w
1
=
EG
cw
t
r
,
w
1
DL
cw
t
r
,
w
1
,where DL
(
(
e
1
,
e
2
,
…
,
e
n
)
) is the total delay elapsed for traversing the walk, ∑
i
=
1
n
(
src
⁡
(
e
i
)
/
sf
⁡
(
e
i
)
), and EG
(
(
e
1
,
e
2
,
…
,
e
n
)
) is the total energy consumption for the walk, C
e
∑
i
=
1
n
src
⁡
(
e
i
)
S
(
sf
⁡
(
e
i
)
).A cycle (closed walk) of WTG is a walk whose starting and ending vertices are the same. That is, a walk(
e
1
,
e
2
,
…
,
e
n
) is a cycle if src
(
e
1
)
=
dst
(
e
n
). Hence, if the corresponding walk of a trace in WTG is a cycle, the trace is ever repeatable. We argue that, in case that the length of the trace is sufficiently long (t
r
→
∞), the average power consumption is minimized when the cycle which minimizes (20) repeats over and over again in the trace.Theorem 8 (optimal cycle of WTG).
Suppose that a cycle of WTG,(21)
c
y
o
p
t
=
e
1
,
e
2
,
…
,
e
n
,has the minimum value of (20) among all cycles of the WTG. Then, if the length of the trace is long enough, the average power consumption of the optimal trace converges to(22)
A
V
G
c
y
o
p
t
=
E
G
c
y
o
p
t
D
L
c
y
o
p
t
.Proof.
An arbitrary walk of a WTG,(
e
1
,
e
2
,
…
,
e
n
), can be decomposed into a path (a walk with distinct vertices) from src
(
e
1
) to dst
(
e
n
) and a set of cycles (see, e.g., Section  10.3 of [17]). Figure 4 depicts a walk example of length 8, where the initial workload level is w
l
2 and the last vertex that it traverses is w
l
6. If a path from w
l
2 to w
l
6, (
e
1
,
e
2
,
e
5
), highlighted in the dashed arrows, is removed from the walk, the remaining part is a set of cycles.
Now, consider a power-optimal tracet
r of length N that starts from the workload level of w
1. The corresponding walk of t
r can be decomposed into a path p
t starting at w
1 and a set of cycles C
Y. Then, the average power consumption of the trace t
r is (23)
AVG
t
r
=
EG
pt
+
∑
cy
∈
CY
EG
cy
DL
pt
+
∑
cy
∈
CY
DL
cy
.Since pt contains at most V
-
1 edges by definition, EG
(
pt
) and DL
(
pt
) can be upper bounded by a certain value. Then, if N is sufficiently large, EG
(
pt
)
≪
∑
c
y
∈
CY
EG
(
c
y
) and DL
(
pt
)
≪
∑
c
y
∈
CY
DL
(
c
y
). That is, if t
r
→
∞,(24)
AVG
t
r
≃
∑
cy
∈
CY
EG
cy
∑
cy
∈
CY
DL
cy
.Note also that the average power consumption of every cycle in CY is not smaller than EG
(
cy
opt
)
/
t
(
cy
opt
) by definition:(25)
EG
cy
DL
cy
≥
AVG
cy
opt
=
EG
cy
opt
D
L
cy
opt
,
∀
cy
∈
CY
.Therefore, the average power consumption of the power-optimal trace t
r, AVG
(
t
r
), will get infinitesimally close to AVG
(
cy
opt
).Figure 4
A walk example of the WTG shown in Figure3(b) of length 8.From Theorem8, it is understood that changing the DVFS mode of the given system following the optimal cycle presented above results in asymptotically optimal average power consumption. Thus, we propose following rules for DVFS operation policy:(i)
If the current workload level vertex is in the optimal cyclecy
opt, just follow the cycle repeatedly ever; that is, at the ith iteration, the speed scaling factor is chosen to be sf
(
e
) such that e is in the optimal cycle and src
(
e
)
=
w
i.
(ii)
Otherwise, take a pathpt
opt
=
(
e
1
,
e
2
,
…
,
e
n
) that has the minimum AVG
(
pt
opt
) value and dst
(
e
n
) is in the optimal cycle cy
opt. In other words, try to get in the optimal cycle with the minimum cost.The optimal cycle cy
opt of WTG can be searched by using an existing cycle enumeration algorithm. In this paper, we use the one proposed by Tarjan [18]. The minimum path to the optimal cycle, pt
opt, can also be searched by simple enumeration. It is worthwhile to mention that we cannot simply use the minimum weight cycle searching algorithm as the weight is not simply a summation of the weights but a complex function of them as presented in (20).Figure5 shows the proposed operation policy in a flowchart diagram. Given the initial workload and the workload function, we generate WTG, from which cy
opt and pt
opt are derived in the next steps. It is worth mentioning that this can be done in a tractable time and is just one-time effort taken offline. As long as the initial workload vertex is not included in cy
opt, the system follows the trace represented in pt
opt until it reaches the optimal cycle of WTG. Then, it simply repeats the trace implied in cy
opt from that iteration on.Figure 5
Flowchart diagram of the proposed operation policy.


## 4.1. Feasibility

In this subsection, we examine under which condition a given system is feasible. First, the system should be schedulable within the given real-time constraintT at every iteration.Theorem 1 (schedulability).
Given the workload functionW and the real-time constraint T, the system isnot schedulable if W
(
t
)
/
t
>
1, ∀
t
∈
(
0
,
T
].Proof.
Suppose that the delay at theith iteration is t
i. Then, w
i
+
1
=
W
(
t
i
)
>
t
i and w
i
+
1
=
k
i
+
1
·
t
i
+
1. Since k
i
+
1
≤
1, t
i
<
t
i
+
1. That is, the delay is increasing as iteration goes by and will eventually reache the real-time constraint: t
j
=
T. At the next iteration, the system becomes unschedulable even with the full speed, as W
(
t
j
=
T
)
=
1
·
t
j
+
1
>
T requires t
j
+
1
>
T.Once the workload gets bigger thanT, the system is trivially not schedulable afterwards even with the full speed, k
i
=
1. Thus, the workload must not be bigger than T at any time. Moreover, once the workload reaches T, k should remain the full speed k
=
1 afterwards. We can make the upper bound of workload even tighter if there exists t
′ such that W
(
t
)
>
t for all t
∈
(
t
′
,
T
]. In this case, the workload larger than W
(
t
′
) is not allowable as it makes the execution delay longer and longer, eventually violating the deadline.Given the workload functionW and the initial workload w
1, one can calculate the lower bound of the workload as well. If a value t
~ exists which satisfies W
(
t
~
)
=
t
~ and W
(
t
~
)
<
w
1, the workload will never become smaller than W
(
t
~
). In other words, even with the full speed, the execution delay never goes below t
~.Then, the valid workload levels and the execution delay range during the lifetime of a given system can be formulated as below.Definition 2 (valid ranges).
Given the workload functionW and the initial workload w
1, the minimum and maximum workload levels of a system are defined to be(8)
wl
m
i
n
=
W
max
⁡
t
~
s.t.
t
~
=
W
t
~
<
w
1
if
∃
t
~
wl
1
otherwise
,
(9)
wl
m
a
x
=
W
min
⁡
t
′
s.t.
W
t
>
t
,
∀
t
∈
t
′
,
T
if
∃
t
′
W
T
otherwise
.Then, the valid range of the execution delay is formulated as [
t
m
i
n
,
t
m
a
x
] according to wl
m
i
n and wl
m
a
x with(10)
t
m
i
n
=
min
⁡
t
~
s.t.
W
t
~
=
wl
m
i
n
,
t
m
a
x
=
min
⁡
T
,
max
⁡
t
′
s.t.
W
t
′
=
wl
m
a
x
.


## 4.2. Workload Transitions

In this subsection, we examine when a workload transition between valid workload levels possibly occurs and how it affects the system.As presented in (4), workload is a function of the delay taken at the previous iteration. If the delay taken at an iteration is t and th
l
-
1
<
t
≤
th
l. Then, if the system works fast enough to result in a shorter delay, t
′
≤
th
l
-
1, the next workload will get smaller than wl
l. Similarly, in case that the delay gets longer (t
′
>
th
l), the system will need to handle a larger workload than wl
k at the successive iteration.However, such workload transitions can occur only within limited ranges. Figure1 depicts valid and invalid transitions from one workload level. Figure 1(a) shows two transitions from a workload level wl
p to lower ones wl
q and wl
r (r
<
q
<
p). To make the next workload level wl
q, the delay should be in the range of (
th
q
-
1
,
th
q
]. Given the current workload wl
p, the speed scaling factor should be larger than or equal to wl
p
/
th
q from (2). If wl
p
/
th
q
≤
k
m
a
x
=
1, this workload transition can possibly occur. In contrast, if wl
p
/
th
r
>
1 for another workload level wl
r, the transition from wl
p to wl
r never happens because the delay never goes below th
r even with the full processing speed.Figure 1
Examples of workload transitions: (a) transitions to lower workload levels and (b) transitions to higher workload levels. The transitions fromwl
p to wl
q are valid, while the ones from wl
p to wl
r are not.
(a)
(b)The same principle is also applied to the transition from a workload level to higher ones. If the delay can be lengthened properly with a speed scaling factor within the range[
k
m
i
n
,
k
m
a
x
], the transitions are valid. Figure 1(b) illustrates that the transition from wl
p to wl
q is valid, while the one to wl
r is not. One can tell if a transition can happen or not with the following definition.Definition 3 (valid transition).
A workload transition fromw
l
o to w
l
n is said to bevalid if w
l
o
/
t
h
n
≤
k
m
a
x
=
1 and w
l
o
/
t
h
n
-
1
≥
k
m
i
n.


## 4.3. Workload Transition Graph

The essential difficulty of the presented power optimization problem lies in the fact that two conflicting forces should be handled at the same time. In order to minimize the power, on one hand, it tries to scale down the speed (thus lengthen the delay) as much as possible as described in (2) and (6). On the other hand, the lengthened delay is not desirable as it imposes a bigger workload in the successive iteration, as shown in (4).Therefore, no one simple intuition can be exploited to solve the problem. Rather, we need to compare different modes in a comprehensive way. In order to be able to explore all possible execution modes and quantify their effects, we need to devise a data structure that includes elementary information on how workload transitions change the system status and power dissipation. In line with that purpose, we propose a graph representation of the workload evolution, Workload Transition Graph (WTG), which captures all possible transition scenarios of the workload changes during the lifetime of a system.A valid workload transition from one workload level to another can be caused by any delay within the corresponding range. A transition fromw
l
p to w
l
q in Figure 1(a), for instance, can be caused by any delay within the range of (
t
h
q
-
1
,
t
h
q
]. In other words, when handling a workload of w
l
p, any scaling factor within the range of [
w
l
p
/
t
h
q
,
w
l
p
/
t
h
q
-
1
) can cause the transition. In the power-optimal execution trace, however, only one specific scaling factor is always chosen for a certain transition even though it happens many times. We show this in the next theorem.Theorem 4 (optimal scaling factor).
In the power-optimal tracet
r
=
(
k
1
,
k
2
,
…
,
k
t
r
), if the workload level handled by k
i is w
l
o and the next workload level is w
l
n,(11)
k
i
=
min
⁡
w
l
o
t
h
n
,
k
m
i
n
.Proof.
We prove this by contradiction. Let us suppose that there exists a power-optimal tracet
r where k
i (which results in the transition from w
l
o to w
l
n) is not equal to min
⁡
(
w
l
o
/
t
h
n
,
k
m
i
n
). Then, we make a new execution trace t
r
′ from t
r by replacing k
i with k
i
′
=
min
⁡
(
w
l
o
/
t
h
n
,
k
m
i
n
). Note that all other execution modes in t
r
′ are the same as in t
r. That is,(12)
tr
⁡
j
=
tr
′
⁡
j
,
∀
j
≠
i
.By the definition of the scaling factor,(13)
k
i
≥
k
m
i
n
,
k
i
≥
w
l
o
t
h
n
,since the transition is from w
l
o to w
l
n. Thus,(14)
tr
⁡
i
=
k
i
>
tr
′
⁡
i
=
k
i
′and accordingly we obtain(15)
S
k
i
>
S
k
i
′
.Then, from (6) and (7), the average power in t
r
′ is lower than that of t
r and this contradicts the proposition.From Theorem4, we know that only one speed scaling factor is associated with all transitions of a certain type in the power-optimal operation scenario. So, we define a scaling factor of a valid transition as follows.Definition 5 (scaling factor of a transition).
The scaling factor of a valid workload transition fromw
l
o to w
l
n is(16)
s
f
w
l
o
,
w
l
n
=
max
⁡
w
l
o
min
⁡
t
h
n
,
T
,
k
m
i
n
.Now, we define WTG.Definition 6 (Workload Transition Graph).
WTG is defined to be a graph(
V
,
E
), where V and E are the sets of vertices and edges, respectively. Each valid workload level forms a vertex(17)
V
=
v
i
=
w
l
i
∣
w
l
min
⁡
≤
w
l
i
≤
w
l
m
a
x
,while a valid transition from a workload level to another forms an edge between vertices. That is, there exists an edge from v
i to v
j corresponding to a valid transition from w
l
i to w
l
j:(18)
E
=
v
i
,
v
j
∣
∃
valid  transition  from
w
l
i
to
w
l
j
.We denote the source and destination vertices of an edge e
∈
E as src
(
e
) and dst
(
e
), respectively.With these definitions, a power-optimal execution tracet
r
=
(
k
1
,
k
2
,
…
,
k
t
r
) can be represented as a walk (a sequence of vertices where any pair of consecutive vertices are connected through an edge) of length t
r
+
1 in WTG. In a different form, the execution trace is a sequence of edges in WTG of length t
r
(
e
1
,
e
2
,
…
,
e
t
r
), where the workload transition from src
⁡
e
i to dst
⁡
e
i is caused by the execution mode sf
⁡
(
src
⁡
e
i
,
dst
⁡
e
i
)
=
k
i.Algorithm1 shows how WTG is generated out of the given workload function W and the initial workload w
1. After the initialization, all valid workload levels are added as vertices in lines  (
5
)
-
(
6
). Then, for each permutation of two workload levels (lines (
7
)
-
(
8
)), it is checked if the in-between transition is valid or not in line (
9
). If valid, it is added as an edge in line (
10
).Algorithm 1:Generation of WTG.
(1)procedure
G
e
n
e
r
a
t
e
W
T
G
(
W
,
w
1
)
(2)w
l
m
i
n
← equation (8);      ⊳ Initializations
(3)w
l
m
a
x
← equation (9);
(4)V
←
ϕ, E
←
ϕ;
(5)for all
w
l
m
i
n
≤
w
l
≤
w
l
m
a
x
do     ⊳ Vertices
(6)V
←
V
∪
w
l;
(7)for all
w
l
m
i
n
≤
w
l
1
≤
w
l
m
a
x
do     ⊳ Edges
(8)for all
w
l
m
i
n
≤
w
l
2
≤
w
l
m
a
x
do
(9)if
∃ valid transition from w
l
1 to w
l
2
then
(10)E
←
E
∪
w
l
1
,
w
l
2Let us take Figure2 as an example of workload function W. Once given the initial workload, one can easily get the valid workload levels according to (8) and (9). When w
1
=
wl
2, for instance, w
l
m
i
n
=
w
l
2 and w
l
m
a
x
=
w
l
6. Figure 3(b) illustrates the corresponding WTG of the workload function shown in Figure 2 with the initial workload of w
l
2. It is not a complete graph as some pairs of vertices cannot be connected directly since it is notvalid according to Definition 3.Figure 2
A workload staircase function example with six workload levels.Figure 3
The corresponding WTG of the workload functionW shown in Figure 2 with the initial workload of (a) w
l
1, (b) w
l
2 or w
l
3, and (c) w
l
4, w
l
5, or w
l
6.
(a)
(b)
(c)The feasible delay range to handle workloadw
l
4 is highlighted in Figure 2, justifying that vertex w
l
4 has three outgoing edges to w
l
6, w
l
5, and itself. To be more specific, when the workload is given as w
l
4, the shortest possible delay is the case when the speed is chosen as k
m
a
x. Then, the delay (x coordinate of the cross point of y
=
w
l
4 and y
=
k
m
a
x
t) is between t
h
3 and t
h
4 as shown in Figure 2. This means that the lowest possible workload in the next iteration is w
l
4. Similarly, the biggest possible workload can also be calculated as w
l
6 as the biggest possible delay is between t
h
5 and T. Note also that some of the vertices may not have an edge directed to itself (self-loop) such as vertex w
l
3. It has outgoing edges only to higher workload levels. This means that the computation burden of that state is so big that it only results in higher workload levels at the next iteration even with the full speed.Different initial workload levels may result in different WTGs as shown in Figures3(a)–3(c). The WTG derived from the initial workload level of w
l
1 is illustrated in Figure 3(a). In contrast to Figure 3(b), vertex w
l
1 is included in the graph. The WTG derived from higher initial workload levels, w
l
4, w
l
5, and w
l
6, is shown in Figure 3(c). Note that the WTGs in Figures 3(a) and 3(c) are notstrongly connected. Vertex w
l
2 in Figure 3(b), for example, is not reachable from w
l
4. However, from the definition of valid workload levels, all vertices are reachable from the initial workload level. This property is important for deriving the optimal operation policy that will be presented in the next subsection.


## 4.4. Proposed Operation Policy

In this subsection, we present the proposed operation policy that compromises the energy-delay tradeoff caused by the delay-workload dependency.As stated earlier, a power-optimal execution tracet
r can be represented as a walk of WTG. Then, we have the following definition.Definition 7 (corresponding walk).
Given the power-optimal execution tracet
r
=
(
k
1
,
k
2
,
…
,
k
t
r
) and its initial workload w
1, the corresponding walk of the trace is denoted as (19)
cw
t
r
,
w
1
=
e
1
,
e
2
,
…
,
e
t
r
,where src
⁡
(
e
1
)
=
w
1 and sf
⁡
(
src
⁡
(
e
i
)
,
dst
⁡
(
e
i
)
)
=
k
i (for simplicity, we also denote it as sf
⁡
(
e
i
)
=
sf
⁡
(
src
⁡
(
e
i
)
,
dst
⁡
(
e
i
)
)
=
k
i for the rest of the paper). The average power consumption of the walk can be formulated as follows:(20)
A
V
G
cw
t
r
,
w
1
=
EG
cw
t
r
,
w
1
DL
cw
t
r
,
w
1
,where DL
(
(
e
1
,
e
2
,
…
,
e
n
)
) is the total delay elapsed for traversing the walk, ∑
i
=
1
n
(
src
⁡
(
e
i
)
/
sf
⁡
(
e
i
)
), and EG
(
(
e
1
,
e
2
,
…
,
e
n
)
) is the total energy consumption for the walk, C
e
∑
i
=
1
n
src
⁡
(
e
i
)
S
(
sf
⁡
(
e
i
)
).A cycle (closed walk) of WTG is a walk whose starting and ending vertices are the same. That is, a walk(
e
1
,
e
2
,
…
,
e
n
) is a cycle if src
(
e
1
)
=
dst
(
e
n
). Hence, if the corresponding walk of a trace in WTG is a cycle, the trace is ever repeatable. We argue that, in case that the length of the trace is sufficiently long (t
r
→
∞), the average power consumption is minimized when the cycle which minimizes (20) repeats over and over again in the trace.Theorem 8 (optimal cycle of WTG).
Suppose that a cycle of WTG,(21)
c
y
o
p
t
=
e
1
,
e
2
,
…
,
e
n
,has the minimum value of (20) among all cycles of the WTG. Then, if the length of the trace is long enough, the average power consumption of the optimal trace converges to(22)
A
V
G
c
y
o
p
t
=
E
G
c
y
o
p
t
D
L
c
y
o
p
t
.Proof.
An arbitrary walk of a WTG,(
e
1
,
e
2
,
…
,
e
n
), can be decomposed into a path (a walk with distinct vertices) from src
(
e
1
) to dst
(
e
n
) and a set of cycles (see, e.g., Section  10.3 of [17]). Figure 4 depicts a walk example of length 8, where the initial workload level is w
l
2 and the last vertex that it traverses is w
l
6. If a path from w
l
2 to w
l
6, (
e
1
,
e
2
,
e
5
), highlighted in the dashed arrows, is removed from the walk, the remaining part is a set of cycles.
Now, consider a power-optimal tracet
r of length N that starts from the workload level of w
1. The corresponding walk of t
r can be decomposed into a path p
t starting at w
1 and a set of cycles C
Y. Then, the average power consumption of the trace t
r is (23)
AVG
t
r
=
EG
pt
+
∑
cy
∈
CY
EG
cy
DL
pt
+
∑
cy
∈
CY
DL
cy
.Since pt contains at most V
-
1 edges by definition, EG
(
pt
) and DL
(
pt
) can be upper bounded by a certain value. Then, if N is sufficiently large, EG
(
pt
)
≪
∑
c
y
∈
CY
EG
(
c
y
) and DL
(
pt
)
≪
∑
c
y
∈
CY
DL
(
c
y
). That is, if t
r
→
∞,(24)
AVG
t
r
≃
∑
cy
∈
CY
EG
cy
∑
cy
∈
CY
DL
cy
.Note also that the average power consumption of every cycle in CY is not smaller than EG
(
cy
opt
)
/
t
(
cy
opt
) by definition:(25)
EG
cy
DL
cy
≥
AVG
cy
opt
=
EG
cy
opt
D
L
cy
opt
,
∀
cy
∈
CY
.Therefore, the average power consumption of the power-optimal trace t
r, AVG
(
t
r
), will get infinitesimally close to AVG
(
cy
opt
).Figure 4
A walk example of the WTG shown in Figure3(b) of length 8.From Theorem8, it is understood that changing the DVFS mode of the given system following the optimal cycle presented above results in asymptotically optimal average power consumption. Thus, we propose following rules for DVFS operation policy:(i)
If the current workload level vertex is in the optimal cyclecy
opt, just follow the cycle repeatedly ever; that is, at the ith iteration, the speed scaling factor is chosen to be sf
(
e
) such that e is in the optimal cycle and src
(
e
)
=
w
i.
(ii)
Otherwise, take a pathpt
opt
=
(
e
1
,
e
2
,
…
,
e
n
) that has the minimum AVG
(
pt
opt
) value and dst
(
e
n
) is in the optimal cycle cy
opt. In other words, try to get in the optimal cycle with the minimum cost.The optimal cycle cy
opt of WTG can be searched by using an existing cycle enumeration algorithm. In this paper, we use the one proposed by Tarjan [18]. The minimum path to the optimal cycle, pt
opt, can also be searched by simple enumeration. It is worthwhile to mention that we cannot simply use the minimum weight cycle searching algorithm as the weight is not simply a summation of the weights but a complex function of them as presented in (20).Figure5 shows the proposed operation policy in a flowchart diagram. Given the initial workload and the workload function, we generate WTG, from which cy
opt and pt
opt are derived in the next steps. It is worth mentioning that this can be done in a tractable time and is just one-time effort taken offline. As long as the initial workload vertex is not included in cy
opt, the system follows the trace represented in pt
opt until it reaches the optimal cycle of WTG. Then, it simply repeats the trace implied in cy
opt from that iteration on.Figure 5
Flowchart diagram of the proposed operation policy.


## 5. Extension to Discrete DVFS

Whilst we assume a continuous DVFS model for ease of presentation and generality, modern microprocessors in reality have finite DVFS modes with a set of predefined operation voltages and frequencies. In this section, we show that the continuity of the model presented in (1) can be relaxed by modifying Definitions 3 and 5 without harming the effectiveness of the proposed technique.Let us suppose that we now have a system with a discrete and finite DVFS model, where onlyk
i
∈
K can be chosen as a speed scaling factor at the ith iteration. Valid transitions, in Definition 3, are redefined: the transition is valid if there is k
∈
K that meets the same requirement.Definition 9 (valid transition in discrete DVFS).
Given a set of feasible scaling factorsK, a workload transition from w
l
o to w
l
n is said to bevalid if(26)
t
h
n
-
1
<
w
l
o
k
≤
min
⁡
t
h
n
,
T
,
∃
k
∈
K
.Likewise, the scaling factor of a valid transition, in Definition5, is also reformed to be minimum k
∈
K that keeps the elapsed delay fallen into the range which results in the same transition. One has the following definition.Definition 10 (scaling factor in discrete DVFS).
Given a set of feasible scaling factorsK, the scaling factor of a valid workload transition from w
l
o to w
l
n is(27)
sf
w
l
o
,
w
l
n
=
arg
⁡
min
k
∈
K
⁡
t
h
n
-
1
<
w
l
o
k
≤
min
⁡
t
h
n
,
T
.


## 6. Experiments

In this section, we validate the proposed model and operation policy with experimental analysis and simulations.


### 6.1. A Case Study: Object Tracking

It is firstly shown that the proposed workload-delay dependency is evidently observed in an object tracking application. The performance of a commonly used object tracking method [19] is profiled, as a tracking solution, using the publicly available implementation [20]. We choose Exynos5422 [21] as the target mobile embedded computing platform, which has 2 GB main memory running Linux operating system. The actual power dissipations of the processor are measured individually for five different DVFS modes. That is, K
=
0.2,0.4,0.6,0.8,1.0 and at the maximum speed the core is operating at 2 GHz. Leveraging on a priori knowledge on the maximum speed of the object, the maximum distance that the object could have moved between two iterations is calculated. In this experiment, it is assumed that the object’s speed never exceeds 10 pixels/ms. If an iteration takes t ms, for instance, the search area for the next iteration is given as a square with the side length of (
10
·
2
·
t
+
125
) pixels. This search area is growing in a discrete manner at every 5 ms. The real-time constraint T is set to 25 ms. The workload function in a shape of staircase is illustrated in Figure 6 with five guiding lines, each of which denotes k
·
t for k
∈
K.Figure 6
Workload-delay dependency functionW of Lucas-Kanade object tracking algorithm.We compare the proposed power management policy with two others. The first one is ALAP, where the speed is chosen to be the slowest one with respect to the real-time constraint. The other comparison is made against a stable trace with the maximum speed as another extreme (ASAP). When the initial workload isw
l
3, that is, w
1
=
w
l
3
=
9.833, ASAP and ALAP result in the average power consumption of 2.5032 W and 1.2623 W, respectively. The average power consumption of the proposed power management policy outperforms the others as 0.7592 W. The optimal cycle of its WTG is the self-loop of node w
l
2, which implies a stable operation mode, ∀
i
,
k
i
=
0.6.


### 6.2. Stable versus Alternating Operation Modes

There are two kinds of cycles in WTG: the first one is a self-loop which implies astable operation mode, where no mode changes happen over the edge. Other than these self-loops, the WTG has one non-self-loop cycle as well. From the perspective of the operation policy, this non-self-loop cycle implies a predefined sequence of mode changes that can repeat over and over again. We call thisalternating operation mode. Many examples including a real-life application shown in the previous subsection, as well as one presented in [11], tend to be optimal in a stable operation mode. However, in principle, the optimal solution cannot be achieved in a stable mode in some configurations. In order to illustrate this, we show a counter example shown in Figure 7 and apply the proposed technique to the example, with a DVFS power modeling function of S
(
k
)
=
5
·
k
3 and K
=
0.4,0.8,0.9. The delay threshold and the real-time constraint are t
h
1
=
0.2, t
h
2
=
0.6, t
h
3
=
0.7, and T
=
1.0, respectively. Figure 7(b) shows the derived WTG for the synthetic example.Figure 7
(a) A synthetic example,W
(
t
) with four workload levels, w
l
1
=
0.3, w
l
2
=
0.4, w
l
3
=
0.5, and w
l
4
=
0.6, and (b) its WTG representation, where the edges are annotated with scaling factors.
(a)
(b)The average power consumption of all self-loops in the synthetic example is tied to2.5600 W. On the other hand, an alternating operation mode implied in w
l
2
→
w
l
4
→
w
l
3
→
w
l
2 shows the least average power consumption in the discrete model. This is due to the fact that a computer system cannot simply operate on an ideal design point. In case that the theoretically optimal design point cannot be captured by a commodity hardware, the proposed technique is particularly useful. It can effectively explore design space and find out the best one in alternating modes.In principle, a stable operation mode is the case that the staircase workload functionW
(
t
) has a crossing point with k
·
t. If this k is sufficiently small, it is likely to be a near-optimal operation mode. However, it does not always result in a near-optimal power consumption. Particularly, in case that only a limited number of DVFS modes are available in a microprocessor, this k which crosses the current workload level may not exist in K.


## 6.1. A Case Study: Object Tracking

It is firstly shown that the proposed workload-delay dependency is evidently observed in an object tracking application. The performance of a commonly used object tracking method [19] is profiled, as a tracking solution, using the publicly available implementation [20]. We choose Exynos5422 [21] as the target mobile embedded computing platform, which has 2 GB main memory running Linux operating system. The actual power dissipations of the processor are measured individually for five different DVFS modes. That is, K
=
0.2,0.4,0.6,0.8,1.0 and at the maximum speed the core is operating at 2 GHz. Leveraging on a priori knowledge on the maximum speed of the object, the maximum distance that the object could have moved between two iterations is calculated. In this experiment, it is assumed that the object’s speed never exceeds 10 pixels/ms. If an iteration takes t ms, for instance, the search area for the next iteration is given as a square with the side length of (
10
·
2
·
t
+
125
) pixels. This search area is growing in a discrete manner at every 5 ms. The real-time constraint T is set to 25 ms. The workload function in a shape of staircase is illustrated in Figure 6 with five guiding lines, each of which denotes k
·
t for k
∈
K.Figure 6
Workload-delay dependency functionW of Lucas-Kanade object tracking algorithm.We compare the proposed power management policy with two others. The first one is ALAP, where the speed is chosen to be the slowest one with respect to the real-time constraint. The other comparison is made against a stable trace with the maximum speed as another extreme (ASAP). When the initial workload isw
l
3, that is, w
1
=
w
l
3
=
9.833, ASAP and ALAP result in the average power consumption of 2.5032 W and 1.2623 W, respectively. The average power consumption of the proposed power management policy outperforms the others as 0.7592 W. The optimal cycle of its WTG is the self-loop of node w
l
2, which implies a stable operation mode, ∀
i
,
k
i
=
0.6.


## 6.2. Stable versus Alternating Operation Modes

There are two kinds of cycles in WTG: the first one is a self-loop which implies astable operation mode, where no mode changes happen over the edge. Other than these self-loops, the WTG has one non-self-loop cycle as well. From the perspective of the operation policy, this non-self-loop cycle implies a predefined sequence of mode changes that can repeat over and over again. We call thisalternating operation mode. Many examples including a real-life application shown in the previous subsection, as well as one presented in [11], tend to be optimal in a stable operation mode. However, in principle, the optimal solution cannot be achieved in a stable mode in some configurations. In order to illustrate this, we show a counter example shown in Figure 7 and apply the proposed technique to the example, with a DVFS power modeling function of S
(
k
)
=
5
·
k
3 and K
=
0.4,0.8,0.9. The delay threshold and the real-time constraint are t
h
1
=
0.2, t
h
2
=
0.6, t
h
3
=
0.7, and T
=
1.0, respectively. Figure 7(b) shows the derived WTG for the synthetic example.Figure 7
(a) A synthetic example,W
(
t
) with four workload levels, w
l
1
=
0.3, w
l
2
=
0.4, w
l
3
=
0.5, and w
l
4
=
0.6, and (b) its WTG representation, where the edges are annotated with scaling factors.
(a)
(b)The average power consumption of all self-loops in the synthetic example is tied to2.5600 W. On the other hand, an alternating operation mode implied in w
l
2
→
w
l
4
→
w
l
3
→
w
l
2 shows the least average power consumption in the discrete model. This is due to the fact that a computer system cannot simply operate on an ideal design point. In case that the theoretically optimal design point cannot be captured by a commodity hardware, the proposed technique is particularly useful. It can effectively explore design space and find out the best one in alternating modes.In principle, a stable operation mode is the case that the staircase workload functionW
(
t
) has a crossing point with k
·
t. If this k is sufficiently small, it is likely to be a near-optimal operation mode. However, it does not always result in a near-optimal power consumption. Particularly, in case that only a limited number of DVFS modes are available in a microprocessor, this k which crosses the current workload level may not exist in K.


## 7. Conclusion

This paper formulates the delay-workload dependency in power optimization problem of embedded systems as a staircase function of the delay taken at the previous iteration. In applying it to the power optimization of DVFS-enabled electronic devices, a novel graph representation, called WTG, is proposed for exploring all possible workload/mode changes. Then, it is shown that the power optimization problem is equivalent to finding a cycle of the graph that has the minimum average power consumption. The effectiveness of the proposed operation policy is proven by the power simulations of synthetic and real-life examples. It has been observed that staying in a low speed scaling factor in a stable operation mode is often the best discipline (self-loop in WTG). However, alternating modes, where the DVFS modes change over a predefined pattern, sometimes outperform the stable ones.



---

*Source: 2010837-2016-08-04.xml*