Performance of Interconnection Rip-Up and Reroute Strategies

Abstract

Rip-up and reroute strategies can be applied following use of conventional wiring algorithms to calculate paths for residual connections failed by preceding techniques. The removal of blocking wire to allow new path runs inevitably introduces new (reroute) wiring requirements. In this paper we address the performance implications of various rates of success experienced while attempting reroutes. Using statistical approaches, we develop formulas which allow calculation of expected completion rate and computational effort for several types of rip-up and reroute algorithms. It is found that a basic router having modest completion rate behavior can be used to achieve surprisingly high completion rates, with rip-up strategies.