基于不同粒度故障模型的NoC容錯(cuò)路由算法研究
發(fā)布時(shí)間：2018-10-16 14:36
【摘要】：容錯(cuò)技術(shù)是片上網(wǎng)絡(luò)(Network on Chip，NoC)提供可靠性數(shù)據(jù)通信的關(guān)鍵技術(shù)之一，是影響網(wǎng)絡(luò)吞吐量和延遲性能的重要因素。容錯(cuò)路由算法是NoC容錯(cuò)技術(shù)中容忍永久性故障的主要方法。研究容錯(cuò)路由算法必須基于一定的故障模型，2D Mesh NoC容錯(cuò)路由算法采用的故障模型按照故障粒度的大小可以分為區(qū)域故障模型、單故障模型和細(xì)粒度故障模型。然而，當(dāng)前針對(duì)不同粒度故障模型NoC容錯(cuò)路由算法的研究還存在一些不足，主要體現(xiàn)在以下三個(gè)方面：（1）單故障模型容錯(cuò)路由算法采用“一步一比較”的數(shù)據(jù)傳輸方式，導(dǎo)致整個(gè)網(wǎng)絡(luò)的平均延遲較高；（2）現(xiàn)有細(xì)粒度故障模型處理鏈路故障的方式過于粗獷，使得節(jié)點(diǎn)內(nèi)的很多有效資源無法得到充分的利用；（3）細(xì)粒度故障模型容錯(cuò)路由算法采用傳統(tǒng)的“避繞容錯(cuò)”方式處理通道故障，導(dǎo)致數(shù)據(jù)的路由路徑過長，整個(gè)NoC的網(wǎng)絡(luò)性能較低。 本文針對(duì)現(xiàn)有不同粒度故障模型中容錯(cuò)路由算法存在的不足，結(jié)合NoC與傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)的不同特性，研究了2D Mesh NoC單故障模型和細(xì)粒度故障模型中的自適應(yīng)容錯(cuò)路由技術(shù)。論文的主要研究工作如下： 1、提出了一種基于單故障模型的低延遲自適應(yīng)NoC容錯(cuò)路由算法。算法摒棄傳統(tǒng)基于單故障模型容錯(cuò)路由算法“一步一比較”的傳輸方式，結(jié)合2D Mesh結(jié)構(gòu)的特點(diǎn)，采用“跳步比較”的方式來傳輸數(shù)據(jù)包，同時(shí)算法使用一種易于采用簡單邏輯電路實(shí)現(xiàn)的模糊優(yōu)先級(jí)策略來保證自適應(yīng)性。實(shí)驗(yàn)結(jié)果表明，該算法是一種適用于大規(guī)模NoC的低延遲容錯(cuò)路由算法；ISE綜合結(jié)果顯示，實(shí)現(xiàn)該算法的硬件成本較低。 2、建立了一種基于細(xì)粒度故障模型改進(jìn)的微粒度故障模型。針對(duì)當(dāng)前細(xì)粒度故障模型將鏈路故障等效處理所帶來的有效資源浪費(fèi)問題，微粒度故障模型在記錄的故障類型中增加鏈路故障，以便能有效區(qū)分模型中的鏈路故障和通道故障；模型在描述的故障類型中增加緩存故障，使得再利用NoC中被丟棄的緩存資源成為可能。本文以可用資源率作為性能指標(biāo)對(duì)比了微粒度故障模型和兩種常用的細(xì)粒度故障模型，并分析了基于三種故障模型的系統(tǒng)級(jí)硬件開銷情況，結(jié)果顯示，微粒度故障模型是一種“性價(jià)比”較高的故障模型。 3、提出了一種基于緩存再利用的微粒度故障模型NoC容錯(cuò)路由算法。算法在本文建立的微粒度故障模型的基礎(chǔ)上，，采用“通道替代容錯(cuò)”來代替?zhèn)鹘y(tǒng)的“通道避繞容錯(cuò)”；“通道替代容錯(cuò)”使用節(jié)點(diǎn)內(nèi)因?yàn)殒溌饭收隙粊G棄的正常通道來替代故障通道，提高了NoC緩存資源利用率和采用最優(yōu)端口輸出數(shù)據(jù)包的概率，增加了整個(gè)NoC用于“正常通信”的路由路徑的數(shù)量，從而有效提升了NoC的網(wǎng)絡(luò)性能。實(shí)驗(yàn)和ISE綜合結(jié)果表明，該算法是一種適用于高故障率NoC，具有高可靠性和高性價(jià)比特點(diǎn)的容錯(cuò)路由算法。
[Abstract]:Fault-tolerant technology is one of the key technologies to provide reliable data communication for on-chip network (Network on Chip,NoC). It is an important factor affecting network throughput and delay performance. Fault-tolerant routing algorithm is the main method to tolerate permanent fault in NoC fault-tolerant technology. The fault-tolerant routing algorithm must be based on a certain fault model. The fault model used in 2D Mesh NoC fault-tolerant routing algorithm can be divided into regional fault model, single-fault model and fine-grained fault model according to the size of fault granularity. However, there are still some shortcomings in the research of fault-tolerant routing algorithm for different granularity fault models NoC, which are mainly reflected in the following three aspects: (1) the single-fault model fault-tolerant routing algorithm adopts the "one-step, one-comparison" data transmission mode. As a result, the average delay of the whole network is high; (2) the existing fine-grained fault model is too rough to deal with link failures, which makes many effective resources in the nodes unable to be fully utilized; (3) the fault-tolerant routing algorithm of fine-grained fault model adopts the traditional method of "avoiding fault tolerance" to deal with the channel fault, which leads to the long route path of the data and the low performance of the whole NoC network. In this paper, the adaptive fault-tolerant routing techniques in 2D Mesh NoC single fault models and fine-grained fault models are studied according to the shortcomings of existing fault-tolerant routing algorithms in different granularity fault models and combined with the different characteristics of NoC and traditional computer networks. The main work of this paper is as follows: 1. A low delay adaptive NoC fault-tolerant routing algorithm based on single fault model is proposed. The algorithm abandons the traditional fault-tolerant routing algorithm based on single fault model "one step, one comparison" transmission mode, combines the characteristic of 2D Mesh structure, and adopts the method of "step comparison" to transmit data packet. At the same time, the algorithm uses a fuzzy priority strategy, which is easy to be implemented by simple logic circuits, to ensure self-adaptability. Experimental results show that the algorithm is a low delay fault-tolerant routing algorithm for large-scale NoC, and the ISE synthesis results show that, The hardware cost of the algorithm is low. 2. An improved micro-granularity fault model based on fine-grained fault model is established. Aiming at the problem of waste of effective resources caused by the current fine-grained fault model equivalent treatment of link fault, the particle size fault model adds link fault to the recorded fault type in order to effectively distinguish link fault and channel fault in the model. The model adds cache faults to the types of faults described, which makes it possible to reuse the discarded cache resources in NoC. In this paper, the available resource rate is used as the performance index to compare the particle size fault model with the two commonly used fine-grained fault models, and the hardware overhead of the system level based on the three fault models is analyzed. The results show that, Particle size fault model is a high performance-price ratio fault model. 3. A fault tolerant routing algorithm based on cache reuse for microgranular fault model (NoC) is proposed. On the basis of the micro-granularity fault model established in this paper, the algorithm uses "channel instead of fault tolerance" to replace the traditional "channel fault tolerance". "Channel substitution fault tolerance" uses the normal channel discarded in the node due to link failure to replace the fault channel, which improves the utilization of NoC cache resources and the probability of using the optimal port to output data packets. The number of routing paths for "normal communication" of the whole NoC is increased, which effectively improves the network performance of NoC. Experimental results and ISE synthesis results show that the proposed algorithm is a fault-tolerant routing algorithm with high reliability and high performance-to-price ratio for NoC, with high failure rate.
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TN47;TN915.02;TP302.8
本文編號(hào)：2274671
[Abstract]:Fault-tolerant technology is one of the key technologies to provide reliable data communication for on-chip network (Network on Chip,NoC). It is an important factor affecting network throughput and delay performance. Fault-tolerant routing algorithm is the main method to tolerate permanent fault in NoC fault-tolerant technology. The fault-tolerant routing algorithm must be based on a certain fault model. The fault model used in 2D Mesh NoC fault-tolerant routing algorithm can be divided into regional fault model, single-fault model and fine-grained fault model according to the size of fault granularity. However, there are still some shortcomings in the research of fault-tolerant routing algorithm for different granularity fault models NoC, which are mainly reflected in the following three aspects: (1) the single-fault model fault-tolerant routing algorithm adopts the "one-step, one-comparison" data transmission mode. As a result, the average delay of the whole network is high; (2) the existing fine-grained fault model is too rough to deal with link failures, which makes many effective resources in the nodes unable to be fully utilized; (3) the fault-tolerant routing algorithm of fine-grained fault model adopts the traditional method of "avoiding fault tolerance" to deal with the channel fault, which leads to the long route path of the data and the low performance of the whole NoC network. In this paper, the adaptive fault-tolerant routing techniques in 2D Mesh NoC single fault models and fine-grained fault models are studied according to the shortcomings of existing fault-tolerant routing algorithms in different granularity fault models and combined with the different characteristics of NoC and traditional computer networks. The main work of this paper is as follows: 1. A low delay adaptive NoC fault-tolerant routing algorithm based on single fault model is proposed. The algorithm abandons the traditional fault-tolerant routing algorithm based on single fault model "one step, one comparison" transmission mode, combines the characteristic of 2D Mesh structure, and adopts the method of "step comparison" to transmit data packet. At the same time, the algorithm uses a fuzzy priority strategy, which is easy to be implemented by simple logic circuits, to ensure self-adaptability. Experimental results show that the algorithm is a low delay fault-tolerant routing algorithm for large-scale NoC, and the ISE synthesis results show that, The hardware cost of the algorithm is low. 2. An improved micro-granularity fault model based on fine-grained fault model is established. Aiming at the problem of waste of effective resources caused by the current fine-grained fault model equivalent treatment of link fault, the particle size fault model adds link fault to the recorded fault type in order to effectively distinguish link fault and channel fault in the model. The model adds cache faults to the types of faults described, which makes it possible to reuse the discarded cache resources in NoC. In this paper, the available resource rate is used as the performance index to compare the particle size fault model with the two commonly used fine-grained fault models, and the hardware overhead of the system level based on the three fault models is analyzed. The results show that, Particle size fault model is a high performance-price ratio fault model. 3. A fault tolerant routing algorithm based on cache reuse for microgranular fault model (NoC) is proposed. On the basis of the micro-granularity fault model established in this paper, the algorithm uses "channel instead of fault tolerance" to replace the traditional "channel fault tolerance". "Channel substitution fault tolerance" uses the normal channel discarded in the node due to link failure to replace the fault channel, which improves the utilization of NoC cache resources and the probability of using the optimal port to output data packets. The number of routing paths for "normal communication" of the whole NoC is increased, which effectively improves the network performance of NoC. Experimental results and ISE synthesis results show that the proposed algorithm is a fault-tolerant routing algorithm with high reliability and high performance-to-price ratio for NoC, with high failure rate.
【學(xué)位授予單位】：解放軍信息工程大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TN47;TN915.02;TP302.8
【參考文獻(xiàn)】
相關(guān)期刊論文 前1條
1 張磊;李華偉;李曉維;;用于片上網(wǎng)絡(luò)的容錯(cuò)通信算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2007年04期
本文編號(hào)：2274671
本文鏈接：http://sikaile.net/kejilunwen/jisuanjikexuelunwen/2274671.html
最近更新
教材專著
