题目：大规模互连网络拓扑结构和路由算法研究

    随着应用需求的多样性、复杂性和大规模集成电路技术的发展，大规模系统的网络规模急剧膨胀，带来诸多问题和挑战，也出于实际研究工作的需要，本文重点研究了拓扑结构、路由算法、仿真模型、基于虚通道的路由芯片设计，以及拓扑映射等内容，并基于大规模网络中常用的胖树网络、立方网络进行了相关实验和分析。

    在拓扑结构方面，针对胖树网络转弯后不能多路径及流量分布不均的问题，提出了一种带侧向链路的一般性混合胖树网络：GFT-X，其中的X可以是任意结构，诸如Mesh、Torus等。X可以提供下行的多路径，还可在下行时绕过故障点或拥塞点。在设计中，我们特例化X为全互连结构，提出了GFT-FC结构。分析表明，GFT-FC即能有效增加网络规模，又能降低网路延迟，同时还能有效降低网络成本。实验表明，采用所设计的路由算法，网络性能约20%左右的提升。此外，也并没有因为采用侧向链路而使得平均路径有较大的变化，基本上接近网络最短直径。

    在仿真模型方面，本文基于网络演算和排队论结合，提出了适合高性能计算领域的胖树网络模型，该模型主要是给出了系统的端到端服务曲线。基于该服务曲线，路由芯片的服务过程基于排队规则，模型研究了均匀流量模式的网络性能，实验表明它基本吻合仿真模拟器的实验结果。    

    在Router设计方面，针对数据流间的干涉与解耦问题，通过研究虚通道的运行机理，提出了一种两阶段路由方式，包括端口层和虚通道层，每一层都可以独立设计。我们的工作聚焦在虚通道层，设计了一种虚通道区间隔离路由，该方案运行在虚通道分配阶段，并设计相应的分布式虚通道分配器，实现并行匹配。仿真表明我们的方案能够有效解耦重负载流和轻流，尤其是在高负载通信的情况下，合适的分组值能够获得更佳的性能。当流量的负载分布比较均匀时，该方案也有效保持了其均匀分布性。

     在拓扑映射方面，针对通信拓扑和网络拓扑的不匹配问题，基于社团发现算法和稀疏矩阵带宽减少算法提出了一个组合的拓扑映射策略，每个算法的使用相当于对原始的通信矩阵的一个矩阵变换。首先对原序按带宽减少算法进行变换，目的是将相互通信的节点尽可能紧邻布局，以便缩短通信距离；然后在该基础上再用社区发现算法探索可作为一组的通信团，实现团内高内聚，团间少交互的要求；最后对团内再次应用带宽减少算法进行变换，以实现团内的紧凑布局。实验表明本文方法在所给的四类大规模稀疏矩阵和六类合成流量模式上都有较好的表现，有效提高了通信性能，尤其对合成流量模式有更好的表现，吞吐率几乎接近1。    

     论文设计并实现了拓扑映射模拟器、流量模式产生器，通过对BookSim2.0进行相应的修改，为其增加了胖树网络、矩阵流量模式，以及相关的路由算法等功能。