Delay-optimal technology mapping by DAG covering

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Delay-optimal technology mapping by DAG covering

Full text

Pdf (201 KB)

Source

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

San Francisco, California, United States

Pages: 348 - 351

Year of Publication: 1998

ISBN:0-89791-964-5

Authors

Yuji Kukimoto	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA
Robert K. Brayton	Department of Electrical Engineering and Computer Sciences University of California, Berkeley, CA
Prashant Sawkar	Strategic CAD Laboratories, Intel Corporation, Hillsboro, OR

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 53, Citation Count: 25

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

ABSTRACT

We propose an algorithm for minimal-delay technology mapping for library-based designs. We show that subject graphs need not be decomposed into trees for delay minimization; they can be mapped directly as DAGs. Experimental results demonstrate that significant delay improvement is possible by this new approach.

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	Jason Cong , Yuzheng Ding, An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.48-53, November 1992, Santa Clara, California, United States
	2	J. Cong and Y. Ding. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Transactions on Computer-Aided Design, 13( 1): 1-12, January 1994.
	3	J. Cong and Y. Ding. On area/depth trade-off in LUT-based FPGA technologymapping. IEEE Ttrmsactions on VLSI Systems, 2(2): 137- 148, June 1994.
	4	Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996 [doi>10.1145/233539.233540]
	5	Jason Cong , Chang Wu, An Improved Algorithm for Performance Optimal Technology Mapping with Retiming in LUT-Based FPGA Desig, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.572-578, October 07-09, 1996
	6	A. Farrahi and M. Sarrafzadeh. Complexity of the lookup-table minimization problem for FPGA technology mapping.lEEE Transactions on Computer-AidedDesign, 13( 11): 13 19-1332, November 1994.
	7	K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
	8	K. Keutzer and D. Richards. Computational complexity of logic synthesis and optimization. InProcee~ngs of International Workshop on Log/c Syntbes/s, May 1989.
	9	Eric Lehman , Yosinori Watanabe , Joel Grodstein , Heather Harkness, Logic decomposition during technology mapping, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.264-271, November 05-09, 1995, San Jose, California, United States
	10	I. Levin and R. Y. Pinter. Realizing expression graphs using tablelookup FPGAs. In Proceedings of the Ewopean Design Automation Conferen~, pages 306-3 11, September 1993.
	11	Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, Proceedings of the 33rd annual conference on Design automation, p.720-725, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240655]
	12	R. Rudell. Logic synthesis for VLSI design. Technical Report UCB/ERL M89/49, University of California, Berkeley, April 1989.
	13	H. J. Touati. Performance-oriented technology mapping. Technical Report UCB/ERL M90/109, University of California, Berkeley, November 1990.
	14	Y. Watanabe. Private communication, October 1997.

CITED BY 25

	Henk Corporaal , Johan Janssen , Marnix Arnold, Computation in the Context of Transport Triggered Architectures, International Journal of Parallel Programming, v.28 n.4, p.401-427, August 2000
	Dirk-Jan Jongeneel , Yosinori Watanbe , Robert K. Brayton , Ralph Otten, Area and search space control for technology mapping, Proceedings of the 37th conference on Design automation, p.86-91, June 05-09, 2000, Los Angeles, California, United States
	Marnix Arnold , Henk Corporaal, Automatic detection of recurring operation patterns, Proceedings of the seventh international workshop on Hardware/software codesign, p.22-26, March 1999, Rome, Italy
	Jovanka Ciric , Gin Yee , Carl Sechen, Delay minimization and technology mapping of two-level structures and implementation using clock-delayed domino logic, Proceedings of the conference on Design, automation and test in Europe, p.277-282, March 27-30, 2000, Paris, France
	Ralph H. J. M. Otten, Global wires: harmful?, Proceedings of the 1998 international symposium on Physical design, p.104-109, April 06-08, 1998, Monterey, California, United States
	Ralph H. J. M. Otten , Robert K. Brayton, Planning for performance, Proceedings of the 35th annual conference on Design automation, p.122-127, June 15-19, 1998, San Francisco, California, United States
	Leon Stok , Vivek Tiwari, Technology mapping, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Rajeev Murgai, Technology-based transformations, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Rajeev Murgai, Performance optimization under rise and fall parameters, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.185-190, November 07-11, 1999, San Jose, California, United States
	Tyler J. Thorp , Gin S. Yee , Carl M. Sechen, Design and synthesis of dynamic circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.141-149, February 2003
	Min Zhao , Sachin S. Sapatnekar, Technology mapping algorithms for domino logic, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.2, p.306-335, April 2002
	Arlindo L. Oliveira , Rajeev Murgai, An exact gate assignment algorithm for tree circuits under rise and fall delays, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Vinícius Correia , André Reis, Advanced technology mapping for standard-cell generators, Proceedings of the 17th symposium on Integrated circuits and system design, September 07-11, 2004, Pernambuco, Brazil
	Rupesh S. Shelar , Prashant Saxena , Xinning Wang , Sachin S. Sapatnekar, An efficient technology mapping algorithm targeting routing congestion under delay constraints, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Bo Hu , Yosinori Watanabe , Alex Kondratyev , Malgorzata Marek-Sadowska, Gain-based technology mapping for discrete-size cell libraries, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Ashish Kumar Singh , Murari Mani , Ruchir Puri , Michael Orshansky, Gain-based technology mapping for minimum runtime leakage under input vector uncertainty, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Chi-Shong Wang , Chingwei Yeh, Performance-driven technology mapping with MSG partition and selective gate duplication, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.4, p.953-973, October 2006
	Hosung (Leo) Kim , John Lillis , Miloš Hrkić , Miloš Hrkić, Techniques for improved placement-coupled logic replication, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
	Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, DAG-aware AIG rewriting a fresh look at combinational logic synthesis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	F. S. Marques , L. S. Rosa, Jr. , R. P. Ribas , S. S. Sapatnekar , A. I. Reis, DAG based library-free technology mapping, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	S. K. Karandikar , S. S. Sapatnekar, Logical effort based technology mapping, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.419-422, November 07-11, 2004
	S. Chatterjee , A. Mishchenko , R. Brayton , X. Wang , T. Kam, Reducing structural bias in technology mapping, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.519-526, November 06-10, 2005, San Jose, CA
	Leon Stok , Mahesh A. Iyer , Andrew J. Sullivan, Wavefront technology mapping, Proceedings of the conference on Design, automation and test in Europe, p.108-es, January 1999, Munich, Germany
	Ryan Mannion , Harry Hsieh , Susan Cotterell , Frank Vahid, System Synthesis for Networks of Programmable Blocks, Proceedings of the conference on Design, Automation and Test in Europe, p.888-893, March 07-11, 2005
	Hosung (Leo) Kim , John Lillis, A framework for layout-level logic restructuring, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA