Abstract
Smartphones are potent mobile devices which are required to operate for extendedperiods of time on battery power. In this thesis smartphone power
management issues are addressed using algorithmic techniques.
Firstly, we consider power efficient scheduling for heterogeneous multi processor
systems that allow dynamic speed scaling. We propose the Virtual Single
Processor (VSP) approach which involves computing and utilising optimal system
configurations. The VSP is used in combination with an efficient single
processor dynamic speed scaling scheduling algorithm to compute highly power
efficient schedules. We find that there is an average power saving of between
4.4% (2 processor system) and 8.175% (16 processor system) when compared
to an alternative algorithm. Simulations also showed that the VSP approach
reduced the objective function of
P
Weighted Flow + Energy by 2.31% more
than the best known alternative. This work was published as a full paper at
MISTA 2011.
Secondly, we discuss low energy Field Programmable Gate Array (FPGA)
function mapping. A substantial FPGA power drain is caused by dynamic
switching of the routing edges; this can be vastly reduced by mapping the input
boolean function such that switching activity is minimised. We formulate the
combinatorial optimisation problem, develop a complete neighbourhood function
and apply simulated annealing to minimise cumulative switching. We find
that our algorithm reduces the cumulative switching activity by an average of
27.44% compared to a genetic algorithm. This work appeared at GreenGEC
2013.
Finally, we examine the sleep state management problem in terms of advice
complexity. We begin by showing the advice complexity of the problem is r log s
where r is the number of idle periods and s is the number of sleep states. We
design an algorithm which uses a single bit of advice to solve the single sleep
state problem and show it to be 1.8-competitve. This is 20% better than the
best possible deterministic algorithm. We also show that our algorithm can
be improved by adding more advice but only until we have [log b] advice bits.
Finally, in the case with more than 2 states our algorithm uses 1 bit of advice
to improve on the deterministic algorithm.
| Date of Award | 2014 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Kathleen Steinhofel (Supervisor) |