Placement, Routing, and Congestion in the Logic Array

A synthesized netlist names cells and the connections between them. Placement decides which physical site each cell occupies, and routing decides which wire segments and switches carry each connection. Both problems are NP-hard in general and are solved by heuristics whose quality depends on the design’s structure. The deliverable is not merely a legal arrangement; it is an arrangement whose delays satisfy the constraint file, and the two goals are frequently in conflict.

Partitioning before placement

The first decision is not about position but about grouping. Cells that will share a lookup table are merged during synthesis; cells that will share a configurable logic block are grouped during packing. Packing matters because a block’s inputs are a limited resource: a slice holding four lookup tables has a bounded number of independent inputs, and a group of tables that need more inputs than the block offers cannot be packed together regardless of how connected they are.

Packing trades two things. Tighter packing reduces the number of blocks, which reduces the number of inter-block connections and therefore routing demand. But tighter packing also concentrates a block’s signals into a small area, which can push its fanout into a region where the local channels are already saturated. A packer that maximizes internal connectivity without regard to placement’s likely outcome produces a netlist that is compact and unplaceable.

Packing also determines the fate of the block’s spare resources. A slice holds both lookup tables and flip-flops, so a netlist that uses one and not the other leaves half of every block idle: a slice filled with combinational tables has its registers unused, and a slice holding nothing but registers has its tables unused. A packer that pairs each register with the table that drives it keeps both halves occupied, and one that groups by function instead can leave whole blocks holding only one of the two.

The placement problem and the annealer

The classic formulation places cells so that the sum of connection lengths, weighted by criticality, is minimized. Connection length is estimated as the bounding box or half-perimeter of the net’s pins, which is cheap to compute and correlates with wirelength but not with delay.

Simulated annealing is the traditional solver. It starts from a random or constructive placement and repeatedly proposes moves, accepting improvements and, early on, accepting some degradations with a probability that decreases with a temperature parameter. The cost function combines wirelength, timing, and a penalty for regions where demand exceeds supply. Early in the anneal, large moves are accepted, which lets the placement escape local minima; late, only improving moves are accepted, which refines.

The timing term in that cost is the awkward part. A net with little slack should be short; a net with abundant slack can be long. But the placer evaluates a cost function that includes the whole design, and improving one critical path can lengthen several others. The annealer does not reason about paths; it reasons about a weighted sum, and the weights are set by the slack distribution at the start. A design whose constraints are wrong gets placed for the wrong objective, which is why the constraint set described in timing constraints and clock definitions is an input to placement and not only to reporting.

Modern tools rarely run a pure annealer over the whole device. Analytical placement, which models the problem as a continuous optimization over cell positions and then legalizes them onto discrete sites, scales better to large designs and has become the dominant method for the placer’s initial phase, with local refinement afterwards. The trade is the same: analytical methods are fast and produce good global structure, while local search fixes the details that the continuous model smooths over.

Routing as a negotiation

The router’s job is to assign each net a path through the segmented channels without exceeding the capacity of any wire segment or switch. Early routers were rip-up-and-reroute: route every net greedily, then identify the nets that failed and rip them up and try again. The failure mode is oscillation, where two nets repeatedly displace each other.

The PathFinder algorithm changed the approach by making the cost of using a congested resource rise with the number of nets using it. Each resource carries a present congestion cost, which rises as it is overused, and a historical congestion cost, which accumulates across iterations for resources that are persistently overused. During an iteration, nets are routed one at a time, each choosing the cheapest path under the current costs, and overuse is allowed temporarily. Successive iterations increase the present cost more steeply, which drives the solution towards a legal routing where no resource is overused, while the historical term prevents the solution from settling into a region that was congested in early iterations.

The consequence for the designer is that routing is a global allocation process with a social contract: a net that takes a short path through a busy channel costs every other net that wanted that channel. A design with a few nets that are individually cheap but collectively excessive will route by spreading other nets far away, which lengthens their paths and creates timing failures that no individual constraint anticipated.

Congestion: what it looks like and what causes it

Congestion reports show, per region, the ratio of routing demand to available capacity. Demand above 1.0 means the region cannot route as placed, and the tool either fails or detours nets around it.

The dominant causes are structural. Wide buses that cross the device, such as a 256-bit datapath that runs from an input to a memory on the opposite side, demand a band of channels proportional to their width. A module with a large number of connections to the rest of the design, such as a control block that drives enables everywhere, creates a hotspot at its boundary. A large multiplexer implemented as a crossbar, which is how a wide selector is often described, requires every source to reach every destination and therefore consumes channel capacity quadratically in the number of inputs.

# Per-region congestion estimate after placement, before routing.
report_design_analysis -congestion -of_objects [get_pblocks pblock_core]

The remedies are structural before they are physical. Registering a wide bus at the boundary of a module breaks it into segments that each cross a smaller region. Sharing a control signal as a decoded local enable rather than routing the full-width control across the design removes a hotspot. Replicating a block so that each instance serves local logic reduces the fanout that would otherwise converge. Only after those changes does floorplanning help, and floorplanning a design whose congestion is caused by a wide bus merely moves the problem.

Floorplanning and its failure modes

A floorplan assigns regions of the device to modules, using placement constraints that confine each module to a rectangular area. The benefit is locality: modules that communicate are placed near each other, and their connections do not cross the whole device. The cost is that a confined module cannot use any cell outside its rectangle, so the density inside increases and internal congestion rises.

The common failure is over-constraining. A module given a region just large enough for its cells, with no room for routing, may fail to route internally while the rest of the device is empty. A useful rule is that a region should have appreciable slack in both cells and channel capacity, and that regions should be sized after inspecting the post-placement congestion map rather than before.

A second failure is the boundary pin problem. A module’s region boundary becomes a wall through which its signals must pass, and the number of signals crossing a boundary is a resource with its own limit. Two modules split across a boundary that carries a 128-bit bus between them may each place without congestion and still fail at the boundary, because the boundary’s channel capacity is smaller than the total number of signals. The remedy is to place the connected modules adjacently and to register the bus at the boundary, which is also the change that helps the timing.

Timing-driven versus routability-driven

The placer and router can be told to prioritize timing or routability. Prioritizing timing lets the tool spread logic to shorten critical paths, which raises congestion. Prioritizing routability compacts logic, which shortens average connections but may place a critical path’s endpoints further apart.

The sequence that works in practice is iterative and evidence-driven: run implementation with timing-driven placement, look at the worst paths and the congestion map together, and decide which is the binding constraint. If the worst paths are 80 percent routing, congestion is the problem and the design needs structural change. If the worst paths are mostly logic with reasonable routing percentages, the problem is the pipeline depth or the logic structure, which belongs to retiming and pipelining. Only when the paths are individually short but geographically scattered does floorplanning become the right tool.

One further property deserves mention because it shapes expectations: placement is deterministic for a given tool version, seed, and constraint set, but not across versions. A design that closes timing on one tool release can fail on the next, because the placer’s cost model or the router’s ordering changed. Recording the tool version alongside the bitstream is part of making a build reproducible, and it is the reason timing closure is a property of a build rather than of a source tree.