论文摘要
超立方体是一种具有优良性质的拓扑，它具有高度冗余通信路径与强容错通信能力、结构对称引入的自嵌入性、便于增加节点的可扩展性、网络寻路算法简洁性等优点。并且其它多种类型拓扑网络均可以便捷的与之相结合形成复合型拓扑，从而该型拓扑成为了高性能并行计算机系统设计中最具吸引力的网络模型之一。应用超立方体作为拓扑连接方式的并行计算机系统性能在很大程度上取决于其所采用的多播路由策略，其主要包括多播通信策略，容错多播通信策略和不相交路径多播通信策略。多播操作产生的通信量在众多并行计算机运算环境中的全部通信量中占相当大比重，设计能够提供高效通信服务的多播通信策略是提高系统通信效率和计算机整体可靠性的有效途径。而并行计算机规模扩大带来计算节点增多，系统中出现计算节点或通信链路故障频率也随之变高，因而在存在部分节点故障和连接故障情况下为了保证系统连续正确运行，设计产生通信信息量尽量小的容错多播通信策略是一个重要挑战性问题。不相交路径路由策略从目标节点数量上分为单目标节点和多目标节点两类，单目标节点不相交路径路由是增大节点间网络带宽并提高容错能力的综合解决方案，而多目标节点不相交路径通信可以看作是以路径不相交为约束条件的多播通信，他们为网络及系统可靠性提供了更高层次保障。如何在容错能力，通信效率，通信开销等方面对这三种通信策略进行优化成为超立方体网络路由策略研究的热点问题。本文的主要研究内容如下：以减少基于树型拓扑多播策略通信开销为目标，提出了一个超立方体网络基于逐层聚簇策略的启发式多播树构造算法（LWC-MT）。利用树型拓扑多播方案生成过程的分析结论及分簇模型，LWC-MT采用了以聚簇代价沿着最小增长方向进行聚簇操作的方法，对多播树建立过程进行了优化。仿真实验结果也表明，该算法在通信开销上优于现存算法。以在保证一定容错通信能力条件下减小多播通信开销为目标，提出了一种容错多播路由策略（FT-MT）和基于局部k维子立方连通超立方体网络的分布式容错多播路由策略（DFT-MT）。FT-MT利用近优容错路径存储模型构造容错多播方案，在保证容错能力的同时，得到了降低多播方案总体网络通信开销的优化结果。DFT-MT针对局部k维子立方连通超立方体网络，实现了对近优容错路径存储模型局部化管理和分布式存储，规避了近优容错路径存储模型在更新过程中的大量信息交换开销。模拟实验结果显示在确保满足局部k维子立方连通约束条件下，算法产生的通信开销优于相关文献中的方法。针对基于路径的多播通信中大量目标节点情况下对路径长度进行优化的问题，提出了一种基于极大目标节点分布密度的多播路径构造策略（MDPMP）和基于蚁群的多播路径构造算法（AMPA）。MDPMP利用目标节点分布密度不均匀性质进行子立方体划分，从而构造多播路径。仿真实验数据显示出在目标节点较多情形下，算法输出路径长度优于相关文献中的策略。为获得更短的多播路径，引入蚁群算法来求取子立方体划分问题（其为组合优化问题）的优化解，并以此建立多播路径，仿真实验数据表明路径长度得到了减小。进一步，论文通过把MDPMP和AMPA相结合的方式给出了分布式蚁群优化策略，有效缓解了蚁群算法引入较大计算时间复杂度问题。实验获得的数据显示，相对于源节点计算路由策略，分布式优化算法对优化结果的影响在可接受范围之内。以减小节点不相交路径通信策略的路径长度为目标，提出了一种一对多目标节点不相交容错优化路径算法和一对一不相交容错双路径算法。一对多目标节点不相交容错优化路径算法利用近优容错路径存储模型优化生成多条不相交路径，其在最长路径上限和平均路径长度两方面均优于已有算法。然后，基于一对一节点不相交多路径的特点，即在大多数情况下两条不相交路径提供了比较充分容错能力和接近扩展一倍的网络带宽，并且其求解效率也明显高于求解多于两条不相交路径，在此条件下，给出了一对一节点不相交容错双路径算法，该算法生成两条不相交路径中至少一条是两点之间经过近优容错路径矩阵充分优化的路径。