论文摘要
互连网络是构成高性能计算机系统和决定系统通信性能的关键部分。随着VLSI技术的飞速发展以及多核、多线程和片上系统等新技术的应用,高性能计算机系统的规模不断扩大,处理结点的性能持续增长。相比之下,互连网络性能增长速度十分缓慢,已逐渐成为制约系统整体性能发挥的瓶颈。因此,在研发新型互连技术(光互连)的同时,如何提高以组播和归约等操作为基础的聚合通信性能也是当前互连网络研究的热点之一。高性能计算机系统规模的不断扩大,导致互连网络中结点出错的概率也大大增加。若某些处理结点出错而导致解决挑战性应用的高性能计算机系统宕机,造成的计算能力的巨大浪费是不可忍受的。因此,系统应具有降级重组能力,保证正确的处理结点能正常工作。此时,互连网络提供容错通信能力,保证结点间的可靠、高效通信至关重要。超立方体是人们最早研究且仍是目前最重要的互连网络拓扑结构之一,具有正规性、对称性、强容错性、直径短、可嵌入性等诸多优点。并且随着高维度路由器和高速串行传输技术的出现,因高维超立方体网络有巨大的结点容量,其备受诟病的可扩展性在很长一段时间内将不成问题。本文研究了超立方体网络上的组播算法。包括对无错误结点的常规超立方体网络的组播算法研究,和对包含错误结点的超立方体网络上的容错组播算法研究。组播的通信开销是评价组播性能的重要标准之一。我们根据超立方体拓扑结构的规整性和组播目标结点间的局部性特征,提出了一个分簇组播模型。分析表明:簇的度较小且簇内目标结点间局部性特征好,使得簇内通信开销小,从而减小组播通信开销。基于分簇组播模型,我们设计了一个组播树算法和一个组播路径算法。这两个算法对组播消息的路由是完全分布的。和已有的同类组播算法相比,基于分簇的组播树和组播路径算法对组播目标结点间局部性特征的利用率更高,能显著减小组播通信开销。针对目前超立方体网络上容错能力最强的容错模型——局部子立方连通,我们提出了一个结点可达性模型。该可达性模型是完全分布的,不需要集中式的控制。并且,我们证明了:仅使用结点上的可达性信息,任意两个正确结点之间均是可路由的。此外,我们设计了三个算法用于结点间交换、更新可达性信息,一个算法用于检测局部子立方体的连通性。这些算法都是简洁高效且完全分布的,算法的主要操作是与、或等逻辑操作,复杂度低,利于硬件实现。基于可达性模型,我们设计了一个简洁高效的容错路由算法。与局部子立方连通超立方体网络上已有的容错路由算法相比,我们的算法是完全分布的,复杂度更低。并且,算法的主要操作是与、或等逻辑操作,利于硬件实现,有很高的实用价值。基于可达性模型,我们设计了局部子立方连通超立方体网络上的首个容错组播算法。该算法也是简洁高效且完全分布的,复杂度低,主要操作是与、或等逻辑操作,利于硬件实现,有很高的实用价值。