片上网络容错路由算法的研究与实现

《片上网络容错路由算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文片上网络容错路由算法的研究与实现RESEARCHANDIMPLEMENTATIONOFFAULTTOLERANTROUTINGALGORITHMFORNETWORKONCHIP郭志海哈尔滨工业大学2014年6月万方数据国内图书分类号：TP393.02学校代码：10213 国际图书分类号：681.34密级：公开工学硕士学位论文片上网络容错路由算法的研究与实现硕士究生：郭志海导师：王玲教授申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2014年6月授予学位单位：哈尔滨工业大学万方数据ClassifiedIndex:TP393.02U.D.

2、C:681.34DissertationfortheMasterDegreeinEngineeringRESEARCHANDIMPLEMENTATIONOFFAULTTOLERANTROUTINGALGORITHMFORNETWORKONCHIPCandidate：GuoZhihaiSupervisor：Prof.WangLingAcademicDegreeAppliedfor：MasterofEngineeringSpecialty：ComputerScience&Technology Affiliation：ComputerScience&Technology DateofD

3、efence：June,2014Degree-Conferring-Institution：HarbinInstituteofTechnology万方数据摘要摘要片上网络（NoC）是解决多处理器系统上通信问题的一个新的设计方法。在片上网络中，两个处理单元之间通过发送数据包来通信。这样的通信方式就解决了在片上系统（SoC）中面临的全局时钟很难同步和长延时的问题。另外，片上网络中的两个结点之间存在多条路径，这些冗余的路径可以提高通信的带宽，并支持并发通信。然而，当前的超大规模集成电路技术已经可以在单个片上网络芯片上集成成百上千个处理核。这样的大型的多核系统是很容易受到故障的影响的，因

4、此在片上网络上引入容错技术是十分必要的。在容错技术中，容错路由技术是一个很常见并且很重要的一个技术。在容错路由算法中一种常见的方法就是把故障结点包含在若干个矩形或多边形的故障区域中。在路由的过程中，如果数据包遇到了一个这样的故障区域，路由算法就会把数据包绕着故障区域的边界路由，从而避开故障区域。为了形成这样的故障区域，一些没有故障的结点会被牺牲掉。正是这些被牺牲掉的结点和故障结点的集合组成了网络中的故障区域。这些被牺牲掉的结点既不能发送有不能接收数据包，就等同于一个故障结点。然而在这些故障区域中很可能存在由这些被牺牲掉的结点组成的贯穿整个故障区域的通路，这些通路可以被用来正常的来

5、路由数据包。然而，所有的使用故障区域的算法都把这些存在于故障区域中的通路给忽略掉了。为了解决这个问题，本文提出了一个可以利用在故障区域中由被牺牲掉的结 点组成的通路来路由数据包的算法。使用这个算法的数据包可以不用绕着故障区 域路由，而是直接的穿过故障区域，这样它的传输路径就缩短了。这可以直接的 减小网络的总的通信延时。另外，在本文的算法中，对故障区域中通路的使用是 有条件的。只有在满足条件的前提下，一个数据包才可以使用这些通路。这样， 一些转弯就可以被禁止掉，死锁也就不会发生了。本文的算法可以在不使用虚通 道的条件下避免死锁的发生。然后，我们使用一个基于SystemC的周期精确的

6、片上网络仿真平台来评价 本文提出的算法。我们精心的设计了这个仿真平台，使得仿真平台的参数很容易 配置。这些参数包括网络规模，路由算法，注入率，还有仿真的轮数。我们在不 同的故障模式和不同的注入率下对我们的算法进行了仿真。仿真结果显示，和传 统的使用故障区域的容错路由算法相比，我们的算法可以大大的降低网络平均延 时，并可以很显著提高网络的吞吐率。关键词：容错；路由算法；故障区域；网格结构；片上网络；死锁-I-万方数据哈尔滨工业大学工学硕士学位论文AbstractNetworkonchip(NoC)isanewparadigmtosolvethecommunicationproble

7、mofmultiprocessorsystems.InNoC,twodifferentprocesselementscommunicatewitheachotherbysendingpackets,thussomeproblemsthatSoCarefacingsuchasglobalsynchronizationandlongtimedelaycanbesolved.Furthermore,betweentwonodesonanetwork,therearemaybemanya