Interconnection Networks: Practice unites with Theory (INPUT)

互连网络是一个（通常是大型）计算机系统的不同组件之间进行通信的机制。互连网络的设计并不简单，因为有许多问题需要考虑，例如：拓扑（即组件连接的基本模式）；路由算法（用于在网络中传输消息）；流量控制的方法（用于处理拥塞时不同的网络数据包，例如，请求有限的硬件资源）；以及交换的方法（一旦选择了消息的路由，该消息在整个网络中从一个组件到另一个组件进行物理传输的方式）。整个领域是硬件、软件和数学的不可思议的组合，并采用了计算机科学和工程学的原理。互连网络领域涵盖了各种不同的通信子系统，从相对较小的、非常本地的芯片上网络，到超级计算机和集群，再到巨大的、远程的和不断发展的网络，比如在网格和云计算中实现的网络（现代社会中如此多的无处不在的计算依赖于这些网络）。尽管许多互连网络原则普遍适用，但不同的领域特征和预期应用导致了许多差异。这里不可能涵盖这些差异的全部程度，但其中之一是互联网络的规模。片上网络相对较小——目前只有几十个节点（尽管有人在努力扩大到一千个节点），而数据中心网络或超级计算机中使用的节点数量可以达到数十万个。本提案的研究旨在通过在互连网络背后的数学与互连网络的实际构建之间建立更紧密的联系，改进超级计算机、集群和数据中心等大型系统的互连网络设计。例如，一台可以填满一个大房间的超级计算机的实际构造是非常复杂的，它有大量的电线、电缆、电路板、芯片、机架和机柜，所有这些都连接在一起，这样一个系统的所有计算能力都可以被用来有效地解决大量数据集上的问题。当然，这样一台超级计算机必须经过编程，以便它的每个计算元素都确切地知道该做什么和什么时候做，从而使单个计算结果能够迅速编译成潜在问题的解决方案。这样一个硬件和软件系统的设计是一个令人难以置信的工程壮举。数学家将这种超级计算机内部的基本互连网络抽象为图形；也就是说，作为一组顶点，它们之间由边连接。虽然这似乎是一个不精确的抽象，但可以使用图论属性来设计互连网络拓扑，这些拓扑具有人们希望的互连网络的许多属性。图的性质，例如，对称性，最短路径，连通性，哈密顿性，递归可分解性和嵌入证明是非常重要的，以确保良好的实用性质的互连网络。然而，到目前为止，数学理论与实际互联网络性能之间存在着相当大的差距。我们的研究计划旨在通过在互连网络的理论和实践之间提供更紧密的联系来缩小这一差距，最终目标是我们可以在理论上设计互连网络并确保其在构建和使用时产生的实际特性的技术。

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.