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

B. Prisacari, G. Rodriguez, C. Minkenberg, T. Hoefler:

 Fast Pattern-Specific Routing for Fat Tree Networks

(ACM Transactions on Architecture and Code Optimization. Vol 10, Nr. 4, In , presented in New York, NY, USA, pages 36:1--36:25, ACM, ISSN: 1544-3566, ISBN: , Dec. 2013, )

Publisher Reference

Abstract

Routing is a fundamental problem in the field of interconnection networks and one of the most important factors that affect the performance of communication workloads across a network. For a given workload and network structure, finding sets of routes that achieve an optimal usage of the available bandwidth is an especially interesting area of research while being at the same time particularly difficult to achieve. In the specific context of network topologies belonging to the extended generalized fat tree (or XGFT) family, widely used in both high performance computing systems and datacenter network designs, we present in this work a generic method of determining optimal routes for arbitrary workloads, method that is based on formulating the routing problem as an integer linear programming problem then producing the solution to that problem by using an open-source integer linear programming solver. To enable the solution to scale to practical network sizes in a relatively small amount of time, we introduce several optimizations, ranging from dividing the problem into local subdomains, all the while ensuring global optimality of the reunion of local solutions, to acceleration techniques meant to allow the linear programming solver to complete the optimization faster. To support the formulation, we will equally introduce in this work a novel generic mathematical XGFT model that is able to more clearly expose XGFT properties, routing-related properties in particular. Finally, we will show through a series of extensive benchmarks that our approach scales in practice to networks with as many as 8192 leaf nodes, using a single threaded freely available linear programming solver, with the potential for higher scalability when using commercial, parallel solvers.

Documents

download article:
download slides:
 

BibTeX

@article{prisacari-pattern-routing,
  author={B. Prisacari and G. Rodriguez and C. Minkenberg and Torsten Hoefler},
  title={{Fast Pattern-Specific Routing for Fat Tree Networks}},
  journal={ACM Transactions on Architecture and Code Optimization},
  institution={},
  year={2013},
  month={12},
  pages={36:1--36:25},
  volume={10},
  number={4},
  booktitle={},
  location={New York, NY, USA},
  publisher={ACM},
  issn={1544-3566},
  isbn={},
  note={},
}