Early relief for 45-nm routing congestion

Moore's Law is both a blessing and a curse. Each new manufacturing process generation provides designers an opportunity to squeeze roughly twice the circuit functionality into an unchanged die area, significantly lowering fabrication costs for systems-on-chip (SoCs). Yet doubling circuit density leads to more wire-routing congestion, which, if significant enough, can make it extremely difficult to achieve a successful detailed route. The problem already occurs frequently at the 90-nm process node and will only get worse in designs fabricated at smaller geometries.

It's important to examine the causes and effects of congestion and to find ways to address the problem. Before physical implementation, designers can examine highly congested regions of a design, changing physical and floor-plan constraints, modifying the register transfer level (RTL) or performing synthesis optimizations to alleviate congestion "hot spots." The ability to predict and mitigate routing congestion during synthesis helps designers create a better starting point for physical implementation, saving both time and effort.

Wire-routing congestion occurs in the place-and-route phase of design when too many wires must be routed through regions too small to accommodate them. To assess the problem, routing tools divide a design into a virtual two-dimensional array of rectangular grids of equal size and routing capacity. For each design technology, a maximum number of wire-routing tracks per grid edge is allocated for routing nets. During global route, the tool calculates demand for vertical and horizontal tracks for each grid based on the number of allocated tracks along each edge. Congestion occurs when track demand exceeds supply. The number of congestion violations per grid is equal to this difference.

Two primary sources of congestion exist for any given design. The first is caused by physical constraints on global placement and routing. If a given design sees an increase in gate use (such as an increase in cell area as a percentage of the total area), the place-and-route tool must "squeeze" more gates into the same area, requiring more routing tracks in certain regions of the design, thus contributing to congestion in these areas. Floor plans that impose challenging constraints based on the locations of macros and ports can also introduce or aggravate congestion in designs that already have high gate use.

The second source of congestion, sometimes referred to as standard-cell congestion, relates to logical structures in the design netlist itself. Depending on what RTL constructs are used and what standard logic cell optimizations are performed during synthesis, some netlists will have intrinsically higher interconnected cell topologies than others. For example: Lookup table logic, coded as case statements in the RTL, often results in highly interconnected topologies in the netlist, something that can lead to congestion.

Physical constraints, highly interconnected logic structures, or a combination of the two can lead to congestion hot spots--regions in a design with high concentrations of grids with significant congestion violations. If congestion in these hot spots is severe enough, it may be impossible to route the design without generating a large number of design rule check (DRC) violations. On the other hand, it may be possible (with significant effort), but numerous timing violations may be encountered that require modifications to the RTL, resynthesis, replacement and rerouting. Whether congestion hot spots make a design entirely "unroutable" or only "difficult to route," dealing with their effects leads to multiple and lengthy iterations between logical and physical implementation, sometimes adding weeks to a project schedule.

Implications for 45 nm
To assess the impact of routing congestion on a 45-nm design flow, let's say that you currently design 90-nm SoCs of roughly equivalent gate complexity and gate use, and that you encounter severe congestion in an average of one out of every three designs. You plan to take advantage of a 45-nm manufacturing process in the near future that will allow you to squeeze roughly four times the logic into the same die size that your current 90-nm process allows. Assuming the same gate use, you will likely encounter severe congestion in about 80 percent of your 45-nm designs. This implies that the number of iterations caused by congestion will increase by a factor of 80 percent divided by 33 percent, or 2.4, if the number of designs you tape out each year remains the same.

If you already encounter severe congestion in nearly every design, you can expect migration to 45 nm to produce an increase in the number of congestion hot spots proportional to the increase in gate count per design.

These examples illustrate that in the absence of a better way to work around wire congestion, significantly more time, effort and resources will be needed to deal with the problem at 45 nm.

Working around wires
Certainly, one approach to dealing with routing congestion is relaxing the physical constraints, although this might not be feasible--or even desirable--at times. Lowering the target gate use, for example, will produce a larger die size, increasing manufacturing costs. Furthermore, changing the floor plan late in the design phase reduces congestion but can create other problems (such as timing divergence) and should be considered a last resort. Finally, resolving standard-cell-type congestion often requires major changes to the netlist topology that cannot be accomplished during the place-and-route phase.