Copyright Notice:

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications of SPCL

P. Yebenes, J. Escudero-Sahuquillo, P. J. Garcia, F. J. Quiles, T. Hoefler:

 Improving Non-Minimal and Adaptive Routing Algorithms in Slim Fly Networks

(In Proceedings of the 25th Annual Symposium on High-Performance Interconnects (HOTI'17), Aug. 2017)

Publisher Reference

Abstract

Interconnection networks must meet the communication demands of current High-Performance Computing systems. In order to interconnect efficiently the end nodes of these systems with a good performance-to-cost ratio, new network topologies have been proposed in the last years which leverage high-radix switches, such as Slim Fly. Adversarial-like traffic patterns, however, may reduce severely the performance of Slim Fly networks when using only minimal-path routing. In order to mitigate the performance degradation in these scenarios, Slim Fly networks should configure an oblivious or adaptive non-minimal routing. The non-minimal routing algorithms proposed for Slim Fly usually rely on Valiant’s algorithm to select the paths, at the cost of doubling the average path-length, as well as the number of Virtual Channels (VCs) required to prevent deadlocks. Moreover, Valiant may introduce additional inefficiencies when applied to Slim Fly networks, such as the “turn-around problem” that we analyze in this work. With the aim of overcoming these drawbacks, we propose in this paper two variants of the Valiant’s algorithm that improve the non-minimal path selection in Slim Fly networks. They are designed to be combined with adaptive routing algorithms that rely on Valiant to select non-minimal paths, such as UGAL or PAR, which we have adapted to the Slim Fly topology. Through the results from simulation experiments, we show that our proposals improve the network performance and/or reduce the number of required VCs to prevent deadlocks, even in scenarios with adversarial-like traffic.

Documents

download article:
 

BibTeX

@inproceedings{,
  author={P. Yebenes and J. Escudero-Sahuquillo and P. J. Garcia and F. J. Quiles and T. Hoefler},
  title={{Improving Non-Minimal and Adaptive Routing Algorithms in Slim Fly Networks}},
  year={2017},
  month={08},
  booktitle={Proceedings of the 25th Annual Symposium on High-Performance Interconnects (HOTI'17)},
}