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.