A hierarchical three-way interconnect architecture for hexagonal processors

ABSTRACT

The problem of interconnect architecture arises when an array of processors needs to be integrated on one chip. With the deep sub-micron technology, devices become cheap while wires are expensive. On the other hand, high performance systems require the shortest communication routes among the processors. Non-blocking hierarchical interconnect architectures have been found to be a feasible solution. First, they can be expanded recursively and so can be applied in large-scale arrays. Second, if well designed, they have the best trade-off between the cost of wire resources and the communication performance. In this paper, a new type of non-blocking hierarchical three-way interconnect architecture, Y tree architecture, is put forward. We find that the arrays of hexagonal cells also have the property of hierarchical expansion, and we put an algorithm to build up a Y tree. We compare the Y architecture with an X hierarchical non-blocking architecture.

REFERENCES

• 1: E.Y. Cheng, F. Zhou, B. Yao, CK Cheng, R. Graham, Balancing the Interconnect Topology for Arrays of Processors between Cost and Power, International Conference on Computer Design, Freiburg, Germany, Sept., 2002.
• 2: Hongyu Chen , Bo Yao , Feng Zhou , Chung-Kuan Cheng, The Y-architecture: yet another on-chip interconnect solution, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119957]
• 3: Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
• 4: Charles E. Leiserson, VLSI theory and parallel supercomputing, Proceedings of the decennial Caltech conference on VLSI on Advanced research in VLSI, p.5-16, June 1989, Cambridge, Massachusetts, United States
• 5: V.E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic, Academic Press, 1965.
• 6: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 7: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 8: C. Clos, A Study of Non-Blocking Switching Networks, Bell System Tech. vol. 32, pp. 406--424, 1953.
• 9: M. Igarashi, T. Mitsuhash, et al., A diagonal-interconnect architecture and its applications to RISC core design, ISSCC Digest of Technical Papers, pp.210--211, San Francisco, 2002.
• 10: Robert C. Carden, IV , Chung-Kuan Cheng, A global router using an efficient approximate multicommodity multiterminal flow algorithm, Proceedings of the 28th conference on ACM/IEEE design automation, p.316-321, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127687]
• 11: Ken Mai , Tim Paaske , Nuwan Jayasena , Ron Ho , William J. Dally , Mark Horowitz, Smart Memories: a modular reconfigurable architecture, Proceedings of the 27th annual international symposium on Computer architecture, p.161-171, June 2000, Vancouver, British Columbia, Canada
• 12: C. A. Moritz , D. Yeung , A. Agarwal, Exploring Optimal Cost-Performance Designs for Raw Microprocessors, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.12, April 15-17, 1998
• 13: William J. Dally , Brian Towles, Route packets, net wires: on-chip inteconnectoin networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 14: Kang G. Shin, HARTS: A Distributed Real-Time Architecture, Computer, v.24 n.5, p.25-35, May 1991 [doi>10.1109/2.76284]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Algorithms, Design

Keywords:
Y architecture, Y tree, interconnect architecture