TY - JOUR
T1 - Integer linear programming and heuristic techniques for system-level low power scheduling on multiprocessor architectures under throughput constraints
AU - Srinivasan, Krishnan
AU - Chatha, Karam S.
N1 - Funding Information:
The research presented in this paper was supported in part by a grant from the National Science Foundation (CNS-0509540) and Consortium of Embedded Systems.
PY - 2007/4
Y1 - 2007/4
N2 - The increased complexity and performance requirements of embedded systems has led to the advent of programmable multiprocessor architectures. The paper presents system-level design techniques for minimizing the power consumption of throughput constrained periodic applications (such as multimedia and network processing) that are mapped to multiprocessor architectures. The paper discusses several design techniques that integrate dynamic voltage scaling (DVS) along with loop transformations (pipelining and unrolling), and apply dynamic power management (DPM) as the final design step. The paper presents an optimal mixed-integer linear programming (MILP) formulation along with three modifications that trade-off solution quality for reduced run times. The paper also presents a heuristic technique along with deterministic (LPPWUdet) and simulated annealing based (LPPWUsa) optimization strategies for solving the system-level low power design problem. The proposed techniques are evaluated by extensive experimentation with multimedia applications (MPEG-1 decoder, JPEG decoder, MP3 encoder), and synthetic taskgraphs (with 10-40 nodes). The proposed techniques are compared with two existing strategies that apply (i) loop pipelining (FP) with DPM but no DVS, and (ii) DVS and DPM but no loop transformations (LPS [Luo, Jha, Power conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems, Proceedings of the International Conference on Computer Aided Design, November 2000]), respectively. The optimal MILP formulation, LPPWUdet and LPPWUsa give an average power reduction of 50.68 %, 48.57 % and 49.23 %, respectively, for multimedia applications when compared against FP. While all our techniques are able to satisfy the performance constraints for JPEG and MPEG-1 decoding applications, the LPS technique fails in many cases. Further, the results produced by our deterministic and simulated annealing based techniques for multimedia benchmarks are on an average within 8.04% and 2.75%, respectively, of the optimum solution produced by the MILP based approach. The experimentation with large synthetic taskgraphs demonstrate that the run times of the heuristic techniques scale very well.
AB - The increased complexity and performance requirements of embedded systems has led to the advent of programmable multiprocessor architectures. The paper presents system-level design techniques for minimizing the power consumption of throughput constrained periodic applications (such as multimedia and network processing) that are mapped to multiprocessor architectures. The paper discusses several design techniques that integrate dynamic voltage scaling (DVS) along with loop transformations (pipelining and unrolling), and apply dynamic power management (DPM) as the final design step. The paper presents an optimal mixed-integer linear programming (MILP) formulation along with three modifications that trade-off solution quality for reduced run times. The paper also presents a heuristic technique along with deterministic (LPPWUdet) and simulated annealing based (LPPWUsa) optimization strategies for solving the system-level low power design problem. The proposed techniques are evaluated by extensive experimentation with multimedia applications (MPEG-1 decoder, JPEG decoder, MP3 encoder), and synthetic taskgraphs (with 10-40 nodes). The proposed techniques are compared with two existing strategies that apply (i) loop pipelining (FP) with DPM but no DVS, and (ii) DVS and DPM but no loop transformations (LPS [Luo, Jha, Power conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems, Proceedings of the International Conference on Computer Aided Design, November 2000]), respectively. The optimal MILP formulation, LPPWUdet and LPPWUsa give an average power reduction of 50.68 %, 48.57 % and 49.23 %, respectively, for multimedia applications when compared against FP. While all our techniques are able to satisfy the performance constraints for JPEG and MPEG-1 decoding applications, the LPS technique fails in many cases. Further, the results produced by our deterministic and simulated annealing based techniques for multimedia benchmarks are on an average within 8.04% and 2.75%, respectively, of the optimum solution produced by the MILP based approach. The experimentation with large synthetic taskgraphs demonstrate that the run times of the heuristic techniques scale very well.
KW - Dynamic power management
KW - Dynamic voltage scaling
KW - Lowpower design
UR - http://www.scopus.com/inward/record.url?scp=33947372104&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33947372104&partnerID=8YFLogxK
U2 - 10.1016/j.vlsi.2006.01.001
DO - 10.1016/j.vlsi.2006.01.001
M3 - Article
AN - SCOPUS:33947372104
SN - 0167-9260
VL - 40
SP - 326
EP - 354
JO - Integration, the VLSI Journal
JF - Integration, the VLSI Journal
IS - 3
ER -