Electrostatics-Based Analytical Global Placement
Background
Placement problem is arranging the gate-level netlist generated by logic synthesis in a rectangular area, it plays an important role in the VLSI physical design automation. Placement performance largely impacts the downstream stages of power grid design, clock tree synthesis, power optimization, global detail routing, postlayout simulation and design variability.
Placement can be divided into two main steps: global placement and detailed placement. In general, the global placement involves macro placement and standard cell placement. The detailed placement includes legalization, wirelength and routability refinement. Among all the steps, global placement is one of the most crucial but timeconsuming steps, which can be cast as a constrained optimization problem. With the improvement of modern computing power, in order to obtain a batter placement quality result in the global placement stage, placement algorithm performance is also constantly improving.
Placement problem has been proved as a NP-hard problem, that is why early placement algorithms were similar to greedy algorithms that tried to find a better placement solution. The history of VLSI placement can trace back to the 1960s , when partition-based methods adopted the idea of divide-andconquer. Analytical placers appeared in the early 1980s, an analytical global placer models the problem as a constrained nonlinear optimization which determines the cell locations while trying to minimize the wirelength and cell overlap. Practical analytical placement techniques can be classified as quadratic and nonquadratic. The quadratic methods are efficient but show relatively worse performance, while non-linear optimization approximates the cost functions more smoothly with the cost of higher complexity. Most state-of-the-art placers follow the framework of analytical placement algorithms
Placement Flow
Global placement
Global placement aims at generating a rough placement solution that may violate some placement constraints while maintaining a global view of the whole netlist.
Legalization
Legalization makes the rough solution from global placement legal by moving modules around locally.
Detailed placement
Detailed placement further improves the legalized placement solution in an iterative manner by rearranging a small group of modules in a local region while keeping all other modules fixed.