A comparative study of two Boolean formulations of FPGA detailed routing constraints

ABSTRACT

A Boolean-based router expresses the routing constraints as a Boolðean function which is satisfiable if and only if the layout is routable. Compared to traditional routers, Boolean-based routers offer two unique features: (1) simultaneous embedding of all nets regardless of net ordering, and (2) ability to demonstrate routing infeasibility by proving the unsatisfiability of the generated routing constraint Boolean function. In this paper, we introduce a new Boolean-based FPGA detailed routing formulation that yields an easy-to-evaluate and more scalable routability Boolean function than the previous methods. The routability constraints are expressed in terms of a set of route variables each of which designating a specific detailed route for a given net. Experimental results clearly show the superiðority of this formulation over an earlier formulation that expressed the constraints in terms of track variables.

REFERENCES

• 1: 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
• 2: M. J. Alexander and G. Robins, "New Performance-Driven FPGA Routing Algorithms", IEEE Trans. on CAD, vol. 15, no. 12, pp. 1505 - 1517, Dec. 1996
• 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. 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: 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]
• 9: DIMACS http://DIMACS.Rutgers.EDU
• 10: 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
• 11: 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]
• 12: C. Y. Lee, "An Algorithm for Path Connections and its Applications", IRE Transactions on Electronic Computers, 1961.
• 13: Yuh-sheng Lee , Allen C.-H. Wu, A performance and routablity driven router for FPGAs considering path delays, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.557-561, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217588]
• 14: G. Lemieux and S. Brown, "A Detailed Router for Allocating Wire Segments in FPGAs," Proc. ACM Physical Design Workshop, California, Apr. 1993.
• 15: João P. Marques-Silva , Karem A. Sakallah, GRASP: A Search Algorithm for Propositional Satisfiability, IEEE Transactions on Computers, v.48 n.5, p.506-521, May 1999 [doi>10.1109/12.769433]
• 16: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 17: S. Nag and R. Rutenbar, "Performance-Driven Simultaneous Placement and Routing for FPGAs", IEEE Trans. on CAD, pp. 499 - 518, June 1998.
• 18: G. Nam, S. Kalman, J. Anderson, R. Jayaraman, S. Nag and J. Zhuang, "A Method and Apparatus for Testing Routability", U.S. patent pending.
• 19: 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]
• 20: J. Rose, W. Snelgrove, Z. Vranesic, "ALTOR:An Automatic Standard Cell Layout Program", Canadian Conf. on VLSI, pp. 169-173, 1985.
• 21: 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]
• 22: Stephen M. Trimberger, Field-Programmable Gate Array Technology, Kluwer Academic Publishers, Norwell, MA, 1994
• 23: Steven Joseph Edward Wilton , Jonathan Rose , Zvenko Vranesic, Architectures and algorithms for field-programmable gate arrays with embedded memory, 1997
• 24: 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]
• 25: Y-L. Wu and M. Marek-Sadowska, "Routing for Array-Type FPGAs", IEEE Trans. on CAD, vol. 16, no. 5, pp. 506 - 518, May 1997.
• 26: http://www.eecg.toronto.edu/~lemieux/sega/sega.html
• 27: http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html
• 28: http://www.xilinx.com/products/xc4000e.html

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

General Terms:
Design, Management, Theory