Simultaneous depth and area minimization in LUT-based FPGA mapping

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simultaneous depth and area minimization in LUT-based FPGA mapping

Full text

Pdf (72 KB)

Source

International Symposium on Field Programmable Gate Arrays archive
Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays table of contents

Monterey, California, United States

Pages: 68 - 74

Year of Publication: 1995

ISBN:0-89791-743-X

Authors

Jason Cong	Department of Computer Science, University of California, Los Angeles, CA
Yean-Yow Hwang	Department of Computer Science, University of California, Los Angeles, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 37, Citation Count: 28

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

ABSTRACT

In this paper, we present an improvement of the FlowMap algorithm, named CutMap, which combines depth and area minimization during the mapping process by computing min-cost min-height K-feasible cuts for critical nodes for depth minimization and computing min-cost K-feasible cuts for non-critical nodes for area minimization. CutMap guarantees depth-optimal mapping solutions in polynomial time as the FlowMap algorithm but uses considerably fewer K-Luts. We have implemented CutMap and tested it on the MCNC logic synthesis benchmarks. For depth-optimal mapping solutions, CutMap uses 15% fewer K-LUTs than FlowMap. We also tested CutMap followed by the depth relaxation routines in FlowMap_r algorithm, which achieves area minimization by depth relaxation. CutMap followed FlowMap_r performs better than FlowMap_r.

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.

	BrRS87	Brayton, R. K., R. Rudell, and A. L. Sangiovanni-Vincentelli, "MIS: A Multiple- Level Logic Optimization," IEEE Transactions on CAD, pp. 1062-1081, Nov. 1987.
	ChCD92	Kuang-Chien Chen , Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar, DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization, IEEE Design & Test, v.9 n.3, p.7-20, July 1992 [doi>10.1109/54.156154]
	CoDi93b	Jason Cong , Yuzheng Ding, Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.110-114, November 07-11, 1993, Santa Clara, California, United States
	CoDi94a	Cong, J. and Y. Ding, "An Optimal Technology Mapping Algorithm fo Delay Optimization in Lookup-Table Based FPGA Designs," IEEE Trans. on Computer-Aided Design, Vol. 13, pp. 1-12, Jan. 1994.
	CoDi94b	Cong, J. and Y. Ding, "On Area/Depth Tradeoff in LUT-Based FPGA Technology Mapping," IEEE Trans. on VLSI Systems, Vol. 2, June 1994.
	CoHw95	Cong, J. and Y.-Y. Hwang, "Simultaneous Depth and Area Minimization in LUT-based FPGA Mapping," in UCLA Computer Science Department Technical Report CSD-950001, , Los Angeles, CA (January 1995).
	CoLB94	Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196609]
	FaMa93	Farrahi, A. and M. Sarrafzadeh, "On the Lookup-Table Minimization Problem for FPGA Technology Mapping," in Tech. Report 93-AC-102, , Department of EECS, Northwestern University (July 1993).
	FrRC90	Robert J. Francis , Jonathan Rose , Kevin Chung, Chortle: a technology mapping program for lookup table-based field programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.613-619, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123418]
	FrRV91b	Francis, R. J., J. Rose, and Z. Vranesic, "Technology Mapping for Delay Optimization of Lookup Table-Based FPGAs," MCNC Logic Synthesis Workshop, 1991.
	Ka91a	Kevin Karplus, Xmap: A technology mapper for table-lookup field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.240-243, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127672]
	LaPV93	Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165078]
	MuNS90	Rajeev Murgai , Yoshihito Nishizaki , Narendra Shenoy , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic synthesis for programmable gate arrays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.620-625, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123421]
	MuSB91	Murgai, R., N. Shenoy, R. K. Brayton, and A. S angiov anni- V inc ente lli, ' 'Performance Directed Synthesis for Table Look Up Programmable Gate Arrays," Prec. IEEE Int'l Conf. on Computer-Aided Design, pp. 572- 575, Nov. 1991.
	ScKC92	Martine D. F. Schlag , Jackson Kong , Pak K. Chan, Routability-Driven Techology Mapping for LookUp-Table-Based FPGAs, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.86-90, October 11-14, 1992

CITED BY 29

	Jason Cong , Kenneth Yan, Synthesis for FPGAs with embedded memory blocks, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.75-82, February 10-11, 2000, Monterey, California, United States
	Jason Cong , Yean-Yow Hwang, Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA design, Proceedings of the 33rd annual conference on Design automation, p.726-729, June 03-07, 1996, Las Vegas, Nevada, United States
	Yu Hu , Victor Shih , Rupak Majumdar , Lei He, FPGA area reduction by multi-output function based sequential resynthesis, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Alan Mishchenko , Sungmin Cho , Satrajit Chatterjee , Robert Brayton, Combinational and sequential mapping with priority cuts, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	David Sheldon , Frank Vahid, A pipelined binary tree as a case study on designing efficient circuits for an FPGA in a bram aware design, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA
	Andy Yan , Rebecca Cheng , Steven J. E. Wilton, On the sensitivity of FPGA architectural conclusions to experimental assumptions, tools, and techniques, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA
	David Sheldon , Frank Vahid, Don't forget memories: a case study redesigning a pattern counting ASIC circuit for FPGAs, Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis, October 19-24, 2008, Atlanta, GA, USA
	H.-G. Martin , W. Rosenstiel, A comparing study of technology mapping for FPGA, Proceedings of the conference on Design, automation and test in Europe, p.939-940, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Taiga Takata , Yusuke Matsunaga, An efficient cut enumeration for depth-optimum technology mapping for LUT-based FPGAs, Proceedings of the 19th ACM Great Lakes symposium on VLSI, May 10-12, 2009, Boston Area, MA, USA
	Darko Kirovski , Yean-Yow Hwang , Miodrag Potkonjak , Jason Cong, Intellectual property protection by watermarking combinational logic synthesis solutions, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.194-198, November 08-12, 1998, San Jose, California, United States
	Julien Lamoureux , Steven J. E. Wilton, On the Interaction Between Power-Aware FPGA CAD Algorithms, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.701, November 09-13, 2003
	Zhi-Hong Wang , En-Cheng Liu , Jianbang Lai , Ting-Chi Wang, Power minization in LUT-based FPGA technology mapping, Proceedings of the 2001 conference on Asia South Pacific design automation, p.635-640, January 2001, Yokohama, Japan
	Hao Li , Srinivas Katkoori , Wai-Kei Mak, Power minimization algorithms for LUT-based FPGA technology mapping, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.1, p.33-51, January 2004
	Gang Chen , Jason Cong, Simultaneous logic decomposition with technology mapping in FPGA designs, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.48-55, February 2001, Monterey, California, United States
	Taiga Takata , Yusuke Matsunaga, Area recovery under depth constraint by cut substitution for technology mapping for LUT-based FPGAs, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Jason Cong , Chang Wu, FPGA synthesis with retiming and pipelining for clock period minimization of sequential circuits, Proceedings of the 34th annual conference on Design automation, p.644-649, June 09-13, 1997, Anaheim, California, United States
	Joey Y. Lin , Ashok Jagannathan , Jason Cong, Placement-driven technology mapping for LUT-based FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	Jason Cong , Yean-Yow Hwang, Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.193-225, April 2000
	Jason Cong , John Peck , Yuzheng Ding, RASP: a general logic synthesis system for SRAM-based FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.137-143, February 11-13, 1996, Monterey, California, United States
	M. Teslenko , E. Dubrova, Hermes: LUT FPGA technology mapping algorithm for area minimization with optimum depth, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.748-751, November 07-11, 2004
	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
	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
	Jason Cong , Kirill Minkovich, Optimality study of logic synthesis for LUT-based FPGAs, Proceedings of the internation symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA
	Yan Lin , Lei He, Stochastic physical synthesis for FPGAs with pre-routing interconnect uncertainty and process variation, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA
	L. JóŹwiak , A. Chojnacki, Effective and efficient FPGA synthesis through general functional decomposition, Journal of Systems Architecture: the EUROMICRO Journal, v.49 n.4-6, p.247-265, September 2003
	Yan Lin , Lei He , Mike Hutton, Stochastic physical synthesis considering prerouting interconnect uncertainty and process variation for FPGAs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.2, p.124-133, February 2008
	Hao Li , Wai-Kei Mak , Srinivas Katkoori, Efficient LUT-based FPGA technology mapping for power minimization, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	D. Chen , J. Cong, DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.752-759, November 07-11, 2004
	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