Satisfiability-based detailed FPGA routing

Gi Joon Nam, Karem A. Sakallah, Rob A. Rutenbar

Research output: Contribution to conferencePaper


In this paper we address the problem of detailed FPGA routing using Boolean formulation methods. In the context of FPGA routing where routing resources are fixed, Boolean formulation methods can prove the unroutability of a given circuit, which is a clear advantage over classical net-at-a-time approaches. Previous attempts at FPGA routing using Boolean methods were based on Binary Decision Diagrams (BDDs) which limited their scope to small FPGAs. In this paper we employ an efficient search-based Boolean satisfiability approach to solve the routing problem and show that such an approach extends the range of Boolean methods to larger FPGAs. Furthermore, we show the possibility that more relaxed formulations of the routing constraints, allowing higher degrees of freedom for net routing, can be easily accommodated. Preliminary experimental results suggest that our approach is quite viable for FPGAs of practical size.

Original languageEnglish (US)
Number of pages4
StatePublished - Jan 1 1999
EventProceedings of the 1999 12th International Conference on VLSI Design - Goa, India
Duration: Jan 7 1999Jan 10 1999


OtherProceedings of the 1999 12th International Conference on VLSI Design
CityGoa, India

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Satisfiability-based detailed FPGA routing'. Together they form a unique fingerprint.

  • Cite this

    Nam, G. J., Sakallah, K. A., & Rutenbar, R. A. (1999). Satisfiability-based detailed FPGA routing. 574-577. Paper presented at Proceedings of the 1999 12th International Conference on VLSI Design, Goa, India, .