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 energycost 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.

[效力级别] Performance

[关键词] Energy;Performance;Parallel applications;Scheduling;Scalability metrics