14.1 INTRODUCTION

Placement is a physical synthesis task that transforms a block/gate/transistor-level netlist into an actual layout for timing convergence. It is a crucial step that assembles the basic building blocks of logic netlist and establishes the overall timing characteristic of a design by determining exact locations of circuit elements within a given region. In modern VLSI designs, the size of chip becomes larger and the required clock frequency keeps increasing due to higher performance and more complex functional requirements on a single chip. Moreover, with aggressive technology scaling into the deep submicron (DSM) era, interconnect delays become the dominant factor for overall chip performance. Because the locations of circuit elements and corresponding interconnect delays are determined during the placement stage, it has significant impact on the final performance of the design. Moreover, if a design is placed poorly, it is virtually impossible to close timing, no matter how much other physical synthesis and routing optimizations are applied to it. Hence, placement is regarded as one of the most important and effective optimization techniques in the physical synthesis flow. Today, placement is no longer a point tool in modern timing closure flow [1]. Significant portions of logic and physical optimization algorithms have to interact with placement to improve timing of a design and to guarantee a legal placement solution after optimizations. Consequently, most industrial and academic physical synthesis tools are developed around a placement infrastructure.

The typical objective function of placement is to minimize...