May, 1997

Advanced routing for deep submicron technologies

Richard Brashears,
Group director, product and design flow engineering, Cadence Design Systems;
and Andrew Kahng, Associate professor, UCLA

Consider routing in 2001, only four years away. Leading-edge CMOS processes will be at 0.12-µm minimum feature size, with 0.9-V supply voltage. Dies will be severely interconnect-limited, despite back-side power distribution (distributing power via plated through-holes or other means). Local interconnects (wires on metal layers 1-4) will have aspect ratios as high as 3:1, with minimum contacted pitch of 0.35 µm. A short 100-µm local metal trace will have over 80 ‡ resistance and 20 fF capacitance. And, 5 µm of wire will give the same capacitive load as a gate input.

At the same time, minimum inverter delays will approach
40 ps, and global interconnects (on metal layer 5-10) will be carefully pre-routed and/or assigned to layers, since the layers will be highly tuned to enable balancing of signal performance, signal distribution, and clock/power distribution. With ten layers of interconnect, layouts will be virtually channelless. A leading-edge design will also have 120 million transistors connected by over 4 km of wire, in a die 20,000 µm on a side. Clock frequency will be well over 1 Ghz.

Together, high-performance architecture and circuits trends, time to market, and the economics of system-on-chip integration imply that in 2001:

• Nearly all 60+ million non-memory transistors will be in pre-designed blocks;
  
• 30-95% of them will be in wide data paths, with top-level interconnect dominated by wide buses;
  
• A significant fraction of the design will have an "analog" or mixed-signal flavor.

The interconnect design challenge

Interconnect design will be as critical to system functionality as choice of embedded cores or overall system architecture. Performance (timing, signal integrity), reliability, and routability will have to be considered simultaneously, creating many new challenges to automatic routing tools. For example, the building block, system-on-chip methodology leads to top-level routing that's "lumpy" and "co-constrained."

Constraints on routing will include:

• High-level system timing and boundary conditions;
  
• Detailed budgeted slacks and required arrival times;
  
• Thermal, hot-electron and electromigration reliability rules;
  
• Noise margins at various classes of logic nodes.

Yield and design reuse economics will require that the interconnect design be statistically centered, and optimized for a range of future process shrinks. To handle this, an advanced router must have sufficient degrees of freedom to change many things: shielding, spacing, and interleaving; device and wire sizing; local logic resynthesis; detailed cell placement; and even on-the-fly cell layout synthesis.

This brave new world is arriving much faster than predicted. Many forces are driving advanced IC routing technology, including: new design methodology contexts; a need for improved constraint handling, functionality, and controllability; and a need for routing tools to blend seamlessly and predictably into all phases of a top-down, convergent chip-implementation methodology.

It's well-understood that ignoring physical implementation in top-down synthesis doesn't permit a "convergent" design process. For 0.25-µm and succeeding process generations, anticipated "design-planning" (chip-implementation planning) tools will accept RTL structural HDL code and system timing descriptions as inputs, and return outputs that include the shaping and packing of blocks, top-level route planning, block pin assignments, and inter- and intra-block timing budgets. This process involves many iterations, back to top-level RTL coding and hierarchy partitioning, or forward through logic synthesis, block layout, and assembly.

In the planning, what will make or break the design depends on whether the routing satisfies crosstalk and delay requirements, fits within available resources, and meets a host of other constraints. Routing is no longer a final batch-run step--it must be iteratively estimated and resynthesized. The route-planning operation functions as the "constructive estimator" of all relevant interconnect characteristics needed to make correct design-planning choices.

The deep submicron design planner will use route-planning results in myriad ways to:

• Modify the floorplan (floorplan compaction and pin assignment derived from the top-level route planning);
  
• Determine new synthesis constraints (budgets for intra-block delay, block input/output boundary conditions);
  
• Modify the netlist (driver sizing, repeater insertion, buffer clustering);
  
• Determine placement directives for block layout (over-block routes will locally affect utilization factors within blocks);
  
• Determine performance-driven routing directives for block layout (wire tapering, spacing, shielding, etc.)

Route planning entails hierarchical and area pin modeling, understanding power/area-delay tradeoffs in devices and interconnects, and the ability to perform and verify "intelligent" bus routing, timing- and signal-integrity-driven routing, repeater insertion, tapering, shielding, interleaving, and so on. Clearly, an advanced routing tool with an out-of-the-box charter is required.

At the block-implementation level, routing is the constructive estimator used to refine floorplan optimizations, synthesis constraints, and place-and-route directives. In later (post-synthesis) iterations, the router can bring constructive estimates, as well as tradeoff analyses of clock, test, and power routing, to bear on the design optimization. Today's methodology typically defers routing until block implementation and "final assembly." In 2001, "assembly" will be nearly implicit in the top-down, convergent-interconnect synthesis methodology.

Constraint-driven technologies

Routing approaches are often classified according to such axes as gridded vs. gridless, area-based vs. channel-based, full-chip vs. switchbox, etc. More detailed classifications distinguish between breadth-first (A* or maze) vs. depth-first (line probe) vs. pattern search, iterative (ripup-reroute) vs. combinatorial (multicommodity flow, linear programming with rounding) heuristics, right- vs. wrong-way-based routing resource models, and so on.

Within this taxonomy, high-capacity ASIC routers typically employ gridded, area-based, N-layer, symbolic, switchbox, global+detailed, A* search, and iterative rip-up/re-route approaches. By contrast, routers for lower-capacity, auto-interactive, full-custom and chip-assembly applications (typically, evolved from high-end PCB tools) are distinguished by their use of gridless, shape-based, and full-chip approaches. Both types are effectively solving a wide range of today's leading-edge design problems. And each must evolve to deliver the constraint handling, functionality, and controllability needed for advanced routing in 2001.

Advanced router technologies require a rich vocabulary and powerful mechanisms to capture, translate, enforce, and verify cost functions and the many constraints of deep submicron interconnects. To handle complex constraints and objectives, an advanced router will have to exploit wire widths, spacings, and shielding/interleaving and driver and repeater sizing. This suggests a shift to gridless, shape-based routing, since gridded, right-way-centric approaches are both unnatural and wasteful of layout resources. The overhead of shape-based routing is offset by the underlying design methodology. Block complexities will be limited by synthesis tools' ability to satisfy performance constraints, and interconnect complexity will remain tractable due to hierarchy.

Other capabilities are required when detailed topology design affects interconnect parasitics in such a way as to render pre-routing estimates useless. Search mechanisms will change when iterative rip-up/re-route no longer finds the topologies that satisfy given constraints. New utilities will "atomically" construct entire topologies to optimize delay, skew, and area/delay/power tradeoffs in arbitrarily costed layouts. The router will be empowered to perform logic resynthesis (gate splitting, buffer-inverter clustering) when gate-level netlists are synthesized with imperfect assumptions about the physical embedding.

Detailed placement will also become part of interconnect design, as up to 50% or more of the design's cell instances are repeaters and inverters, and as resynthesis flows (based on pre-detailed routing) lose accuracy. For leading-edge designs, routing-directed, on-the-fly synthesis of cell layouts (i.e., an "infinite cell library") can be expected.

The next generation will be distinguished from present-day methodology by its longer loops and added flexibility, as well as its "construct by correction" philosophy. Long loops stem from the need to "constructively estimate" deep into the design process (to the level of a gate-level netlist, placement, and detailed routing, even while performing early chip planning). Added flexibility stems from overlapping degrees of freedom that can be used to solve a given violation. For example, a crosstalk violation can be fixed by a combination of placement, net ordering, shielding, spacing, driver sizing, and repeater insertion. Together, these attributes suggest the advanced router must support a highly re-entrant and interactive use model.

Toward convergence

Fundamental methodology changes are in store for routing technology, including unification of previously disparate flow stages, and empowering the router to perform logic resynthesis and detailed placement. The greatest challenges may lie in integrating new routing technology within an effective, convergent, design-planning and implementation methodology.

The first challenge is to make routing tools more predictable by upstream design steps. The CPU cost of "constructive estimation" (brute-force modeling by actually executing the router) can hamper the search of the design space, particularly when deeper lookahead is required. Hence, modeling of routing tools must receive greater attention.

The second challenge is to establish appropriate "flow-internal links," so that the "design planner's route planner" can be an early consumer of constraints, simulation results, and other information from earlier flow stages. In tight loops, implementing such links with common data structures or common databases, instead of typical binary or ASCII interchange files, can afford substantial speed-ups.

The third and greatest challenge is to improve the synthesis-analysis links, particularly within the parasitic extraction/performance analysis/interconnect loop. Determining cost-effective analysis methods, and melding traditionally distinct geometric databases from layout and verification, are critical to achieving the so-called "stage 3" routing capability that directly embeds physical performance analysis into constraint-driven interconnect synthesis.