Satisfiability-based layout revisited

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Satisfiability-based layout revisited: detailed routing of complex FPGAs via search-based Boolean SAT

Full text

Pdf (2.18 MB)

Source

International Symposium on Field Programmable Gate Arrays archive
Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays table of contents

Monterey, California, United States

Pages: 167 - 175

Year of Publication: 1999

ISBN:1-58113-088-0

Authors

Gi-Joon Nam	Department of EECS, University of Michigan, Ann Arbor, MI
Karem A. Sakallah	Department of EECS, University of Michigan, Ann Arbor, MI
Rob A. Rutenbar	Department of ECE, Carnegie Mellon University, Pittsburgh, PA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 23, Citation Count: 16

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/296399.296450 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	M. Abramovici, M.A. Breuer and A.D. Friedman, Digital Systems Testing and Testable Design, Computer Science Press, 1990.
	2	Michael J. Alexander , James P. Cohoon , Joseph L. Ganley , Gabriel Robins, Performance-oriented placement and routing for field-programmable gate arrays, Proceedings of the conference on European design automation, p.80-85, September 18-22, 1995, Brighton, England
	3	Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
	4	Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
	5	S. Brown, J. Rose, and Z.G. Vranesic, "A Detailed Router for Field Programmable Gate Arrays," IEEE Trans. CAD, pp. 620-628, vol. 11, no. 5, May 1992.
	6	Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
	7	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]
	8	Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
	9	S. T Chakradhar, V. D. Agrawal and S. G. Rothweiler, "A Transitive Closure Algorithm for Test Generation," IEEE Transactions on Computer-Aided Design, vol. 12, no. 7, pp.1015-1028, July 1993.
	10	Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, On routability prediction for field-programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.326-330, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164915]
	11	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]
	12	DIMACS http://DIMACS. Rutgers. EDU.
	13	J. Dion, Fast printed circuit board routing, Proceedings of the 24th ACM/IEEE conference on Design automation, p.727-734, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.38004]
	14	John Giraldi , Michael L. Bushnell, Search State Equivalence for Redundancy Identification and Test Generation, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.184-193, October 26-30, 1991
	15	Jonathan Greene , Vwani Roychowdhury , Sinan Kaptanoglu , Abbas El Gamal, Segmented channel routing, Proceedings of the 27th ACM/IEEE conference on Design automation, p.567-572, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123405]
	16	Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
	17	Wolfgang Kunz , Dhiraj K. Pradhan, Recursive Learning: An Attractive Alternative to the Decision Tree for Test Genration in Digital Circuits, Proceedings of the IEEE International Test Conference on Discover the New World of Test and Design, p.816-825, September 20-24, 1992
	18	Tracy Larrabee, Efficient generation of test patterns using Boolean satisfiability, Stanford University, Stanford, CA, 1990
	19	C. Y. Lee, "An Algorithm for Path Connections and its applications," IRE Transactions on Electronic Computers, 1961.
	20	Guy G. F. Lemieux , Stephen D. Brown , Daniel Vranesic, On two-step routing for FPGAS, Proceedings of the 1997 international symposium on Physical design, p.60-66, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267682]
	21	P. C. McGeer, A. Saldanha, P. R. Stephan, R. K. Brayton and A. L. Sangiovanni-Vincentelli, "Timing Analysis and Delay-Fault Test Generation Using Path Recursive Functions," in Proceedings of the International Conference on Computer-Aided Design, pp. 180- 183, 1991
	22	S. K. Nag and R. A. Rutenbar, "Performance-Driven Simultaneous Placement and Routing for FPGA's," IEEE Transactions on CAD, pp. 499-518, June 1998.
	23	J. S. Rose, W. M. Snelgrove, Z. G. Vranesic, "ALTOR: An Automatic Standard Cell Layout Program," Canadian Conf. on VLSi, pp. 169-173, 1985.
	24	João P. Marques Silva , Karem A. Sakallah, Dynamic search-space pruning techniques in path sensitization, Proceedings of the 31st annual conference on Design automation, p.705-711, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196621]
	25	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
	26	P. R. Stephan, R. K. Brayton and A. L. Sangiovanni- Vincentelli, "Combinational Test Generation Using Satisfiability," Memorandum no. UCB/ERL M92/112, Department of Electrical Engineering and Computer Science, University of California at Berkeley, October 1992.
	27	Jordan S. Swartz , Vaughn Betz , Jonathan Rose, A fast routability-driven router for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.140-149, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275134]
	28	N. Togawa, M. Yanagisawa, and T. Ohtsuki, "Mapleopt: A Performance-Oriented Simultaneous Technology Mapping, Placement, and Global Routing Algorithm for FPGA's," IEEE Transactions on CAD, pp. 803-815, Sept. 1998.
	29	R. Glenn Wood , Rob A. Rutenbar, FPGA routing and routability estimation via Boolean satisfiability, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.119-125, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258322]
	30	R. Glenn Wood , Rob A. Rutenbar, FPGA routing and routability estimation via Boolean satisfiability, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.6 n.2, p.222-231, June 1998 [doi>10.1109/92.678873]
	31	Steven Joseph Edward Wilton , Jonathan Rose , Zvenko Vranesic, Architectures and algorithms for field-programmable gate arrays with embedded memory, 1997
	32	XILINX, The Programmable Gate Array Data Book, Xilinx, Inc., San Jose, California, 1993
	33	R. Zabih and D. A. McAllester, "A Rearrangement Search Strategy for Determining Propositional Satisfiability," in Proceedings of the National Conference on Artificial Intelligence, pp. 155-160, 1988.
	34	http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html
	35	.h. ttp://www, eecg.toronto.edu/-lemieuxlsega/sega.html

CITED BY 16

	Gi-Joon Nam , Fadi Aloul , Karem Sakallah , Rob Rutenbar, A comparative study of two Boolean formulations of FPGA detailed routing constraints, Proceedings of the 2001 international symposium on Physical design, p.222-227, April 01-04, 2001, Sonoma, California, United States
	Rajeev Jayaraman, Physical design for FPGAs, Proceedings of the 2001 international symposium on Physical design, p.214-221, April 01-04, 2001, Sonoma, California, United States
	G. Nam , K. Sakallah , R. Rutenbar, A boolean satisfiability-based incremental rerouting approach with application to FPGAs, Proceedings of the conference on Design, automation and test in Europe, p.560-565, March 2001, Munich, Germany
	Slawomir Pilarski , Gracia Hu, SAT with partial clauses and back-leaps, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Hui Xu , Rob A. Rutenbar , Karem Sakallah, sub-SAT: a formulation for relaxed boolean satisfiability with applications in routing, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Miron Abramovici , Jose T. de Sousa , Daniel Saab, A massively-parallel easily-scalable satisfiability solver using reconfigurable hardware, Proceedings of the 36th ACM/IEEE conference on Design automation, p.684-690, June 21-25, 1999, New Orleans, Louisiana, United States
	Frank Schmiedle , Daniel Unruh , Bernd Becker, Exact switchbox routing with search space reduction, Proceedings of the 2000 international symposium on Physical design, p.26-32, May 2000, San Diego, California, United States
	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
	Grant Wigley , David Kearney, The management of applications for reconfigurable computing using an operating system, Australian Computer Science Communications, v.24 n.3, p.73-81, January-February 2002
	Xiaoyu Song , William N. N. Hung , Alan Mishchenko , Malgorzata Chrzanowska-Jeske , Alan Coppola , Andrew Kennings, Board-level multiterminal net assignment, Proceedings of the 12th ACM Great Lakes symposium on VLSI, April 18-19, 2002, New York, New York, USA
	Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002
	Keith So, Solving hard instances of FPGA routing with a congestion-optimal restrained-norm path search space, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Deming Chen , Jason Cong , Peichen Pan, FPGA Design Automation: A Survey, Foundations and Trends® in Electronic Design Automation, v.1 n.3, p.139-169, January 2006
	Cristian Coarfa , Demetrios D. Demopoulos , Alfonso San Miguel Aguirre , Devika Subramanian , Moshe Y. Vardi, Random 3-SAT: The Plot Thickens, Constraints, v.8 n.3, p.243-261, July 2003
	Lintao Zhang , Sharad Malik, Validating SAT Solvers Using an Independent Resolution-Based Checker: Practical Implementations and Other Applications, Proceedings of the conference on Design, Automation and Test in Europe, p.10880, March 03-07, 2003
	Sharad Malik , Lintao Zhang, Boolean satisfiability from theoretical hardness to practical success, Communications of the ACM, v.52 n.8, August 2009