Symmetry-aware Placement Algorithm Using Transitive Closure Graph Representation for Analog Integrated Circuits

Authors

Lihong Zhang, University of MagdeburgFollow
Yuping Zhang, Shanghai Normal University
Yingtao Jiang, University of Nevada, Las VegasFollow
C.-J. Richard Shi, University of Washington - Seattle CampusFollow

Document Type

Article

Publication Date

4-2010

Publication Title

International Journal of Circuit Theory and Applications

Volume

38

Issue

3

First page number:

221

Last page number:

241

Abstract

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(n2) 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.

Keywords

Analog integrated circuits; Analog circuit layout; Graph theory; Symmetry; Placement; Topological representation; Transitive closure graph

Disciplines

Electrical and Computer Engineering | Engineering | Signal Processing | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

Repository Citation

Zhang, L., Zhang, Y., Jiang, Y., Shi, C. R. (2010). Symmetry-aware Placement Algorithm Using Transitive Closure Graph Representation for Analog Integrated Circuits. International Journal of Circuit Theory and Applications, 38(3), 221-241.