Towards energy-performance trade-off analysis of parallel applications

"Energy consumption by computer systems has emerged as an important concern, both at the level of individual devices (limited battery capacity in mobile systems) and at the societal level (the production of Green House Gases). In parallel architectures, applications may be executed on a variable number of cores and these cores may operate at different frequencies. The performance and energy cost of a parallel algorithm executing on a parallel architecture have different trade-offs, depending on how many cores the algorithm uses, at what frequencies these cores operate, and the structure of the algorithm. The problem of defining metrics to quantify energy performance trade-offs was posed as an important open problem in a recent NSF workshop. Moreover, in a recent IEEE computer article, Krishna Kant argues that ""A formal understanding of energy and computation trade-offs will lead to significantly more energy-efficient hardware and software designs"". We believe that examining the relation between the performance of parallel applications and their energy requirements on parallel processors can be facilitated by analyzing a set of metrics, each for a different purpose. These metrics can provide programmers with intuitions about the energy required by different parallel applications, thus guiding the choice of algorithm, architecture, the number of cores to use and the frequency at which to operate them. Moreover, such metrics would help in the design of more energy efficient algorithms. Towards this goal, we introduce four energy-performance trade-off metrics namely: (a) energy consumption under fixed performance for energy conservation in time constrained applications, (b) energy bounded performance for improving performance in energy constrained applications, (c) energy efficiency for energy efficient computing, and (e) cost metric for reducing the monetary cost associated with running the application. We have considered the optimization problems (corresponding to the four metrics) for problem instances, represented as Directed Acyclic Graphs (DAGs), of parallel applications. Moreover, we extend the traditional notion of scalability to our energy-performance trade-off metrics and proposed corresponding scalability metrics. We propose methodologies to evaluate the scalability metrics, and illustrated them by analyzing different genre of algorithms such as low communication overhead (almost embarrassingly parallel) algorithms, dense matrix algorithms, sorting algorithms, graph based algorithms, and fast Fourier transform algorithms for a message passing model. We also consider a shared memory model (with memory hierarchy). Three algorithms namely, addition, prefix sums and Cole's mergesort are analyzed for this shared memory model."

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2012

Author dc:creator

• Korthikanti, Vijay Anand

Contributors dc:contributor

• Agha, Gul A.
• Kale, Laxmikant V.
• Gazaran, Maria
• Greenstreet, Mark

• Energy
• Performance
• Parallel applications
• Scheduling
• Scalability metrics

Statement dc:rights

• Copyright 2011 Vijay Anand R. Korthikanti

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/29681

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/29681