FPGA routing and routability estimation via Boolean satisfiability

摘要

Guaranteeing or even estimating the routability of a portion of anplaced field programmable gate array (FPGA) remains difficult ornimpossible in most practical applications. In this paper, we develop annovel formulation of both routing and routability estimation that reliesnon a rendering of the routing constraints as a single large Booleannequation. Any satisfying assignment to this equation specifies ancomplete detailed routing. By representing the equation as a binaryndecision diagram (BDD), we represent all possible routes for all netsnsimultaneously. Routability estimation is transformed to Booleannsatisfiability, which is trivial for BDD's. We use the technique in thencontext of a perfect routability estimator for a global router.nExperimental results from a standard FPGA benchmark suite suggest thentechnique is feasible for realistic circuits, but refinements are needednfor very large designs