Paper Info
Title
Heuristics and Evaluations of Energy-Aware Task Mapping on Heterogeneous Multiprocessors
Abstract
On various heterogeneous multiprocessor platforms, it is necessary to optimize the throughput and the energy consumption. The problem of optimally mapping tasks onto a set of given heterogeneous processors for minimum overall completion time has been known, in general, to be NP-complete. The energy consumption of a task may be very different in heterogeneous processors. However, if the most energy-efficient processor for each task is always chosen in the task mapping, the completion time of a set of tasks may grow wildly in the worst case. DVS (Dynamic Voltage Scaling) technique is currently available in a larger number of processors to effectively reduce dynamic power dissipation and consequently to save a proportion of total energy consumption, but meanwhile the execution time of a task running in lower voltage definitely becomes longer. Hence, the task mapping problem in terms of time, energy and voltage turns more complicated and harder to solve along with the heterogeneity. Moreover, today most processors only support discrete DVS and thus the optimization problem tends to be Integer Linear Programming problems for which, as we know, there is no polynomial time algorithm unless P = NP. In this paper we formulate and study the optimization problem of reducing overall completion time and the total energy consumption, and then some heuristics, which are experimentally evaluated and compared.
Year
DOI
Venue
2011
10.1109/IPDPS.2011.209
IPDPS Workshops
Keywords
Field
DocType
execution time,power aware computing,dynamic voltage scaling technique,task energy consumption,energy-aware task mapping,overall completion time,heterogeneous processor,integer programming,np-complete problem,total energy consumption,completion time,linear programming,integer linear programming,multiprocessing systems,polynomial time algorithm,optimization problem,computational complexity,heterogeneous multiprocessors,energy consumption,heterogeneous multiprocessor platform,minimum overall completion time,optimally mapping task,dynamic power dissipation,optimization,np complete problem,schedules,power dissipation,energy efficient
Dynamic voltage scaling,Mathematical optimization,Computer science,Parallel computing,Integer programming,Heuristics,Linear programming,Time complexity,Energy consumption,Optimization problem,Computational complexity theory
Conference
ISSN
ISBN
Citations 
1530-2075 E-ISBN : 978-0-7695-4577-6
978-0-7695-4577-6
8
PageRank 
References 
Authors
0.52
13
2
Name
Order
Citations
PageRank
SUN Wei124726.63
Tomoyoshi Sugawara2132.40