Probabilistic congestion prediction

Congestion is a fundamental problem in VLSI design flows. Typically, it is handled by feeding back density information to the placers and routers. Fast and accurate congestion estimation is key in order to obtain a design flow with less iterations and higher predictability.Fast congestion prediction is based on an accurate approximation of the actual routing engine. In this paper we show experimentally that the number of two-pin nets with more than two bends in the actual router is negligible. It is also established that the ratio between the number of L-shapes and Z-shapes is more or less a constant.A fast and accurate algorithm for congestion prediction is developed. The above observations are translated into probabilities, that are used to "smear" out a net over its possible realizations. Extensive experimental evidence is provided using industrial designs.