基于3D-Torus互连网络的交换机制与路由算法的研究

摘要

3D-Torus互连网络是互连网络中直连网络的一个重要组成部分，凭借其特有的规整性、对称性和正交性，许多高性能并行计算机已经应用它进行了设计开发。本文从3D-Torus互连网络的拓扑结构、交换机制以及路由算法等方面进行了研究，得出了一些对3D-Torus互连网络较有意义的结论。 首先，本文对应用于3D-Torus互连网络的几种常见的交换机制进行了分析对比，结果表明，无论从时延要求还是网络吞吐率来看，虚拟直通交换机制都是符合3D-Torus互连网络性能要求的最合适方案。此外，针对虚拟直通交换机制下的不同参数仿真模拟，其结论对于实际系统的设计也具有借鉴意义。 其次，本文又研究了基于3D-Torus互连网络的路由算法设计问题，重点解决单播和多播路由算法设计和实现的问题。单播路由中，本文提出了基于3D-Torus互连网络的确定性维序路由和部分自适应路由，并对它们进行了模拟仿真和比较，结果发现应用部分自适应路由可以在一定程度上降低网络传输的时延，不过部分自适应路由对结点中路由器的功能要求颇高，从而也在一定程度上加大了硬件设计的困难。多播路由中，本文提出了应用在3D-Torus互连网络上的分布式包复制多播路由算法。通过模拟分析，该算法能够大大提高传输通道的利用率，却并未对消息包的格式结构提出过高的要求。算法在设计时都确保路由时不会形成环路，所以都能够避免死锁问题的发生。 总之，对于3D-Torus互连网络的交换机制及路由算法的研究有其现实意义，如何降低网络传输时延以及提高网络整体吞吐率是这些研究的主要目标。

目录

文摘

英文文摘

声明

第1章 绪论

§1.1引言

§1.2互连网络概述

§1.2.1互连网络的分类

§1.2.2互联网络的路由器模型

§1.2.3互连网络的交换机制

§1.2.4互连网络的拓扑结构

§1.2.5互连网络的路由算法

§1.3论文研究重点及结构安排

第2章 3D-Torus互连网络基本概述

§2.1引言

§2.2 3D-Torus互连网络的拓扑结构

§2.3 3D-Torus互连网络的基本特性

§2.3.1规整性(Regularity)

§2.3.2对称性(Symmetry)

§2.3.3正交性(Orthogonality)

§2.4 3D-Torus互连网络的坐标系统

§2.4.1 3D-Torus互连网络的结点编号与结点坐标转换

§2.5 3D-Torus互连网络的应用

§2.6 3D-Torus互连网络的模拟

§2.6.1模拟环境中的各功能部件

§2.6.2模拟环境的具体工作流程

§2.6.3模拟环境中各个操作的时延定义

§2.7本章小结

第3章 基于3D-Torus互连网络的交换机制

§3.1引言

§3.2基于3D-Torus互连网络的交换机制

§3.2.1电路交换(Circuit Switching)

§3.2.2存储转发交换(Store and Forward switching)

§3.2.3虫孔交换(Wormhole Switching)

§3.2.4虚拟直通交换(Virtual Cut Through Switching)

§3.3虚通道技术

§3.4模拟结果与性能分析

§3.4.1应用三种交换机制的仿真结果与分析

§3.4.2应用虚拟直通交换机制的仿真结果与分析

§3.5本章小结

第4章 基于3D-Torus互连网络的路由算法

§4.1引言

§4.2死锁及活锁

§4.2.1死锁避免

§4.2.2活锁避免

§4.3基于3D-Torus互连网络的单播(Unicast)路由

§4.3.1确定性维序路由算法

§4.3.2部分自适应路由算法

§4.4基于3D-Torus互连网络的多播(Multicast)路由

§4.4.1多播通信模型

§4.4.2基于树的多播路由

§4.4.3基于路径的多播路由

§4.5模拟结果与性能分析

§4.5.1单播路由算法性能比较

§4.5.2多播路由算法性能比较

§4.6本章小结

第5章 结论与展望

§5.1已经完成的工作

§5.2进一步的研究工作

参考文献

作者攻读学位期间公开发表的论文

致 谢