Interconnection Networks: Practice unites with Theory (INPUT)

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

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.