面向NoC的無(wú)死鎖路由算法的研究.pdf

1、隨著計(jì)算機(jī)技術(shù)的發(fā)展，很多研究領(lǐng)域不斷地交叉和融合。在微電子技術(shù)領(lǐng)域，一些研究者提出使用并行計(jì)算機(jī)互連網(wǎng)絡(luò)技術(shù)解決單一芯片上多個(gè)內(nèi)核的集成問(wèn)題，這一技術(shù)稱為片上網(wǎng)絡(luò)(NoC)技術(shù)。NoC是片上系統(tǒng)(SoC)的通訊子系統(tǒng)，它利用互連網(wǎng)絡(luò)解決單一芯片上的多個(gè)內(nèi)核之間的通訊問(wèn)題，這提高了單一芯片系統(tǒng)的通訊性能，也帶來(lái)了互連網(wǎng)絡(luò)中的一個(gè)關(guān)鍵問(wèn)題，即網(wǎng)絡(luò)死鎖的問(wèn)題。出于網(wǎng)絡(luò)資源利用率和硬件成本等方面的考慮，本文提出使用死鎖避免的策略，即設(shè)計(jì)無(wú)死鎖

2、的路由算法解決NoC網(wǎng)絡(luò)中的死鎖問(wèn)題。 NoC網(wǎng)絡(luò)與并行計(jì)算機(jī)互連網(wǎng)絡(luò)之間有很多不同的地方，互連網(wǎng)絡(luò)中的無(wú)死鎖路由算法不能直接應(yīng)用于NoC網(wǎng)絡(luò)中。這首先是因?yàn)楹芏郚oC網(wǎng)絡(luò)(例如特定應(yīng)用NoC網(wǎng)絡(luò))具有獨(dú)特的拓?fù)浣Y(jié)構(gòu)，這就要求NoC網(wǎng)絡(luò)路由算法具有更低的路由限制以保持路由的連通性。其次，由于芯片成本和功耗方面的限制，這就要求NoC網(wǎng)絡(luò)路由算法使用更低數(shù)量的虛擬通道。NoC技術(shù)是芯片制造業(yè)發(fā)展的必然趨勢(shì)，因此有必要現(xiàn)在開展NoC網(wǎng)

3、絡(luò)無(wú)死鎖路由的研究，儲(chǔ)備相關(guān)的核心技術(shù)。 針對(duì)于目前提出的一些可擴(kuò)展的NoC網(wǎng)絡(luò)結(jié)構(gòu)，分別提出統(tǒng)一的、低虛擬通道使用和低路由限制的無(wú)死鎖路由方案是本論文研究和探索的主要內(nèi)容。研究工作的創(chuàng)新點(diǎn)主要體現(xiàn)在以下五個(gè)方面： 一是將NoC網(wǎng)絡(luò)分為以特定應(yīng)用NoC為代表的不規(guī)則拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)和以多核處理器NoC為代表的規(guī)則拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)。其中不規(guī)則拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)包括非正交不規(guī)則網(wǎng)絡(luò)和正交不規(guī)則網(wǎng)絡(luò)(例如不規(guī)則Mesh網(wǎng)絡(luò))，規(guī)則拓?fù)浣Y(jié)構(gòu)網(wǎng)

4、絡(luò)包括正交網(wǎng)絡(luò)、非正交網(wǎng)絡(luò)和具有部分正交特征的網(wǎng)絡(luò)(例如RDT網(wǎng)絡(luò))。 二是提出了基于通道類依賴圖的新的無(wú)死鎖路由判定定理，這一定理與Duato定理是等價(jià)的，也是無(wú)死鎖路由的充要判定條件。由于通道類依賴圖與網(wǎng)絡(luò)規(guī)模無(wú)關(guān)，這一定理可以成為NoC網(wǎng)絡(luò)無(wú)死鎖路由算法設(shè)計(jì)的有力工具。 三是提出了不規(guī)則Mesh網(wǎng)絡(luò)繞行障礙路由算法。這一算法與不規(guī)則Mesh的規(guī)模和形狀無(wú)關(guān)，能夠在具有不同矩形障礙區(qū)域的不規(guī)則Mesh網(wǎng)絡(luò)中保持路由的

5、連通性，同時(shí)算法只需要將網(wǎng)絡(luò)中每一個(gè)物理通道分為三個(gè)虛擬通道使用。而且通過(guò)對(duì)這一算法進(jìn)行擴(kuò)展，本文分別提出了自適應(yīng)、最短路徑和耐故障的不規(guī)則Mesh網(wǎng)絡(luò)繞行障礙路由算法。 四是提出了不規(guī)則Mesh網(wǎng)絡(luò)組合路由算法。組合路由算法由兩個(gè)子路由算法組成，并使用兩個(gè)虛擬通道，即每個(gè)子路由算法分別使用一個(gè)虛擬通道。通過(guò)將部分節(jié)點(diǎn)設(shè)置為路由盲區(qū)，組合路由算法能夠在不規(guī)則Mesh網(wǎng)絡(luò)中保持路由的連通性。本文還提出了基于組合矩陣計(jì)算和帶權(quán)無(wú)向圖

6、的優(yōu)化算法，這一算法能夠最小化組合路由算法的路由盲區(qū)。 五是提出了PRDT(2，1)網(wǎng)絡(luò)二進(jìn)制路由算法，這一路由算法基于二進(jìn)制計(jì)算進(jìn)行路由決策，其路由決策速度更快。而且當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，這一算法無(wú)需使用虛擬通道即可實(shí)現(xiàn)無(wú)死鎖路由。此外，基于這一算法本文進(jìn)一步提出了完全自適應(yīng)的二進(jìn)制路由算法。 論文的結(jié)構(gòu)如下： 第1章主要描述了互連網(wǎng)絡(luò)中死鎖產(chǎn)生的原因和解決的策略，以及一些經(jīng)典的無(wú)死鎖路由理論。 第2章介紹