Early evaluation techniques for low power binding

ABSTRACT

This paper presents effective metrics to evaluate the power dissipation of scheduled data flow graphs (DFGs). This enables early evaluation of schedules without performing the computationally expensive resource-binding step. Our metrics correlate heavily (as high as 0.95 and > 0.75 for most test cases) with power dissipation values obtained after resource binding and rescheduling for power optimization steps. An experimental flow that integrates path-based scheduling, power optimal binding and power driven iterative rescheduling stages is constructed. The flow integrates commercial tools like Synopsys, VSS and academic compilers like SUIF in a common optimization framework. Experimental results on DFGs from MediaBench suit also demonstrate the fact that metric evaluation is on average 42.6 times faster than performing optimal binding and iterative power improvement. Hence metric based evaluation enables fast design exploration at early stages.

REFERENCES

• 1: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]
• 2: Chun Gi Lyuh , Taewhan Kim , C. L. Liu, An integrated data path optimization for low power based on network flow method, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 3: David Ku , Gionvanni De Micheli, Relative scheduling under timing constraints, Proceedings of the 27th ACM/IEEE conference on Design automation, p.59-64, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123227]
• 4: Lars Kruse , Eike Schmidt , Gerd Jochens , Ansgar Stammermann , Arne Schulz , Enrico Macii , Wolfgang Nebel, Estimation of lower and upper bounds on the power consumption from scheduled data flow graphs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.1, p.3-15, Feb. 2001 [doi>10.1109/92.920813]
• 5: Aurobindo Dasgupta , Ramesh Karri, Simultaneous scheduling and binding for power minimization during microarchitecture synthesis, Proceedings of the 1995 international symposium on Low power design, p.69-74, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224094]
• 6: Dasgupta A., and Karri R., High-Reliability, Low Energy Microarchitecture Synthesis, IEEE, TCAD, 1998.
• 7: Hu T.C., Parallel Sequencing and Assembly Line Problems, Operations Research, No. 9, pp. 841--848, 1961.
• 8: Paulin P., Knight J., Force Directed Scheduling for the Behavioral Synthesis of ASIC's, IEEE Transactions on CAD, Vol. 8, No. 6, pp. 661--679, 1989.
• 9: Potasman R., Lis J., Nicolau A., Gajski D., Percolation Based Scheduling, Design Automation Conference, (DAC), 1990.
• 10: Camposano R., Path-based Scheduling for Synthesis, IEEE Transactions on CAD, Vol. 10, No. 1, pp. 85--93, 1990.
• 11: S. Ogrenci Memik , E. Bozorgzadeh , R. Kastner , M. Sarrafzadeh, A super-scheduler for embedded reconfigurable systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 12: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 13: SUIF.<http://suif.stanford.edu>.
• 14: Anand Raghunathan , Niraj K. Jha, An iterative improvement algorithm for low power data path synthesis, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.597-602, November 05-09, 1995, San Jose, California, United States
• 15: Catherine H. Gebotys, Low energy memory and register allocation using network flow, Proceedings of the 34th annual conference on Design automation, p.435-440, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266192]
• 16: Sungpack Hong , Taewhan Kim, Bus optimization for low-power data path synthesis based on network flow method, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California

INDEX TERMS

General Terms:
Design

Keywords:
low power design, metric evaluation, resource binding, scheduling