Logic synthesis for programmable gate arrays

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Logic synthesis for programmable gate arrays

Full text

Pdf (914 KB)

Source

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

Orlando, Florida, United States

Pages: 620 - 625

Year of Publication: 1991

ISBN:0-89791-363-9

Authors

Rajeev Murgai	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA
Yoshihito Nishizaki	Kawasaki Steel Corporation, Tokyo, Japan and Department of Electrical Engineering and Computer Sciences University of California, Berkeley, CA
Narendra Shenoy	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
Alberto Sangiovanni-Vincentelli	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 27, Citation Count: 59

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

ABSTRACT

The problem of combinational logic synthesis is addressed for two interesting and popular classes of programmable gate array architectures: table-look-up and multiplexor-based. The constraints imposed by some of these architectures require new algorithms for minimization of the number of basic blocks of the target architecture, taking into account the wiring resources.

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	Xilinx Programmable Gate Array User's Guide. 1988 Xilinx, Irtc.
	2	A.Gamal, J. Greene, J. Reyneri, E. Rogoyski, K. A. EI-Ayat, and A. Mohsen, "An Architecture for Electrically Configurable Gate Arrays", IEEE Journal of Solid State Circuits, Vol.24, No. 2, April 1989, pp 394-398.
	3	Act 1 Family Gate Arrays, Design Reference Manual
	4	Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
	5	P. J. Roth and R. M. Karp, "Minimization over Boolean graphs", IBM Journal of Research and Development vol. 6/No. 2/April 1962.
	6	R. L. Ashenhurst, "The Decomposition of switching functions", Proc. of International Syrup theory of Switching Functions, 1959.
	7	R.K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. R. Wang, "MIS: A Multiple-Level Logic Optimization System", IEEE Transactions on CAD, November 1987.
	8	E. Detjens, private communication.
	9	Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
	10	R. L. Rudell, "Logic Synthesis for VLSI Design", UCB/ERL Memorandum M89/49, April 1989.
	11	Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic Synthesis for Field-Programmable Gate Arrays, Kluwer Academic Publishers, Norwell, MA, 1995
	12	H. -J. Mathony, "Universal logic design algorithm and its application to the synthesis of two-level switching circuits", IEE Proc., Vol. 136, Pt. E, No. 3, May 1989.
	13	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]
	14	S. Malik, A. Wang, R. K. Brayton, A. Sangiovanni- Vincentelli, "Logic Verification using Binary Decision Diagrams", IEEE Int. Conf. on CAD (ICCAD), 1988.

CITED BY 59

	Amit Chowdhary , John P. Hayes, Technology mapping for field-programmable gate arrays using integer programming, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.346-352, November 05-09, 1995, San Jose, California, United States
	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
	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
	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
	Jason Cong , Yean-Yow Hwang, Simultaneous depth and area minimization in LUT-based FPGA mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.68-74, February 12-14, 1995, Monterey, California, United States
	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
	Rajeev Murgai , Robert K. Brayton , Albert Sangiovanni-Vincentelli, Sequential synthesis for table look up programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.224-229, June 14-18, 1993, Dallas, Texas, United States
	Robert J. Francis, A tutorial on logic synthesis for lookup-table based FPGAs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.40-47, November 1992, Santa Clara, California, United States
	D. D. Hill , E. Detjens, FPGA design principles (a tutorial), Proceedings of the 29th ACM/IEEE conference on Design automation, p.45-46, June 08-12, 1992, Anaheim, California, United States
	P. Sawkar , D. Thomas, Area and delay mapping for table-look-up based field programmable gate arrays, Proceedings of the 29th ACM/IEEE conference on Design automation, p.368-373, June 08-12, 1992, Anaheim, California, United States
	Yuji Kukimoto , Masahiro Fujita, Rectification method for lookup-table type FPGA's, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.54-61, November 1992, Santa Clara, California, United States
	Jason Cong , Yuzheng Ding, On area/depth trade-off in LUT-based FPGA technology mapping, Proceedings of the 30th international conference on Design automation, p.213-218, June 14-18, 1993, Dallas, Texas, United States
	Mahesh Mehendale, MIM: logic module independent technology mapping for design and evaluation of antifuse-based FPGAs, Proceedings of the 30th international conference on Design automation, p.219-223, June 14-18, 1993, Dallas, Texas, United States
	Jason Cong , Songjie Xu, Technology mapping for FPGAs with embedded memory blocks, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.179-188, February 22-25, 1998, Monterey, California, United States
	Amit Chowdhary , John P. Hayes, General technology mapping for field-programmable gate arrays based on lookup tables, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.1-32, January 2002
	Bernd Wurth , Klaus Eckl , Kurt Antreich, Functional multiple-output decomposition: theory and an implicit algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.54-59, June 12-16, 1995, San Francisco, California, United States
	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
	Nam-Sung Woo, A heuristic method for FPGA technology mapping based on the edge visibility, Proceedings of the 28th conference on ACM/IEEE design automation, p.248-251, June 17-22, 1991, San Francisco, California, United States
	Wen-Zen Shen , Juinn-Dar Huang , Shih-Min Chao, Lambda set selection in Roth-Karp decomposition for LUT-based FPGA technology mapping, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.65-69, June 12-16, 1995, San Francisco, California, United States
	Peichen Pan , Chih-Chang Lin, A new retiming-based technology mapping algorithm for LUT-based FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.35-42, February 22-25, 1998, Monterey, California, United States
	Ted Stanion , Carl Sechen, A method for finding good Ashenhurst decompositions and its application to FPGA synthesis, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.60-64, June 12-16, 1995, San Francisco, California, United States
	Naoaki Suganuma , Yukihiro Murata , Satoru Nakata , Shinichi Nagata , Masahiro Tomita , Kotaro Hirano, Reconfigurable machine and its application to logic diagnosis, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.373-376, November 1992, Santa Clara, California, United States
	Christian Legl , Bernd Wurth , Klaus Eckl, A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs, Proceedings of the 33rd annual conference on Design automation, p.730-733, June 03-07, 1996, Las Vegas, Nevada, United States
	Peichen Pan , C. L. Liu, Optimal clock period FPGA technology mapping for sequential circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.437-462, July 1998
	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
	Peichen Pan , C. L. Liu, Technology mapping of sequential circuits for LUT-based FPGAs for performance, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.58-64, February 11-13, 1996, Monterey, California, United States
	Chau-Shen Chen , Yu-Wen Tsay , TingTing Hwang , Allen C. H. Wu , Youn-Long Lin, Combining technology mapping and placement for delay-optimization in FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.123-127, November 07-11, 1993, Santa Clara, California, United States
	Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Cube-packing and two-level minimization, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.115-122, November 07-11, 1993, Santa Clara, California, United States
	Valeria Bertacco , Maurizio Damiani, The disjunctive decomposition of logic functions, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.78-82, November 09-13, 1997, San Jose, California, United States
	Kevin Karplus, Amap: A technology mapper for selector-based field-programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.244-247, June 17-22, 1991, San Francisco, California, United States
	Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States
	Nozomu Togawa , Masao Sato , Tatsuo Ohtsuki, A simultaneous technology mapping, placement, and global routing algorithm for field-programmable gate arrays, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.156-163, November 06-10, 1994, San Jose, California, United States
	Thomas R. Shiple , Ramin Hojati , Alberto L. Sangiovanni-Vincentelli , Robert K. Brayton, Heuristic minimization of BDDs using don't cares, Proceedings of the 31st annual conference on Design automation, p.225-231, June 06-10, 1994, San Diego, California, United States
	U. Schlichtmann , F. Brglez , M. Hermann, Characterization of Boolean functions for rapid matching in FPGA technology mapping, Proceedings of the 29th ACM/IEEE conference on Design automation, p.374-379, June 08-12, 1992, Anaheim, California, United States
	R. Murgai , R. K. Brayton , A. L. Sangiovanni-Vincentelli, An improved synthesis algorithm for multiplexor-based PGA's, Proceedings of the 29th ACM/IEEE conference on Design automation, p.380-386, June 08-12, 1992, Anaheim, California, United States
	Jerry R. Burch , David E. Long, Efficient Boolean function matching, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.408-411, November 1992, Santa Clara, California, United States
	Silvia Ercolani , Giovanni De Micheli, Technology mapping for electrically programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.234-239, June 17-22, 1991, San Francisco, California, United States
	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
	David Filo , Jerry Chih-Yuan Yang , Frédéric Mailhot , Giovanni De Micheli, Technology mapping for a two-output RAM-based field programmable gate array, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Uwe Hinsberger , Reiner Kolla, Boolean matching for large libraries, Proceedings of the 35th annual conference on Design automation, p.206-211, June 15-19, 1998, San Francisco, California, United States
	Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, Compatible class encoding in Roth-Karp decomposition for two-output LUT architecture, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.359-363, November 05-09, 1995, San Jose, California, United States
	Kuang-Chien Chen , Jason Cong, Maximal reduction of lookup-table based FPGAs, Proceedings of the conference on European design automation, p.224-229, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	C. Scholl, Multi-output functional decomposition with exploitation of don't cares, Proceedings of the conference on Design, automation and test in Europe, p.743-748, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Bernd Wurth , Ulf Schlichtmann , Klaus Eckl , Kurt J. Antreich, Functional multiple-output decomposition with application to technology mapping for lookup table-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.313-350, July 1999
	Zafar Hasan , David Harrison , Maciej Ciesielski, A Fast Partitioning Method for PLA-Based FPGAs, IEEE Design & Test, v.9 n.4, p.34-39, October 1992
	Sudip Nag , Kaushik Roy, On Routability for FPGAs under Faulty Conditions, IEEE Transactions on Computers, v.44 n.11, p.1296-1305, November 1995
	Chi-Chou Kao , Yen-Tai Lai, An efficient algorithm for finding the minimal-area FPGA technology mapping, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.168-186, January 2005
	Narendra V. Shenoy , Jamil Kawa , Raul Camposano, Design automation for mask programmable fabrics, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Navin Vemuri , Priyank Kalla , Russell Tessier, BDD-based logic synthesis for LUT-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.501-525, October 2002
	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
	Stephen Plaza , Valeria Bertacco, STACCATO: disjoint support decompositions from BDDs through symbolic kernels, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Steven J. E. Wilton, SMAP: heterogeneous technology mapping for area reduction in FPGAs with embedded memory arrays, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.171-178, February 22-25, 1998, Monterey, California, United States
	Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Optimum functional decomposition using encoding, Proceedings of the 31st annual conference on Design automation, p.408-414, June 06-10, 1994, San Diego, California, United States
	Cheng-Hsing Yang , Chia-Chun Tsai , Jan-Ming Ho , Sao-Jie Chen, Hmap: a fast mapper for EPGAs using extended GBDD hash tables, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.2, p.135-150, April 1997
	Christian Legl , Bernd Wurth , Klaus Eckl, An Implicit Algorithm for Support Minimization during Functional Decomposition, Proceedings of the 1996 European conference on Design and Test, p.412, March 11-14, 1996
	Stephen Jang , Billy Chan , Kevin Chung , Alan Mishchenko, WireMap: FPGA technology mapping for improved routability, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA
	Manoj A. Kumar , Jayaram Bobba , V Kamakoti, MemMap: Technology Mapping Algorithm for Area Reduction in FPGAs with Embedded Memory Arrays Using Reconvergence Analysis, Proceedings of the conference on Design, automation and test in Europe, p.20922, February 16-20, 2004
	Stephen Jang , Billy Chan , Kevin Chung , Alan Mishchenko, WireMap: FPGA Technology Mapping for Improved Routability and Enhanced LUT Merging, ACM Transactions on Reconfigurable Technology and Systems (TRETS), v.2 n.2, p.1-24, June 2009
	Rüdiger Ebendt , Rolf Drechsler, Weighted A∗ search -- unifying view and application, Artificial Intelligence, v.173 n.14, p.1310-1342, September, 2009