The authors present a placement method for cell-based layout styles. It is composed of alternating and interacting global optimization and partitioning steps that are followed by an optimization of the area utilization. Methods using the divide-and-conquer paradigm usually lose the global view by generating smaller and smaller subproblems. In contrast, GORDIAN maintains the simultaneous treatment of all cells over all global optimization steps, thereby considering constraints that reflect the current dissection of the circuit. The global optimizations are performed by solving quadratic programming problems that possess unique global minima. Improved partitioning schemes for the stepwise refinement of the placement are introduced. The area utilization is optimized by an exhaustive slicing procedure. The placement method is applied to real-world problems, and excellent results in terms of placement quality and computation time are obtained.>

A placement method for cell-based layout styles composed of alternating and interacting global optimization and partitioning phases is presented. In contrast to other methods using the divide-and-conquer paradigm, it maintains the simultaneous treatment of all cells during optimization over all levels of partitioning. In the global optimization phases, constrained quadratic optimization problems with unique global minima are solved. Their solutions induce the assignment of cells to regions during the partitioning phases. For general-cell circuits, a highly efficient exhaustive slicing procedure is applied to small subsets of cells. The designer may choose a configuration from a menu to meet his requirements on chip area, chip aspect ratio and wire length. Placements with high area utilization are obtained within short computation times. The method has been applied to general-cell and standard-cell circuits with up to 3000 cells and nets.>