基于Torus拓扑的自适应片上网络路由算法研究

摘要

随着半导体技术的发展与芯片集成度的提高，传统总线通信架构的片内通信方式已经不能满足众多片上功能模块的通信要求。片上网络将计算机网络通信方式引入到片上通信架构，使用包交换的方式进行片内数据通信，大幅提升了网络的通信带宽与网络可扩展性，受到了广泛的关注。路由算法作为片上网络中数据包转发策略的关键协议，对网络的整体性能具有十分重要的影响。如何设计一个高效且低功耗的路由算法成为了研究的热点。本文主要完成基于Torus结构的路由算法研究，提出了基于距离导向的二维和三维Torus路由算法。
　　本文首先对片上网络的关键技术进行了研究分析，包括拓扑结构、路由算法、路由结构与交换方式等，并对影响路由性能的因素进行了分析。通过开源仿真平台对不同拓扑结构和虚通道数量对片上网络性能的影响进行了仿真分析。根据实验结果选择了Torus网络拓扑作为本文路由算法研究的拓扑结构，同时确定了路由器中合适的虚通道数量划分范围。
　　根据Torus拓扑网络的结构特点，本文提出了基于距离导向的适用于二维Torus拓扑的TD路由算法与应用于三维Torus拓扑的RTTD路由算法。这两种路由算法均以当前节点与目的节点间的距离为导向进行路由决策。同时在网络中当前节点的下一跳备选路由节点与目标节点距离相同时，使用下一跳备选路由节点的拥塞状况进行部分自适应路由。TD与RTTD路由算法中路由节点的每条输入信道均使用6条虚通道来避免死锁的发生。其中RTTD路由算法根据源节点与目的节点间的位置关系引入了概率象限分布，根据三维Torus网络的结构特点，通过产生随机数随机选择数据包的路由方向来实现均衡网络负载的目的。
　　为了验证路由算法的有效性，本文在Nirgam开源仿真平台上进行了路由算法的仿真验证，并改进了平台结构使其支持三维Torus拓扑结构。论文对不同网络规模、均匀流量模式和热点流量模式下的平均延迟和网络功耗进行评估，并与XY、OE、XYZ、DyXYZ路由算法进行对比分析。实验结果表明，TD与RTTD路由算法在热点流量模式下具有较好的网络数据包延迟表现且功耗表现较优。其中TD路由算法对比XY与OE路由算法网络中的数据包延迟时间降低4％以上，同时平均能耗降低8%以上。RTTD路由算法对比XYZ与DyXYZ路由算法网络数据包延迟时间降低2.4%以上，网络平均能耗降低2.5%以上。
　　论文完成了基于二维Torus拓扑与三维Torus拓扑的自适应路由算法的设计与实现，有效的提升了网络在热点模式下的性能表现，降低了网络通信功耗。论文为NoC路由算法的进一步研究与探索提供了一定的参考。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1课题研究背景

1.2片上网络路由算法研究现状

1.3论文主要内容及结构安排

第二章 片上网络基础及关键技术

2.1片上网络拓扑结构

2.2片上网络路由算法

2.3仿真平台

2.4本章小结

第三章 Torus拓扑路由结构研究及性能分析

3.1 Mesh和Torus路由结构研究

3.2网络数据格式设计

3.3虚通道交换技术

3.4影响路由性能因素分析

3.5本章小结

第四章 二维Torus拓扑路由算法

4.1 Torus拓扑结构路由算法设计

4.2 TD自适应路由算法设计

4.3死锁与活锁问题解决

4.4仿真验证与结果分析

4.5本章小结

第五章 三维Torus拓扑负载均衡路由算法

5.1三维Torus路由算法设计

5.2 RTTD自适应路由算法设计

5.3三维Torus拓扑结构与数据格式设计

5.4仿真验证与结果分析

5.5本章小结

第六章 总结与展望

参考文献

致谢

作者简介