Distance and symmetry properties of graphs and their application to interconnection networks and codes

Abstract

ABSTRACT: The topology of a interconnection network is the graph of its routers. The topologies that are being currently used in large supercomputers can be classified into two families: the ones that use routers with moderate radix and the ones using high-radix routers. The objective of this thesis is to define topologies for both families that exhibit better properties than the actual ones.

Examples of moderate degree machines are the Cray XK7, the K computer and the Blue Gene/Q, whose topologies are tori. In this thesis the lattice graphs are proposed. They are variant of tori with reduced distances and which can be symmetric for sizes in which the tori is forced to be asymmetric.

Among the most used topologies for the family of high-radix routers there are the Clos networks, and more recently, the dragonfly networks. This thesis focuses on dragonfly networks. In this thesis, it is explained how Hamming graphs can be seen as a dragonfly with large global trunking and that some properties of the Hamming graphs can be extrapolated to dragonflies.

The problem of finding lattice graphs with optimal distance properties is actually equivalent to the problem of finding good codes over the Lee space. In this thesis several quasi-perfect codes are built, which can then be seen as nearly optimal lattice graphs. They include quasi-perfect codes for arbitrarily large dimensions that reach half the density of the density of potential perfect Lee.

RESUMEN: La topología de una red de interconexión es el grafo de sus elementos encaminadores o routers. Las topologías actualmente usadas en los grandes supercomputadores se pueden dividir en dos familias: las que usan routers con grado moderado y las que usan routers de alto grado. El objetivo de esta tesis es proponer topologías para ambas familias que posean mejores propiedades que las actuales.

Ejemplos de máquinas con topologías de grado moderado son el Cray XK7, el K computer y el Blue Gene/Q, cuyas topologías son toros. En esta tesis se proponen los lattice graphs, que son variantes de los toros con distancias reducidas y que pueden ser simétricos para tamaños en que los toros están forzados a ser asimétricos.

Dentro de la familia de topologías de routers de alto grado más usadas se encuentran las redes de Clos y más recientemente, las dragonflies. En esta tesis nos hemos centrado en está última. En esta memoria se explica cómo un grafo de Hamming puede verse como una dragonfly con gran trunking global y como ciertas propiedades de los grafos de Hamming pueden extenderse a otras dragonflies.

El problema de buscar lattice graphs con propiedades de distancia óptimas resulta ser equivalente al problema de encontrar buenos códigos sobre el espacio de Lee. En esta tesis se construyen varios códigos cuasi-perfectos, que se pueden por tanto ver como topologías casi óptimas. Entre ellos, se incluyen códigos cuasi-perfectos para dimensiones arbitrariamente grandes que alcanzan la mitad de la densidad de los posibles códigos perfectos. Lo cual supone un acercamiento a una conjetura hecha por Golomb y Welch en 1930.