Getting early access to useful wire information requires access to smart routing technology that has the capacity and flexibility to correctly route multiple millions of nets flat, and can be leveraged during silicon virtual prototyping, logical/physical optimization and clock tree synthesis.

There are three basic categories of routers to choose from on the market today: grid-based routers, shape-based routers and graph-based routers. The size, complexity, and performance target of the design dictate which category of router is most appropriate.

Grid-based routers

Gridded routers, the most commonly used today, perform well for designs in less than 3M gate range (flat) and with geometries at 130 nm and larger. Depending on clock speed and complexity, this capacity may be substantially reduced. Gridded routers are known for their relatively high speed, but lack the flexibility required for today's complex designs. Even so, gridded routers have been the standard for years and have held up under growing design complexity for almost a decade.

Gridded routers superimpose a mesh-like template over the routing area of the design with evenly spaced tracks (or multiples thereof), called "grids," running both vertically and horizontally across the design area. Each vertical and horizontal grid intersection point on the mesh is maintained as a pointer in memory, and any routing operation that is performed must take into account all the grid points in the design as a whole.

Any trade-offs, timing, congestion, or DRC involved in the specific operation must be factored in before completion. All of these activities take time and resources, which is why gridded routers are less desirable for designs over 2M gates.

The larger the design grows or the smaller the process geometry becomes, the more grid points need to be allocated in memory. This means it will take more time for a gridded router to perform any given task.

Figure 1 -- Routing choices

Shape-based routers

Shape-based routers are known for extreme flexibility, although they are severely limited in capacity and performance. On-grid or off-grid routing and the respective connection points are not important for this genre of router. Shape-based routers do not need to adhere to the concept of a grid, and therefore are not bound by the grid's restrictions. In many cases, a shape-based router is the preferred solution for top-level routing and can handle very complex requirements, such as differential pair routing, shielding, bus interleaving, river routing, along with other analog or custom routing requirements, such as 45-degree routing, that other routers cannot even begin to handle.

Unfortunately, shape-based routers top out at approximately 20,000 to 30,000 nets, and this limits their use to very small designs or top-level designs only. As a result, shape-based routers have been used as specialty routers only at the top level (grid-based routers would be used for block-based routing).

Using both a grid-based router and a shape-based router in tandem for a given design flow has been a common scenario for designers in the past. However, because of the inherent limitations of each of these routers individually, together with the amount of nets at the top level for system-on-chip (SoC) type of designs today, another type of router is needed.

Graph-based routers

Graph-based routing is a leap forward in routing architecture. This type of router effectively brings together the performance characteristics of a grid-based router and combines them with the flexibility of a shape-based router. The end result is a very fast tool capable of handling all aspects of routing complex multi-million gate designs, both at the block level and the top level.

Graph-based routers view a design similarly to grid-based routers in that there are grids both in the vertical and horizontal direction that can be followed. However, a graph-based router considers these grids only as guidelines for routing, and is not required to use them. Off-grid routing or variable metal pitch does not pose a problem for this kind of router, and it can handle the most complex routing rules and off-grid connection points without slowing down.

In addition to offering flexibility, the graph-based routing algorithm does not require that every grid intersection on the design be allocated a pointer in memory. Only the grid points in the vicinity of the routing task will be considered as needed, and the time it takes to perform any given task is considerably faster than with a grid-based router. This also means that through efficient memory handling, graph-based routers can handle significantly larger design sizes.

Traditional design closure methodologies rely on placement information and global route estimates at the front-end of the design cycle to provide reliable information to make critical design decisions. These wire estimates have shown to be orders of magnitude away from post-route timing results. For nanometer design, a more realistic approach to design and optimization based on real physical wire information is required.

Real wires are real important

Interconnect, and its impact on timing and SI, has proven to be one of the most daunting challenges for designers and the most difficult element to predict. At 90nm, wires account for nearly 75% of a circuit's total delay. Even more insidious, however, is that nearly 40% of these nets have greater than 50% of their total net capacitance attributed to the cross-coupling capacitance between neighboring signals. At this point a new design and optimization paradigm based on real wires is required.

Figure 2 -- Impact of cross-coupling on total wire capacitance

Traditional design methodologies leave final routing until the end of the flow, which marks the first time a designer can accurately analyze the impact of a proposed final wire topology on overall routability, timing, and signal integrity (SI). Often, a project at this stage does not meet its timing target and is inundated with literally tens of thousands of SI violations which, to fix, would add weeks and even months to the design schedule.

Faced with the decision to either spend a significant amount of time further optimizing a design for timing and SI improvements, or to meet a strict tapeout schedule, designers often opt to accept a lower performing chip and hope that any remaining design issues will not result in a silicon failure. Realistically, however, most of these designs that go to fabrication result in failed silicon the first time, and of these, most do not make it through to tapeout the second time.

Until real physical wires are present, layer selection, layer order, wire length, via count, spacing between adjacent signals, and overall net topology are not part of the optimization equation. As a result, timing predictions based on global routing are highly inaccurate and can differ from post-route analysis results by as much as 700%, which underscores the issue that non-convergent front-to-back design iterations are a substantial problem when attempting final tapeout.

One solution is to obtain real physical wire information as early in the design cycle as possible, when there is more flexibility to modify design and connectivity directives for preventative measure. Using detail routing information as the basis for early design trade-offs during silicon virtual prototyping is key to accurate timing and SI prediction and prevents surprises from occurring late in the design cycle when they are much more difficult, time consuming, and expensive to resolve.

A viable router for nanometer design must be able to quickly deliver accurate physical wire information, and be accessible throughout the complete design flow from register transfer level design to detail routing and final sign-off.

Requirements for routing in the nanometer era

Not only are routers responsible for connecting all signal nets, power nets, and busses in a design, they are also expected to (1) do this quickly and be free from DRC, LVS, and SI errors and (2) effectively meet design for manufacturability and overall timing specifications. With design complexity and design sizes growing to over 100 million gates, this becomes an enormous task.

Smart routing
Routing large, high frequency, complex designs is a continuous process in the nanometer era. However, all the available routing performance, capacity, and flexibility will not deliver fast time to market if a design is not able to converge on timing or SI, cannot be routed, or cannot meet manufacturability rules.

A router may be able to route a design functionally correct, but have trouble achieving DRC-clean results due to complex spacing and/or wire width rules. Or, it may yield a result that is DRC-clean but plagued by timing convergence issues. More often, the timing target of the design is met and routing is DRC-clean; however, thousands of SI violations may appear, thus causing incremental delay or functional errors that must be addressed before tapeout.

At nanometer geometries, problems relating to congestion, timing, SI, and manufacturability have become more severe due to exponentially tighter physical and electrical tolerances required for deep sub-micron designs. Requirements of next-generation routing are driving the demand for ever-increasing performance with taller, thinner wires, reduced feature sizes, lowered power supply voltages, and sinking threshold voltages.

New timing closure paradigm
Timing closure has always been a matter of concern for design engineers, and it drove automated timing-driven placement and routing tools and methodologies throughout the 1990s and into the new millennium. SI issues entered the picture at high-speed 250nm and 180nm technology nodes. Even at these technologies, SI issues could still be mostly addressed through post-route optimization via adequate analysis tools and manual fixes.

Because of this, design engineers have tended to treat timing and SI closure as mutually exclusive tasks — and many modern design methodologies are still geared around this paradigm through over-design or introducing pessimistic design practices. In a world that demands every nanosecond of performance from silicon, over-design can be a waste of chip or board space, and introducing unnecessary pessimism can artificially stunt chip performance.

Traditional design methodologies require global, detailed, and search-and-repair routing to run before accurate extraction, delay calculation, timing, or SI analysis can be performed. All of these tasks are run in a serial fashion and require starting over again if a design closure problem should occur along the way. For nanometer design, a smarter, more efficient and heuristic parallel routing approach that can handle these tasks synchronously with detailed routing is required. The ability to perform incremental per-net RC-based extraction and delay calculation on-the-fly to support SI, timing, and congestion-aware routing is essential.

To achieve fast design closure for nanometer design, timing closure and SI need to be addressed concurrent to wire construction and optimization, when real wire information is available. This requires a multi-dimensional approach to detail routing that can grasp the expanding interdependencies between chip timing, SI, design for manufacturability and congestion in routing. The new timing closure equation for nanometer design must be timing closure plus the crosstalk impact on overall timing.

Finally, an effective nanometer router should have the flexibility to use industry-standard timing information for timing-driven routing and optimization. Correlating the results of multiple timing engines for each point tool or technology across a design flow is tortuous and introduces massive inefficiencies and inaccuracies. Clearly, having an open architecture for timing driven routing and optimization is essential.

Powerful control mechanisms
For optimal final results, explicit control mechanisms must be in place to make smart, simultaneous trade-offs between congestion, manufacturability, timing, and SI issues. An advanced and unified routing algorithm is required to combine all of these aspects.

Routing optimization features should include explicit per-net length controls to avoid detoured or scenic routes and create as many short point-to-point connections as possible. Simultaneously, the router should exercise intelligent layer selection to minimize net resistance and capacitance, including cross-coupling capacitance from neighboring wires.

The detailed router should be able to perform on-the-fly timing and delay calculations (based on resistance and capacitance of the physical wires) while it lays down routing tracks. This way, the router knows immediately if, for example, it should move or otherwise modify the track that was just committed. The router should also have the power to change a track assignment for a given wire, such as moving it away from a strongly driven signal that could be a candidate for SI problems, or choose a different layer, based on layer resistivity or capacitance.

Additionally, to reduce crosstalk effect and to correct SI issues during routing, a nanometer router must also have the authority and automation to perform on-the-fly wire spacing, layer switching, net re-ordering, and parallel wire reduction. Since detail routing is where overall net topology and final net characteristics are completed, SI and timing analysis at this stage will be accurate. If a router is not able to perform SI prevention on-the-fly with detail routing, multiple design iterations will be required to achieve final design closure (if even possible).

These mechanisms automatically employed at the right place and the right time will accelerate design closure and enable fast time-to-market.

Scaleable performance
A nanometer router must be scalable and be able to leverage the power of today's typical design hardware environments, which can consist of a mixture of multi-CPU machines, and both centralized and decentralized computer farms. Applications that leverage multi-CPU workstations can deliver near-linear overall performance scalability with each additional CPU added, but distributed methodologies also provide a degree of scalability as well and tend to be a low-cost alternative to multiple CPU servers. Routing applications that can simultaneously combine both architectures would have the most flexibility and maximize performance scalability.

A scaleable architecture is critical in the nanometer era because significantly more data must be processed quicker and time-to-market pressures require maximum speed. A multi-CPU architecture which spreads a computational workload among multiple processors on a single machine is technically favored over a distributed computing methodology, which spreads the workload among multiple servers through a load-sharing mechanism.

However, the cost advantage of dual-CPU Linux farms is a very compelling argument and hard to dispute. A lesser degree of linear performance increases is acceptable to cost conscious design teams under these conditions.

To be effective, a nanometer router must be able to leverage either or both architectures and deliver the maximum performance possible while being flexible enough to fit any hardware environment.

Summary

As today's designs continue to grow in complexity, routing has an even more critical role to play. Early detailed routing provides the physical wiring information necessary for prevention of problems for physical synthesis and silicon virtual prototyping, and delivers good results in design closure. In the nanometer era, look to new-generation routing technologies that combine high performance and capacity with the integration of congestion, timing, SI prevention, and correction algorithms as the best means of getting to design closure quickly. These are the routing technologies will ensure faster time-to-market and time-to-profitability.

David Desharnais is senior product marketing manager for Digital IC Marketing at Cadence Design Systems. During over a decade of digital design and EDA industry experience, David has held key positions in technical applications, business development, and marketing.