Exploring pattern-aware routing in generalized fat tree networks

ABSTRACT

New static source routing algorithms for High Performance Computing (HPC) are presented in this work. The target parallel architectures are based on the commonly used fat-tree networks and their slimmed versions. The evaluation of such proposals and their comparison against currently used routing mechanisms have been driven by realistic traffic generated by HPC applications. Our experimental framework is based on the integration of two existing simulators, one replaying an MPI application and another simulating the network details. The resulting simulation platform has been fed with traces from real executions.

We have obtained several interesting findings: (i) contrary to the widely accepted belief, random static routing in k-ary n-trees (which is the default option for InfiniBand and Myrinet technologies) is not a good solution for HPC applications; (ii) some existing oblivious routing techniques can be very good for certain communication patterns present on applications, but clearly fail for some others and (iii) one of the proposed pattern-aware routing algorithms could be used to better utilize network resources and thus achieve higher performance, particularly for the case of cost-effective networks.

REFERENCES

• 1: Salvador Coll , Duato Duato , Fabrizio Petrini , Francisco J. Mora, Scalable Hardware-Based Multicast Trees, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.54, November 15-21, 2003
• 2: N. Desai, P. Balaji, P. Sadayappan, and M. Islam. Are Nonblocking Networks Really Needed for High-End-Computing Workloads? In Proc. 2008 IEEE International Conference on Cluster Computing, pages 152--159, Washington, DC, USA, 2008. IEEE Computer Society.
• 3: Zhu Ding , Raymond R. Hoare , Alex K. Jones , Rami Melhem, Level-wise scheduling algorithm for fat tree interconnection networks, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188556]
• 4: Improving Routing Performance in Myrinet Networks, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.27, May 01-05, 2000
• 5: C. Gomez, F. Gilabert, M. Gomez, P. Lopez, and J. Duato. Deterministic versus adaptive routing in fat-trees. Proc. of the 21st Parallel and Distributed Processing Symposium, 2007, pages 1--8, Mar. 2007.
• 6: Ronald I. Greenberg , Charles E. Leiserson, Randomized routing on fat-tress, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, p.241-249, October 21-23, 1985 [doi>10.1109/SFCS.1985.46]
• 7: A. Jajszczyk. Nonblocking, repackable, and rearrangeable Clos networks: fifty years of the theory evolution. Communications Magazine, IEEE, 41(10):28--33, Oct. 2003.
• 8: G. Johnson, D. J. Kerbyson, and M. Lang. Optimization of InfiniBand for Scientific Applicationsa. In Proc. of the 22nd International Parallel and Distributed Processing Symposium, pages 1--8. IEEE, 2008.
• 9: S. Kamil, J. Shalf, L. Oliker, and D. Skinner. Understanding ultra-scale application communication requirements. Proc. Workload Characterization Symposium, pages 178--187, Oct. 2005.
• 10: H. Kariniemi. On-Line Reconfigurable Extended Generalized Fat Tree Network-on-Chip for Multiprocessor System-on-Chip Circuits. PhD thesis, Tampere University of Technology, 2006.
• 11: Jesús Labarta , Sergi Girona , Vincent Pillet , Toni Cortes , Luis Gregoris, DiP: A Parallel Program Development Environment, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.665-674, August 26-29, 1996
• 12: 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]
• 13: X.-Y. Lin, Y.-C. Chung, and T.-Y. Huang. A multiple LID routing scheme for fat-tree-based InfiniBand networks. Proc. of the 18th International Parallel and Distributed Processing Symposium, pages 11--, 2004.
• 14: Cyriel Minkenberg , Germán Rodriguez, Trace-driven co-simulation of high-performance computing systems using OMNeT++, Proceedings of the 2nd International Conference on Simulation Tools and Techniques, March 02-06, 2009, Rome, Italy [doi>10.4108/ICST.SIMUTOOLS2009.5521]
• 15: J. Navaridas, J. Miguel-Alonso, F. J. Ridruejo, and W. Denzel. Reducing complexity in tree-like computer interconnection networks. Technical Report EHU-KAT-IK-06-07, UPV/EHU, 2007.
• 16: Sabine R. Öhring , Maximilian Ibel , Sajal K. Das , Mohan J. Kumar, On generalized fat trees, Proceedings of the 9th International Symposium on Parallel Processing, p.37, April 25-28, 1995
• 17: Maurizio Palesi , Rickard Holsmark , Shashi Kumar , Vincenzo Catania, Application Specific Routing Algorithms for Networks on Chip, IEEE Transactions on Parallel and Distributed Systems, v.20 n.3, p.316-330, March 2009 [doi>10.1109/TPDS.2008.106]
• 18: Judea Pearl, Heuristics: intelligent search strategies for computer problem solving, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 19: F. Petrini and M. Vanneschi. A comparison of wormhole-routed interconnection networks. In Proc. Third International Conference on Computer Science and Informatics, Research Triangle Park, NC, USA, Mar. 1997.
• 20: José Carlos Sancho , Antonio Robles, Improving the Up*/Down* Routing Scheme for Networks of Workstations, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.882-889, August 29-September 01, 2000
• 21: José Carlos Sancho , Antonio Robles , José Duato, Effective Strategy to Compute Forwarding Tables for InfiniBand Networks, Proceedings of the 2001 International Conference on Parallel Processing, p.48-60, September 03-07, 2001
• 22: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
• 23: Jeffrey S. Vetter , Frank Mueller, Communication characteristics of large-scale scientific applications for contemporary cluster architectures, Journal of Parallel and Distributed Computing, v.63 n.9, p.853-865, September 2003 [doi>10.1016/S0743-7315(03)00104-7]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Topology (e.g., bus, point-to-point)

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Performance

Keywords:
k-ary n-trees, clos networks, communication/traffic patterns, extended generalized fat trees (xgft's), network topologies, routing algorithms