Symmetry-aware placement algorithm using transitive closure graph representation for analog integrated circuits

Document Type



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.


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


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


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.

UNLV article access

Search your library