An interconnection network is a mechanism by which different components of a (usually large) computer system communicate. The design of interconnection networks is not straightforward as there are many issues to take into account, such as: the topology (that is, the basic pattern of connectivity of the components); the routing algorithms (that are used in order to transfer messages around the network); the methods of flow-control (that are used in order to deal with congestion when different network packets, for example, request limited hardward resources); and the methods of switching (the way in which once a route for a message has been selected, the message is physically transferred from component to component throughout the network). The whole area is an incredible mix of hardware, software and mathematics, and employs principles from both computer science and engineering.
The field of interconnection networks covers a wide variety of different communications subsystems, from relatively small, very local on-chip networks, through supercomputers and clusters, and on to vast, remote and evolving networks such as those implemented in grid and cloud computing (upon which so much of the ubiquitous computing in modern society depends). Although many interconnection network principles apply universally, the varying domain characteristics and intended applications lead to a number of differences. The full extent of these differences is impossible to cover here but one is the scale of the interconnection network. On-chip networks are relatively small - currently tens of nodes (though there are efforts to scale up to a thousand nodes), whilst the number of nodes used in data centre networks or supercomputers can be hundreds of thousands. The research in this proposal aims to improve the design of interconnection networks for large-scale systems such as those employed in supercomputers, clusters and data centres by developing closer links between the mathematics behind interconnection networks and the practical construction of interconnection networks.
The practical construction of, for example, a supercomputer that might fill a large room is immensely complex, with a multitude of wires, cables, boards, chips, racks and cabinets all conjoined so that all of the computational power of such a system can be employed to yield efficient solutions to problems on massive data sets. Of course, such a supercomputer has to be programmed so that each of its computational elements knows exactly what to do and when to do it and so that the individual computational results can be rapidly compiled into a solution of the underlying problem. The design of such a hardware and software system is an incredible feat of engineering. Mathematicians abstract the essential interconnection network within such a supercomputer as a graph; that is, as a set of vertices, pairs of which are joined by edges. Whilst this may seem an imprecise abstraction, one can use graph-theoretic properties in order to design interconnection network topologies which possess many properties one would wish of an interconnection network. Graph properties relating to, for example, symmetry, shortest-paths, connectivity, Hamiltonicity, recursive decomposability and embeddings prove to be extremely important in securing good practical properties for interconnection networks. However, up until now there has been a considerable gap between the mathematical theory on the one hand and practical interconnection network performance on the other. Our research proposal aims to narrow this gap by providing a closer link between the theory and practice of interconnection networks, with the ultimate goal being techniques by which we can theoretically design an interconnection network and be sure of its resulting practical properties when built and used.
|