TL;DR
This paper introduces "perimeter-degree," a novel metric to proactively measure and balance interconnection complexity across a chip. By using this metric to guide placement decisions, the authors demonstrate significant reductions in routing congestion without sacrificing wirelength, offering a more efficient approach to VLSI design.
What Problem Does This Paper Address?
Modern integrated circuits are becoming increasingly complex, with interconnects consuming a significant portion of chip area and power. A major challenge in designing these chips is routing congestion, which occurs when the demand for routing resources in a particular area exceeds the available supply. Traditional placement algorithms often focus on minimizing wirelength (e.g., using the half-perimeter wirelength metric), but this can lead to localized "hotspots" of high interconnection density, making routing difficult or impossible. Existing methods to address congestion often do so after the initial placement (posteriori), which can be inefficient and may degrade wirelength. This paper aims to tackle congestion before it becomes a problem by developing a proactive metric and integrating it into a multilevel placement framework.
Methods
The core contribution of this paper is the introduction of the perimeter-degree metric. This metric quantifies the interconnection complexity of a region by normalizing the "degree" (number of external nets connected to a region) by the region's perimeter. The authors argue that this is a more accurate measure of local routing demand than simply looking at the number of external nets or pin density, especially when regions have different areas.
They integrate this perimeter-degree metric into a multilevel placement framework in several ways:
- Perimeter-Degree Based Cell Inflation: Before clustering, cells with high perimeter-degree are "inflated" (given more whitespace) to preemptively dilute dense interconnect regions.
- Perimeter-Degree Based Cluster Inflation: After clusters are formed, those with high perimeter-degree are also inflated to address non-homogeneity introduced during clustering.
- Perimeter-Degree as Capacity Bound: Instead of using area alone, the paper proposes using the sum of perimeter-degrees of clusters as a capacity bound for bins. This aims to create a more balanced distribution of interconnection complexity across bins.
These methods are applied within a standard multilevel placement flow, which involves coarsening the design, placing it on a coarse grid, and then refining the placement through successive uncoarsening and refinement steps.
Datasets
The authors evaluated their methods on 20 industrial benchmark designs. The paper provides a table (Table 2) detailing the number of cells, nets, macro cells, and utilization for these benchmarks. No new benchmarks were introduced.
Key Insights and Ideas
- Perimeter-Degree is a Superior Metric: The paper convincingly argues that perimeter-degree is a more effective metric for identifying potential congestion hotspots than simple metrics like "number of external nets" or "pin density." This is because it accounts for both the demand (nets) and the available "edge" for routing (perimeter).
- Homogenizing Interconnection Complexity is Key: The results strongly suggest that reducing the variability in interconnection density (making it more homogeneous) is crucial for reducing congestion, even more so than just minimizing the average density.
- Proactive Congestion Management Works: By integrating perimeter-degree into the placement process before routing, the authors achieve significant congestion reduction with minimal or even negligible impact on wirelength. This contrasts with traditional posteriorti approaches.
- Interconnect-Centric Design is Essential: The paper highlights the growing importance of interconnect-centric approaches in modern VLSI design, where interconnects are no longer a secondary concern but a primary driver of design quality.
Key Results
The paper reports significant improvements in congestion reduction across various heuristics:
- Cell Inflation (3.1.1): Reduced mild congested edges by an average of 8% and severe congested edges by 14%, with a negligible wirelength increase.
- Cluster Inflation (3.1.2): On average, mild congested edges reduced by 3% and severe congested edges by 14%. While wirelength slightly worsened, this method showed promise.
- Combined Method (3.1.1 & 3.1.2): Achieved an average reduction of 6% in mild congested edges and 19% in severe congested edges, with only a slight increase in wirelength.
- Perimeter-Degree as Capacity Bound (3.2): This method showed the most impressive results, reducing mild congested edges by 11% and severe congested edges by 26%, with a reduction in routed wirelength by 0.7% and a negligible increase in half-perimeter wirelength.
Overall, the perimeter-degree based approaches demonstrated substantial congestion reduction without significant wirelength penalty, with some methods even improving wirelength.
Limitations and Future Work
- Whitespace Allocation Optimization: The authors note that the implicit whitespace allocation schemes require further investigation to determine the optimal amount of allocation. The current experiments used default capacity bound configurations.
- Handling Routing Supply Non-homogeneity: While the paper focuses on interconnection complexity, it acknowledges that routing supply also varies (e.g., due to macro cells or physical location). Future work could involve estimating perimeter-degree-based bin bounds by accurately estimating routing supply to further reduce congestion.
- Legalization Effort: The perimeter-degree as capacity bound method surprisingly did not encounter significant legalization problems, which the authors attribute to the relatively low utilization factors of the benchmarks. This might be a limitation for designs with higher utilization.
Summary updated