论文部分内容阅读
目前高性能计算研究的重点之一是并行计算机系统结构的研究,而并行计算机系统结构研究中的一个核心领域是对互连网络的研究。互连网络的拓扑结构是各处理单元间的通信结构的理论抽象,决定了处理单元和存储器以及I/O设备部分之间的数据通路,制约着整个系统的信息传输的速度、容错能力、路由控制算法的复杂性以及整个系统的工作效率,从而对整个并行计算机系统的性能有着重要的影响。因此对拓扑结构及对应路由算法的研究一直是互连网络研究的基础和重要课题之一。对角线递归带环网格RDT具有可扩展性、小直径和小平均距离、以及网格/带环网格的良好嵌入性,需要对路由算法、理论性能和耐故障特性等进行研究。RDT结构定义中参数的选择可以确定特定的实用结构,为了继承完全RDT结构的性能,同时具有低节点度,需要根据特定的系统需求研究相应的参数选择和带环网格分配来确定对应的实用结构。本课题选取RDT及其面向中等规模的实用结构作为研究对象。
本文通过研究RDT结构特征,提出与结构定义相一致的双重递归向量路由算法,也称作降序向量路由算法。该算法与单一递归向量路由算法具有同样的性能,但是算法实现更为简单。由于上述两种路由算法都是以向量路由算法为核心的,以向量路由算法为基础,研究RDT结构理论性能,得到理论直径和平均距离,并分析RDT结构参数对性能的影响。耐故障是互连网络路由算法的重要特性之一,本文针对耐故障特性进行研究,以向量路由算法为基础分别提案了面向完全结构PRDT(n,R)和实用结构的容错路由算法。
目前具有商业价值的并行系统较多采用支持中等规模(千节点左右)的互连网络。本文以完全RDT结构为基础提案了实用结构RDT(2,2,1)/alpha,该结构继承了RDT结构的优于经典结构的性能。