| Circuit placement---spatially arranging the components of an electronic circuit in a non-overlapping configuration on a chip---is a crucial step in today's VLSI physical design flow. Placement determines the basic structure of the interconnect, and interconnect delay is the bottleneck of nanoscale VLSI-system performance. Placement is challenging not only because of the enormous number of objects to be placed, but also because of many complex constraints related to non-overlap, signal timing, wireability, temperature, manufacturability, and noise.;A high quality placement tool---mPL6---has been developed and analyzed in this thesis. It is a highly scalable non-convex nonlinear programming algorithm. It makes use of accurate and smooth approximations of a bounding-box wire length objective function and generalized bin-based density constraints. These incorporate complicated pairwise cells non-overlapping constraints and are evaluated globally and scalably by fast numerical methods for a Poisson-based partial differential equation (PDE). The nonlinear optimization engine is embedded in a multilevel framework which enables scalability and better global optimization.;Experiments show that mPL6 is a fast placement algorithm producing the shortest wirelength among the state-of-the-art academic placers. It is a stable and robust algorithm that has consistent good performances on wide variety of publicly available benchmarks. The runtime of mPL6 on designs with problem size up to 2 millions is less than 9 hours on a Linux, 1.8GHz AMD Opteron machine. |
