互连网络子系统是并行处理计算机系统的重要组成部分。随着处理器数目的不断增加以及处理器计算能力的不断提高,处理器之间的通信问题变得越来越突出,设计高性能的互连通信子系统成为提高并行计算机系统性能的关键。而互连通信子系统的性能常常受限于路由算法和通信方式,底层硬件得不到充分利用,造成网络通信系统实际使用性能低效。 本文主要研究如何在通用的k-ary n-cube网络上实现高效的通信,研究重点是自适应路由算法和组播算法。 设计自适应路由算法首先需解决网络死锁问题。对于无边带连接的k-ary n-cube网络(网格),我们利用虚跨步切换技术中消息的依存关系只与相邻缓冲区队列有关的特点,设计实现了基于信约和报文路由信息的新型流控策略—RIFC(Routing Information-based Flow Control)。在RIFC基础上,设计了完全自适应路由算法—FAR(Fully Adaptive Routing)算法。通过证明,我们得出:在采用RIFC流控策略、虚跨步切换的无边带连接的k-ary n-cube网络中,FAR路由算法是无死锁的。 我们在RSIM模拟器上用实际应用程序测试了FAR路由算法的性能。通过修改RSIM的网络模拟器—NETSIM的代码,实现了RIFC流控和FAR路由算法。模拟结果表明:在二维网格中,FAR路由算法的性能优于维序路由算法的性能,无论后者采用虫孔切换还是虚跨步切换。 对于边带连接的k-ary n-cube网络(环网),我们综合Bubble流控和RIFC流控的设计思想,设计实现了一种新的流控策略—RIABFC(Routing Information-based And Bubble-based Flow Control)。基于RIABFC,设计了完全自适应路由算法—NFAR(New Fully Adaptive Routing)算法。并且证明了:对于采用RIABFC流控策略、虚跨步切换的边带连接的k-ary n-cube网络,NFAR路由算法是无死锁的。 为了模拟NFAR路由算法和组播算法的性能,我们采用C++语言设计实现了称为RingNetSim的模拟器。RingNetSim模拟器实现二维环网结构,采用离散事件驱动。在RingNetSim模拟器上,我们选择了不同的通信模式和仲裁策略,对NFAR路由算法进行了测试。模拟结果表明:在二维环网中,NFAR自适应路由算法的性能优于维序路由算法。