Team Information Publications

The energy and power requirements of computing devices have been increasing exponentially. While the power density in microprocessors has doubled every three years, battery capacities have been growing at a linear rate. This results in great problems for battery operated mobile devices. Furthermore, a large part of the energy consumed by the processors is converted into heat, therefore, even systems that do not rely on batteries need to deal with power consumption. The heat generated by modern processors is becoming harder to dissipate and is particularly problematic when large numbers of them are in close proximity, such as in a supercomputer or a server farm. Exponential rise in heat density together with exponentially rising cooling cost has threatened the ability of industry to deploy new systems.

A straightforward technique of power management is to shut down the processor when it is idle. A more advanced and dominant technique is dynamic voltage / speed scaling. which is more effective than simply shutting down the processor. Modern processor technologies enable processors to operate at various processor speeds. The development of these technologies is based on the property that the power consumed of a processor is usually a convex and increasing function of processor speed, the convexity of the power function means that the more slowly a task is run, the less energy is used to complete the task. To take full advantage of this new technology, a power management strategy is required to determine the voltage/speed to be used to make sure that the energy is used efficiently.

Power consumption
is usually estimated by the well-known cube-root rule:
the speed s a processor operates at is roughly proportional to the
cube-root of the power p, equivalently, p(s) = s^{3}.
For example, if we double the speed of the processor,
we can halve the time spent on a task but the power
consumption rate is increased eight times, and the
total energy needed is therefore increased by four times.
At the first glance, one may think that
the problem can be solved by operating the processor
as slow as possible.
Unfortunately, the problem is not so trivial since
there are usually other orthogonal objectives
which aim at providing some kind of quality of service,
like deadline feasibility, makespan (finish time),
response time, throughput.
Therefore, it is crucial that the right speed is used.
The scheduling algorithm, therefore, has to determine the
speed at which the processor should run at every time unit,
this is known as dynamic speed-scaling (DVS)
or dynamic voltage scaling.

Classical job scheduling schedules jobs on processors running at the same speed throughout and the decision to be made is which task to run at each time unit. With DVS, the scheduling algorithm also has to determine the speed at which the processor runs. We consider both the off-line version and the on-line version of the problem with different optimization objectives like minimizing total energy consumption while completing all jobs by deadlines, minimizing total energy plus response time, etc.

Power management is not only important to conserve energy but also to reduce temperature. Temperature is important because the processor's life time can be severely shortened if a processor exceeds its thermal threshold. Therefore, it is wise to use multiprocessor to provide high processing power while keeping temperature of each processor low. In this respect, a low-cost option is to use GPU - General Purpose Graphical Processing Unit. The main question is how to ensure energy efficient computation on GPU.

Additional information (Top)

- Related Grants:
**EPSRC Small Scale Equipment Grants**- Energy Efficient Algorithms (**P Wong**) - part of the EPSRC Small Scale Equipment Grant awarded to University of Liverpool**Coleman-Cohen Grant**- Travel grant for visiting Prof Shmuel Zaks in Technion, Israel**British Council UK-Tel Hai Academic Research Scheme**(PI:**P Wong**, M Shalom, CoI: D Kowalski, S Zaks)**Royal Society Conference Grant**- for ACM Symposium on Parallelism in Algorithms and Architectures SPAA 2008**Coleman-Cohen Grant**- Travel grant for visiting Prof Shmuel Zaks in Technion, Israel**EPSRC Grant**- Algorithmic Issues in Power Management by Speed Scaling (APM)**The Nuffield Foundation - Awards to Newly Appointed Lecturers**, on Algorithmic Issues on Effective Real-time Data Dissemination to Massive Clients - Current Team Members:

Fencol C.C. Yung, Thomas Carroll, Alison Hsiang-Hsuan Liu, Fu-Hong Liu - Past Team Members:

Paul Bell, Isaac Kar-Keung To, Mihai Burcea, Jieming Ma, Sheng Yu

Publications (Journals and Conferences): (Top)

Full publications see DBLP

- Scheduling for Electricity Cost in Smart Grid.

Accepted to Journal of Scheduling (JoS), to appear. [Download paper (pdf)] [From Springer] - Pairwise Sequence Alignment with Gaps with GPU

Accepted to Proceedings of IEEE Cluster 2015 - sth International Workshop on Heterogenous and Unconventional Cluster Architectures and Applications (HUCAA), 2015, to appear. - Online Nonpreemptive Scheduling for Electricity Cost in Smart Grid.

The 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2015. - Multiprocessor Speed Scaling for Jobs
with Arbitrary Sizes and Deadlines.

Journal of Combinatorial Optimization (JoCO), 29(4) 739--749, 2015. [Download paper (pdf)] [From Springer] - Optimizing Busy Time on Parallel Machines

Theoretical Computer Science (TCS), 562, 524--541, 2015. [From ScienceDirect] - Online Optimization of Busy Time on Parallel Machines

Invited to Theoretical Computer Science (TCS), 560, 190--206, 2014. [Download paper (pdf)] [From ScienceDirect] - Scheduling for Electricity Cost in Smart Grid.

Proceedings of the 7th International Conference of Combinatorial Optimization and Applications (COCOA), 2013, pp. 306--317. [Download paper (pdf)] [From Springer] - Online Speed Scaling Based on Active Job Count to Minimize Flow plus Energy.

Algorithmica, 65:3, 605--633, 2013. [Download paper (pdf)] [From Springer] - Interval Scheduling to Maximize Bandwidth Provision.

The 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2013. [Download paper (pdf)] - Energy-efficient Flow Time Scheduling: An Experimental Study.

The 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2013. [Download paper (pdf)] - Online Optimization of Busy Time on Parallel Machines

Proceedings of the 9th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2012, pp. 448--460. [Download paper (pdf)] [From Springer] - Optimizing Busy Time on Parallel Machines

Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2012, pp. 238--248. [Download paper (pdf)] [From IEEE] - Improved Multi-processor Scheduling for Flow Time and Energy.

Journal of Scheduling (JoS), 15(1):105--116, 2012. [Download paper (pdf)] [From Springer] - Multiprocessor Speed Scaling for Jobs
with Arbitrary Sizes and Deadlines.

Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2011, pp. 27--36. [Download paper (pdf)] [From Springer] - Deadline Scheduling and
Power Management for Speed Bounded Processors.

Theoretical Computer Science (TCS), 411:40-42, pp. 3587--3600, 2010. [Download paper (pdf)] [From ScienceDirect] - Optimizing Throughput and Energy in Online Deadline Scheduling.

Transactions on Algorithms (TALG), 6(1):10, 2009. [Download paper (pdf)] [From ACM] - Sleep with Guilt and Work Faster to
Minimize Flow plus Energy.

Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), 2009, 665--676. [Download paper (pdf)] [From Springer] - Deadline Scheduling and Power
Management for Speed Bounded Processors.

The 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2009, pp. 82--84. [Download paper (pdf)] - Multiprocessor Speed Scaling for Jobs
with Arbitrary Sizes and Deadlines.

The 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2009, pp. 44--46. [Download paper (pdf)] - Non-migratory Multi-processor Scheduling
for Response Time and Energy.

IEEE Transactions on Parallel and Distributed Systems (TPDS) Special Issue on Power-Aware Parallel and Distributed Systems, 19(11):1527-1539, 2008. [Download paper (ps)] [From IEEE] - Improved On-line Broadcast
Scheduling with Deadlines.

Journal of Scheduling (JoS), 11(4):299-308, 2008. [From Springer] - Speed Scaling Functions
for Flow Time Scheduling Based on Active Job Count.

Proceedings of the 16th Annual European Symposium on Algorithms (ESA), 2008, pp. 647--659. [Download paper (pdf)] [From Springer] - Competitive Non-migratory Scheduling for Flow Time and Energy.

Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2008, pp. 256--264. [Download paper (pdf)] [From ACM] - Energy Efficient Deadline Scheduling
in Two Processor Systems.

Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), 2007, pp. 476--487. [Download paper (pdf)] - Online Deadline Scheduling with Bounded Energy Efficiency.

Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2007, 416--427. [Download paper (pdf)] [From Springer] - Energy Efficient Online Deadline Scheduling.

Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, pp. 795--804. [Download paper (ps)] [From ACM]

Maintained by Prudence Wong