Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Standard Cell Routing via Boolean Satisfiability

 Ryzhenko N.V.
Date of publication

 We propose a flow for routing nets within a standard cell that 1) generates candidate routes for point-to-point segments; 2) finds conflicts (electrical shorts and geometric design rule violations) between candidate routes; and 3) solves a SAT instance producing a legal and complete routing for all nets in the standard cell. This approach enables routing automation for cutting-edge process technology nodes. We present how to make this technique more effective by introducing pruning techniques to reduce the work required in all three steps. We also show how we can further optimize routing quality within the SAT formulation through the use of successively more stringent constraints. Recent improvements in the speed of SAT solvers make such a formulation practical for even complex standard cells. A routing tool based on our SAT formulation is currently being used to route real industrial standard cell layouts. It demonstrates acceptable runtime and 89% coverage of our industrial standard cell library, including scan flip-flops, adders, and multiplexers.
 routing, standard cells, boolean satisfiability
Library reference
 Ryzhenko N.V. Standard Cell Routing via Boolean Satisfiability // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2012. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2012. P. 225-230.
URL of paper

Copyright © 2009-2019 IPPM RAS. All Rights Reserved.

Design of site: IPPM RAS