Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams

Full text

Pdf (492 KB)

Source

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

San Francisco, California, United States

Pages: 417 - 420

Year of Publication: 1991

ISBN:0-89791-395-7

Authors

Kenneth M. Butler	Texas Instruments, P.O. Box 655303 MS 3683, Dallas, TX
Don E. Ross	Dept.of Electrical Eng., Texas A&M University, College Station, TX
Rohit Kapur	The University of Texas, Dept. of ECE, ENS 143, Austin, TX
M. Ray Mercer	The University of Texas, Dept. of ECE, ENS 143, Austin, TX

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 14, Citation Count: 10

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/127601.127705 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.

	BERM88	C.L. Berman, "Circuit width, register allocation, and reduced function graphs," IBM Res. Rep. RC 14127, Nov. 1988.
	BERM89	C.L. Berman, "Ordered Binary Decision Diagrams and Circuit Structure," Extended Abstract, Proc. Int. Conf. Comput. Deszgn, Oct. 1989, pp. 392-395.
	BRAC90	Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123222]
	BRGL85	F. Brglez, H. Fujiwara, "A neutral netlist of 10 combinational benchmark circuits and a target translator in FORTRAN," Proc. IEEE Int. Symp. on Circ. Syst. (ISCAS), June 1985, pp. 695-698.
	BRYA86	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]
	FRIE90	S. J. Friedman , K. J. Supowit, Finding the Optimal Variable Ordering for Binary Decision Diagrams, IEEE Transactions on Computers, v.39 n.5, p.710-713, May 1990 [doi>10.1109/12.53586]
	FUJI88	M. Fujita, H. Fujisawa, N. Kawato, "Evaluation and improvements of Boolean comparison method based on binary decision diagrams," Dig. Technical Papers, Int. Conf. CAD, Nov. 1988, pp. 2-5.
	GOLD79	L.H. Goldstein, "Controllability/ Observability analysis of digital circuits," IEEE Trans. Circ. Syst., vol. CAS-26, no. 9, Sept. 1979, pp. 685-693.
	MALI88	S. Malik, A.R. Wang, I~.K. Brayton, A. Sangiovanni-Vincentelli, "Logic verification using binary decision diagrams in a logic synthesis environment," D~g. Technical Papers, Int. Conf. CAD, Nov. 1988, pp. 6-9.
	MALI90	S. Malik, personal communication, May 1990.
	MINA90	Shin-ichi Minato , Nagisa Ishiura , Shuzo Yajima, Shared binary decision diagram with attributed edges for efficient Boolean function manipulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.52-57, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123225]
	ROSS90	Don Edgar Ross , M. Ray Mercer, Functional calculations using ordered partial multidecision diagrams, 1990
	ROSS91	Don E. Ross , Kenneth M. Butler , Rohit Kapur , M. Ray Mercer, Fast functional evaluation of candidate OBDD variable orderings, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands

CITED BY 10

	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
	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
	M. R. Mercer , R. Kapur , D. E. Ross, Functional approaches to generating orderings for efficient symbolic representations, Proceedings of the 29th ACM/IEEE conference on Design automation, p.624-627, June 08-12, 1992, Anaheim, California, United States
	J. Gergov , C. Meinel, Efficient Boolean Manipulation with OBDD's Can be Extended to FBDD's, IEEE Transactions on Computers, v.43 n.10, p.1197-1209, October 1994
	Beate Bollig , Ingo Wegener, Improving the Variable Ordering of OBDDs Is NP-Complete, IEEE Transactions on Computers, v.45 n.9, p.993-1002, September 1996
	Yu-Liang Wu , Hongbing Fan , Malgorzata Marek-Sadowska , C. k. Wong, OBDD Minimization Based on Two-Level Representation of Boolean Functions, IEEE Transactions on Computers, v.49 n.12, p.1371-1379, December 2000
	Apu Kapadia , Geetanjali Sampemane , Roy H. Campbell, KNOW Why your access was denied: regulating feedback for usable security, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA
	Detlef Sieling, The nonapproximability of OBDD minimization, Information and Computation, v.172 n.2, p.103-138, January 29, 2002
	Yuke Wang , Carl McCrosky, Solving Boolean Equations Using ROSOP Forms, IEEE Transactions on Computers, v.47 n.2, p.171-177, February 1998
	Orna Grumberg , Shlomi Livne , Shaul Markovitch, Learning to order BDD variables in verification, Journal of Artificial Intelligence Research, v.18 n.1, p.83-116, January 2003