Effective graph theoretic techniques for the generalized low power binding problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Effective graph theoretic techniques for the generalized low power binding problem

Full text

Pdf (165 KB)

Source

International Symposium on Low Power Electronics and Design archive
Proceedings of the 2003 international symposium on Low power electronics and design table of contents

Seoul, Korea

SESSION: Advances in low power synthesis table of contents

Pages: 152 - 157

Year of Publication: 2003

ISBN:1-58113-682-X

Authors

Azadeh Davoodi	University of Maryland, College Park, MD
Ankur Srivastava	University of Maryland, College Park, MD

Sponsors

ACM: Association for Computing Machinery
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 6, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/871506.871544 What is a DOI?

ABSTRACT

This paper proposes two very fast graph theoretic heuristics for the low power binding problem given fixed number of resources and multiple architectures for the resources. First the generalized low power binding problem is formulated as an Integer Linear Programming(ILP) problem which happens to be an NP-complete task to solve. Then two polynomial-time heuristics are proposed that provide a speedup of up to 13.7 with an extremely low penalty for power when compared to the optimal ILP solution for our selected benchmarks.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Raghunathan and N. Jha. "An ILP Formulation for Low Power Based on Minimizing Switched Capacitance During Datapath Allocation ". In Procs of IEEE Symposium on Circuits and Systems 1995.
	2	Ankur Srivastava , Majid Sarrafzadeh, Predictability: definition, ananlysis and optimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.118-121, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774589]
	3	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
	4	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]
	5	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]
	6	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

CITED BY 2

	Rajarshi Mukherjee , Seda Ogrenci Memik , Gokhan Memik, Peak temperature control and leakage reduction during binding in high level synthesis, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA
	Min Ni , Seda Ogrenci Memik, Thermal-induced leakage power optimization by redundant resource allocation, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California