Implicit Heuristics to Mitigate Interconnect Congestion in a Multilevel Placement Framework

Abstract

The congestion minimization techniques have become more important due to the shrinking geometries and ``taller'' interconnects, causing numerous design convergence problems. Also, multilevel placement algorithms are becoming more prevalant due to their ability to natively incorporate mixed-mode placement, in addition to their ability to scale to very large design sizes. In this context, we have developed a number of implicit heuristics for minimizing congestion in the process of enhancing an existing industrial multilevel placment tool (Dolphin). In contrast to the explicit congestion heuristics that explicity measure congestion either by stochastic estimators or by approximate global routing, our techniques primarily rely on pre-emptively identifying congestion-prone clusters and making amends to them. Essentially, we intervene during the clustering phase of the multilevel placement to identify such congestion-prone clusters and try to increase the supply of routing resources to those clusters. Increasing the supply of routing resources can be done by whitespace injection. Cell/cluster inflation is however, not a new technique, but what is new in our techniques is that we inflate the clusters {em before} any placement information is obtained. In addition to the effective schemes of cluster inflation that reduce congestion substantially (upto 25% on average), we have also modified the clustering formulation to generate clusters that are less prone to congestion. These new clustering schemes do not use any additional area and as a result a more attractive option for designs with very high utilization. The non-use of addtional whitespace does not mean they are ineffective, even though these formulations are dwarfed in quality by whitespace techniques, they reduce congestion at a significant rate of 20% on average. Furthermore, a new area distribution heuristic is also developed that reduce congestion by 32% on average, and by far this is the best among the techniques develped.

Part of the success of our schemes is derived from the novel metric we used to identify clusters with higher congestion risk. We first describe well-known implicit congestion metrics such as pin-density and bin-degree, and then examine the pros and cons of deploying them for our purpose. The new metric called ``perimeter-degree'' is developed to over come the disadvantages of pin-density and bin-degree in our multilevel placement setup.

Due to the simplicity of the heuristics presented, the run time penalty is extremely small. Not only that, but these techniques can also be applied in a complementary fashion to the existing explicit congestion mitigating methods, which further improves the desirability of these techniques.