FPGA routing and routability estimation via Boolean satisfiability

R. Glenn Wood, Rob A. Rutenbar

Research output: Contribution to journalArticlepeer-review


Guaranteeing or even estimating the routability of a portion of a placed field programmable gate array (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 all nets simultaneously. Routability estimation is transformed to Boolean satisfiability, which is trivial for BDD's. 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.

Original languageEnglish (US)
Pages (from-to)222-231
Number of pages10
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number2
StatePublished - 1998
Externally publishedYes


  • Computer-aided design
  • Field programmable gate array (FPGA)
  • Placement
  • Rapid prototype
  • Routing

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'FPGA routing and routability estimation via Boolean satisfiability'. Together they form a unique fingerprint.

Cite this