Abstract In this paper, we propose a new on-chip interconnect scheme called Y-architecture, which can utilize the on-chip routing resources more efficiently than traditional Manhattan interconnect architecture by allowing wires routed in three directions (OD, 60D, and l2Oo). To evaluate the efficiency of different interconnect architectures, we assume mesh structures with uniform communication demand and develop a multi-commodity flow (MCF) approach to model the on-chip communication traffic. We also extend the combinatorial MCF algorithm in [5] to compute the optimal routing resource allocations for different interconnect architectures. The experiments show that: ( I ) Compared with Manhattan architecture, the Y-architecture demonstrates a throughput improvement of 30.7% for square chip. The throughput of the Y-architecture is only 2.5% smaller than that of X-architecture. (2) A chip with the shape of a convex polygon produces better throughput than a rectangular chip: For Y-architecture, a hexagonal chip provides 41% more throughput than a squared chip using the Manhattan architecture. For Manhattan architecture, a diamond chip achieves a throughput improvement of 19.5%) over the squared chip using the same interconnect architecture. (3) Compared with Manhattan architecture, the Y-architecture reduces the wire length of a randomly distributed two pin net by 13.4% and the average wire length of Y-architecture is only 4.3%) more than that of the X-architecture. With rapid technology scaling, the interconnect becomes one most precious resource on a chip. Traditional Manhattan interconnect architecture organizes wires on two orthogonal routing directions, 0" and 90' directions, for the simplicity of routing embedding and design rule checking. However, its artificial restriction on routing directions adds significant wire length over the Euclidean optimum and thus decreases the communication capability of the on-chip interconnects. In the past decade, many researchers have explored the possibility of using nonrectilinear wires to improve the efficiency of on-chip interconnects. [4] Most of these work discussed about how to introduce 45-degree short jogs to improve the routability of the chip in the detailed routing stage. Majority of the wires on the chip are still routed on either 0-degree or 90-degree direction. Recently, Mutrunoi et. al. [7] proposed a new on-chip interconnect architecture named the X-architecture, which is targeting at the designs with 5 or more routing layers. 111 the X-architecture, the wires are organized in 0-degree, 45-degIee. 90-degree and 135-degree directions. The experimental 840 results show that it achieves a chip performance improvement of 10% and power reduction of 20% than Manhattan architecture for a high performance design. In the foreseeable future, more than 12 routing layers will be available in the high performance circuit designs. [l] It is both possible and desirable for us to explore the different ways to organize the on-chip routing resources. However, the prohibitive cost of actually designing and manufacturing a chip with new interconnect archtectures makes it very hard to implement and test new interconnect architectures one by one. It is necessary to develop a quantitative framework to evaluate the efficiency of different interconnect architectures. From early 1990s, researchers [2][6] studied the wire length reduction by allowing more routing directions. Most of these works concentrated on the Steiner cost of a single signal net. The competition on the routing resources between different nets is ignored in these works. We adopt Multi-commodity flow (MCF) approach to model the on-chip communication traffk. We assumc a mesh structure with uniform communication demand, and use the MCF throughput of the mesh to measure the communication capability of different interconnect architectures. This method is independent with particular test cases and can reflect the exact communication bottleneck on the chip. Recent advance in MCF algorithm [5] allows LLS to solve MCF problem much more efficiently. Our implementation can compute the throughput of meshes with up to 289 nodes withm 12 hours computing. We also extend thls algorithm to compute the optimal routing resource allocation for different interconnect architectures. In this paper, we propose the use of Y-architecture, w h c h has three symmetrical routing directions (0-degree, 60-degree, and 120-degree). We compare this interconnect architecture with the Manhattan architecture and the X-architecture. Based on our experiments on throughputs and analytical analysis on wire length, we have following reason to motivate the use of the Y-architecture : (1) Using Y-archtecture can gain a throughput improvement of 33.3% over the traditional Manhattan architecture on a squared mesh. Comparing with the X-architecture, which has one more routing direction, the Y-architecture produces almost the same (2.6% less) throughput on a squared mesh. ( 2 ) The Y-architecture achieves an average of 13.4'% wire length reduction over Manhattan architecture for a two-pins connection. The more complex X-architecture can only 0-7803-7659-5/03/$17.00 02003 IEEE.
As another routing model, Y-architecture based on 0, 60 and 120 degree directions is proposed REF .
The Y-architecture: yet another on-chip interconnect solution