面向NoC的無死鎖路由算法的研究.pdf

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

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

3、絡(luò)無死鎖路由的研究，儲備相關(guān)的核心技術(shù)。 針對于目前提出的一些可擴(kuò)展的NoC網(wǎng)絡(luò)結(jié)構(gòu)，分別提出統(tǒng)一的、低虛擬通道使用和低路由限制的無死鎖路由方案是本論文研究和探索的主要內(nèi)容。研究工作的創(chuàng)新點主要體現(xiàn)在以下五個方面： 一是將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ò))。 二是提出了基于通道類依賴圖的新的無死鎖路由判定定理，這一定理與Duato定理是等價的，也是無死鎖路由的充要判定條件。由于通道類依賴圖與網(wǎng)絡(luò)規(guī)模無關(guān)，這一定理可以成為NoC網(wǎng)絡(luò)無死鎖路由算法設(shè)計的有力工具。 三是提出了不規(guī)則Mesh網(wǎng)絡(luò)繞行障礙路由算法。這一算法與不規(guī)則Mesh的規(guī)模和形狀無關(guān)，能夠在具有不同矩形障礙區(qū)域的不規(guī)則Mesh網(wǎng)絡(luò)中保持路由的

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

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