论文题目: 基于k-ary n-cube网络的高效通信
论文类型: 博士论文
论文专业: 计算机科学与技术
作者: 肖灿文
导师: 张民选
关键词: 并行处理系统,网络,流控,路由算法,流控,路由算法,模拟器,模拟器,组播路由算法
文献来源: 国防科学技术大学
发表年度: 2005
论文摘要: 互连网络子系统是并行处理计算机系统的重要组成部分。随着处理器数目的不断增加以及处理器计算能力的不断提高,处理器之间的通信问题变得越来越突出,设计高性能的互连通信子系统成为提高并行计算机系统性能的关键。而互连通信子系统的性能常常受限于路由算法和通信方式,底层硬件得不到充分利用,造成网络通信系统实际使用性能低效。 本文主要研究如何在通用的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自适应路由算法的性能优于维序路由算法。
论文目录:
摘要
ABSTRACT
第一章 绪论
1．1 并行处理与互连网络
1．2 并行计算机体系结构
1．3 并行计算机系统的互连网络
1．3．1 网络的拓扑结构
1．3．2 切换技术
1．3．3 路由算法
1．3．4 通信方式
1．4 问题描述
1．5 论文的主要工作和贡献
1．6 论文的组织形式
第二章 RIFC:基于路由信息的流控
2．1 背景及相关研究
2．1．1 部分自适应路由算法
2．1．2 跳步算法
2．1．3 虚拟网络
2．2 RIFC流控策略
2．3 定义
2．4 定理及证明
2．5 总结
第三章 FAR路由算法模拟测试及性能分析
3．1 测试方法概述
3．1．1 解释执行和对比原本执行
3．1．2 二进制代码对比汇编语言指令
3．1．3 踪迹驱动
3．1．4 执行驱动
3．2 常用的模拟工具
3．3 RSIM模拟器
3．4 模拟结果及分析
3．4．1 模拟程序及设置
3．4．2 LU模拟运行结果
3．4．3 FFT模拟运行结果
3．4．4 SOR模拟运行结果
3．4．5 QS模拟运行结果
3．4．6 WATER模拟运行结果
3．5 模拟结论
第四章 RIABFC:基于 RIFC和 BUBBLE的流控
4．1 背景和动机
4．2 RIABFC流控策略
4．3 NFAR路由算法
4．4 结论
第五章 NFAR路由算法模拟测试及性能分析
5．1 环网模拟器 RingNetSim
5．1．1 RingNetSim概述
5．1．2 RingNetSim模拟器的组成部分
5．2 模拟结果及分析
5．2．1 完全随机通信模式下模拟结果
5．2．2 位反通信模式下模拟结果
5．2．3 就近通信模式下模拟结果
5．2．4 An-to-All通信模式下模拟结果
5．3 结论
第六章 2DMR组播算法
6．1 背景及相关研究
6．1．1 基于树的组播
6．1．2 基于路径的组播算法
6．1．3 BRCP-HL算法
6．2 2DMR组播路由算法
6．2．1 多目标报文头组织
6．2．2 报文复制和组播路由算法
6．3 结论
第七章 2DMR组播算法模拟测试及性能分析
7．1 组播算法实现
7．2 模拟结果及分析
7．2．1 就近通信模式下模拟结果
7．2．2 完全随机通信模式下模拟结果
7．2．3 All-to-All通信模式下模拟结果
7．3 模拟结论
第八章 支持组播的自适应路由芯片设计
8．1 介绍
8．1．1 芯片整体结构
8．2 路由芯片设训
8．2．1 输入缓冲区管理
8．2．2 仲裁和开关模块
8．3 芯片实现及测试结论
第九章 结束语
9．1 工作回顾
9．2 进一步工作
攻读博士学位期间发表和已录用的论文
致谢
参考文献
发布时间: 2005-11-07
相关论文
- [1].高性能计算机互连系统研究[D]. 邓波.中国人民解放军国防科学技术大学2000
- [2].大规模组通信组播技术研究[D]. 刘志峰.国防科学技术大学2005
- [3].高速边缘路由器IPSec体系结构及关键技术的研究[D]. 荣霓.国防科学技术大学2005
- [4].基于接口自动机的组合验证方法研究[D]. 文艳军.国防科学技术大学2005
- [5].规则网络容错路由算法及可靠组播的研究[D]. 张祖平.中南大学2005
- [6].微分网格处理技术[D]. 许栋.浙江大学2006
- [7].计算网格环境中任务管理的研究[D]. 栾翠菊.浙江大学2006
- [8].非结构化网格生成及其并行化的若干问题研究[D]. 陈建军.浙江大学2006
- [9].基于资源类型的非集中式网格资源发现方法研究[D]. 朱承.国防科学技术大学2004
- [10].多计算机互连网络上聚合通信算法的研究[D]. 刘刚.中国科学技术大学2006