Tolerating faults in interconnection networks for parallel computing

在分布式内存多处理器中，抑制更快全局计算的主要因素是处理器间通信。通信取决于互连网络的拓扑结构、路由机制、流量控制策略和交换方法。我们关注的是与互连网络的拓扑结构有关的问题。如何连接分布式内存多处理器中的处理器是一个基本的设计决策。有许多往往相互矛盾的考虑因素需要牢记。例如，我们希望互连网络是对称的（使编程和分析更容易），直径小（减少消息传递延迟），可递归分解（以提高可扩展性），高度连接（提高容错性和可靠性），规则度低（以减少通信开销和设计复杂性），支持快速和简单的处理器间通信，支持基于其他拓扑的其他机器的仿真，这些性质都提高了计算性能。然而，并不存在一个在所有方面都是最佳的互连网络，必须作出权衡。已经提出了大量的互连网络，其中每个网络具有一些好的（拓扑）属性和一些不太好的。当构建具有大量处理器的分布式内存多处理器时，需要一定的容错能力，因为人们仍然希望机器在（有限数量的）处理器或链路故障下运行。至于容错方面的要求取决于上下文，但最低要求是互连网络（的非故障部分）应保持连接。但通常需要更多。与并行计算相关的其他重要性质包括Hamilton性性质，因为网络中Hamilton圈的存在至关重要，因为这种圈在许多分布式算法中作为数据结构无处不在（它们主要用于促进消息传递）。不仅是存在的哈密尔顿圈非常重要，但也存在的哈密尔顿道路，更普遍的存在的循环和道路的不同长度。当我们经常需要在分布式内存多处理器中模拟线性阵列计算时，哈密顿路径（或者至少是长路径）的存在是非常有用的;有一个长路径允许我们满足这种模拟，其中有许多不同的阵列长度参与模拟。此外，由于基于循环的计算和算法在并行计算中的普遍性，不仅基于线性阵列的计算的模拟是重要的，而且基于循环的计算（不同长度）的模拟也是重要的。研究的思路有三个：在条件故障假设下（即假设网络中故障的分布），研究各种互连网络中路径和环（不同长度）的存在性;研究光转置互连系统（奥蒂斯）网络的容错性;以及在故障网络中嵌入结构的分布式构造。

In distributed-memory multiprocessors, the dominant factor inhibiting faster global computations is inter-processor communication. Communication is dependent upon the topology of the interconnection network, the routing mechanism, the flow control policy , and the method of switching. We are concerned with issues relating to the topology of the interconnection network. The choice of how we connect processors in a distributed-memory multiprocessor is a fundamental design decision. There are numerous, often conflicting, considerations to bear in mind. For instance, we would like our interconnection network to be symmetric (to make programming and analysis easier), have small diameter (to lessen message-passing latency), be recursively decomposable (to aid scalability), be highly connected (to improve fault-tolerance and reliability), be regular of low degree (to lessen communication overheads and design complexity), support rapid and easy inter-processor communication, support the simulation of other machines based on other topologies, and so on. These properties all give rise to improved computational performance. However, there does not exist an interconnection network that is optimal on all counts and trade-offs have to be made. A multitude of interconnection networks have been proposed with each of these networks having some good (topological) properties and some not so good. When building distributed-memory multiprocessors with massive numbers of processors, some capacity for fault-tolerance is required, for one would still wish the machine to be operative under (a limited number of) processor or link faults. As to what one requires in terms of fault-tolerance depends upon the context, but the minimal requirement is that the (non-faulty portion of the) interconnection network should remain connected. However, usually more is required. Other important properties relevant to parallel computing include Hamiltonicity properties, for the existence of Hamiltonian cycles in networks is of crucial importance, given the ubiquity of such cycles as data structures in many distributed algorithms (they are primarily used to facilitate message-passing). Not only is the existence of Hamiltonian cycles of great importance but also the existence of Hamiltonian paths, and more generally the existence of cycles and paths of different lengths. The existence of Hamiltonian (or, at least, long) paths is extremely useful as we regularly need to simulate linear-array computations in distributed-memory multiprocessors; having a long path allows us to cater for such simulations where there are many different array-lengths involved in the simulations. In addition, given the ubiquity of cycle-based computations and algorithms in parallel computation, not only is the simulation of linear-array-based computations important but so is the simulation of cycle-based computations (of varying lengths).The research in this proposal is all about the toleration of faults in interconnection networks. There are three threads to the research: the study of the existence of paths and cycles (of varying lengths) in various interconnection networks under conditional fault assumptions (that is, asumptions on the distributions of the faults in the network); the study of fault-tolerance in Optical Transpose Interconnect System (OTIS) networks; and the distributed construction of embedded structures within a faulty network.