基于垂直优先策略的异构3D NoC TSV容错路由算法的研究

摘要

3D NoC(Network on Chip)集3D芯片和片上网络互连方式的优点于一身，具有功耗低、延迟低、集成度高、可扩展性强等诸多优点。在其设计上，由于每一层中器件所占面积和功能的巨大差异，很难做到每一层上的网络节点布局一致，从而导致某些路由节点有TSV同上层或下层相连，而某些节点则没有。同时由于目前TSV制造技术还不够成熟，制造成本高，且极易在制造和使用过程中被损坏。因此，在保证芯片通信的前提下，TSV的数量应该尽可能少。这种每层结构不一致且TSV不完全互连的3D NoC被称为异构3D NoC。本文针对这种异构3D NoC的通信问题及TSV容错问题作出研究。
　　为了解决异构3D NoC中的通信问题、TSV失效问题、垂直方向通道拥塞问题，本文提出了一种依据异构3D NoC中TSV连接状况建立通道表的方法。每个节点中包含一个通道表，它为节点指明一个合适的垂直方向传输通道。对于不具有垂直方向传输通道的普通节点，通道表为该节点指明距离最近的上通道节点和下通道节点;对于自身有垂直方向传输通道的通道节点，通道表为该节点在发生TSV故障或垂直方向通道拥塞情况时指明附近可用的上通道节点和下通道节点。同时针对建立通道表过程中需要分别寻找每一层中上通道节点和下通道节点的最短回路问题，将其抽象成图的Hamilton回路问题，提出了一种基于外围优先策略的贪心算法来求解。实验证明使用本文算法求解的回路长度比使用传统贪心算法算短15％以上。
　　利用本文提出的这种通道表，提出了一种基于垂直优先策略的异构3D NoCTSV容错路由算法。该算法在通信节点本身不具有垂直方向传输通道，或者TSV故障、垂直方向通道出现拥塞的情况下，查找通道表，找到一个距离较近的通道节点来传输数据。实验结果表明本文提出的这种路由算法可以很好处理异构3DNoC中的通信问题，且同其它路由算法比较，本文方法在不过多增加片上路由器面积开销的情况下，具有更好的性能。

目录

声明

致谢

摘要

第一章 绪论

1．1 研究背景

1．1．1 集成电路的发展历程

1．1．2 三维集成电路的出现

1．1．3 三维片上网络(3D NoC，Three-Dimension Network-on-Chip)的出现

1．2 异构3D NoC的研究意义

1．3 国内外研究现状

1．4 本文主要内容概况和论文结构

第二章 3D NoC及其路由算法简介

2．1 3D NoC组成要素

2．1．1 通信节点

2．1．2 资源节点

2．1．3 普通数据链路

2．1．4 TSV

2．2 3D NoC拓扑结构

2．2．1 3D Mesh结构NoC

2．2．2 3D纤毛Mesh结构NoC

2．2．3 3D堆叠Mesh结构NoC

2．2．4 异构3D NoC

2．3 常见的3D NoC路由器结构

2．4 常见的NoC路由算法

2．4．1 X-Y-Z维序路由算法

2．4．2 3D轮转路由算法

2．5 本章小结

第三章 依据异构3D NoC连接状况建立通道表的方法

3．1 问题描述

3．2 使用通道表的方法来解决异构3D NoC通信问题的方案

3．2．1 问题解决思路

3．2．2 问题解决方法

3．3 用于异构3D NoC的通道表建立方法

3．4 寻找最短环形路由的方法

3．4．1 通道节点的抽象化表示

3．4．2 抽象成Hamilton回路问题

3．4．3 使用贪心算法来寻找最短Hamilton回路的近似解

3．5 使用基于外围优先策略的贪心算法求解最短回路问题

3．5．1 基于外围优先策略的贪心算法

3．5．2 实验比较

3．6 本章小结

第四章 基于垂直优先策略的异构3D NoC TSV容错路由算法

4．1 TSV故障测试方法

4．2 用于异构3D NoC的TSV容错路由算法

4．2．1 采用轮转路由算法的层内通信策略

4．2．2 采用通道表的层间通信策略

4．2．3 路由算法

4．2．4 数据包格式

4．2．5 算法应用举例

4．3 实验评估

4．3．1 延迟

4．3．2 吞吐率

4．3．3 面积开销

4．4 本章小结

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

攻读硕士学位期间的学术活动及成果情况