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

Navaratnasothie Selvakkumaran, Phiroze N. Parakh, George Karypis

Research output: Contribution to conferencePaperpeer-review

11 Scopus citations


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%.

Original languageEnglish (US)
Number of pages7
StatePublished - 2003
Event2003 International Workshop on System Level Interconnect Prediction - Monterey, CA, United States
Duration: Apr 5 2003Apr 6 2003


Other2003 International Workshop on System Level Interconnect Prediction
Country/TerritoryUnited States
CityMonterey, CA


  • Congestion
  • Interconnection complexity
  • Multilevel global placement
  • Nonhomogeneity
  • Perimeter-degree
  • Routability


Dive into the research topics of 'Perimeter-Degree: A Priori Metric for Directly Measuring and Homogenizing Interconnection Complexity in Multilevel Placement'. Together they form a unique fingerprint.

Cite this