Placement with symmetry constraints for analog layout using red-black trees

The traditional way of approaching placement problems in computer-aided design (CAD) tools for analog layout is to explore an extremely large search space of feasible or unfeasible placement configurations, where the cells are moved in the chip plane (being even allowed to overlap) by a stochastic optimizer. This paper presents a novel analog placement technique operating on the set of tree representations of the layout, where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the exploration of the solution space. The computation times exhibited by this novel approach are typically 3-6 times better than those of the algorithms using the traditional exploration strategy. This superior efficiency is due to the use of red-black trees, a data structure introduced by Guibas and Sedgewick to support operations on dynamic sets of intervals.