FPGA routing and routability estimation via Boolean satisfiability
- 1 June 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 6 (2) , 222-231
- https://doi.org/10.1109/92.678873
Abstract
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.Keywords
This publication has 24 references indexed in Scilit:
- A New Global Routing Algorithm For FPGAsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- On The Np-completeness Of Regular 2-d Fpga Routing Architectures And A Novel SolutionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Optimal layout via Boolean satisfiabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Iterative and adaptive slack allocation for performance-driven layout and FPGA routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Interleaving based variable ordering methods for ordered binary decision diagramsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Graph based analysis of FPGA routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Segmented channel routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- FPGA routing and routability estimation via Boolean satisfiabilityPublished by Association for Computing Machinery (ACM) ,1997
- On routability prediction for field-programmable gate arraysPublished by Association for Computing Machinery (ACM) ,1993
- An r-Dimensional Quadratic Placement AlgorithmManagement Science, 1970