Handbook of Algorithms for Physical Design Automation part 42 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 392 Handbook of Algorithms for Physical Design Automation Relaxation Iterative improvement at each level may employ various techniques network flows simulated annealing nonlinear programming force-directed models provided that it can support incorporation of complex constraints appropriate to the modeling scale at the current level. Important considerations for relaxation include the following 1. Should it be local . annealing-based or global . force-directed 2. How should net models objectives and density models be adapted to different modeling scales 3. To what extent should relaxation be expected to change the starting configuration it inherits from an adjacent level 4. What termination criteria should be used 5. How scalable must the relaxation be 6. How easily can it be implemented 7. How readily can it be adapted to accomodate additional complex constraints For example in both mPL and APlace the density grid sizes and log-sum-exp HPWL smoothing parameter and bin-grid density smoothing parameters are chosen to match the scale of resolution implied by the average cluster size. For this reason both these engines carefully control the variation in cluster sizes during coarsening. mPL6 In mPL5 49 and mPL6 39 fast numerical PDE solvers are used in a generalization of the Eisenmann-Johannes force-directed model 10 13 at each level of hierarchy Chapter 18 . The global NLP relaxations in mPL6 are observed to dramatically improve quality over the earlier implementations 50 relying more on localized iterations. In mPL6 39 iterations at each level terminate when the average area-density overflow over all bins is sufficiently small. Convergence to nonuniform area-density distributions is enabled by the introduction of filler cells 51 unconnected to modules in the netlist. These are introduced hierarchically from the top-down in proportion to the white space available in each rectangular subregion region following the initial unconstrained placement.
