Algorithmic Aspects of VLSI Layout

In the past two decades, research in VLSI physical design has been directed toward automation of layout process. Since the cost of fabricating a circuit is a fast growing function of the circuit area, circuit layout techniques are developed with an aim to produce layouts with small areas. Other criteria of optimality such as delay and via minimization need to be taken into consideration. This book includes 14 articles that deal with various stages of the VLSI layout problem. It covers topics including partitioning, floorplanning, placement, global routing, detailed routing and layout verification. Some of the chapters are review articles, giving the state-of-the-art of the problems related to timing driven placement, global and detailed routing, and circuit partitioning. The rest of the book contains research articles, giving recent findings of new approaches to the above-mentioned problems. They are all written by leading experts in the field. This book will serve as good references for both researchers and professionals who work in this field.

Issues in timing driven layout, M. Marek-Sadowska; binary formulations for placement and routing problems, M. Sriram, S.M. Kang; a survey of parallel algorithms for placement, P. Banerjee; near optimal fast solution to graph and hypergraph partitioning, F. Makedon, S. Tragoudas; LP formulation of global routing and placement, T. Lengauer, M. Lugering; circuit partitioning algorithms based on geometry model, T. Asano & Tokuyama; on the Manhattan and knock-knee routing modes, D. Zhou, F.P. Preparata; a note on the complexity of Stockmeyer's floorplan optimization technique, T.C. Wang, D.F. Wong; the virtual height of a straight line embedding of a plane graph, T. Takahashi, Y. Kajitani; routing around two rectangles to minimize the layout area, T. Gonzalez, S.L. Lee.