Simulated annealing (SA) for physical placement is the probabilistic combinatorial optimization metaheuristic that models the thermal annealing process in condensed matter physics to escape local cost minima and converge on globally near-optimal placement solutions for VLSI cell placement, floorplanning, and mixed-signal block arrangement. Drawing from Metropolis et al.'s Monte Carlo sampling of thermodynamic equilibrium states, SA accepts not only cost-improving moves (wire-length reduction, congestion improvement) but also cost-increasing perturbations with probability $P_{\text{accept}} = \exp(-\Delta C / T)$, where $\Delta C$ is the cost increase and $T$ is the annealing temperature. At high temperatures, large uphill moves enable exploration of the entire solution space; as temperature cools according to a carefully designed annealing schedule, the algorithm increasingly accepts only improving moves, converging to a high-quality placement near the global optimum. Modern SA placement engines form the core of industry tools including Cadence Innovus and Synopsys Fusion Compiler for multi-million-instance SoC floorplanning.

The Metropolis acceptance criterion is the statistical mechanism enabling simulated annealing to escape local optima and explore global placement space. At each SA iteration, a random perturbation move (cell swap, displacement, or cluster shift) generates a candidate placement with cost change $\Delta C = C_{\text{new}} - C_{\text{old}}$. If $\Delta C \leq 0$ (cost improvement), the move is always accepted. If $\Delta C > 0$ (cost increase), the move is accepted with probability:

where $T$ is the current annealing temperature. High $T$ gives $P_{\text{accept}} \approx 1$ even for large uphill moves, allowing the algorithm to escape local minima basins. As $T \to 0$, $P_{\text{accept}} \to 0$ for any positive $\Delta C$, making the algorithm increasingly greedy. Critically, if a random number $r \sim U(0,1)$ satisfies $r < P_{\text{accept}}$, the move is accepted regardless of cost sign.

Geometric cooling schedules balance solution quality against runtime by controlling the temperature decay rate. The most common schedule applies a constant multiplicative factor: $T_{k+1} = \alpha \cdot T_k$, where $\alpha \in [0.90, 0.98]$ determines the cooling rate. Starting from initial temperature $T_0$ (calibrated so approximately $80\%$ of random moves are accepted), the algorithm performs $M$ inner-loop moves at each temperature step before cooling. Total moves equal $M \times N_{\text{steps}}$, where $N_{\text{steps}} = \log(T_{\text{freeze}}/T_0)/\log(\alpha)$. With $\alpha = 0.95$ and $N_{\text{steps}} \approx 135$ steps from $T_0$ to $T_{\text{freeze}} = T_0 \times 10^{-3}$, each step executing $100k$ moves gives approximately $13.5\text{ M}$ total perturbations per placement.

Half-Perimeter Wire Length provides an efficient incremental wirelength proxy that enables O(1) cost updates per move. For a net connecting cells at coordinates $\{(x_i, y_i)\}$, the Half-Perimeter Wire Length (HPWL) is:

Summed across all nets, total HPWL correlates strongly with final routed wire length (within $10\text{--}20\%$). After a cell swap, only nets connected to the two swapped cells require HPWL recomputation; all other nets remain unchanged. This incremental update property reduces per-move cost evaluation from $O(N_{\text{nets}})$ to $O(\text{fanout of swapped cells})$, enabling millions of moves per second on modern multi-core processors.

Timing-driven placement integrates incremental static timing analysis to weight critical-path nets during annealing. Pure wire-length minimization ignores path delays and can yield placements with timing violations requiring expensive post-placement fixes. Timing-driven SA assigns net weights $w_i > 1$ to nets on critical timing paths, modifying the cost function to $C = \sum_{\text{nets}} w_i \cdot \text{HPWL}_i + \lambda \cdot \text{slack\_penalty}$. During annealing, a lightweight incremental timer updates slack estimates after each accepted move affecting critical nets. Nets on paths with negative slack receive exponentially higher weights ($w \propto e^{-\text{slack}/\sigma}$), attracting their driver and receiver cells closer together and reducing propagation delay until timing closure is achieved.

st=>start: Input: gate-level netlist, standard cell library, floorplan constraints
init=>operation: Initialize: random or analytical seed placement; calibrate T₀ for 80% acceptance rate
outer=>operation: Outer loop: current temperature T; check freeze criterion (accept_rate < 0.001)
inner=>operation: Inner loop: M perturbation moves; generate swap/displace/cluster candidate
delta=>operation: Compute ΔC (incremental HPWL + timing penalty); Metropolis accept/reject
cool=>operation: Cool temperature: T ← α × T; update net weights from incremental STA results
legal=>operation: Legalization: remove cell overlaps; align to placement rows and site grids
pass=>end: Signoff-quality placement: HPWL within 5% of bound; zero DRC; timing constraints met
st->init->outer->inner->delta->cool->legal->pass

Achieving routing-closure-quality VLSI cell placement across multi-million-instance SoC designs requires analyzing physical placement optimization through a simulated-annealing-placement-temperature-schedule-and-metropolis-criterion lens. By uniting the probabilistic Metropolis acceptance rule, geometric temperature schedules with adaptive feedback, incremental half-perimeter wire-length evaluation, timing-driven net weighting, and parallel multi-chain annealing, SA placement engines navigate the exponential combinatorial solution space of million-cell designs. Mastering SA placement fundamentals enables engineers to tune placement quality-runtime tradeoffs for advanced-node FinFET and nanosheet SoC tapeouts targeting 5–3 nm process nodes.