On the behavior of congestion minimization during placement

Maogang Wang, Majid Sarrafzadeh

1999 · 84 citations · 7 references

DOIFull text

Open access

Concepts

Abstract

Typical placement objectives involve reducing net-cut cost or minimizing wirelength. Congestion minimization is least understood, however, it models routability accurately. In thii paper, we study the congestion minimization problem during placement. We introduce the notion of consistent routing model and promote its adoption by placement systems. First, we show that in thii model the wirelength objective is indeed a good measure of congestion by establishing that a placement with minimum wirelength has minimum total congestion. We show that miniibmg wirelength may (and in general, will) create locally congested regions. We demonstrate that most other congestion related objectives are ill behaved and they should only be used in a post processing step. We then propose several novel congestion minimization objectives. One in psrticulsr, called overflow minimization with look-ahead, performs very well and can be computed very efficiently in an incremental manner. At the end, we propose a post processing phase that further improves the congestion. By combining the overflow minimization with look-ahead and the post processing phase, we improve the congestion by more than 40% on the average.

References

7