Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Automatic Determining of Auxiliary Constraints at Boundaries for Standard Cells Synthesis Flow
Authors
	Bykov S.A.
	Ryzhenko N.V.
	Sorokin A.A.
Date of publication
	2016
Abstract
	Standard cell methodology significantly reduces the complexity of the design. A library of standard cells is designed so to guarantee that any possible allowed place-ment of standard cells does not violate any design rule. Due to the large number and complexity of design rules, it is a difficult task to formulate such additional constraints, that they will prevent any DRVs between abutted cells. Moreover, it is difficult to generalize this approach – each new technology or a set of design rules requires new algorithms and approaches to generate several variants of rules and choose the most appropriate one. Current paper proposes a solution for automatic exploration of additional boundary constraints. Key components are: description of design rules using Boolean expressions over discrete layout objects; usage of Boolean satisfiability framework to generate all possible DR-clean layouts within a clip; maximal clique’s enumeration procedure to divide layouts into groups; logical minimization to compute resulting boundary constraints in form of Boolean expressions. Experimental results demonstrated applicability of the proposed approach for a wide class of design rules. At the first stage, we build a clip, big enough to contain input design rules. The clip includes a set of cell bounda-ries. Then rules are translated into a set of Boolean expressions [1], expressed as conjunctive normal form (CNF). Cell boundaries can be considered as symmetries axis: if we allow to place an object on one side from a boundary, we must allow to use a corresponding object on the other side. We extent CNF formula with such equivalence constraints. At the second stage, we use Boolean satisfiability framework and AllSat techniques [2] to enumerate all possible DR-clean layouts within the given clip. At this point we know that it is safe to place each layout to itself – such pair do not produce design rules violations. At the third stage, we use graph representation to find groups of layouts. We build a graph, where each vertex corresponds to a layout. We draw an edge between a pair of layouts if and only if they do not produce DRVs together. Each maximal clique in such graph correspond to a set of layouts, which are safe to abut to each other. We enumerate them all using algorithm that is described in [3]. At the last stage, we use logic minimization framework [4]-[5] to compute additional constraints on boundaries using layouts, which correspond to a clique. Thus, each clique produces a specific set of design rules. The algorithm was used to process several sets of de-sign rules and to generate corresponding additional con-straints on cell boundaries. For a small test case it took approx. 1 min to generate 13 layouts and group them into 4 rules variants. The task included 65 Boolean variables and 16 clauses. The largest test case involved 16164 literals and 30996 clauses. 20136 layouts were found, they were grouped into 7798 classes. 8 min were required to process the task.
Keywords
	routing, standard cells, design rules, cell library, optical lithography, Boolean satisfiability.
Library reference
	Bykov S.A., Ryzhenko N.V., Sorokin A.A. Automatic Determining of Auxiliary Constraints at Boundaries for Standard Cells Synthesis Flow // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2016. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2016. Part 1. P. 137-143.
URL of paper
	http://www.mes-conference.ru/data/year2016/pdf/D039.pdf