發(fā)布時(shí)間：2018-01-09 17:59

  本文關(guān)鍵詞：基于哈密頓路徑的片上網(wǎng)絡(luò)容錯(cuò)算法　出處：《西安電子科技大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 三維片上網(wǎng)絡(luò) 容錯(cuò)路由算法 死鎖 哈密頓路徑

【摘要】：隨著市場(chǎng)對(duì)集成電路的需求量和性能要求的不斷提高,片上多核系統(tǒng)(MultiProcessor Systems-on-Chip,MPSoCs)被越來(lái)越多的使用在高性能、高速度、低功耗的集成電路產(chǎn)品中。隨著片上處理單元數(shù)量的增加,傳統(tǒng)的單總線模式由于自身較差的擴(kuò)展性和帶寬受限等原因,越來(lái)越不能滿足系統(tǒng)上多核之間通信的要求,而片上網(wǎng)絡(luò)(Network on Chip,NoC)作為一種片上多核系統(tǒng)新的互聯(lián)范式,能夠?qū)⑼ㄐ畔到y(tǒng)從計(jì)算系統(tǒng)中剝離出來(lái),有效地提高片上系統(tǒng)(System on Chip,SoC)的性能。在片上網(wǎng)絡(luò)的通信過(guò)程中,路由器或鏈路通道中存在一定的故障發(fā)生率,這些故障引發(fā)的錯(cuò)誤會(huì)降低片上網(wǎng)絡(luò)的可靠性,甚至導(dǎo)致整個(gè)片上網(wǎng)絡(luò)系統(tǒng)失效,因此片上網(wǎng)絡(luò)中容錯(cuò)策略的設(shè)計(jì)尤為重要。基于這樣的背景,本文在網(wǎng)格(mesh)拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上,結(jié)合哈密頓路徑和HOE(Hamiltonian-based Odd-Even)轉(zhuǎn)彎模型,在二維和三維片上網(wǎng)絡(luò)中,分別提出了無(wú)死鎖的可容錯(cuò)路由算法,論文的主要工作如下:1、基于傳統(tǒng)的哈密頓路徑,在二維mesh結(jié)構(gòu)上設(shè)計(jì)了一種不需要虛通道和額外信息的無(wú)死鎖可容錯(cuò)路由算法HoeFA(Hamiltonian-based odd-even Fault-tolerant Algorithm),該方法保證數(shù)據(jù)包檢測(cè)到故障之后,在每一個(gè)節(jié)點(diǎn)都存在逃逸方向和路徑,結(jié)合HOE轉(zhuǎn)彎模型,探索在一些情況下的最短路由路徑,提升容錯(cuò)路由時(shí)最短路徑的使用率,并且充分利用此轉(zhuǎn)彎模型增加的轉(zhuǎn)彎,實(shí)現(xiàn)路由算法的部分自適應(yīng)性,改善網(wǎng)絡(luò)中交通量的均勻程度,相比于傳統(tǒng)哈密頓容錯(cuò)算法,該算法對(duì)于吞吐量以及數(shù)據(jù)包的到達(dá)數(shù)都有2%到6%的提升率,并且能降低網(wǎng)絡(luò)的平均延遲和最大延遲。2、在二維容錯(cuò)算法設(shè)計(jì)的基礎(chǔ)上,考慮涉及縱向路由的容錯(cuò)策略,并在不同的奇偶平面上分別采用基于不同轉(zhuǎn)彎模型的容錯(cuò)方法,從而獲得在三維片上網(wǎng)絡(luò)中的算法設(shè)計(jì),與二維實(shí)驗(yàn)結(jié)果相似,該算法對(duì)三維網(wǎng)絡(luò)中的吞吐量,延遲和數(shù)據(jù)包到達(dá)數(shù)均有提高。3、結(jié)合硬件冗余的方法,修改mesh結(jié)構(gòu)邊沿的通路設(shè)計(jì),在網(wǎng)絡(luò)邊沿增加相應(yīng)的冗余通路,通過(guò)冗余通路提供某些邊沿故障發(fā)生時(shí)的備選通路,從而避免死鎖情況的發(fā)生。冗余通路的開(kāi)銷小,結(jié)合容錯(cuò)算法設(shè)計(jì),能夠保證網(wǎng)絡(luò)的全局無(wú)死鎖和對(duì)各類故障的支持。
[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.
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TN47

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 楊敏華;谷建華;周興社;;片上網(wǎng)絡(luò)[J];微處理機(jī);2006年05期

2 鞠宏浩;顧華璽;尹小杰;;片上網(wǎng)絡(luò)中服務(wù)質(zhì)量的研究[J];計(jì)算機(jī)與現(xiàn)代化;2009年04期

3 劉炎華;劉靜;賴宗聲;;片上網(wǎng)絡(luò):新一代的片上系統(tǒng)結(jié)構(gòu)[J];電子與封裝;2011年05期

4 唐名華;;兩種綜合流量模式對(duì)片上網(wǎng)絡(luò)性能影響分析[J];廣東石油化工學(xué)院學(xué)報(bào);2011年04期

5 韋良芬;王勇;;片上網(wǎng)絡(luò)系統(tǒng)設(shè)計(jì)分析[J];吉首大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年03期

6 王宏偉;陸俊林;佟冬;程旭;;層次化片上網(wǎng)絡(luò)結(jié)構(gòu)的簇生成算法[J];電子學(xué)報(bào);2007年05期

7 付方發(fā);張慶利;王進(jìn)祥;喻明艷;孫玉峰;;支持多種流量分布的片上網(wǎng)絡(luò)性能評(píng)估技術(shù)研究[J];哈爾濱工業(yè)大學(xué)學(xué)報(bào);2007年05期

8 王宏偉;陸俊林;佟冬;程旭;;層次化的片上網(wǎng)絡(luò)設(shè)計(jì)方法[J];北京大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年05期

9 丁永文;劉建輝;;片上網(wǎng)絡(luò)體系結(jié)構(gòu)設(shè)計(jì)分析[J];科技信息(學(xué)術(shù)研究);2007年31期

10 周干民;;片上網(wǎng)絡(luò):下一代技術(shù)[J];商業(yè)文化(學(xué)術(shù)版);2007年06期

相關(guān)會(huì)議論文 前10條

1 白原;鄭焱;王紅;楊士元;;不規(guī)則結(jié)構(gòu)片上網(wǎng)絡(luò)的測(cè)試方法研究[A];第六屆中國(guó)測(cè)試學(xué)術(shù)會(huì)議論文集[C];2010年

2 王祺;吳寧;葛芬;;片上網(wǎng)絡(luò)仿真與性能評(píng)估[A];全國(guó)第19屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];2008年

3 景乃鋒;毛志剛;;面向片上網(wǎng)絡(luò)的集成電路設(shè)計(jì)技術(shù)[A];第十屆中國(guó)科協(xié)年會(huì)信息化與社會(huì)發(fā)展學(xué)術(shù)討論會(huì)分會(huì)場(chǎng)論文集[C];2008年

4 付斌章;韓銀和;李華偉;李曉維;;面向高可靠片上網(wǎng)絡(luò)通信的低成本可重構(gòu)路由算法[A];第六屆中國(guó)測(cè)試學(xué)術(shù)會(huì)議論文集[C];2010年

5 齊樹(shù)波;蔣江;李晉文;張民選;;面向片上網(wǎng)絡(luò)的多播吞吐率和能量模型[A];第十五屆計(jì)算機(jī)工程與工藝年會(huì)暨第一屆微處理器技術(shù)論壇論文集（B輯）[C];2011年

6 張熙敏;李晉文;肖立權(quán);;基于逃逸通道的片上網(wǎng)絡(luò)擁塞緩解技術(shù)[A];第十六屆計(jì)算機(jī)工程與工藝年會(huì)暨第二屆微處理器技術(shù)論壇論文集[C];2012年

7 歐陽(yáng)一鳴;朱兵;梁華國(guó);;一種用于片上網(wǎng)絡(luò)的自適應(yīng)路由算法[A];全國(guó)第19屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];2008年

8 蘇琦;李玉柏;王堅(jiān);;用OPNET實(shí)現(xiàn)片上網(wǎng)絡(luò)仿真[A];2008年中國(guó)西部青年通信學(xué)術(shù)會(huì)議論文集[C];2008年

9 歐陽(yáng)一鳴;劉蓓;齊蕓;;三維片上網(wǎng)絡(luò)測(cè)試的時(shí)間優(yōu)化方法[A];第六屆中國(guó)測(cè)試學(xué)術(shù)會(huì)議論文集[C];2010年

10 彭�；�;尤志強(qiáng);鄺繼順;張大方;;一種基于BFT型拓?fù)浣Y(jié)構(gòu)片上網(wǎng)絡(luò)低費(fèi)用測(cè)試方法[A];第六屆中國(guó)測(cè)試學(xué)術(shù)會(huì)議論文集[C];2010年

相關(guān)重要報(bào)紙文章 前1條

1 清華大學(xué)微處理器與SOC 技術(shù)研究中心 陳磊 王驚雷 李兆麟 汪東升;片上網(wǎng)絡(luò)：解決CMP互連瓶頸[N];計(jì)算機(jī)世界;2005年

相關(guān)博士學(xué)位論文 前10條

1 王堅(jiān);片上網(wǎng)絡(luò)通信性能分析與優(yōu)化[D];電子科技大學(xué);2011年

2 樂(lè)千榿;基于智能算法的片上網(wǎng)絡(luò)布局優(yōu)化研究[D];電子科技大學(xué);2014年

3 秦明偉;片上網(wǎng)絡(luò)（NoC）業(yè)務(wù)量建模方法及應(yīng)用研究[D];電子科技大學(xué);2015年

4 周芳;片上網(wǎng)絡(luò)低功耗設(shè)計(jì)方法研究[D];南京航空航天大學(xué);2015年

5 楊鵬飛;高可靠片上網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[D];西安電子科技大學(xué);2015年

6 王俊輝;高性能多核處理器的低功耗片上網(wǎng)絡(luò)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2015年

7 李寶亮;片上網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)與性能分析關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2015年

8 馬立偉;專用片上網(wǎng)絡(luò)設(shè)計(jì)方法：通信建模、拓?fù)錁?gòu)造與自動(dòng)生成[D];清華大學(xué);2006年

9 趙建武;片上網(wǎng)絡(luò)系統(tǒng)可測(cè)試性設(shè)計(jì)及測(cè)試技術(shù)研究[D];電子科技大學(xué);2009年

10 王煒;面向大規(guī)模片上多處理器的片上網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[D];清華大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 王曉袁;片上網(wǎng)絡(luò)系統(tǒng)模型[D];西安電子科技大學(xué);2008年

2 付方發(fā);片上網(wǎng)絡(luò)性能評(píng)估平臺(tái)設(shè)計(jì)[D];哈爾濱工業(yè)大學(xué);2007年

3 王祺;基于應(yīng)用的片上網(wǎng)絡(luò)設(shè)計(jì)與性能評(píng)估[D];南京航空航天大學(xué);2009年

4 劉華;片上網(wǎng)絡(luò)多播通信關(guān)鍵技術(shù)研究[D];武漢理工大學(xué);2011年

5 李慧;光片上網(wǎng)絡(luò)的可靠性研究[D];西安電子科技大學(xué);2013年

6 易恒柱;面向神經(jīng)元?jiǎng)幼麟娢环诸惖钠舷到y(tǒng)任務(wù)映射的研究[D];哈爾濱工業(yè)大學(xué);2015年

7 李盛楠;基于Spike sorting的NoC-based CMP的研究與實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2015年

8 蔣珊珊;片上網(wǎng)絡(luò)感知故障容錯(cuò)路由算法研究[D];電子科技大學(xué);2015年

9 劉躍;2D Mesh片上網(wǎng)絡(luò)容錯(cuò)路由算法設(shè)計(jì)與研究[D];電子科技大學(xué);2014年

10 俞劍明;容偏差百核片上網(wǎng)絡(luò)設(shè)計(jì)與多核粒度建模[D];復(fù)旦大學(xué);2014年

，

本文編號(hào)：1402058