Prabhakar Raghavan and Clark D. Thompson

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-84-202

, 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},
    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