BDD based decomposition of logic functions with application to FPGA synthesis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

BDD based decomposition of logic functions with application to FPGA synthesis

Full text

Pdf (612 KB)

Source

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

Dallas, Texas, United States

Pages: 642 - 647

Year of Publication: 1993

ISBN:0-89791-577-1

Authors

Yung-Te Lai
Massoud Pedram
Sarma B. K. Vrudhula

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 34, Citation Count: 40

Additional Information:

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

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.L. Ashenhurst, "The decomposition of switching functions," Ann. Computation Lab., Harvard University, vol. 29, pp. 7'4-116, 1959.
	2	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]
	3	H.A. Curtis, "A new approach to the design of switching circuits, Princeton, N.J., Van Nostrand, 1962.
	4	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 [doi>10.1145/127601.127670]
	5	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	6	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]
	7	Y.-T. Lai , S. Sastry, Edge-valued binary decision diagrams for multi-level hierarchical verification, Proceedings of the 29th ACM/IEEE conference on Design automation, p.608-613, June 08-12, 1992, Anaheim, California, United States
	8	Heh-Tyan Liaw , Chen-Shang Lin, On the OBDD-Representation of General Boolean Functions, IEEE Transactions on Computers, v.41 n.6, p.661-664, June 1992 [doi>10.1109/12.144618]
	9	R. Murgai, N, Shenoy, R.K. Brayton and A. Sangiovanni- Vincentelll, "Improved logic synthesis algorithms for table look up architectures," ICCAD, 1991.
	10	J.P. Roth and R.M. Karp, "Minimization over Boolean graphs," IBM Journal, April 1962, pp. 227-238.
	11	Y-T. Lai, M. Pedram and S. Vrudhula, "BDD-based logic decomposition: theory," Technical Report, Dept. of EE Systems, University of Southern California. 1992.

CITED BY 40

	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
	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
	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
	Enrico Macii , Massimo Poncino, Predicting the functional complexity of combinational circuits by symbolic spectral analysis of Boolean functions, Proceedings of the conference on European design automation, p.294-299, September 18-22, 1995, Brighton, England
	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
	H. Sawada , S. Yamashita , A. Nagoya, Restructuring logic representations with easily detectable simple disjunctive decompositions, Proceedings of the conference on Design, automation and test in Europe, p.755-761, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Chau-Shen Chen , TingTing Hwang , C. L. Liu, Low power FPGA design—a re-engineering approach, Proceedings of the 34th annual conference on Design automation, p.656-661, June 09-13, 1997, Anaheim, California, United States
	Victor N. Kravets , Karem A. Sakallah, Resynthesis of multi-level circuits under tight constraints using symbolic optimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.687-693, November 10-14, 2002, San Jose, California
	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
	Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, Formal Verification Using Edge-Valued Binary Decision Diagrams, IEEE Transactions on Computers, v.45 n.2, p.247-255, February 1996
	Jason Cong , Yean-Yow Hwang, Partially-dependent functional decomposition with applications in FPGA synthesis and mapping, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.35-42, February 09-11, 1997, Monterey, 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
	Masahiro Fujita , Yusuke Matsunaga , Maciej Ciesielski, Multi-level logic optimization, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, FGILP: an integer linear program solver based on function graphs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.685-689, 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
	Victor N. Kravets , Karem A. Sakallah, Constructive library-aware synthesis using symmetries, Proceedings of the conference on Design, automation and test in Europe, p.208-215, March 27-30, 2000, Paris, France
	Shigeru Yamashita , Hiroshi Sawada , Akira Nagoya, An efficient framework of using various decomposition methods to synthesize LUT networks and its evaluation, Proceedings of the 2000 conference on Asia South Pacific design automation, p.253-258, January 2000, Yokohama, Japan
	Jin S. Zhang , Malgorzata Chrzanowska-Jeske , Alan Mishchenko , Jerry R. Burch, Detecting support-reducing bound sets using two-cofactor symmetries, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Peter H. Schneider , Kurt J. Antreich , Ulf Schlichtmann, A new power estimation technique with application to decomposition of Boolean functions for low power, Proceedings of the conference on European design automation, p.388-393, September 19-23, 1994, Grenoble, France
	Hiroshi Sawada , Takayuki Suyama , Akira Nagoya, Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.353-358, November 05-09, 1995, San Jose, California, United States
	Shin-ichi Minato , Giovanni De Micheli, Finding all simple disjunctive decompositions using irredundant sum-of-products forms, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.111-117, November 08-12, 1998, San Jose, California, United States
	Juinn-Dar Huang , Jing-Yang Jou , Wen-Zen Shen, An iterative area/performance trade-off algorithm for LUT-based FPGA technology mapping, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.13-17, November 10-14, 1996, San Jose, 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
	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
	Tsutomu Sasao , Munehiro Matsuura, A method to decompose multiple-output logic functions, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Lech Jóźwiak , Aleksander S´lusarczyk, General decomposition of incompletely specified sequential machines with multi-state behavior realization, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.8, p.445-492, August 2004
	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
	Tsutomu Sasao , Munehiro Matsuura, BDD representation for incompletely specifiedvmultiple-output logic functions and its applications to functional decomposition, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	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
	L. Jóźwiak , S. Biegański , A. Chojnacki, Information-driven circuit synthesis with the pre-characterized gate libraries, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.6-7, p.405-423, June-July 2005
	Alan Mishchenko , Xinning Wang , Timothy Kam, A new enhanced constructive decomposition and mapping algorithm, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Tomasz S. Czajkowski , Stephen D. Brown, Functionally linear decomposition and synthesis of logic circuits for FPGAs, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	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
	Venkatesan Muthukumar , Robert J. Bignall , Henry Selvaraj, An efficient variable partitioning approach for functional decomposition of circuits, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.1, p.53-67, January, 2007
	C. Scholl , S. Melchior , G. Hotz , P. Molitor, Minimizing ROBDD Sizes of Incompletely Specified Boolean Functions by Exploiting Strong Symmetries, Proceedings of the 1997 European conference on Design and Test, p.229, March 17-20, 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
	Munehiro Matsuura , Tsutomu Sasao, BDD Representation for Incompletely Specified Multiple-Output Logic Functions and Its Applications to the Design of LUT Cascades, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.12, p.2762-2769, December 2007