Physical synthesis of bus matrix for high bandwidth low power on-chip communications

Renshen Wang, Evangeline F. Y. Young, Ronald L. Graham, Chung-Kuan ChengISPD 2010 · DOI

TL;DR

This paper tackles the challenge of designing efficient on-chip communication architectures for modern System-on-Chips (SoCs). They propose a novel physical synthesis flow for bus matrices that optimizes for bandwidth, power, and wire usage by leveraging floorplan information and employing Steiner graph-based optimization and segment merging techniques. This approach aims to create compact and power-efficient bus matrices, crucial for overcoming the thermal wall in VLSI design.

What Problem Does This Paper Address?

As VLSI technology scales, the "thermal wall" and power consumption of interconnects are becoming major bottlenecks, limiting circuit performance. While on-chip communication is essential for parallelism in SoCs, traditional bus architectures often struggle with bandwidth, and Network-on-Chips (NoCs), while offering bandwidth, suffer from significant latency. Bus matrices offer a compromise, but existing designs can be inefficient in terms of power and wire usage. This paper addresses the need for a bus matrix synthesis methodology that can achieve high bandwidth and low power consumption while minimizing wire length, by considering the physical layout (floorplan) of components on the chip.

Methods

The authors propose a two-stage optimization approach:

  1. Ideal Bus Matrix Formulation: They first define an "ideal" bus matrix that guarantees maximum parallelism and shortest Manhattan distance for each data transaction. This formulation, however, is computationally expensive.
  2. Practical Bus Matrix Formulation: To make the problem tractable, they introduce a practical formulation where each master-slave connection is assigned a fixed shortest path. The core of their synthesis flow then focuses on optimizing this practical formulation.

Key techniques include:

  • Steiner Graph Generation: They utilize shortest-path Steiner graphs, known for their efficiency in power reduction, as the underlying topology for the bus matrix.
  • Edge Weighting (Maximum Matching): To handle multiple concurrent transactions on shared edges, they employ a maximum bipartite matching algorithm to determine the required number of parallel bus lines (edge weights) for each segment of the Steiner graph. This ensures high bandwidth capacity.
  • Parallel Segment Merging: To further reduce wire length and improve compactness, they introduce a heuristic algorithm that identifies and merges parallel segments in the Steiner graph. This process iteratively merges segments that offer the best trade-off between wire length reduction and potential path length increase.
  • Overall Optimization Flow: The paper outlines an overall flow that generates a series of bus matrix graphs by iteratively applying segment merging and evaluating the resulting configurations to find optimal trade-offs between power, wire length, and bandwidth.

Datasets

The paper evaluates their approach using test cases from a previous work ([14]). These test cases involve various configurations of masters and slaves, with component locations distributed on a 1000x1000 square grid for random cases. Specific cases like T1 (3,16) and T8 (16,10) are highlighted for detailed analysis. No new benchmarks were introduced.

Key Insights and Ideas

  • Physical Synthesis is Crucial: The paper strongly emphasizes that optimizing on-chip communication requires considering the physical layout (floorplan) of components. Simply optimizing topology without physical awareness leads to suboptimal results.
  • Steiner Graphs for Power Efficiency: Leveraging shortest-path Steiner graphs, originally proposed for gated bus power saving, proves effective for bus matrices by minimizing wire length and enabling efficient routing.
  • Maximum Matching for Bandwidth: Using maximum bipartite matching to assign edge weights is a clever way to ensure the bus matrix can handle concurrent transactions up to its theoretical maximum bandwidth without over-provisioning wires unnecessarily.
  • Segment Merging for Wire Reduction: The parallel segment merging technique is a key innovation for reducing wire length in bus matrices, especially in cases with long, narrow routing structures. It offers a way to trade a small increase in path length for significant wire savings.
  • Flexible Trade-offs: The proposed framework allows designers to explore a spectrum of trade-offs between power, wire length, and bandwidth, enabling them to tailor the bus matrix to specific design constraints and priorities.

Key Results

The paper presents results for two main optimization goals:

  • Minimal Power Bus Matrix: Achieved a total wire length that was approximately one-third to one-fourth of the total path lengths, demonstrating significant efficiency gains from physical synthesis.
  • Minimal Wire Bus Matrix: Through segment merging, they achieved further wire length reduction, with reductions ranging from about 1/6 to 1/4 compared to the min-power bus matrix on random cases. The average path length increase was generally small (under 5%).

Figure 7 and 8 illustrate the trade-offs between total wire length, total edge length, and average path length, showing that optimal points can vary significantly based on the system floorplan. Figure 9 demonstrates the wire length vs. bandwidth trade-off for a specific case.

Limitations and Future Work

  • Computational Complexity: While the practical formulation is more tractable, finding the absolute minimal Steiner graph is NP-hard. The paper uses heuristic algorithms, which provide good but not necessarily optimal solutions.
  • Floorplan Dependency: The effectiveness of the segment merging technique is highly dependent on the specific floorplan and the resulting Steiner graph structure.
  • Future Work: The authors suggest exploring more possibilities in formulations and algorithms for bus matrix architectures. They also mention that while their current work focuses on data buses, similar principles could be applied to address bus architectures for other types of traffic (e.g., address buses). Further investigation into the trade-offs between bandwidth capacity, power, and wire length is also suggested.

Summary updated

BibTeX
@inproceedings{wang2010physical,
  author = {Renshen Wang and Evangeline F. Y. Young and Ronald L. Graham and Chung-Kuan Cheng},
  title = {{Physical synthesis of bus matrix for high bandwidth low power on-chip communications}},
  booktitle = {ISPD},
  year = {2010},
  doi = {10.1145/1735023.1735049},
}
Figure