基于3D Mesh的NoC容错路由算法的研究与实现.pdf

《基于3D Mesh的NoC容错路由算法的研究与实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于3DMesh的NoC容错路由算法的研究与实现RESEARCHANDIMPLEMENTATIONOFFAULTTOLERANTROUTINGALGORITHMFORNOCBASEDON3DMESH李新涛哈尔滨工业大学2018年6月国内图书分类号：TP393.02学校代码：10213国际图书分类号：681.34密级：公开工学硕士学位论文基于3DMesh的NoC容错路由算法的研究与实现硕士研究生：李新涛导师：王玲教授申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：20

2、18年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP393.02U.D.C:681.34DissertationfortheMasterDegreeinEngineeringRESEARCHANDIMPLEMENTATIONOFFAULTTOLERANTROUTINGALGORITHMFORNOCBASEDON3DMESHCandidate：LiXintaoSupervisor：Prof.WangLingAcademicDegreeAppliedfor：MasterofEngineeri

3、ngSpeciality：ComputerScienceandTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：June,2018Degree-Conferring-Institution：HarbinInstituteofTechnology摘要摘要目前，在3DNoC容错路由算法中，有一类算法就是把网络中故障结点包围在若干个不相交的长方体故障区域内。在路由数据包时，若是一个数据包碰到了这样的长方体故障区域，这类算法

4、就将把数据包围绕着长方体故障区域的边缘进行路由，从而避开长方体故障区域。因为在构成这样的长方体故障区域时，会牺牲掉一部分本身无故障的结点，所有故障结点和那些牺牲掉的无故障结点的集合组成了网络中的长方体故障区域。那些被牺牲掉的无故障结点在路由时就等同一个故障点，不可以接收数据包也不可以转发数据包。然而这种长发体故障区域的划分有两个弊端：一是它不能利用故障区中的非故障节点，因为故障区内的非故障结点也可能形成一条路由通道；二是这种长方体故障区域的形成是以大量非故障结点的牺牲为代价的。为了解决上述的两个现存问题，本文

5、经研究提出了一个在3DNoC中仅需要牺牲较少部分无故障结点建立故障区并可以利用所建故障区域中由那些被牺牲的无故障结点组成的通道来进行数据包转发的路由算法。该算法首先将传统3DNoC长方体故障区分解到若干个二维平面中，每个平面中的二维故障区域由故障结点和设为不活动的完好结点构成，在利用我们的容错算法的片上网络中，注到网络中的数据包不再围绕长方体故障区域边缘进行转发路由，也不用围绕二维平面中的矩形故障区路由，而是在满足一定条件后可以直接穿过这种故障区内，从而缩短数据包路由路径长度，直接减小网络的总的通信时延。这种

6、一定条件下才能使用穿过故障区通路的限制是为了防止死锁的发生，即需要防止一些转弯的出现，因此本文算法不需要利用虚通道就可避免死锁产生。最后，我们修改并使用了3DNoC仿真软件AccessNoxim来验证并评价本文提出的容错路由算法。我们通过修改相应参数来设置3DNoC的网络规模，数据包注入率以及实验轮数等，分别在均匀流量模式和热点流量模式下用渐渐增大的分组注人速率对本文提出的容错算法做了多次模拟仿真并根据数据作了性能评估。和现有的使用长方体故障区域的容错路由算法相比，实验结果显示，本文算法可以很大程度的降低网络

7、平均时延，并且显著提高网络的吞吐率，和-I-摘要路由算法HamFA相比，我们的算法也可以显著降低网络时延并且有更高的可靠性。关键词：容错；路由算法；三维网格；片上网络；故障区域-II-AbstractAbstractAtpresent,Inthe3DNoCfault-tolerantroutingalgorithms,thereisaclassofalgorithmsthatencirclingthefaultnodesinthenetworkinanumberofdisjointcuboidfaultare

8、as.Whenroutingdatapackets,ifapacketmeetssuchacuboidfaultzone,thiskindofalgorithmwillroutethedatapackagearoundtheedgeofthecuboidfaultzoneandthusavoidthecuboidfaultareas.Becauseintheformofsuchacuboidfaul