Prabhakar Raghavan and Clark D. Thompson

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-84-202
September 1984

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-202.pdf

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.

BibTeX citation:

@techreport{Raghavan:CSD-84-202,
    Author = {Raghavan, Prabhakar and Thompson, Clark D.},
    Title = {Randomized Routing in Gate-Arrays},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1984},
    Month = {Sep},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5832.html},
    Number = {UCB/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.}
}

EndNote citation:

%0 Report
%A Raghavan, Prabhakar
%A Thompson, Clark D.
%T Randomized Routing in Gate-Arrays
%I EECS Department, University of California, Berkeley
%D 1984
%@ UCB/CSD-84-202
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5832.html
%F Raghavan:CSD-84-202