Level-wise scheduling algorithm for fat tree interconnection networks

ABSTRACT

This paper presents an efficient hardware architecture for scheduling connections on a fat-tree interconnection network for parallel computing systems. Our technique utilizes global routing information to select upward routing paths so that most conflicts can be resolved. Thus, more connections can be successfully scheduled compared with a local scheduler. As a result of applying our technique to two-level, three-level and four-level fat-tree interconnection networks of various sizes in the range of 64 to 4096 nodes, we observe that the improvement of schedulability ratio averages 30% compared with greedy or random local scheduling. Our technique is also scalable and shows increased benefits for large system sizes.

REFERENCES

• 1: Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
• 2: Charles E. Leiserson , Zahi S. Abuhamdeh , David C. Douglas , Carl R. Feynman , Mahesh N. Ganmukhi , Jeffrey V. Hill , Daniel Hillis , Bradley C. Kuszmaul , Margaret A. St. Pierre , David S. Wells , Monica C. Wong , Shaw-Wen Yang , Robert Zak, The network architecture of the Connection Machine CM-5 (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.272-285, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141883]
• 3: Z. Bozkus, S. Ranka, and G. Fox, "Benchmarking the CM-5 multicomputer," in Fourth Symposium on the Frontiers of Massively Parallel Computation, pp. 100--107, 1992.
• 4: Klaus E. Schauser , Chris J. Scheiman, Experience with active messages on the Meiko CS-2, Proceedings of the 9th International Symposium on Parallel Processing, p.140-149, April 25-28, 1995
• 5: "AlphaServer SC:terascale single-system-image supercomputing," tech. rep., COMPAQ Inspiration Technology, 2002. http://h18002.www1.hp.com/alphaserver/download/.
• 6: J. Beecroft, D. Addison, F. Petrini, and M. McLaren, "Qs-NetII: an interconnect for supercomputing applications," IEEE Micro, 2003.
• 7: Lionel M. Ni , Yadong Gui , Sherry Moore, Performance Evaluation of Switch-Based Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.462-474, May 1997 [doi>10.1109/71.598274]
• 8: Yucel Aydogan , Craig B. Stunkel , Cevdet Aykanat , Bülent Abali, Adaptive Source Routing in Multistage Interconnection Networks, Proceedings of the 10th International Parallel Processing Symposium, p.258-267, April 15-19, 1996
• 9: H. Kariniemi and J. Nurmi, "New adaptive routing algorithm for extended generalized fat trees on-chip." in International Symposium on System-on-Chip (IEEE, ed.), pp. 113--118, 2003.

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)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling; Routing and layout

General Terms:
Algorithms, Design