Modeling and minimization of routing congestion

Typical placement objectives involve reducing net-cut cost or minimizing wirelength. Congestion minimization is least understood, however, it models routability most accurately. In this paper, we study the congestion minimization problem during placement. First we point out that the bounding box router used previously is not an accurate measurement of the congestion in the placement. We use a realistic global router to evaluate congestion in the placement stage. This ensures that the final placement is truely congestion minimized. We also propose two new post processing algorithms, the flow-based cell-centric algorithm and the net-centric algorithm. While the flow-based cell-centric algorithm can move multiple cells at the same time to minimize the congestion, it suffers large consumption of memory. Experimental results show that the net-centric algorithm can effectively identify the congested spots in the placement and reduce the congestion. It can produce on an average 7.7% less congestion than the bounding box router method. Finally, we use a final global router to verify that the placement obtained from our algorithm has 39% less congestion than a wirelength-optimized placement obtained by TimberWolf (commercial version 1.3.1).