Estimating routing congestion using probabilistic analysis

Design routability is a major concern in the application-specific design flow, particularly with today's increasingly aggressive process technology nodes. Increased die areas, cell densities, routing layers, and net count all contribute to complex interconnect requirements, which can significantly deteriorate performance and sometimes lead to unroutable solutions. Congestion analysis and optimization must be performed early in the design cycle to improve routability. This paper presents a congestion estimation algorithm for a placed net list. We propose a net-based stochastic model for computing expected horizontal and vertical track usage, which considers routing blockages. The main advantages of this algorithm are its accuracy and fast runtime. We show that the congestion estimated by this algorithm correlates well with postroute congestion and present experimental results of subsequent congestion minimization based on this algorithm.