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

G. J. Nam, F. Aloul, K. Sakallah, R. Rutenbar

Research output: Contribution to conferencePaperpeer-review


A Boolean-based router expresses the routing constraints as a Boolean 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 superiority of this formulation over an earlier formulation that expressed the constraints in terms of "track" variables.

Original languageEnglish (US)
Number of pages6
StatePublished - 2001
Externally publishedYes
Event2001 International Symposium on Physical Design - Sonoma, CA, United States
Duration: Apr 1 2001Apr 4 2001


Other2001 International Symposium on Physical Design
Country/TerritoryUnited States
CitySonoma, CA

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'A comparative study of two boolean formulations of FPGA detailed routing constraints'. Together they form a unique fingerprint.

Cite this