Global wiring for a performance-driven rubber-band router

This work describes a global router that addresses several of the performance issues of modern IC technology. This global router is a key component in a topological routing system that models wires as flexible objects and supports incremental design modifications, on-line design-rule checks and non-traditional wiring geometries. The global router does not require a predefined global routing graph, which is appropriate for modern IC technologies with increasing numbers of metal layers. It is based on a top-down partitioning approach and handles large problem sizes efficiently. An industrial cell-based design with more than 40,000 nets can be global routed in less than 15 minutes. I present a flexible strategy for assigning locations to nets that cross partition boundaries that reduces maximum routing congestion by 28% on average over the fixed-position method. I also investigate other aspects of the global routing problem including the relationship between partitioning strategy and crossing location assignment, global routing with non-uniform wire widths, and heuristic techniques for reducing routing congestion. I describe extensions to my basic global routing approach to consider both timing and noise. A topology selection algorithm chooses routing trees that balance routing congestion and timing goals. A branch bound allocation technique distributes timing slack among the branches of a tree topology. I explore several approaches to the problem of routing wires to reduces routing congestion within given timing bounds including methods based on both simple and k-shortest path searches. These techniques are effective at reducing the number of timing violations. The effects of crosstalk noise have been largely ignored during the global routing step due to the difficulty of evaluating capacitive coupling before precise detail routing geometry is available. I describe an extension to my global routing system that is the first approach that directly considers the effects of coupled noise during global routing. It uses a global crosstalk measure that combines routing estimates with temporally dependent net noisiness and sensitivity information to estimate the total degree of coupling conflict in a global routing solution. I describe a technique for maintaining this global conflict measure incrementally during global routing. Experimental results demonstrate global routing solutions with an average 19.8% reduction in this conflict measure at the expense of a 3% increase in total wire length. This post-global-route decrease translates into an 18.5% average reduction in crosstalk conflict after local routing.