TL;DR
This paper introduces the "Y tree" architecture, a novel hierarchical interconnect for hexagonal processor arrays. It offers a competitive alternative to existing "X tree" architectures, balancing communication performance with the cost of on-chip wiring, particularly relevant in deep sub-micron technologies.
What Problem Does This Paper Address?
As semiconductor technology advances, integrating more processors onto a single chip becomes feasible. This leads to a critical challenge: efficiently connecting these processors. The cost of on-chip wires increases significantly with their length, while high-performance systems demand short communication paths. Traditional interconnects can become bottlenecks. Hierarchical architectures offer a solution by organizing connections in a tree-like structure, allowing for scalability and a better trade-off between wire cost and communication speed. This paper focuses on designing such an architecture specifically for hexagonal processor arrays, which offer advantages over traditional rectangular layouts.
Methods
The paper proposes a "Y tree" architecture, a non-blocking hierarchical interconnect designed for hexagonal processor arrays. This architecture is built recursively, clustering three hexagonal cells at each level to form a "Y" shape. The authors detail an algorithm for constructing these Y trees, considering different "configurations" of the Y orientations at each level. They also introduce a method for representing polygons formed by merged hexagons using "hex-sequences" and discuss algorithms for merging these polygons, both for unoriented and oriented cases. The performance of the Y tree is compared to the existing "X tree" architecture using an objective function that balances wire cost and power consumption.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Hexagonal Arrays Enable Hierarchical Expansion: The paper demonstrates that hexagonal processor arrays, much like rectangular ones, possess inherent properties that allow for recursive, hierarchical expansion, making them suitable for complex interconnect designs.
- The "Y Tree" as a Viable Alternative: The proposed Y tree architecture offers a competitive performance-to-cost ratio compared to the established X tree architecture, especially for hexagonal layouts. This suggests that the choice of underlying processor geometry can influence the optimal interconnect topology.
- Recursive Construction and Configurations: The Y tree's recursive nature and the concept of "configurations" (different orientations of the Y shapes at each level) provide a flexible framework for building scalable interconnects.
- Hex-Sequences for Polygon Representation: The introduction of hex-sequences offers a novel and efficient way to represent and manipulate the shapes and boundaries of merged hexagonal regions, which is crucial for understanding and constructing complex interconnect structures.
Key Results
The paper presents theoretical results and comparisons:
- Comparable Performance: The Y architecture is shown to have comparable performance to the X architecture when evaluated using the proposed objective function that balances wire length and signal path length. For instance, normalized metrics for wire length (Mxnorm(n) ≈ 0.43 vs. Mynorm(n) ≈ 0.59) and signal path length (Dxnorm(n) ≈ 0.71 vs. Dynorm(n) ≈ 0.85) are presented, indicating a trade-off but overall competitiveness.
- Recursive Properties: Theorems 2-4 establish that the proposed algorithm can recursively generate Y tree architectures without cell overlapping, covering all cells, and that the number of cells covered at level n is 3<sup>n</sup>.
- Polygon Merging Algorithms: Algorithms are presented for merging polygons represented by hex-sequences, both for unoriented and oriented cases, which are fundamental for constructing the Y tree structure.
Limitations and Future Work
- Limited Quantitative Comparison: While the paper compares the Y and X architectures using an objective function, it doesn't present extensive simulation results or benchmarks on actual hardware performance. The comparisons are largely theoretical.
- Focus on Specific Hexagonal Layout: The Y tree architecture is specifically designed for hexagonal processor arrays. Its applicability to other array topologies might require further investigation.
- Future Work: The paper suggests that the polygon merging algorithm, particularly for oriented polygons, is a key component for building complex Y trees. Further exploration of this algorithm and its implications for practical implementations would be a natural next step. The authors also mention the potential for improved throughput with hexagonal chips, hinting at further research avenues in optimizing for specific geometries.
Summary updated