place

**Place and Route Algorithm Fundamentals** is **the computational methods for positioning logic gates (placement) and establishing connections between them (routing) — crucial for physical implementation achieving timing, power, and manufacturability targets**. Place and Route (P&R) is the core of physical design, transforming logical netlist into physical layout. Placement assigns each logic gate (cell) to a specific location on the chip. Routing establishes wires connecting placed cells according to logical netlist. Quality of placement directly affects overall chip quality — timing, power, and manufacturability depend on placement. Placement Algorithms: Simulated annealing: probabilistic algorithm starting with random placement, iteratively swapping cells. Swap costs objective function (wirelength, timing, congestion). Probabilistic acceptance of cost-increasing swaps helps escape local minima. Convergence is slow but effectiveness is good. Min-cut partitioning: recursively partitions netlist minimizing cut (wires crossing partitions). Partition-based placement places in assigned regions. Fast but may be suboptimal. Analytical methods: optimize objective as continuous problem, then discretize solutions. Force-directed placement uses repulsive/attractive forces. Nonlinear optimization approaches converge quickly. Genetic algorithms: mimic biological evolution, mutating and crossing over solutions. Slow but robust. Placement objectives: wirelength minimization (reduces delay and power), timing optimization (critical paths first), congestion relief (even distribution of wires), thermal management (avoid hotspots). Multi-objective optimization balances these goals. Legalization: initial placement may have overlaps or standard-cell violations. Legalization moves cells to legal rows while minimizing additional movement. Constraint satisfaction and local optimization techniques legalize placement. Routing Algorithms: Maze routing: explores paths through grid from source to sink, finding shortest unblocked path. Dijkstra or breadth-first search finds path. Queue-based approach explores efficiently. Scales poorly to large designs. Negotiated congestion-driven routing: global routes approximately, then detailed routing refines. Global routing accounts for congestion; detailed routing assigns specific wires/vias. Iterative negotiation resolves congestion. Steiner tree routing: connects multiple pins minimizing total wirelength. Constructs minimal tree connecting all pins. Rectilinear Steiner tree is NP-hard; approximation algorithms find near-optimal solutions. Manhattan-distance routing: wires horizontal/vertical (no diagonal). Routing grid defines positions. Via placement at intersections. Multiple routing layers enable complex interconnect. Layer assignment: assigning wires to routing layers affects congestion and parasitic capacitance. Preferential via layers (preferred directions) guide routing. Via count minimization reduces resistance and power. Design Rule Checking (DRC) and Electrical Rule Checking (ERC) verify routing validity. Wire width and spacing must satisfy technology rules. Antenna rule violations (floating wires charged during processing) must be fixed. **Place and Route algorithms optimize placement and routing through combinatorial search, legalization, and multi-layer routing, balancing timing, congestion, power, and manufacturability.**