Buscar

Lattice Graphs for High-Scale Interconnection Topologies


Abstract: Torus networks of moderate degree have been widely used in the supercomputer industry. Tori are superb when used for executing applications that require near-neighbor communications. Nevertheless, they are not so good when dealing with global communications. Hence, typical 3D implementations have evolved to 5D networks, among other reasons, to reduce network distances. Most of these big systems are mixed-radix tori, which are not the best option for minimizing distances and efficiently using network resources. This paper is focused on improving the topological properties of this kind of networks. By using integral matrices to deal with Cayley graphs over Abelian groups, we have been able to propose and analyze a family of high-dimensional mesh-based interconnection networks. As they are built over n-dimensional grids that induce a regular tiling of space, these topologies have been denoted lattice graphs. Higher dimensional networks can be composed over these graphs by means of a lift operation, which is also introduced in the paper. Easy network partitioning and minimal routing algorithm are also provided for these topologies based on this new network operation. Later we focus on cubic crystal lattices for modeling symmetric 3D networks and to show how lattice graphs can help in the design of twisted interconnection networks. In all cases, the networks obtained are better, in topological terms, than their standard tori counterparts. Finally, some practical issues such as implementability and preliminary performance evaluations have been addressed at the end of this work. © 2014 IEEE.

 Fuente: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 9, SEPTEMBER 2015

Editorial: IEEE Computer Society

 Fecha de publicación: 01/09/2015

Nº de páginas: 14

Tipo de publicación: Artículo de Revista

DOI: 10.1109/TPDS.2014.2355827

ISSN: 1045-9219,1558-2183

Proyecto español: IN2010-21291-C02-02 ; TIN2013-46957-C2-2-P

Url de la publicación: https://doi.org/10.1109/TPDS.2014.2355827