Distance and symmetry properties of graphs and their application to interconnection networks and codes ; Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos

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 ...