Optimizing Yield in Global Routing

We present the first efficient approach to global routing that takes spacing-dependent costs into account and provably finds a near-optimum solution including these costs. We show that this algorithm can be used to optimize manufacturing yield. The core routine is a parallelized fully polynomial approximation scheme, scaling very well with the number of processors. We present results showing that our algorithm reduces the expected number of defects in wiring by more than 10 percent on state-of-the-art industrial chips