Probabilistic Congestion Prediction with Partial Blockages

Zhuo Li1,  Chuck Alpert1,  Steve Quay2,  Sachin Sapatnekar3,  Weiping Shi4
1IBM Austin Research Lab, 2IBM EDA, 3University of Minnesota, 4Texas A&M University


Abstract

Fast and accurate routing congestion estimation is essential for optimizations such as floorplanning, placement, buffering, and physical synthesis that need to avoid routing congestion. Using a probabilistic technique instead of a global router has the advantage of speed and easy updating. Previously proposed probabilistic models [1][2] do not account for wiring that may already be fixed in the design, e.g., due to macro blocks or power rails. These ``partial wiring blockages'' certainly influence the global router, so they should also influence a probabilistic routing prediction algorithm. This work proposes a probabilistic congestion prediction metric to model partial wriring blockages. We also show an new fast algorithm to generate the congestion map and demonstrate the effectiveness of our methods on real routing problems.