Publications of Torsten Hoefler

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

Fast Pattern-Specific Routing for Fat Tree Networks

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

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:

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},
  year={2013},
  month={Dec.},
  pages={36:1--36:25},
  volume={10},
  number={4},
  location={New York, NY, USA},
  publisher={ACM},
  issn={1544-3566},
  source={http://www.unixer.de/~htor/publications/},
}


serving: 18.189.170.65:39813	© Torsten Hoefler