Premium
Symmetry‐aware placement algorithm using transitive closure graph representation for analog integrated circuits
Author(s) -
Zhang Lihong,
Zhang Yuping,
Jiang Yingtao,
Shi C.J.Richard
Publication year - 2010
Publication title -
international journal of circuit theory and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.364
H-Index - 52
eISSN - 1097-007X
pISSN - 0098-9886
DOI - 10.1002/cta.551
Subject(s) - transitive closure , representation (politics) , analogue electronics , algorithm , transitive relation , topology (electrical circuits) , computer science , graph , analog computer , mathematics , electronic circuit , theoretical computer science , discrete mathematics , combinatorics , electrical engineering , politics , political science , law , engineering
Recently several topological representations have been explored as alternatives to the conventional absolute‐coordinate representation for integrated circuit layout automation. Those topological representations, however, lack one or more aspects in capturing the solution space subject to symmetry constraints, which are abundant in analog layouts. In this paper, we explore the use of transitive closure graphs (TCGs) to represent analog placements, i.e. placements with symmetry constraints. We define a set of conditions so that a TCG satisfying these conditions, referred to as a symmetric‐feasible TCG , will correspond to a valid symmetric placement and vice versa. We then present an O ( n 2 ) algorithm, where n is the number of cells to be placed, to build a symmetric placement from a symmetric‐feasible TCG, a problem known as packing. We further describe a set of random perturbation operations on existing symmetric‐feasible TCGs to generate new symmetric‐feasible TCGs with time complexity of O ( n ) . This allows our TCG‐based symmetry‐aware analog placer to search only the symmetric‐feasible TCG solution space, leading to a substantial reduction of the search space and solution time. Experimental results on several analog circuits have confirmed the superiority of the TCG representation to the conventional absolute‐coordinate representation as well as several other topological representations in analog layout design. Copyright © 2008 John Wiley & Sons, Ltd.