Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Standard Cell Routing via Boolean Satisfiability
Authors
	Ryzhenko N.V.
Date of publication
	2012
Abstract
	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.
Keywords
	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
	http://www.mes-conference.ru/data/year2012/pdf/D51.pdf