# A Dynamic Programming Solution for Energy-Optimal Video Playback on Mobile Devices

Authors: Minseok Song; Jinhan Park
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Due to the development of mobile technology and wide availability of smartphones, the Internet of Things (IoT) starts to handle high volumes of video data to facilitate multimedia-based services, which requires energy-efficient video playback. In video playback, frames have to be decoded and rendered at high playback rate, increasing the computation cost on the CPU. To save the CPU power, dynamic voltage and frequency scaling (DVFS) dynamically adjusts the operating voltage of the processor along with frequency, in which appropriate selection of frequency on power could achieve a balance between performance and power. We present a decoding model that allows buffering frames to let the CPU run at low frequency and then propose an algorithm that determines the CPU frequency needed to decode each frame in a video, with the aim of minimizing power consumption while meeting buffer size and deadline constraints, using a dynamic programming technique. We finally extend this algorithm to optimize CPU frequencies over a short sequence of frames, producing a practical method of reducing the energy required for video decoding. Experimental results show a system-wide reduction in energy of27
%, compared with a processor running at full speed.


---

## Body

## 1. Introduction

The Internet of Things (IoT) allows physical objects to interact and cooperate with one another by exchanging data, and multimedia-related services based on the IoT are now gaining popularity in various applications areas [1]. For example, users of home security systems now see images from cameras on a smartphone, and telemedicine systems allow doctors to monitor a patient’s health using video communication.To support multimedia applications within the IoT, the characteristics of video need to be considered carefully. For example, the amount of data involved requires the use of compression techniques for codecs, but encoding and decoding processes are computationally intensive. Video transmission is a real-time process, which requires continuously periodic decoding to avoid distorted playback. Most importantly, mobile IoT devices have a limited energy budget, making the energy requirements of video transmission an important issue.An effective way of reducing CPU power consumption is to use a dynamic voltage and frequency scaling (DVFS) technique, which adjusts the operating voltage and frequency of the processor [2–4]. Because the energy dissipated by the CPU scales quadratically with the supply voltage, reducing the voltage saves a lot of energy but also slows program execution, so that an appropriate compromise is always required.In video playback, frames have to be decoded and rendered at playback rate to avoid a loss of quality. For example, to play a video at 25 frames per second, a frame must be decoded every 40 ms. This decoding process needs to finish within this period, but workload imposed by each frame varies significantly with video content [5–10].In most previous work on the application of DVFS to videos, the lowest frequency that satisfies the deadline of the decoding time is chosen to reduce power consumption [11], but more energy can be saved by introducing flexibility in timing, by means of buffering techniques: if several frames are decoded in advance, the CPU can operate at lower frequencies on average, but buffering comes with its own costs [12]. Therefore, power saving is only effective with an appropriate frequency selection method subject to buffer constraints, but previous work took no account of this issue.We propose a new scheme that determines the CPU frequency needed to decode each frame, which minimizes energy consumption while avoiding buffer overrun. We start by developing a video playback and energy model, formulate the energy optimization problem, and go on to use a dynamic programming technique to determine a sequence of frequencies. We finally present experimental results based on measurement of smartphone energy consumption and decoding times.The rest of this paper is organized as follows. We present related work in Section2 and the system model in Section 3. We formulate an optimization problem in Section 4, propose a new frequency selection algorithm in Section 5, and extend it in Section 6. We assess our scheme in Section 7 and finally conclude the paper in Section 8.


## 2. Related Work

CPU power management has been the subject of a lot of research, and most of the resulting techniques involve either dynamic power management (DPM) or DVFS. DPM puts an idle CPU into sleep mode [13], whereas DVFS reduces the voltage and frequency of an active CPU [2, 4]. DPM is not generally suitable for real-time applications that run continuously, because the idle intervals are too short to allow the CPU to enter sleep mode [8]. Therefore, we only review previous works about DVFS only in this section.DVFS techniques can be classified into interval-based and task-based algorithms [7, 14]. Interval-based schemes monitor the CPU load at intervals and respond by changing the CPU frequency and voltage. A representative scheme is the Linux Ondemand governor, which adjusts frequency periodically based on CPU utilization in the preceding interval [15]. Another scheme is LongRun [16] which varies the frequency to suit the measured utilization. These methods are typically easy to implement but can make inaccurate predictions based on the assumption that loads are similar to recent loads [14].Task-based schemes can overcome this problem to some extent by classifying tasks into several types to which different frequency selection policies are applied. Ayoub et al. [17] manage frequency and voltage to meet a performance target, expressed as a fraction of maximum system performance. Flautner and Mudge [18] propose a method that chooses a CPU frequency for each task based on its recent computational requirements. Seo et al. [14] present a frequency allocation method to reduce the average response time of tasks. However, all of these methods have been developed for general workloads and therefore may not be suitable for multimedia applications with real-time constraints.DVFS techniques for real-time systems are generally integrated with real-time scheduling [2–4]. Based on the analysis of worst-case execution times, they select CPU frequencies that satisfy the real-time constraints; but tasks are often complete before their worst-case execution times, so several algorithms incorporate methods of reclaiming the unused time [2, 4]. The CPU starts each period running at a frequency which will meet the worst-case demands and the frequency is then reduced in response to the actual computation requirement.Several groups have investigated DVFS techniques for video applications [6, 7], in which the key issue is to estimate the computational requirements of successive frames. Most of these techniques predict the workload required to decode a frame from the workloads incurred in decoding previous frames and adjust the CPU frequency. The accuracy of these schemes has been improved by feedback mechanisms, which take previous prediction errors into account [19].It has been widely observed [5–10] that frame decoding times vary significantly. For example, some of the frames in an MPEG video can take ten times as long to decode as an average frame [20]. That makes it difficult to estimate the computational requirements of successive frames to meet their deadlines [5–7]. Several workload estimation techniques have been proposed for video applications [5–7, 11, 19], and they can be categorized [5] into methods which make use of the relationship between the amount of data in a frame and decoding time and methods which predict decoding times based on recent times and aim to correct prediction errors using a feedback mechanism.A close relationship between frame size and decoding time has been widely observed [5, 6, 11], especially in videos encoded with MPEG-style compression, and this relationship allows decoding times to be predicted with reasonable confidence. For example, Liu et al. [6] established a linear relationship between frame size and decoding time and used it to predict decoding times, while Yang and Song [11] improved the accuracy of this approach by introducing a logarithmic relationship, and Bavier et al. [21] used it to predict decoding times. Lee et al. [5] introduced particle-filter techniques to further improve the accuracy of this approach for H.264 codecs.Yuan et al. [8–10] proposed several DVFS techniques in which the CPU speed is adjusted on the basis of a statistical analysis of past workloads. Urunuela et al. [7] developed a history-based DVFS technique, but it is tailored to video kiosks rather than general video players. Choi et al. [22] adopted a hybrid approach in which different DVFS policies are applied depending on the characteristics of each frame. Im and Ha [12] presented DVFS techniques in which buffers were used to reclaim unused CPU time, and Huang et al. [20] introduced a method of predicting decoding times from offline analysis of frame characteristics.Most of these techniques do not consider the characteristics of video playback, in which some deadline misses and frame skipping are acceptable. Kim et al. [23] presented a DVFS scheme specifically for scalable video coding (SVC) codecs, which makes use of temporal scalability. The scheme put forward by Yang and Song [11] acknowledges the effect of the ratio of deadline miss on energy consumption, but this paper does not provide a satisfactory solution that selects the appropriate frequency while minimizing energy consumption, nor does it examine how buffering affects power consumption.


## 3. Model

### 3.1. System Model

To support periodic nature of video playback, a video player decodesr frames per second, and so the decoding period of a frame, T
d, is 1
/
r. The Notations explain important symbols used in this paper. Suppose that a CPU supports N
f frequency levels and that level k is the frequency f
k (k
=
1
,
…
,
N
f). If k
<
m, then f
k
<
f
m, so that f
N
f is the highest possible frequency. Let N
d be the number of frames decoded in a video. Let P
k
a
c
t
i
v
e and P
k
i
d
l
e, respectively, be the active and idle power consumption of the system at frequency level k.We will assume that the decoding time of each frame is known in advance: decoding times can be predicted by an offline analysis of the bitstream of a video [20] or by formulating a relationship between frame size and decoding time [5, 6, 11]. This decoding time information can be inserted into the header of a video [20], and we assume that these frames are available to our frequency selection algorithm. Specifically, d
j
,
k is the decoding time of frame j at frequency level k.


### 3.2. Video Playback Model

Frame-level DVFS is appropriate for a media player [5–7, 11], which then selects the frequency which best matches the CPU workload imposed by the current frame, before that frame is decoded. The CPU does not change its frequency until the frame has been decoded.Figure1 shows our video playback model. The decoding task produces frames at playback rate and passes them to a buffer which stores frames for consumption by a display task, which fetches frames at playback rate. If there was no buffer, then only one frame can be handled by the display task, so the decoder enters sleep state until the frame is consumed by the display task. However, if a number of frames can be stored in the buffer, then decoding can run late, allowing lower frequencies to be selected, but this flexibility is limited by the size of buffer. For example, suppose that the buffer can accommodate N
b frames. If there are already N
b frames in the buffer, then decoding of a new frame must be delayed until the next decoded frame has gone to the display task. For example, consider Figure 1, where N
b
=
4. If the buffer already contains 4 frames, then the decoder enters sleep state until frame j has been consumed by the display task.Figure 1
Video playback model.To explain how this buffering technique can decrease CPU power consumption, consider a CPU with 4 frequency levels of 0.8 GHz, 1.2 GHz 1.6 GHz, and 1.8 GHz. We assume thatT
d
=
40ms and that the process of a frame requires 36 ms at level 4, 40.5 ms at level 3, 54 ms at level 2, and 81 ms at level 1. If there was no buffer, then frequency level 4 must be chosen for every frame to keep the decoding time within 40 ms, as shown in Figure 2(a). However, if there is a buffer, which contains frames decoded when playback starts, then frequency level 1 can be selected for the first three frames, level 2 for the next two frames, and level 3 for the final frame as shown in Figure 2(b), without violating deadlines.Figure 2
Comparison between buffering and nonbuffering.
(a)
Nonbuffering
(b)
Buffering


## 3.1. System Model

To support periodic nature of video playback, a video player decodesr frames per second, and so the decoding period of a frame, T
d, is 1
/
r. The Notations explain important symbols used in this paper. Suppose that a CPU supports N
f frequency levels and that level k is the frequency f
k (k
=
1
,
…
,
N
f). If k
<
m, then f
k
<
f
m, so that f
N
f is the highest possible frequency. Let N
d be the number of frames decoded in a video. Let P
k
a
c
t
i
v
e and P
k
i
d
l
e, respectively, be the active and idle power consumption of the system at frequency level k.We will assume that the decoding time of each frame is known in advance: decoding times can be predicted by an offline analysis of the bitstream of a video [20] or by formulating a relationship between frame size and decoding time [5, 6, 11]. This decoding time information can be inserted into the header of a video [20], and we assume that these frames are available to our frequency selection algorithm. Specifically, d
j
,
k is the decoding time of frame j at frequency level k.


## 3.2. Video Playback Model

Frame-level DVFS is appropriate for a media player [5–7, 11], which then selects the frequency which best matches the CPU workload imposed by the current frame, before that frame is decoded. The CPU does not change its frequency until the frame has been decoded.Figure1 shows our video playback model. The decoding task produces frames at playback rate and passes them to a buffer which stores frames for consumption by a display task, which fetches frames at playback rate. If there was no buffer, then only one frame can be handled by the display task, so the decoder enters sleep state until the frame is consumed by the display task. However, if a number of frames can be stored in the buffer, then decoding can run late, allowing lower frequencies to be selected, but this flexibility is limited by the size of buffer. For example, suppose that the buffer can accommodate N
b frames. If there are already N
b frames in the buffer, then decoding of a new frame must be delayed until the next decoded frame has gone to the display task. For example, consider Figure 1, where N
b
=
4. If the buffer already contains 4 frames, then the decoder enters sleep state until frame j has been consumed by the display task.Figure 1
Video playback model.To explain how this buffering technique can decrease CPU power consumption, consider a CPU with 4 frequency levels of 0.8 GHz, 1.2 GHz 1.6 GHz, and 1.8 GHz. We assume thatT
d
=
40ms and that the process of a frame requires 36 ms at level 4, 40.5 ms at level 3, 54 ms at level 2, and 81 ms at level 1. If there was no buffer, then frequency level 4 must be chosen for every frame to keep the decoding time within 40 ms, as shown in Figure 2(a). However, if there is a buffer, which contains frames decoded when playback starts, then frequency level 1 can be selected for the first three frames, level 2 for the next two frames, and level 3 for the final frame as shown in Figure 2(b), without violating deadlines.Figure 2
Comparison between buffering and nonbuffering.
(a)
Nonbuffering
(b)
Buffering


## 4. Problem Formulation

We formulate an optimization problem with a solution which will minimize energy consumption subject to the constraints of buffer size and decoding deadlines. Framej
(
j
=
1
,
…
,
N
d
) must be decoded before its deadline T
j
e
n
d, which is j
T
d. At T
j
e
n
d, frame j leaves the buffer to be displayed on the screen. Let S
j be the frequency level selected for decoding frame j; and let T
j
s
t
a
r
t be the earliest possible time at which the decoding of frame j can start. Because the buffer can contain N
b frames, the decoding of frame j can start at T
j
-
N
b
e
n
d (i.e., (
j
-
N
b
)
T
d), at which frame j
-
N
b can be removed from the buffer and displayed, allowing a new frame to be decoded and stored in the buffer. Thus, T
j
s
t
a
r
t can be expressed as follows:(1)
T
j
start
=
0
j
=
1
,
…
,
N
b
j
-
N
b
T
d
j
=
N
b
+
1
,
…
,
N
d
.LetT
j
,
k
o
v
e
r
(
j
=
1
,
…
,
N
d
-
1
) be the length of time by which the decoding of frame j would overrun if frequency level k is chosen, relative to the start time of the next frame T
j
+
1
s
t
a
r
t. The value of T
0
,
k
o
v
e
r
∀
k is initialized to 0. This overrun can be expressed as follows:(2)
T
j
,
k
over
=
max
⁡
0
,
d
j
,
k
+
T
j
-
1
,
S
j
-
1
over
+
T
j
start
-
T
j
+
1
start
.If the decoding of frame j indeed finishes after T
j
+
1
s
t
a
r
t, then T
j
,
k
o
v
e
r is the time difference between the actual time at which the decoding of frame j finishes (i.e., d
j
,
k
+
T
j
-
1
,
S
j
-
1
o
v
e
r
+
T
j
s
t
a
r
t) and T
j
+
1
s
t
a
r
t, when frequency level k is chosen for frame j. Conversely, if time remains after the decoding of frame j, the CPU enters its idle state and remains in this state until T
j
+
1
s
t
a
r
t, when T
j
,
k
o
v
e
r is set to 0.IfT
j
,
k
o
v
e
r
=
0, then the CPU stays in its idle state for the length of T
j
,
k
s
l
e
e
p, which can be expressed as T
j
+
1
s
t
a
r
t
-
(
T
j
s
t
a
r
t
+
d
j
,
k
+
T
j
-
1
,
S
j
o
v
e
r
); otherwise, T
j
,
k
s
l
e
e
p is set to 0. The determination of T
j
,
k
s
l
e
e
p can thus be summarized as follows:(3)
T
j
,
k
sleep
=
T
j
+
1
start
-
T
j
start
-
d
j
,
k
-
T
j
-
1
,
S
j
-
1
over
if
T
j
,
k
over
=
0
0
otherwise
.The energy consumed during the period of d
j
,
k
+
T
j
,
k
s
l
e
e
p while frame j is decoded at frequency level k is written as E
j
,
k, which can be expressed as follows:(4)
E
j
,
k
=
d
j
,
k
P
k
active
+
T
j
,
k
sleep
P
k
idle
.At this point, we must introduce a further variableT
j
,
k
d
i
f
f, which is the difference between the actual time at which the decoding of frame j finishes (d
j
,
k
+
T
j
-
1
,
S
j
-
1
o
v
e
r
+
T
j
s
t
a
r
t) and T
j
s
t
a
r
t, and this difference can be expressed as follows:(5)
T
j
,
k
diff
=
d
j
,
k
+
T
j
-
1
,
S
j
-
1
over
.Figure 3 shows the relationship between T
j
,
k
o
v
e
r, T
j
,
k
s
l
e
e
p, and T
j
,
k
d
i
f
f in a short sequence of frames.Figure 3
Sequence of frames showing the relationship betweenT
j
,
k
o
v
e
r, T
j
,
k
s
l
e
e
p, and T
j
,
k
d
i
f
f.The decoding of framej must start after T
j
s
t
a
r
t and finish before T
j
e
n
d. We can express this period for each frame j  (
j
=
1
,
…
,
N
d
) as T
j
r
o
u
n
d, so that T
j
r
o
u
n
d
=
T
j
e
n
d
-
T
j
s
t
a
r
t. Each frame j must be decoded before its deadline T
j
e
n
d, so T
j
,
k
d
i
f
f
≤
T
j
r
o
u
n
d. Our frequency selection policy has to minimize the total energy consumption ∑
j
=
1
N
d
‍
E
j
,
S
j. We can now formulate this frequency selection problem that determines S
j  (
j
=
1
,
…
,
N
d
) as follows:(6)
Minimize
∑
j
=
1
N
d
E
j
,
S
j
Subject  to
T
j
,
S
j
diff
≤
T
j
round
,
∀
j
,
j
=
1
,
…
,
N
d
.


## 5. Frequency Allocation Algorithm

### 5.1. Algorithm Concept

We now propose an algorithm to solve the problem using a dynamic programming technique. We will use a resolution of 1 ms for time values such asT
j
,
k
d
i
f
f. Let V
j
,
u
e
n
e
r
g
y be the minimum amount of energy when T
j
,
S
j
d
i
f
f is u milliseconds and frame j is decoded (j
=
1
,
…
,
N
d and u
=
1
,
…
,
T
j
r
o
u
n
d). Let F
j
,
u be the frequency level required to achieve the energy consumption of V
j
,
u
e
n
e
r
g
y; further, let V
j
,
u
o
v
e
r be the corresponding value of T
j
,
S
j
o
v
e
r and V
j
,
u
d
i
f
f the value of T
j
-
1
,
S
j
d
i
f
f.The main idea of the dynamic programming is to construct a table of the optimal energyV
j
,
u
e
n
e
r
g
y for each frame j when T
j
,
k
d
i
f
f
=
u (u
=
1
,
…
,
T
j
r
o
u
n
d), as described in Table 1, where the minimum value in the final row, m
i
n
u
=
1
,
…
,
T
N
d
r
o
u
n
d
V
N
d
,
u
e
n
e
r
g
y, represents the amount of energy consumed by the optimal frequency allocation. For this purpose, we first initialize the values of V
1
,
u
e
n
e
r
g
y and then develop the recurrence relationship between consecutive frames so as to find all the values of V
j
,
u
e
n
e
r
g
y in the table.Table 1
Table for the value ofV
j
,
u
e
n
e
r
g
y against T
j
,
k
d
i
f
f.
Frame number
T
j
,
k
d
i
f
f values
1
2
⋯
T
j
r
o
u
n
d
-
1
T
j
r
o
u
n
d
1
V
1,1
e
n
e
r
g
y
V
1,2
e
n
e
r
g
y
⋯
V
1
,
T
1
r
o
u
n
d
e
n
e
r
g
y
V
1
,
T
1
r
o
u
n
d
e
n
e
r
g
y
2
V
2,1
e
n
e
r
g
y
V
2,2
e
n
e
r
g
y
⋯
V
2
,
T
2
r
o
u
n
d
e
n
e
r
g
y
V
2
,
T
2
r
o
u
n
d
e
n
e
r
g
y
⋮
⋮
⋮
⋯
⋮
⋮
N
d
V
N
d
,
1
e
n
e
r
g
y
V
N
d
,
2
e
n
e
r
g
y
⋯
V
N
d
,
T
N
d
-
1
r
o
u
n
d
e
n
e
r
g
y
V
N
d
,
T
N
d
r
o
u
n
d
e
n
e
r
g
yWe also maintain a two-dimensional array of tuples (F
j
,
u
,
V
j
,
u
d
i
f
f) which leads to the minimum energy of V
j
,
u
e
n
e
r
g
y as illustrated in Figure 4. Using this array, a backtracking phase starts from frame N
d to frame 1 to select frequency of every frame. For example, Figure 4 shows an array of these tuples when N
d
=
5 and T
j
r
o
u
n
d
=
10. Suppose that the third column in the last row has the minimum energy value. Because V
j
,
u
d
i
f
f points to the column index of the previous frame, a sequence of frequencies can be selected as follows: (
6,3
,
4,5
,
1
). Likewise, our dynamic programming algorithm has three phases: (
1
) initialization, (
2
) establishment of recurrence relation, and (
3
) backtracking.Figure 4
Process of backtracking.


### 5.2. Initialization

For initialization, consider the following:(1)
V
j
,
u
e
n
e
r
g
y, V
j
,
u
o
v
e
r, V
j
,
u
d
i
f
f, and F
j
,
u are all initialized to ∞ (∀
j
,
u, j
=
1
,
…
,
N
d and u
=
1
,
…
,
T
j
r
o
u
n
d).
(2)
∀
k, where d
1
,
k
≤
T
1
e
n
d, the values of T
1
,
k
o
v
e
r, T
1
,
k
s
l
e
e
p, and E
1
,
k are calculated from (2), (3), and (4), respectively. Next, V
1
,
d
1
,
k
o
v
e
r is replaced with T
1
,
k
o
v
e
r; then, V
1
,
d
1
,
k
e
n
e
r
g
y is updated to E
1
,
k, and F
1
,
d
1
,
k is replaced with frequency level k.


### 5.3. Establishment of Recurrence Relation

During the recurrence establishment phase,V
j
,
u
e
n
e
r
g
y, F
j
,
u, V
j
,
u
d
i
f
f, and V
j
,
u
o
v
e
r
(
j
=
2
,
…
,
N
d and u
=
1
,
…
,
T
j
r
o
u
n
d
) are updated as follows:(1)
For each value ofj and u
(
j
=
2
,
…
,
N
d and u
=
1
,
…
,
T
j
r
o
u
n
d
), we maintain a two-dimensional array, A
j
,
u
(
i
,
k
) (i
=
1
,
…
,
T
j
-
1
r
o
u
n
d and k
=
1
,
…
,
N
f). The following steps are repeated to find the value of A
j
,
u
(
i
,
k
), ∀
i
,
k if V
j
-
1
,
i
e
n
e
r
g
y
≠
∞:
(a)
Calculate the value ofT
j
,
k
o
v
e
r using (2), after replacing T
j
-
1
,
S
j
-
1
o
v
e
r with V
j
-
1
,
i
o
v
e
r.
(b)
Using the resulting value ofT
j
,
k
o
v
e
r, calculate T
j
,
k
s
l
e
e
p from (3).
(c)
Using the resulting value ofT
j
,
k
s
l
e
e
p, calculate E
j
,
k from (4) and use this value of E
j
,
k to update A
{
j
,
d
j
,
k
+
V
j
-
1
,
i
o
v
e
r
}
(
i
,
k
).
(2)
V
j
,
u
e
n
e
r
g
y, F
j
,
u, V
j
,
u
d
i
f
f, and V
j
,
u
o
v
e
r are updated as follows:(7)
V
j
,
u
energy
=
min
i
=
1
,
…
,
T
j
-
1
round
,
k
=
1
,
…
,
N
f
⁡
V
j
-
1
,
i
energy
+
A
j
,
u
i
,
k
,
F
j
,
u
=
arg
⁡
min
k
=
1
,
…
,
N
f
⁡
V
j
,
u
energy
,
V
j
,
u
diff
=
arg
⁡
min
i
=
1
,
…
,
T
j
-
1
round
⁡
V
j
,
u
energy
,
V
j
,
u
over
=
max
⁡
0
,
V
V
j
,
u
diff
+
d
j
,
F
j
,
u
-
T
j
+
1
start
.


### 5.4. Backtracking

We find values ofS
j using a backtracking technique as follows:(1)
j is initialized to N
d, and u is set to arg
⁡
min
u
=
1
,
…
,
T
N
d
round
⁡
V
N
d
,
u
e
n
e
r
g
y, so that V
N
d
,
u
e
n
e
r
g
y represents the amount of minimum energy consumption.
(2)
Whilej
>
0, the following procedures are repeated: (
1
)
S
j is set to F
j
,
u, (
2
)
V
j
,
u
d
i
f
f is substituted for u, and (
3
)
j is decremented by 1.Pseudocode for this frequency selection algorithm (FSA) is presented as Algorithm 1. If T
m
a
x is the maximum round length so that T
m
a
x
=
m
a
x
j
=
2
,
…
,
N
d
T
j
r
o
u
n
d, we can easily see from Algorithm 1 that the complexity of FSA is O
(
N
d
N
f
T
m
a
x
).Algorithm 1:FSA (frequency selection algorithm).
(1)Temporary variables: j, u, i and k;
(2)
for  j
=
1 to N
d  do
(3) for  u
=
1 to T
j
r
o
u
n
d  do
(4)  V
j
,
u
e
n
e
r
g
y, V
j
,
u
o
v
e
r, V
j
,
u
d
i
f
f and F
j
,
u
←
∞;
(5) end for
(6)
end for
(7)
for  u
=
1 to T
j
r
o
u
n
d  do
(8) for  k
=
1 to N
f  do
(9)  if  d
1
,
k
≤
T
1
e
n
d and u
=
d
1
,
k  then
(10)    Calculate T
1
,
k
o
v
e
r, T
1
,
k
s
l
e
e
p and E
1
,
k using (2), (3), and (4), respectively;
(11)    V
1
,
u
e
n
e
r
g
y
←
E
1
,
k;
(12)    F
1
,
u
←
k;
(13)    V
1
,
u
o
v
e
r
←
T
1
,
k
o
v
e
r;
(14)   end if
(15)  end for
(16) end for
(17) for  j
=
2 to N
d  do
(18)  for  i
=
1 to T
j
-
1
r
o
u
n
d  do
(19)   for  k
=
1 to N
f  do
(20)    if  V
j
-
1
,
i
e
n
e
r
g
y
≠
∞  then
(21)     Calculate the value of T
j
,
k
o
v
e
r from (2) by replacing T
j
-
1
,
S
j
-
1
o
v
e
r with V
j
-
1
,
i
o
v
e
r;
(22)     T
j
,
k
s
l
e
e
p is calculated from (3) by replacing T
j
-
1
,
S
j
-
1
o
v
e
r with V
j
-
1
,
i
o
v
e
r;
(23)     E
j
,
k is calculated from (4), and A
j
,
d
j
,
k
+
V
j
-
1
,
i
o
v
e
r
(
i
,
k
) is updated using this value of E
j
,
k;
(24)    end if
(25)   end for
(26)  end for
(27)  V
j
,
u
e
n
e
r
g
y
←
min
i
=
1
,
…
,
T
j
-
1
round
and
k
=
1
,
…
,
N
f
⁡
(
V
j
-
1
,
i
e
n
e
r
g
y
+
A
j
,
u
(
i
,
k
)
);
(28)  F
j
,
u
←
arg
⁡
min
k
=
1
,
…
,
N
f
⁡
V
j
,
u
e
n
e
r
g
y;
(29)  V
j
,
u
d
i
f
f
←
arg
⁡
min
i
=
1
,
…
,
T
j
-
1
round
⁡
V
j
,
u
e
n
e
r
g
y;
(30)  V
j
,
u
o
v
e
r
←
max
⁡
(
0
,
V
V
j
,
u
d
i
f
f
+
d
j
,
F
j
,
u
-
T
j
+
1
s
t
a
r
t
);
(31) end for
(32) j
←
N
d;
(33) u
←
arg
⁡
min
i
=
1
,
…
,
T
N
d
round
⁡
V
N
d
,
i
e
n
e
r
g
y;
(34) while  j
>
0  do
(35)  S
j
←
F
j
,
u;
(36)  u
←
V
j
,
u
d
i
f
f;
(37)  j
←
j
-
1;
(38) end while


## 5.1. Algorithm Concept

We now propose an algorithm to solve the problem using a dynamic programming technique. We will use a resolution of 1 ms for time values such asT
j
,
k
d
i
f
f. Let V
j
,
u
e
n
e
r
g
y be the minimum amount of energy when T
j
,
S
j
d
i
f
f is u milliseconds and frame j is decoded (j
=
1
,
…
,
N
d and u
=
1
,
…
,
T
j
r
o
u
n
d). Let F
j
,
u be the frequency level required to achieve the energy consumption of V
j
,
u
e
n
e
r
g
y; further, let V
j
,
u
o
v
e
r be the corresponding value of T
j
,
S
j
o
v
e
r and V
j
,
u
d
i
f
f the value of T
j
-
1
,
S
j
d
i
f
f.The main idea of the dynamic programming is to construct a table of the optimal energyV
j
,
u
e
n
e
r
g
y for each frame j when T
j
,
k
d
i
f
f
=
u (u
=
1
,
…
,
T
j
r
o
u
n
d), as described in Table 1, where the minimum value in the final row, m
i
n
u
=
1
,
…
,
T
N
d
r
o
u
n
d
V
N
d
,
u
e
n
e
r
g
y, represents the amount of energy consumed by the optimal frequency allocation. For this purpose, we first initialize the values of V
1
,
u
e
n
e
r
g
y and then develop the recurrence relationship between consecutive frames so as to find all the values of V
j
,
u
e
n
e
r
g
y in the table.Table 1
Table for the value ofV
j
,
u
e
n
e
r
g
y against T
j
,
k
d
i
f
f.
Frame number
T
j
,
k
d
i
f
f values
1
2
⋯
T
j
r
o
u
n
d
-
1
T
j
r
o
u
n
d
1
V
1,1
e
n
e
r
g
y
V
1,2
e
n
e
r
g
y
⋯
V
1
,
T
1
r
o
u
n
d
e
n
e
r
g
y
V
1
,
T
1
r
o
u
n
d
e
n
e
r
g
y
2
V
2,1
e
n
e
r
g
y
V
2,2
e
n
e
r
g
y
⋯
V
2
,
T
2
r
o
u
n
d
e
n
e
r
g
y
V
2
,
T
2
r
o
u
n
d
e
n
e
r
g
y
⋮
⋮
⋮
⋯
⋮
⋮
N
d
V
N
d
,
1
e
n
e
r
g
y
V
N
d
,
2
e
n
e
r
g
y
⋯
V
N
d
,
T
N
d
-
1
r
o
u
n
d
e
n
e
r
g
y
V
N
d
,
T
N
d
r
o
u
n
d
e
n
e
r
g
yWe also maintain a two-dimensional array of tuples (F
j
,
u
,
V
j
,
u
d
i
f
f) which leads to the minimum energy of V
j
,
u
e
n
e
r
g
y as illustrated in Figure 4. Using this array, a backtracking phase starts from frame N
d to frame 1 to select frequency of every frame. For example, Figure 4 shows an array of these tuples when N
d
=
5 and T
j
r
o
u
n
d
=
10. Suppose that the third column in the last row has the minimum energy value. Because V
j
,
u
d
i
f
f points to the column index of the previous frame, a sequence of frequencies can be selected as follows: (
6,3
,
4,5
,
1
). Likewise, our dynamic programming algorithm has three phases: (
1
) initialization, (
2
) establishment of recurrence relation, and (
3
) backtracking.Figure 4
Process of backtracking.


## 5.2. Initialization

For initialization, consider the following:(1)
V
j
,
u
e
n
e
r
g
y, V
j
,
u
o
v
e
r, V
j
,
u
d
i
f
f, and F
j
,
u are all initialized to ∞ (∀
j
,
u, j
=
1
,
…
,
N
d and u
=
1
,
…
,
T
j
r
o
u
n
d).
(2)
∀
k, where d
1
,
k
≤
T
1
e
n
d, the values of T
1
,
k
o
v
e
r, T
1
,
k
s
l
e
e
p, and E
1
,
k are calculated from (2), (3), and (4), respectively. Next, V
1
,
d
1
,
k
o
v
e
r is replaced with T
1
,
k
o
v
e
r; then, V
1
,
d
1
,
k
e
n
e
r
g
y is updated to E
1
,
k, and F
1
,
d
1
,
k is replaced with frequency level k.


## 5.3. Establishment of Recurrence Relation

During the recurrence establishment phase,V
j
,
u
e
n
e
r
g
y, F
j
,
u, V
j
,
u
d
i
f
f, and V
j
,
u
o
v
e
r
(
j
=
2
,
…
,
N
d and u
=
1
,
…
,
T
j
r
o
u
n
d
) are updated as follows:(1)
For each value ofj and u
(
j
=
2
,
…
,
N
d and u
=
1
,
…
,
T
j
r
o
u
n
d
), we maintain a two-dimensional array, A
j
,
u
(
i
,
k
) (i
=
1
,
…
,
T
j
-
1
r
o
u
n
d and k
=
1
,
…
,
N
f). The following steps are repeated to find the value of A
j
,
u
(
i
,
k
), ∀
i
,
k if V
j
-
1
,
i
e
n
e
r
g
y
≠
∞:
(a)
Calculate the value ofT
j
,
k
o
v
e
r using (2), after replacing T
j
-
1
,
S
j
-
1
o
v
e
r with V
j
-
1
,
i
o
v
e
r.
(b)
Using the resulting value ofT
j
,
k
o
v
e
r, calculate T
j
,
k
s
l
e
e
p from (3).
(c)
Using the resulting value ofT
j
,
k
s
l
e
e
p, calculate E
j
,
k from (4) and use this value of E
j
,
k to update A
{
j
,
d
j
,
k
+
V
j
-
1
,
i
o
v
e
r
}
(
i
,
k
).
(2)
V
j
,
u
e
n
e
r
g
y, F
j
,
u, V
j
,
u
d
i
f
f, and V
j
,
u
o
v
e
r are updated as follows:(7)
V
j
,
u
energy
=
min
i
=
1
,
…
,
T
j
-
1
round
,
k
=
1
,
…
,
N
f
⁡
V
j
-
1
,
i
energy
+
A
j
,
u
i
,
k
,
F
j
,
u
=
arg
⁡
min
k
=
1
,
…
,
N
f
⁡
V
j
,
u
energy
,
V
j
,
u
diff
=
arg
⁡
min
i
=
1
,
…
,
T
j
-
1
round
⁡
V
j
,
u
energy
,
V
j
,
u
over
=
max
⁡
0
,
V
V
j
,
u
diff
+
d
j
,
F
j
,
u
-
T
j
+
1
start
.


## 5.4. Backtracking

We find values ofS
j using a backtracking technique as follows:(1)
j is initialized to N
d, and u is set to arg
⁡
min
u
=
1
,
…
,
T
N
d
round
⁡
V
N
d
,
u
e
n
e
r
g
y, so that V
N
d
,
u
e
n
e
r
g
y represents the amount of minimum energy consumption.
(2)
Whilej
>
0, the following procedures are repeated: (
1
)
S
j is set to F
j
,
u, (
2
)
V
j
,
u
d
i
f
f is substituted for u, and (
3
)
j is decremented by 1.Pseudocode for this frequency selection algorithm (FSA) is presented as Algorithm 1. If T
m
a
x is the maximum round length so that T
m
a
x
=
m
a
x
j
=
2
,
…
,
N
d
T
j
r
o
u
n
d, we can easily see from Algorithm 1 that the complexity of FSA is O
(
N
d
N
f
T
m
a
x
).Algorithm 1:FSA (frequency selection algorithm).
(1)Temporary variables: j, u, i and k;
(2)
for  j
=
1 to N
d  do
(3) for  u
=
1 to T
j
r
o
u
n
d  do
(4)  V
j
,
u
e
n
e
r
g
y, V
j
,
u
o
v
e
r, V
j
,
u
d
i
f
f and F
j
,
u
←
∞;
(5) end for
(6)
end for
(7)
for  u
=
1 to T
j
r
o
u
n
d  do
(8) for  k
=
1 to N
f  do
(9)  if  d
1
,
k
≤
T
1
e
n
d and u
=
d
1
,
k  then
(10)    Calculate T
1
,
k
o
v
e
r, T
1
,
k
s
l
e
e
p and E
1
,
k using (2), (3), and (4), respectively;
(11)    V
1
,
u
e
n
e
r
g
y
←
E
1
,
k;
(12)    F
1
,
u
←
k;
(13)    V
1
,
u
o
v
e
r
←
T
1
,
k
o
v
e
r;
(14)   end if
(15)  end for
(16) end for
(17) for  j
=
2 to N
d  do
(18)  for  i
=
1 to T
j
-
1
r
o
u
n
d  do
(19)   for  k
=
1 to N
f  do
(20)    if  V
j
-
1
,
i
e
n
e
r
g
y
≠
∞  then
(21)     Calculate the value of T
j
,
k
o
v
e
r from (2) by replacing T
j
-
1
,
S
j
-
1
o
v
e
r with V
j
-
1
,
i
o
v
e
r;
(22)     T
j
,
k
s
l
e
e
p is calculated from (3) by replacing T
j
-
1
,
S
j
-
1
o
v
e
r with V
j
-
1
,
i
o
v
e
r;
(23)     E
j
,
k is calculated from (4), and A
j
,
d
j
,
k
+
V
j
-
1
,
i
o
v
e
r
(
i
,
k
) is updated using this value of E
j
,
k;
(24)    end if
(25)   end for
(26)  end for
(27)  V
j
,
u
e
n
e
r
g
y
←
min
i
=
1
,
…
,
T
j
-
1
round
and
k
=
1
,
…
,
N
f
⁡
(
V
j
-
1
,
i
e
n
e
r
g
y
+
A
j
,
u
(
i
,
k
)
);
(28)  F
j
,
u
←
arg
⁡
min
k
=
1
,
…
,
N
f
⁡
V
j
,
u
e
n
e
r
g
y;
(29)  V
j
,
u
d
i
f
f
←
arg
⁡
min
i
=
1
,
…
,
T
j
-
1
round
⁡
V
j
,
u
e
n
e
r
g
y;
(30)  V
j
,
u
o
v
e
r
←
max
⁡
(
0
,
V
V
j
,
u
d
i
f
f
+
d
j
,
F
j
,
u
-
T
j
+
1
s
t
a
r
t
);
(31) end for
(32) j
←
N
d;
(33) u
←
arg
⁡
min
i
=
1
,
…
,
T
N
d
round
⁡
V
N
d
,
i
e
n
e
r
g
y;
(34) while  j
>
0  do
(35)  S
j
←
F
j
,
u;
(36)  u
←
V
j
,
u
d
i
f
f;
(37)  j
←
j
-
1;
(38) end while


## 6. Algorithm Execution

If the frame decoding time is known in advance, then FSA can run without modification. For example, before playback, frequency allocation table during the entire playback can be obtained as a result of algorithm execution. However, since the algorithm complexity depends on the number of frames to be decoded, we divide the algorithm into iterations and limit the number of frames taken by the algorithm toN
l  (
N
l
<
N
d
). Therefore, at the beginning of the mth iteration, the algorithm chooses the frequency for frames between (
m
-
1
)
N
l
+
1 and m
N
l, which we call FSA-split, as shown in Algorithm 2.Algorithm 2:FSA-split (frequency selection algorithm for the mth iteration).
(1)Temporary variables: j, u, i and k;
(2)Input parameter from the previous iteration (m
>
1): I
p
r
e
v
(3)
I
p
r
e
v
←
arg
⁡
min
i
=
1
,
…
,
T
(
m
-
1
)
N
l
round
⁡
V
(
m
-
1
)
N
l
,
i
e
n
e
r
g
y;
(4)
for  j
=
(
m
-
1
)
N
l
+
1 to m
N
l  do
(5) for  u
=
1 to T
j
r
o
u
n
d  do
(6)  V
j
,
u
e
n
e
r
g
y, V
j
,
u
o
v
e
r, V
j
,
u
d
i
f
f and F
j
,
u
←
∞;
(7) end for
(8)
end for
(9)
for  u
=
1 to T
j
r
o
u
n
d  do
(10)  for  k
=
1 to N
f  do
(11)   if  d
(
m
-
1
)
N
l
+
1
,
k
≤
T
(
m
-
1
)
N
l
+
1
e
n
d and u
=
d
(
m
-
1
)
N
l
+
1
,
k  then
(12)
if  m
>
1  then
(13)    Calculate T
(
m
-
1
)
N
l
+
1
,
k
o
v
e
r, T
(
m
-
1
)
N
l
+
1
,
k
s
l
e
e
p and E
(
m
-
1
)
N
l
+
1
,
k using (2), (3), and (4), respectively, by replacing T
j
-
1
,
S
j
-
1
o
v
e
r
with V
(
m
-
1
)
N
l
,
I
p
r
e
v
o
v
e
r;
(14)
else
(15)    Calculate T
(
m
-
1
)
N
l
+
1
,
k
o
v
e
r, T
(
m
-
1
)
N
l
+
1
,
k
s
l
e
e
p and E
(
m
-
1
)
N
l
+
1
,
k using (2), (3), and (4), respectively, by replacing T
j
-
1
,
S
j
-
1
o
v
e
r with 0;
(16)
end if
(17)
V
(
m
-
1
)
N
l
+
1
,
u
e
n
e
r
g
y
←
E
(
m
-
1
)
N
l
+
1
,
k;
(18)
F
(
m
-
1
)
N
l
+
1
,
u
←
k;
(19)
V
(
m
-
1
)
N
l
+
1
,
u
o
v
e
r
←
T
(
m
-
1
)
N
l
+
1
,
k
o
v
e
r;
(20)   end if
(21)  end for
(22) end for
(23) for  j
=
(
m
-
1
)
N
l
+
2 to m
N
l  do
(24)  for  i
=
1 to T
j
-
1
r
o
u
n
d  do
(25)   for  k
=
1 to N
f  do
(26)    if V
j
-
1
,
i
e
n
e
r
g
y
≠
∞  then
(27)     Calculate the value of T
j
,
k
o
v
e
r from (2) by replacing T
j
-
1
,
S
j
-
1
o
v
e
r with V
j
-
1
,
i
o
v
e
r;
(28)     T
j
,
k
s
l
e
e
p is calculated from (3) by replacing T
j
-
1
,
S
j
-
1
o
v
e
r with V
j
-
1
,
i
o
v
e
r;
(29)     E
j
,
k is calculated from (4), and A
j
,
d
j
,
k
+
V
j
-
1
,
i
o
v
e
r
(
i
,
k
) is updated using this value of E
j
,
k;
(30)    end if
(31)   end for
(32)  end for
(33)  V
j
,
u
e
n
e
r
g
y
←
min
i
=
1
,
…
,
T
j
-
1
round
and
k
=
1
,
…
,
N
f
⁡
(
V
j
-
1
,
i
e
n
e
r
g
y
+
A
j
,
u
(
i
,
k
)
);
(34)  F
j
,
u
←
arg
⁡
min
k
=
1
,
…
,
N
f
⁡
V
j
,
u
e
n
e
r
g
y;
(35)  V
j
,
u
d
i
f
f
←
arg
⁡
min
i
=
1
,
…
,
T
j
-
1
round
⁡
V
j
,
u
e
n
e
r
g
y;
(36)  V
j
,
u
o
v
e
r
←
max
⁡
(
0
,
V
V
j
,
u
d
i
f
f
+
d
j
,
F
j
,
u
-
T
j
+
1
s
t
a
r
t
);
(37) end for
(38) j
←
m
N
l;
(39) u
←
arg
⁡
min
i
=
1
,
…
,
T
m
N
l
round
⁡
V
m
N
l
,
i
e
n
e
r
g
y;
(40) while  j
>
(
m
-
1
)
N
l  do
(41)  S
j
←
F
j
,
u;
(42)  u
←
V
(
m
-
1
)
N
l
+
j
,
u
d
i
f
f;
(43)  j
←
j
-
1;
(44) end whileFSA-split has the following characteristics in comparison with FSA:(i)
FSA-split determines the frequencies of frames between(
m
-
1
)
N
l
+
1 and m
N
l.
(ii)
An initialization part (lines between(
9
) and (
22
) in Algorithm 2) takes the length of overrun in the previous iteration (V
(
m
-
1
)
N
l
,
I
p
r
e
v
o
v
e
r) for the calculation of the parameter values.Several methods were developed for decoding time estimation, most of which predict future decoding times based on recent measured times [5–7, 11, 19]. The decoding times of the frames in a certain GOP do not change a lot compared with those of its neighboring GOPs [11]. We can therefore predict the decoding times of the next GOP on the basis of those of the current GOP. For example, if N
l is set to the number of frames of a GOP, then the frequency allocation table can be established for the next GOP by passing predicted decoding times of the next GOP to the input parameters of the FSA-split.


## 7. Experimental Results

### 7.1. Setup

We performed simulations to evaluate our schemes using power data and timings obtained experimentally. The power consumption of a Samsung Nexus S smartphone (not just the CPU) was measured, and Table2 shows its active and idle power values. The time taken to decode video frames was also measured for the two videos in Table 3. We compared our scheme with two other algorithms as follows:(1)
HF always selects the highest frequency, which is equivalent to no DVFS.
(2)
LF selects the lowest frequency level which will get each frame decoded in time. This method is a good heuristic, because CPU frequency can be expected to have a monotonic relationship with energy consumption [4–7, 11].Table 2
Measured power consumption against frequency of Samsung Nexus S phone.
Frequency (MHz)
1000
800
400
200
100
Active power (mW)
1324
1082
741
557
444
Idle power (mW)
545
527
503
471
420Table 3
Video characteristics.
Type
Title
Resolution
Average bitrate
Playback time
GOP length
Animation
Ice Age 4
352 × 288
736 kb/s
5 minutes
12
Sports
Soccer
352 × 288
199 kb/s
5 minutes
12


### 7.2. Efficacy of FSA

Table4 shows how energy consumption depends on the number of frames that are buffered. We see that (
1
) FSA always shows the best performance, using 13% less energy than LF and 27% less energy than HF on average, and (
2
) increasing the size of the buffer saves more energy, but this amount of energy saved gradually tails off. In particular, even when N
b
=
1 so that only one additional buffer is used, FSA uses 11% less energy than LF on average, suggesting that the buffer overhead of FSA is not high.Table 4
Relative energy consumption of FSA against a number of buffers.
Video type
Animation
Sports
Number of buffers (N
b)
1
2
3
4
1
2
3
4
Energy used relative to HF
68.6%
67.1%
66.9%
66.9%
80%
77.8%
77.3%
77.2%
Energy used relative to LF
84.2%
82.3%
82.1%
82%
93.2%
90.6%
90.1%
89.9%The results in Table4 can be attributed to FSA’s effective use of the slack times generated by storing decoded frames in the buffer, allowing the CPU to operate at lower frequencies. For example, Table 5 shows the average percentage of the frames in both video clips that are decoded at each frequency; FSA chooses lower frequencies than LF, decreasing energy consumption. FSA chooses the highest frequency (1000 MHz) more often than LF, which increases the idle time, allowing relatively lower frequencies to be chosen than LF. These results suggest that frequency selection has a great effect on energy consumption.Table 5
Percentage of frames decoded at each frequency.
Video type
Animation
Sports
Frequency (MHz)
100
200
400
800
1000
100
200
400
800
1000
LF
28.5%
3.7%
63.5%
4.3%
0%
0%
9.3%
90.4%
0.2%
0%
FSA (N
b
=
1)
72%
0.8%
9.8%
14.8%
2.6%
4.8%
52.7%
31.1%
11.1%
0.3%
FSA (N
b
=
2)
75.5%
0%
0.8%
19.9%
3.8%
24.7%
8.6%
27.2%
38.2%
1.3%
FSA (N
b
=
3)
75.2%
0%
0.3%
19.7%
4.8%
28.1%
2.1%
21.8%
46.7%
1.3%
FSA (N
b
=
4)
75.3%
0%
0.3%
20.0%
4.4%
28.9%
1.1%
18.4%
50.6%
1.1%


### 7.3. Efficacy of FSA-Split

To evaluate the efficacy of FSA-split, we examined how the values ofN
l affect the energy consumption against different values of N
b as tabulated in Table 6. We see that (
1
) their energy difference is marginal, exhibiting 1.47% difference at maximum, even when N
l is set to 12 which is the GOP size; (
2
) increasing the value of N
l decreases the energy gap; and (
3
) increasing the buffer size increases the energy gap even though the difference is negligible. Although FSA exhibits slightly better performance than FSA-split, it takes all frame parameters for algorithm execution, requiring a lot of computation. These results suggest that FSA-split is a practical method of reducing the energy required for video decoding.Table 6
Percentage energy difference between FSA and FSA-split against different values ofN
l.
Video type
Animation
Sports
N
l
12
24
48
96
192
12
24
48
96
192
N
b
=
1
0.88%
0.48%
0.26%
0.14%
0.07%
0.22%
0.11%
0.05%
0.03%
0.02%
N
b
=
2
1.26%
0.66%
0.33%
0.17%
0.09%
0.42%
0.21%
0.11%
0.06%
0.03%
N
b
=
3
1.40%
0.70%
0.35%
0.18%
0.09%
0.49%
0.24%
0.12%
0.07%
0.04%
N
b
=
4
1.47%
0.76%
0.38%
0.20%
0.10%
0.52%
0.24%
0.12%
0.06%
0.04%


## 7.1. Setup

We performed simulations to evaluate our schemes using power data and timings obtained experimentally. The power consumption of a Samsung Nexus S smartphone (not just the CPU) was measured, and Table2 shows its active and idle power values. The time taken to decode video frames was also measured for the two videos in Table 3. We compared our scheme with two other algorithms as follows:(1)
HF always selects the highest frequency, which is equivalent to no DVFS.
(2)
LF selects the lowest frequency level which will get each frame decoded in time. This method is a good heuristic, because CPU frequency can be expected to have a monotonic relationship with energy consumption [4–7, 11].Table 2
Measured power consumption against frequency of Samsung Nexus S phone.
Frequency (MHz)
1000
800
400
200
100
Active power (mW)
1324
1082
741
557
444
Idle power (mW)
545
527
503
471
420Table 3
Video characteristics.
Type
Title
Resolution
Average bitrate
Playback time
GOP length
Animation
Ice Age 4
352 × 288
736 kb/s
5 minutes
12
Sports
Soccer
352 × 288
199 kb/s
5 minutes
12


## 7.2. Efficacy of FSA

Table4 shows how energy consumption depends on the number of frames that are buffered. We see that (
1
) FSA always shows the best performance, using 13% less energy than LF and 27% less energy than HF on average, and (
2
) increasing the size of the buffer saves more energy, but this amount of energy saved gradually tails off. In particular, even when N
b
=
1 so that only one additional buffer is used, FSA uses 11% less energy than LF on average, suggesting that the buffer overhead of FSA is not high.Table 4
Relative energy consumption of FSA against a number of buffers.
Video type
Animation
Sports
Number of buffers (N
b)
1
2
3
4
1
2
3
4
Energy used relative to HF
68.6%
67.1%
66.9%
66.9%
80%
77.8%
77.3%
77.2%
Energy used relative to LF
84.2%
82.3%
82.1%
82%
93.2%
90.6%
90.1%
89.9%The results in Table4 can be attributed to FSA’s effective use of the slack times generated by storing decoded frames in the buffer, allowing the CPU to operate at lower frequencies. For example, Table 5 shows the average percentage of the frames in both video clips that are decoded at each frequency; FSA chooses lower frequencies than LF, decreasing energy consumption. FSA chooses the highest frequency (1000 MHz) more often than LF, which increases the idle time, allowing relatively lower frequencies to be chosen than LF. These results suggest that frequency selection has a great effect on energy consumption.Table 5
Percentage of frames decoded at each frequency.
Video type
Animation
Sports
Frequency (MHz)
100
200
400
800
1000
100
200
400
800
1000
LF
28.5%
3.7%
63.5%
4.3%
0%
0%
9.3%
90.4%
0.2%
0%
FSA (N
b
=
1)
72%
0.8%
9.8%
14.8%
2.6%
4.8%
52.7%
31.1%
11.1%
0.3%
FSA (N
b
=
2)
75.5%
0%
0.8%
19.9%
3.8%
24.7%
8.6%
27.2%
38.2%
1.3%
FSA (N
b
=
3)
75.2%
0%
0.3%
19.7%
4.8%
28.1%
2.1%
21.8%
46.7%
1.3%
FSA (N
b
=
4)
75.3%
0%
0.3%
20.0%
4.4%
28.9%
1.1%
18.4%
50.6%
1.1%


## 7.3. Efficacy of FSA-Split

To evaluate the efficacy of FSA-split, we examined how the values ofN
l affect the energy consumption against different values of N
b as tabulated in Table 6. We see that (
1
) their energy difference is marginal, exhibiting 1.47% difference at maximum, even when N
l is set to 12 which is the GOP size; (
2
) increasing the value of N
l decreases the energy gap; and (
3
) increasing the buffer size increases the energy gap even though the difference is negligible. Although FSA exhibits slightly better performance than FSA-split, it takes all frame parameters for algorithm execution, requiring a lot of computation. These results suggest that FSA-split is a practical method of reducing the energy required for video decoding.Table 6
Percentage energy difference between FSA and FSA-split against different values ofN
l.
Video type
Animation
Sports
N
l
12
24
48
96
192
12
24
48
96
192
N
b
=
1
0.88%
0.48%
0.26%
0.14%
0.07%
0.22%
0.11%
0.05%
0.03%
0.02%
N
b
=
2
1.26%
0.66%
0.33%
0.17%
0.09%
0.42%
0.21%
0.11%
0.06%
0.03%
N
b
=
3
1.40%
0.70%
0.35%
0.18%
0.09%
0.49%
0.24%
0.12%
0.07%
0.04%
N
b
=
4
1.47%
0.76%
0.38%
0.20%
0.10%
0.52%
0.24%
0.12%
0.06%
0.04%


## 8. Conclusions

We have proposed a new frequency allocation scheme which minimizes energy consumption while avoiding buffer overrun, using a dynamic programming technique. This scheme establishes recurrence relationship between consecutive frames to construct a table of the minimum energy values required to decode each frame and determines a sequence of frequencies required to decode every frame using a backtracking technique. It was extended to optimize CPU frequencies over a short sequence of frames, which gives a basis for energy-saving video decoding in practice.Experimental results show that it uses27
% less energy than a processor at the highest frequency on average. In particular, it uses 13% less energy, compared to the widely used heuristic which chooses the lowest frequency to get each frame decoded in time. We believe that these results give a useful guideline for low-power video service by providing the minimum bound on power consumption required for video playback.



---

*Source: 1042525-2016-05-03.xml*