基于哈密顿路径的片上网络容错算法

发布时间：2018-01-09 17:59

本文关键词：基于哈密顿路径的片上网络容错算法　出处：《西安电子科技大学》2015年硕士论文　论文类型：学位论文

【摘要】：随着市场对集成电路的需求量和性能要求的不断提高,片上多核系统(MultiProcessor Systems-on-Chip,MPSoCs)被越来越多的使用在高性能、高速度、低功耗的集成电路产品中。随着片上处理单元数量的增加,传统的单总线模式由于自身较差的扩展性和带宽受限等原因,越来越不能满足系统上多核之间通信的要求,而片上网络(Network on Chip,NoC)作为一种片上多核系统新的互联范式,能够将通信系统从计算系统中剥离出来,有效地提高片上系统(System on Chip,SoC)的性能。在片上网络的通信过程中,路由器或链路通道中存在一定的故障发生率,这些故障引发的错误会降低片上网络的可靠性,甚至导致整个片上网络系统失效,因此片上网络中容错策略的设计尤为重要。基于这样的背景,本文在网格(mesh)拓扑结构的基础上,结合哈密顿路径和HOE(Hamiltonian-based Odd-Even)转弯模型,在二维和三维片上网络中,分别提出了无死锁的可容错路由算法,论文的主要工作如下:1、基于传统的哈密顿路径,在二维mesh结构上设计了一种不需要虚通道和额外信息的无死锁可容错路由算法HoeFA(Hamiltonian-based odd-even Fault-tolerant Algorithm),该方法保证数据包检测到故障之后,在每一个节点都存在逃逸方向和路径,结合HOE转弯模型,探索在一些情况下的最短路由路径,提升容错路由时最短路径的使用率,并且充分利用此转弯模型增加的转弯,实现路由算法的部分自适应性,改善网络中交通量的均匀程度,相比于传统哈密顿容错算法,该算法对于吞吐量以及数据包的到达数都有2%到6%的提升率,并且能降低网络的平均延迟和最大延迟。2、在二维容错算法设计的基础上,考虑涉及纵向路由的容错策略,并在不同的奇偶平面上分别采用基于不同转弯模型的容错方法,从而获得在三维片上网络中的算法设计,与二维实验结果相似,该算法对三维网络中的吞吐量,延迟和数据包到达数均有提高。3、结合硬件冗余的方法,修改mesh结构边沿的通路设计,在网络边沿增加相应的冗余通路,通过冗余通路提供某些边沿故障发生时的备选通路,从而避免死锁情况的发生。冗余通路的开销小,结合容错算法设计,能够保证网络的全局无死锁和对各类故障的支持。
[Abstract]:With the increasing demand and performance of integrated circuits in the market, the multi-core system on chip is called MultiProcessor Systems-on-Chip. MPSoCsare used more and more in high performance, high speed, low power IC products. As the number of on-chip processing units increases. Because of its poor expansibility and limited bandwidth, the traditional single-bus mode can not meet the requirements of multi-core communication on the system, and the on-chip network network on Chip. As a new interconnection paradigm of on-chip multi-core systems, NOC) can separate communication systems from computing systems and effectively improve the on-chip system on Chip. The performance of SoC. In the communication process of on-chip network, there is a certain incidence of faults in the router or link channel, which will reduce the reliability of the on-chip network. Even leads to the failure of the entire on-chip network system, because the design of fault-tolerant strategy in the on-chip network is particularly important. Based on this background, this paper is based on the grid mesh topology. Combined with Hamiltonian path and HOE(Hamiltonian-based Odd-Even) turning model, in two-dimensional and three-dimensional on-chip networks. The main work of this paper is as follows: 1, based on the traditional Hamiltonian path. A novel deadlock-free fault-tolerant routing algorithm, HoeFA (), is designed for two-dimensional mesh architecture without virtual channels and additional information. Hamiltonian-based odd-even Fault-tolerant algorithm. This method ensures that there is escape direction and path at each node after the packet detects the fault. Combined with the HOE turning model, the shortest routing path in some cases is explored. Improve the utilization rate of the shortest path in fault-tolerant routing, and make full use of the turn added by this turning model, realize partial adaptation of routing algorithm, and improve the uniformity of traffic volume in the network. Compared with the traditional Hamiltonian fault-tolerant algorithm, the algorithm has a lifting rate of 2% to 6% for throughput and the number of packet arrivals, and can reduce the average delay and maximum delay of the network. 2. Based on the design of two-dimensional fault-tolerant algorithm, fault-tolerant strategies involving longitudinal routing are considered, and fault tolerant methods based on different turning models are adopted in different parity planes. Thus the algorithm design in 3D on-chip network is obtained, which is similar to the two-dimensional experimental results. The algorithm can improve the throughput, delay and arrival number of packets in 3D network by using the method of hardware redundancy. Modify the path design of the mesh structure edge, add the corresponding redundant path in the network edge, and provide some alternative paths in the event of edge failure through the redundant path. In order to avoid the deadlock, the redundant path is less expensive, combined with the fault-tolerant algorithm, it can guarantee the global deadlock-free network and the support for all kinds of faults.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN47

【相似文献】