Congestion estimation for 3-D circuit architectures

Three-dimensional (3-D) routing is an important step in deep submicrometer very large-scale integrated design. Given a 3-D grid graph and a set of two-terminal nets to be routed, we propose a probabilistic model to calculate the routing density (congestion) on each edge of the grid graph. The routing density provides a direct congestion estimation. Our experimental results demonstrate the effectiveness of the method on routing benchmarks. Index Terms--Estimation, probabilistic methods, routing.