Adaptive Routing Protocols in Massively Parallel Architectures

本研究致力于基于超立方体互连网络(HINS)的大规模并行体系结构的自适应路由协议的发现和发展。此类包括众所周知的二进制n立方体、k元n立方体和多维数组。开发了路由协议的分类，并使用该分类将注意力集中在不同的类别上。在这项研究中，两个新概念将被开发和探索。首先，将严格描述这些协议的保守性和乐观性。我们将研究这些属性对消息延迟、网络带宽和网络拓扑的影响。其次，介绍并开发了多阶段协议的类。这些协议的行为是消息到目的地距离的函数。所提出的路由器体系结构将通过仿真进行建模和评估。我们将特别关注在存在布线复杂性、引脚数和链路层协议等实施限制的情况下的性能评估。

The research is concerned with the discovery and development of adaptive routing protocols for massively parallel architectures using Hypercube Interconnection Networks (HINs). This class includes the well known binary n-cube, k-ary n- cube, and multidimensional arrays. A taxonomy of routing protocols is developed and used to focus attention on distinct classes. Two new concepts will be developed and explored in this study. First, the properties of conservatism and optimism of these protocols will be rigorously characterized. The effect of these properties on message latency, network bandwidth, and network topology will be studied. Second, the class of multi-phase protocols will be introduced and developed. These are protocols whose behavior is a function of the distance of a message from the destination. The proposed router architectures will be modeled and evaluated via simulation. Particular attention will be focused on the evaluation of performance in the presence of implementation constraints such as wiring complexity, pin count, and link layer protocols.