Randomized Routing in Gate-Arrays
Thompson, Clark D.
Technical Report Identifier: CSD-84-202
Abstract: A stochastic model for analyzing the performance of randomized algorithms for routing gate-arrays is presented; our model is based on an empirical observation known as Rent's Rule. Using the model, we analyze the space requirement of a wiring technique that only uses one-bend routes. We show how the technique can be extended to a case where several wiring layers are available, with near-optimal saving in area. As a by-product, we obtain a random procedure for converting a two-layer gate-array routing to a many-layer routing while reducing area efficiently. Within our model, we also show that the one-bend strategy is sub-optimal in terms of space requirement. However, we also show that the optimal strategy is not significantly superior to the random one-bend strategy.