FPGA routing and routability estimation via Boolean satisfiability

ABSTRACT

Guaranteeing or even estimating the routability of a portion of a placed FPGA remains difficult or impossible in most practical applications. In this paper we develop a novel formulation of both routing and routability estimation that relies on a rendering of the routing constraints as a single large Boolean equation. Any satisfying assignment to this equation specifies a complete detailed routing. By representing the equation as a Binary Decision Diagram (BDD), we represent all possible routes for allnets simultaneously. Routability estimation is transformed to Boolean satisfiability, which is trivial for BDDs. We use the technique in the context of a perfect routability estimator for a global router. Experimental results from a standard FPGA benchmark suite suggest the technique is feasible for realistic circuits, but refinements are needed for very large designs.

REFERENCES

• Alex94: Michael J. Alexander , James P. Cohoon , Joseph L. Ganley , Gabriel Robins, An architecture-independent approach to FPGA routing based on multi-weighted graphs, Proceedings of the conference on European design automation, p.259-264, September 19-23, 1994, Grenoble, France
• Berm89: C.L. Berman, "Ordered Binary Decision Diagrams and Circuit Structure," Prec. IEEE ICCD, pp. 392-395, Oct. 1989.
• Bern95: Jochen Bern , Christoph Meinel , Anna Slobodová, Efficient OBDD-based boolean manipulation in CAD beyond current limits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.408-413, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217563]
• 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]
• Brow92a: S. Brown, J. Rose, and Z.G. Vranesie, "A Detailed Router for Field Programmable Gate Arrays," IEEE Trans. CAD, pp. 620-628, vol. 11, no. 5, May 1992.
• Brow92b: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 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]
• Brya92: 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]
• Chan93: 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]
• Chan94: Yao-Wen Chang , Shashidhar Thakur , Kai Zhu , D. F. Wong, A new global routing algorithm for FPGAs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.356-361, November 06-10, 1994, San Jose, California, United States
• Deva89: S. Devadas, "Optimal Layout Via Boolean Safisfiability," Prec. ACM/IEEE iCCAD, pp. 294-297, 1989.
• Gree90: 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]
• Hall70: K.M. Hall, "An R-Dimensional Quadratic Placement Algorithm,'' Management Set, vol. 17, pp. 219-229, Nov. 1970.
• Lemi93: G. Lemieux and S. Brown, "A Detailed Router for Allocating Wire Segments in FPGAs," Prec. ACM Physical Design Workshop, California, Apr. 1993.
• Marq97: 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
• Mina93: Shin-ichi Minato, Zero-suppressed BDDs for set manipulation in combinatorial problems, Proceedings of the 30th international conference on Design automation, p.272-277, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164890]
• McMu95: 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]
• Nag95: Sudip K. Nag , Rob A. Rutenbar, Performance-driven simultaneous place and route for island-style FPGAs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.332-338, November 05-09, 1995, San Jose, California, United States
• Nag94: Sudip K. Nag , Rob A. Rutenbar, Performance-driven simultaneous place and route for row-based FPGAs, Proceedings of the 31st annual conference on Design automation, p.301-307, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196387]
• Rude93: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• Wood96: R. Glenn Wood, Routing for FPGAs via Boolean Sati~ability, M.S. Thesis, Dept. of ECE, Carnegie Mellon University, May 1996.
• Wu93: Y-L, Wu and M. Marek-Sadowska, "Graph Based Analysis of FPGA Routing," Prec. European Design Auto. Conf., pp. 104-109, 1993.
• Wu94: Yu-Liang Wu , Douglas Chang, On the NP-completeness of regular 2-D FPGA routing architectures and a novel solution, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.362-366, November 06-10, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Experimentation