Evaluation, prediction and reduction of routing congestion

Routing congestion is a critical issue in deep submicron design technology and it becomes one of the most challenging problems in today's design flow. In this paper, various congestion-related metrics were defined and evaluated during placement stage of physical design flow. Our experiments show that the overflow metric results are more accurate than others. In addition, the bend distributions after detailed routing for IBM-PLACE benchmarks were extracted and used to guide a pure probabilistic method. Furthermore, router's behavior for congestion minimization was modeled and used to propose a true congestion prediction algorithm. Experimental results show that the proposed algorithm estimates the congestion more accurately than a commonly used method by about 21% on average. Additionally, a new congestion reduction algorithm is presented based on contour plotting. Our experiments show that our algorithm reduces the peak congestion by about 25% on average. In addition, comparing our results with a recent approach shows that our technique reduces congestion more by about 10% on average. In order to evaluate the results of white space allocations on the quality of our reduction technique, several other experiments were attempted. Various amounts of white space were added to several IBM-PLACE benchmarks and the contour plotting-based reduction technique was used to reduce the peak and average congestion. The experiments show that our technique works better on the benchmarks with more white space as it has more capability to distribute routing congestion evenly.