片上网络高效自适应路由算法研究

发布时间：2020-10-28 15:14

　　 随着集成电路(Integrated Circuit,IC)工艺节点的进步,在片上系统(System-on-chip,SoC)上可集成的IP(Intellectual Property)核数越来越多,实现的功能也越来越复杂。SoC设计方法学通常采用总线式结构设计,目前在系统设计中总线面临的有限地址空间和较大的延迟问题已成为设计的瓶颈。片上网络(Network-on-chip,NoC)技术借鉴了分布式计算机网络通信的特点,它具有的并行通信能力和网络可扩展性可以有效地解决复杂SoC的通信瓶颈问题,已成为具有广阔前景的片上互连解决方案。在片上网络设计中,路由算法对网络的延迟、吞吐率和硬件开销等性能有重要的影响,因此,高效路由算法的研究十分重要。路由算法中确定性路由算法的路径唯一、实现简单,但不能根据网络状态选择路径,仅适用于低注入率;而其中的自适应路由算法可以根据网络的状态动态选择轻负载路径,适用于高注入率。本论文系统地分析了片上网络设计的关键技术,对自适应路由算法展开了深入的研究,提出了一些设计思路,主要的研究内容和研究成果如下:(1)对已存在的XY、XY-YX、CXY和OE(Odd Even)路由算法进行了详细的分析和实现,通过流程框图、伪代码和转弯模型(Turn Model)分析了每种路由算法的设计思想和优缺点,然后通过对比分析找出了已有路由算法可以进一步改进的创新点,即将传统的OE路由算法改进为真正的具有自适应性的OE路由算法。(2)针对传统OE路由算法不能动态选择路由路径的问题,提出了一种公平仲裁路由(Fair Arbiter Routing,FAR),该算法采用了兼顾优先级和公平性的可变优先级(Alterable Priority,AP)仲裁方案在路由节点上实现了输出多路径的动态随机选择,缓解了拥塞,提高了网络性能。公平的FAR路由算法分别在OE模型和XY模型上实现,Noxim仿真平台的仿真和在SMIC 0.13μm CMOS工艺下的验证结果表明,公平仲裁FAR路由算法以较低的硬件开销增加有效地改善了路由的网络性能。(3)针对轻负载路径的选取问题,提出了一种本地自适应公平仲裁路由(Local Adaptive Fair Arbiter Routing,LAFAR),该算法采用拥塞感知的方式获取相邻路由器的拥塞信息,通过比较相应路由端口的拥塞值大小选择低拥塞值的路径,有效地避开了拥塞区域,改善了网络性能;若拥塞值相同,则该路由算法退化为FAR路由算法,通过AP公平仲裁随机选择路由路径。LAFAR路由算法分别在OE模型和XY模型上实现,Noxim仿真平台的仿真和在SMIC 0.13μm CMOS工艺下的验证结果表明,低拥塞LAFAR自适应路由算法具有良好的路由网络性能和较低的额外硬件开销增加。
【学位单位】：西安电子科技大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TN47
【文章目录】：
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
    1.1 研究背景和研究意义
    1.2 国内外研究现状和进展
        1.2.1 国外研究现状
        1.2.2 国内研究现状
    1.3 论文研究内容
    1.4 论文结构安排
第二章 NoC路由基础及关键技术研究
    2.1 NoC路由概述
    2.2 拓扑结构和路由算法
        2.2.1 拓扑结构
        2.2.2 路由算法
    2.3 交换机制和负载模式
        2.3.1 交换机制
        2.3.2 负载模式
    2.4 NoC性能评估
        2.4.1 NoC网络性能
        2.4.2 NoC硬件资源开销
    2.5 本章小结
第三章 传统NoC路由算法的优化分析
    3.1 XY路由算法
    3.2 XY-YX路由算法
    3.3 CXY路由算法
    3.4 OE路由算法
    3.5 仿真性能分析
    3.6 本章总结
第四章 公平仲裁FAR路由算法设计
    4.1 OE路由算法改进
        4.1.1 改进的原因
        4.1.2 改进的方式
    4.2 公平仲裁
        4.2.1 RR（Round-Robin）仲裁
        4.2.2 FP（Fixed-Priority）仲裁
        4.2.3 Lottery仲裁
        4.2.4 公平的AP仲裁
    4.3 FAR路由算法
        4.3.1 FAR路由算法的提出
        4.3.2 在OE模型上的实现
        4.3.3 在XY模型上的实现
    4.4 本章总结
第五章 自适应LAFAR路由算法设计
    5.1 网络拥塞
    5.2 LAFAR路由算法的提出
    5.3 LAFAR路由算法的实现
        5.3.1 在OE模型上的实现
        5.3.2 在XY模型上的实现
    5.4 本章总结
第六章 总结与展望
    6.1 总结
    6.2 展望
参考文献
致谢
作者简介

【参考文献】

相关期刊论文 前7条

1 吴睿振;杨银堂;张丽;周端;;自调整附加权动态仲裁算法[J];计算机辅助设计与图形学学报;2014年09期

2 吴睿振;杨银堂;张丽;陆锋雷;;一种基于权重与轮询的双层仲裁算法[J];电子与信息学报;2013年12期

3 张剑贤;周端;杨银堂;赖睿;高翔;;一种低能耗的片上网络映射算法[J];西安电子科技大学学报;2011年04期

4 欧阳一鸣;董少周;梁华国;;基于2D Mesh的NoC路由算法设计与仿真[J];计算机工程;2009年22期

5 杨晓强;;片上网络关键技术研究[J];微计算机信息;2008年20期

6 张恒龙;顾华玺;王长山;;片上网络拓扑结构的研究[J];中国集成电路;2007年11期

7 高明伦;杜高明;;NoC:下一代集成电路主流设计技术[J];微电子学;2006年04期

相关博士学位论文 前4条

1 周小锋;片上网络高效路由关键技术研究[D];西安电子科技大学;2017年

2 张剑贤;高性能片上网络关键技术研究[D];西安电子科技大学;2012年

3 董文箫;片上网络低功耗设计研究[D];浙江大学;2010年

4 周干民;NoC基础研究[D];合肥工业大学;2005年

相关硕士学位论文 前1条

1 宋平;负载均衡的NoC路由算法研究[D];合肥工业大学;2017年

本文编号：2860260