Congestion estimation for hexagonal routing

Abstract

Interconnect planning is an important issue in VLSI designs. Routing congestion is an important problem during placement. This paper presents a novel approach to estimating the routing congestion on the hexagonal model with bounded-length detours. It is the first probabilistic estimation work on hexagonal topologies. A combinatorial estimation algorithm is presented. The experimental results demonstrate the effectiveness of the method.

Keywords:

• VLSI Routing
• Probabilistic methods
• Estimation

Acknowledgements

We are grateful to Yu Xiao, for his implementation experiments. This research was funded in part by the Chinese National 973 Plan (Project No. 2004CB719400), PR China.