Fast post-placement rewiring using easily detectable functional symmetries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast post-placement rewiring using easily detectable functional symmetries

Full text

Pdf (59 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 37th Annual Design Automation Conference table of contents

Los Angeles, California, United States

Pages: 286 - 289

Year of Publication: 2000

ISBN:1-58113-187-9

Authors

Chih-Wei Chang	Dept. of Electrical and Computer Engineering, University of California, Santa Barbara, Santa Barbara, CA
Chung-Kuan Cheng	Dept. of Computer Science and Engineering, University of California, San Diego, La Jolla, CA
Peter Suaris	Mentor Graphics Corporation, Wilsonville, Oregon
Malgorzata Marek-Sadowska	Dept. of Electrical and Computer Engineering, University of California, Santa Barbara, Santa Barbara, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 13, Citation Count: 9

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/337292.337420 What is a DOI?

ABSTRACT

Timing convergence problem arises when the estimations made during logic synthesis can not be met during physical design. In this paper, an efficient rewiring engine is proposed to explore maximal freedom after placement. The most important feature of this approach is that the existing placement solution is left intact throughout the optimization. A linear time algorithm is proposed to detect functional symmetries in the Boolean network and is used as the basis for rewiring. Integration with an existing gate sizing algorithm further proves the effectiveness of our technique. Experimental results are very promising.

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	R. Brayton, G. Hachtel, and A. Sangiovanni-Vincentelli, "Multilevel Logic Synthesis",Proc.IEEE,vol.78, pp.264-300, Feb. 1990.
	2	Olivier Coudert, Gate sizing for constrained delay/power/area optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.4, p.465-472, Dec. 1997 [doi>10.1109/92.645073]
	3	Yi-Min Jiang , Angela Krstic , Kwang-Ting Cheng , Malgorzata Marek-Sadowska, Post-layout logic restructuring for performance optimization, Proceedings of the 34th annual conference on Design automation, p.662-665, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266313]
	4	B. M. Riess and G. G. Ettlt, "Speed: Fast and efficient timing driven placement,", in IEEE International Symposium on Circuits and Systems, pp. 377-380, 1995
	5	I. Pomeranz and S. M. Reddy, "On determining symmetries in inputs of logic circuits", in IEEE Trans. on Computer-Aided Design, vol. 13, NO. 11, November, 1994
	6	J. P. Roth, "Diagnosis of automata failures: A calculus and a method," IBM J. Res. Develop., vol 10, pp. 278-291, July 1966.
	7	Subarnarekha Sinha , Robert K. Brayton, Implementation and use of SPFDs in optimizing Boolean networks, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.103-110, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288584]
	8	"SIS: A System for Sequential Circuit Synthesis", Report M92/ 41, University of California, Berkeley, May, 1992
	9	Kun-Han Tsai , Malgorzata Marek-Sadowska , Janusz Rajski, Star test: the theory and its applications, 1999

CITED BY 9

	C. Chang , B. Hu , M. Marek-Sadowska, In-place delay constrained power optimization using functional symmetries, Proceedings of the conference on Design, automation and test in Europe, p.377-382, March 2001, Munich, Germany
	Jason Cong , Yizhou Lin , Wangning Long, SPFD-based global rewiring, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA
	Chih-Wei Chang , Kai Wang , Malgorzata Marek-Sadowska, Layout-driven hot-carrier degradation minimization using logic restructuring techniques, Proceedings of the 38th conference on Design automation, p.97-102, June 2001, Las Vegas, Nevada, United States
	Chih-Wei Jim Chang , Malgorzata Marek-Sadowska, ATPG-based logic synthesis: an overview, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.786-789, November 10-14, 2002, San Jose, California
	Jason Cong , Joey Y. Lin , Wangning Long, A new enhanced SPFD rewiring algorithm, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.672-678, November 10-14, 2002, San Jose, California
	Chih-Wei Jim Chang , Malgorzata Marek-Sadowska, Who are the alternative wires in your neighborhood? (alternative wires identification without search), Proceedings of the 11th Great Lakes symposium on VLSI, p.103-108, March 2001, West Lafayette, Indiana, United States
	Jin S. Zhang , Alan Mishchenko , Robert Brayton , Malgorzata Chrzanowska-Jeske, Symmetry detection for large Boolean functions using circuit representation, simulation, and satisfiability, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Chih-Wei(Jim) Chang , Malgorzata Marek-Sadowska, Theory of wire addition and removal in combinational Boolean networks, Microelectronic Engineering, v.84 n.2, p.229-243, February, 2007
	Stephen M. Plaza , Igor L. Markov , Valeria Bertacco, Optimizing non-monotonic interconnect using functional simulation and logic restructuring, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA