Perimeter-Degree: A Priori Metric for Directly Measuring and Homogenizing Interconnection Complexity in Multilevel Placement

In this paper, we describe an accurate metric (perimeter-degree) for measuring interconnection complexity and effective use of it for controlling congestion in a multilevel framework. Perimeter-degree is useful for uniformly spreading interconnection density. In modern designs interconnects consume significant area and power. By making interconnect spread homogeneous, it is possible to improve routability as well as power dissipation distribution. Most of the existing congestion minimization heuristics are posteriori. In this work, we extend and complement our previous work on priori congestion minimization techniques. In [16], we identified and used perimeter-degree for constructing congestion friendly clusters. This paper extends that work by unveiling perimeter-degree based whitespace allocation techniques. We show why "number of external nets" is not a desirable candidate for identifying potential regions of high interconnect density and provide perimeter-degree as a possible alternative. We also provide empirical evidence for the effectiveness of perimeter-degree in effectively identifying congested regions even before they are formed. By implicitly allocating resources to these potential high interconnect density regions, 19% reduction in congestion was achieved. Traditionally, bin capacity bounds are expressed in units of area. In a true interconnect centric approach we ignore area and instead use interconnect complexity as weights for clusters and capacity bounds for bins. This technique creates a placement with homogeneous interconnect density, but slightly unbalanced utilization. On average, this novel interconnect complexity driven scheme reduces congestion by 26%.