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

摘要

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.rnIn 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.rnWe 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.