Title :
Automated techniques for energy efficient scheduling on homogeneous and heterogeneous chip multi-processor architectures
Author :
Zhang, Sushu ; Chatha, Karam S.
Author_Institution :
Arizona State Univ., Tempe
Abstract :
We address performance maximization of independent task sets under energy constraint on chip multi-processor (CMP) architectures that support multiple voltage/frequency operating states for each core. We prove that the problem is strongly NP-hard. We propose polynomial time 2-approximation algorithms for homogeneous and heterogeneous CMPs. To the best of our knowledge, our techniques offer the tightest bounds for energy constrained design on CMP architectures. Experimental results demonstrate that our techniques are effective and efficient under various workloads on several CMP architectures.
Keywords :
computational complexity; computer architecture; microprocessor chips; power aware computing; processor scheduling; NP-hard; energy efficient scheduling; heterogeneous chip multi-processor architectures; homogeneous chip multi-processor architectures; polynomial time 2-approximation algorithms; Approximation algorithms; Computer architecture; Computer science; Dynamic voltage scaling; Energy consumption; Energy efficiency; Frequency; Polynomials; Portable computers; Processor scheduling;
Conference_Titel :
Design Automation Conference, 2008. ASPDAC 2008. Asia and South Pacific
Conference_Location :
Seoul
Print_ISBN :
978-1-4244-1921-0
Electronic_ISBN :
978-1-4244-1922-7
DOI :
10.1109/ASPDAC.2008.4484026