Files in this item



application/pdfKorthikanti_VijayAnand.pdf (4MB)
(no description provided)PDF


Title:Towards energy-performance trade-off analysis of parallel applications
Author(s):Korthikanti, Vijay Anand
Director of Research:Agha, Gul A.
Doctoral Committee Chair(s):Agha, Gul A.
Doctoral Committee Member(s):Kale, Laxmikant V.; Gazaran, Maria; Greenstreet, Mark
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Parallel applications
Scalability metrics
Abstract: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.
Issue Date:2012-02-06
Rights Information:Copyright 2011 Vijay Anand R. Korthikanti
Date Available in IDEALS:2012-02-06
Date Deposited:2011-12

This item appears in the following Collection(s)

Item Statistics