RRR: A Load Balanced Routing Scheme for Slimmed Fat-trees

Hits: 2579
Year:
2013
Type of Publication:
Article
Keywords:
fat-tree, static routing, interconnect
Authors:
  • Yuan, Xin
  • Mahapatra, Santosh
  • Lang, Michael
  • Pakin, Scott
BibTex:
Note:
The 3rd Workshop on Communication Architecture for Scalable Systems (CASS) 2013. To be held in conjunction with the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2013)
Abstract:
Fat-trees are widely adopted in HPC systems. While existing static routing schemes such as destination-modk (D-mod-k) routing are load-balanced and effective for full bisection bandwidth fat-trees, they are not load-balanced for many slimmed fat-trees, which have recently been suggested to reduce costs in HPC systems. In this work, we propose a load balanced routing scheme, called Round-Robin Routing (RRR), for 2- and 3-level extended generalized fat-trees (XGFTs), which represent many fat-tree variations including slimmed fat-trees. RRR achieves near perfect load-balancing for any such XGFT in that links at the same level of a tree carry traffic from almost the same number of source-destination pairs. Simulation results show that on many slimmed fat-trees, RRR is significantly better than D-mod-K for majority of traffic patterns.
Back

© 2017 New Mexico Consortium