Recent advances in VLSI layout

The current status of VLSI layout and directions for future research are addressed, with emphasis on the authors' own work. Necessary terminology and definitions and, whenever possible, a precise formulation of the problems are provided. Placement and floorplanning for both the sea-of-gates and building-block designs are examined. The former emphasizes the connectivity specification, whereas the latter must also consider module shape and size. Global routing based on a method of successive cuts on a chip is discussed. This is a hierarchical top-down approach that is useful for both of the above designs. A two-dimensional detailed routing problem and the rip-up and rerouting problem are also discussed. The field of computational geometry and its application to layout-in particular, to gridless routing and compaction-are reviewed, and layout engines are considered.>