The Y-architecture: yet another on-chip interconnect solution

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 (0°, 60°, and 120°). 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: (1) 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.

REFERENCES

• 1: International Technology Roadmpa for Semiconductors, 2001 Edition-Interconnect
• 2: S. Burman, H. Chen, and N. Sherwani, "Improved global routing using λ-geometry," in Proc. of 29th Annual Allerton Conference on Communication, Computing, and Controls, Oct. 1991
• 3: Physical Planning Of On-Chip Interconnect Architectures, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.30, September 16-18, 2002
• 4: C. Chiang and M. Sarrafzadeh, "Wirability of Knock-knee Layouts with 45-degree wires," IEEE Trans. on Circuits & Systems, vol. 38, No.6, June 1991, pp. 613--624
• 5: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 6: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 7: I. Mutsunori, T. Mitsuhashi, A. Le, S. Kazi, Y. Lin, A. Fujimura, and S. Teig, "A Diagonal Interconnect Architecture and Its Application to RISC Core Design," Proc. ISSCC, pp. 684--689. San Jose, CA, Feb. 2002.
• 8: M. Sarrafzadeh, C. K. Wong, "Hierarchical Steiner tree construction in uniform orientations,". IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 11, (no.9), Sept. 1992. p. 1095--103
• 9: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 10: Steven L. Teig, The X architecture: not your father's diagonal wiring, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505355]