Probabilistic Estimation Of Routing Congestion

Accurate estimation of wirelength and congestion has become an important issue forautomation of the VLSI physical design. Excessive congestion will result in a localshortage of routing resources. This will lead to a large expansion in area or an unroutabledesign. In this case, the design process must be restarted from an early stage such asfloorplanning and placement. Therefore, congestion analysis and removal techniques arerequired in the earlier phases of the physical design flow in order to get an early analysisand prediction of the connection message, thus reducing the time expense. Furthermore,the mainstream of global routers uses the rip-up and reroute technical, which dependshighly on the estimation of routing congestion to bypass overloaded areas. Manyestimation algorithms were proposed in the literature, which differ mainly in the way theymodel routing estimation. There are two different routing estimation approaches inplacement at present, namely stochastic based and empirical methods. Stochastic basedmodels consider all possible paths by which a net can be routed, and every path is assigneda probability based on various assumptions, while empirical estimators use layoutparameters to estimate wirelength and routability. But they basically fail to produceaccurate results since they ignore congestion-related detouring and effects of the number ofvias and bends.The two main contributions of this dissertation are: Firstly, we propose a newtheoretical estimation model. The model considers only two-terminal nets with at mostthree bends which is matching with the actual routers. According to certain ratios amongthe number of one, two or three bends in a chip, it computes the probability of usage ofeach unit line segment, thus resulting in a fast and accurate algorithm for congestionestimation. Unfortunately, there is no experimental result to support its validity andefficiency at the moment. Secondly, we propose a model which is quite similar to the onein [1]. As in [1], it also considers routes with at most two bends. The difference is that ourmodel is much simpler and so it is faster. By comparing its estimations with the bestsolutions in the ISPD’07global routing contest, we find that it gets fairly good estimationaccuracy.