A massively-parallel easily-scalable satisfiability solver using reconfigurable hardware

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A massively-parallel easily-scalable satisfiability solver using reconfigurable hardware

Full text

Pdf (102 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 684 - 690

Year of Publication: 1999

ISBN:1-58133-109-7

Authors

Miron Abramovici	Bell Labs - Lucent Technologies, Murray Hill, NJ
Jose T. de Sousa	Bell Labs - Lucent Technologies, Murray Hill, NJ
Daniel Saab	Case Western Reserve University, Cleveland, Ohio

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): 4, Downloads (12 Months): 26, Citation Count: 5

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/309847.310028 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	Miron Abramovici , Daniel G. Saab, Satisfiability on reconfigurable hardware, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.448-456, September 01-03, 1997
	2	Miron Abramovici , Jose T. de Sousa, A Virtual Logic Algorithm for Solving Satisfiability Problems Using Reconfigurable Hardware, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.306, April 21-23, 1999
	3	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
	4	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	5	Martin Davis , Hilary Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM (JACM), v.7 n.3, p.201-215, July 1960 [doi>10.1145/321033.321034]
	6	S. Devadas, "Optimal Layout Via Boolean Satisfiability," Proc. Intn' I. Conf. on CAD, pp. 294-297, November 1989
	7	S. Devadas , K. Keutzer , S. Malik , A. Wang, Certified timing verification and the transition delay of a logic circuit, Proceedings of the 29th ACM/IEEE conference on Design automation, p.549-555, June 08-12, 1992, Anaheim, California, United States
	8	DIMACS Challenge Benchmarks, ftp://dimacs.rutg ers.edu/p ub/ chal len g e/ sat/ benchmarks/ cnf/
	9	H. Fujiwara and T. Shimono, "On the Acceleration of Test Generation Algorithms," IEEE Trans. on Computers, vol. C-32, no 12, pp. 1137-1144, December, 1983.
	10	P. Goel, "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits," IEEE Trans. on Computers, Vol. C-30, No. 3, pp. 215-222, March, 1981.
	11	J. Gu, "Satisfiability Problems in VLSI Engineering," DIMACS Workshop on Satisfiability Problem: Theory and Applications, March 1996
	12	J. Gu, E W. Purdom, J. Franco, and B. W. Wah, "Algorithms for the Satisfiability (SAT) Problem: A Survey," DIMACS Workshop on Satisfiability Problem: Theory and Applications, pp. 19-51, March 1996
	13	J. Gu and R. Puri, "Asynchronous Circuit Synthesis with Boolean Satisfiability", IEEE Trans. on CAD, Vol. 14, No. 8, pp. 961-973, August 1995
	14	T. Larrabee, "Test Pattern Generation Using Boolean Satisfiability," IEEE Trans. on CAD, Vol. 11, No. 1, pp. 4-15, January, 1992
	15	P. C. McGeer et al., "Timing Analysis and Delay-Fault Test Generation Using Path Recursive Functions," Proc. Intn' 1. Conf. on CAD, pp. 180-183, November 1991
	16	Marco Platzner , Giovanni De Micheli, Acceleration of Satisfiability Algorithms by Reconfigurable Hardware, Proceedings of the 8th International Workshop on Field-Programmable Logic and Applications, From FPGAs to Computing Paradigm, p.69-78, August 31-September 03, 1998
	17	Azra Rashid , Jason Leonard , William H. Mangione-Smith, Dynamic Circuit Generation for Solving Specific Problem Instances of Boolean Satisfiability, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.196, April 15-17, 1998
	18	J. M. Silva, "An Overview of Backtrack Search Satisfiability Algorithms," Proc. 5th Intn' 1. Symp. on Artificial Intelligence and Mathematics, January 1998
	19	João P. Marques Silva , Karem A. Sakallah, GRASP—a new search algorithm for satisfiability, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.220-227, November 10-14, 1996, San Jose, California, United States
	20	L. G. Silva et al., "Realistic Delay Modeling in Satisfiability-Based Timing Analysis," Proc. Intn' 1. Symp. on Circuits and Systems (ISCAS), May 1998
	21	P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli, "Combinational Test Generation Using Satisfiability," IEEE Trans. on CAD, vol. 15, no. 9, pp. 1167-1176, Sept. 1996.
	22	Takayuki Suyama , Makoto Yokoo , Hiroshi Sawada, Solving Satisfiability Problems on FPGAs, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.136-145, September 23-25, 1996
	23	Gi-Joon Nam , Karem A. Sakallah , Rob A. Rutenbar, Satisfiability-based layout revisited: detailed routing of complex FPGAs via search-based Boolean SAT, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.167-175, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296450]
	24	P. Zhong , M. Martonosi , P. Ashar , S. Malik, Accelerating Boolean Satisfiability with Configurable Hardware, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.186, April 15-17, 1998
	25	Peixin Zhong , Pranav Ashar , Sharad Malik , Margaret Martonosi, Using reconfigurable computing techniques to accelerate problems in the CAD domain: a case study with Boolean satisfiability, Proceedings of the 35th annual conference on Design automation, p.194-199, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277098]

CITED BY 5

	João P. Marques-Silva , Karem A. Sakallah, Boolean satisfiability in electronic design automation, Proceedings of the 37th conference on Design automation, p.675-680, June 05-09, 2000, Los Angeles, California, United States
	Andreas Dandalis , Viktor K. Prasanna, Run-time performance optimization of an FPGA-based deduction engine for SAT solvers, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.547-562, October 2002
	Lucas Bordeaux , Youssef Hamadi , Lintao Zhang, Propositional Satisfiability and Constraint Programming: A comparative survey, ACM Computing Surveys (CSUR), v.38 n.4, p.12-es, 2006
	Miron Abramovici , Jose T. De Sousa, A SAT Solver Using Reconfigurable Hardware and Virtual Logic, Journal of Automated Reasoning, v.24 n.1-2, p.5-36, February 2000
	Kanupriya Gulati , Suganth Paul , Sunil P. Khatri , Srinivas Patil , Abhijit Jas, FPGA-based hardware acceleration for Boolean satisfiability, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.2, p.1-11, March 2009