4? 路由算法

　　路由策略的研究是NoC中的一個(gè)重要內(nèi)容，在給定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，決定數(shù)據(jù)包在網(wǎng)絡(luò)中的投遞路徑。其目的是使數(shù)據(jù)包的網(wǎng)絡(luò)延時(shí)、數(shù)據(jù)吞吐率、數(shù)據(jù)包投遞所需的功耗和可靠性都達(dá)到指標(biāo)。

　　NoC路由算法的分類：依照路由結(jié)果的計(jì)算位置、路徑選擇方式、路徑距離等方法，由算法決定數(shù)據(jù)包在網(wǎng)絡(luò)結(jié)構(gòu)中傳輸?shù)姆较?，把傳輸路徑集合限制為合理的路徑子集。如果消息的路由完全由它的源和目的地址決定，與網(wǎng)絡(luò)中其他流量無關(guān)，這種路由算法稱為確定性路由，對(duì)于每一個(gè)源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間，采用確定性路由得到一條路徑計(jì)算結(jié)果。而自適應(yīng)路由算法是允許路徑上的其它流量影響數(shù)據(jù)包的路由策略，對(duì)于每一對(duì)源和目的節(jié)點(diǎn)，算法可根據(jù)網(wǎng)絡(luò)的擁堵狀況給出多條的路徑計(jì)算結(jié)果。路由計(jì)算模塊是一個(gè)相對(duì)獨(dú)立的處理單元，通常需要根據(jù)不同的算法改變交換節(jié)點(diǎn)中的路由計(jì)算模塊，就可以實(shí)現(xiàn)NoC路由算法的改變。

　　維序路由采用較為廣泛的路由算法，應(yīng)用了確定性路由的方法，數(shù)據(jù)包無論其路徑上的鏈路是否阻塞都要沿該路徑走下去。該算法的思想是數(shù)據(jù)包先在低維上投遞，直至數(shù)據(jù)包在該維度上相對(duì)于目的節(jié)點(diǎn)的偏移量為0，然后轉(zhuǎn)移到下一維度以相同的模式進(jìn)行投遞，直到達(dá)到目的節(jié)點(diǎn)。因此維序路由是分布式路由，也是一種較小距離路由。

　　圖9是二維Mesh網(wǎng)格中維序路由的一種算法，稱為xy路由。表示不同源節(jié)點(diǎn)、目的節(jié)點(diǎn)下維序路由算法得出的路由路徑結(jié)果以及在二維Mesh網(wǎng)絡(luò)中，路由路徑的可能轉(zhuǎn)向。數(shù)據(jù)包先在x維度上投遞，然后在y維度上投遞，直至達(dá)到目的節(jié)點(diǎn)，該路由算法不會(huì)出現(xiàn)死鎖現(xiàn)象。

　　5? 交換技術(shù)

　　交換技術(shù)是按照某種方式動(dòng)態(tài)地分配傳輸線路和接口的資源，是影響網(wǎng)絡(luò)性能，決定交換節(jié)點(diǎn)結(jié)構(gòu)的重要技術(shù)。NoC中運(yùn)用的交換技術(shù)可分為兩類：面向連接的和無連接的。面向連接的交換方式主要有電路交換，無連接的方式主要有存儲(chǔ)交換、虛切通和蟲孔交換。

　?。?）電路交換（Circuit Switching）是一種面向連接的交換機(jī)制。在通信之前，要通過信息頭按照路由規(guī)則選路，然后建立路徑，同時(shí)預(yù)定所經(jīng)過路徑的信道資源。目的端在成功收到此信息頭后將沿原路返回一個(gè)應(yīng)答，源節(jié)點(diǎn)收到此應(yīng)答后便開始傳輸數(shù)據(jù)。數(shù)據(jù)傳輸之前源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立直接的連接路徑，一旦數(shù)據(jù)開始傳輸，消息的傳輸不會(huì)阻塞。數(shù)據(jù)部分在網(wǎng)絡(luò)中傳輸時(shí)將獨(dú)占此路徑中各段鏈路的整個(gè)帶寬，無需做路由選擇。

　　（2）存儲(chǔ)交換（Store and Forward Switching）是先將數(shù)據(jù)完全存儲(chǔ)，然后進(jìn)行路南決策，最后再轉(zhuǎn)發(fā)到下一節(jié)點(diǎn)的一種交換機(jī)制。NoC中的存儲(chǔ)交換主要以分組為流控單元，每個(gè)分組有一個(gè)分組頭，含有源、目的節(jié)點(diǎn)地址以及其它控制信息。路由節(jié)點(diǎn)接收到一個(gè)分組后，先將整個(gè)分組存儲(chǔ)在緩存器中，從分組頭中獲取路由信息由路由器的路南決策單元選擇一條輸出通道后，置位交叉矩陣中的內(nèi)部連接，如果下一路由節(jié)點(diǎn)中有足夠的空間存放此分組，就將此分組轉(zhuǎn)發(fā)到下一路由節(jié)點(diǎn)。存儲(chǔ)交換的優(yōu)點(diǎn)是通道只在一個(gè)數(shù)據(jù)包需要傳輸?shù)臅r(shí)候才被占用。

　?。?）虛切通交換（Virtual Cut-throuth Switching）將分組進(jìn)一步劃分為更小的片，并按順序排好，將所需的路由信息放入第一個(gè)片中，在無阻塞的情況下，路由節(jié)點(diǎn)收到頭片后，從中讀取路由信息，然后由路由決策單元負(fù)責(zé)選路，如果輸出通道空閑，則將頭片轉(zhuǎn)發(fā)出去，后續(xù)片緊隨頭片向前路由，從而在較大程度上縮小了存儲(chǔ)交換的時(shí)延。由于在任何一個(gè)節(jié)點(diǎn)上都可能有多條消息被阻塞，每一個(gè)節(jié)點(diǎn)都要提供能存儲(chǔ)所要通過他的數(shù)據(jù)的存儲(chǔ)空間。所以每一個(gè)節(jié)點(diǎn)都需要較大的存儲(chǔ)空間。

　?。?）蟲孔交換（Wormhole Switching）是目前NoC中的主流交換機(jī)制。它和虛切通交換的思想基本相同，只是二者在發(fā)生阻塞時(shí)所表現(xiàn)出的行為不同。在蟲孔交換中，數(shù)據(jù)包也被細(xì)分成片，以流水的方式在網(wǎng)絡(luò)上傳輸，并且允許一個(gè)分組由一個(gè)片組成。頭片中包含路由信息，其他數(shù)據(jù)片都跟隨頭片在他確定的路徑上流動(dòng)，就像蟲子一樣。當(dāng)頭片發(fā)生阻塞時(shí)，分組中的所有片都將停止前進(jìn)，頭片緩存在當(dāng)前節(jié)點(diǎn)，數(shù)據(jù)片就地緩存在其后的若干個(gè)中間節(jié)點(diǎn)中。每個(gè)路由節(jié)點(diǎn)只需提供一個(gè)片大小的緩存資源。蟲孔交換對(duì)數(shù)據(jù)包大小和路徑長度不敏感，資源占用少，實(shí)現(xiàn)代價(jià)小，且效率高，適合NoC使用。蟲孔交換的示意圖如圖10所示。

　　蟲孔交換結(jié)構(gòu)的處理過程如下：數(shù)據(jù)包的片段到達(dá)蟲孔交換結(jié)構(gòu)，存儲(chǔ)在輸入通道緩存單元中，并進(jìn)行路由計(jì)算。得到路由信息后，數(shù)據(jù)包提出傳輸請(qǐng)求，仲裁器根據(jù)請(qǐng)求進(jìn)行帶寬資源分配，一旦該數(shù)據(jù)片被允許傳輸，它將被交換到目的端口并投遞出去，直到數(shù)據(jù)包的最后一個(gè)片段離開交換節(jié)點(diǎn)。根據(jù)此處理過程，蟲孔交換電路的結(jié)構(gòu)如圖11所示，由緩存單元、路由計(jì)算單元、仲裁請(qǐng)求管理單元、交換分配和交換陣列5部分組成。

　　在VLSI實(shí)現(xiàn)中，NoC交換節(jié)點(diǎn)多采用流水結(jié)構(gòu)設(shè)計(jì)，一般流水處理結(jié)構(gòu)分為路由計(jì)算、通道分配、交換分配、數(shù)據(jù)交換和傳輸?shù)?級(jí)。在NoC設(shè)計(jì)中，總是希望得到良好的網(wǎng)絡(luò)性能，從交換節(jié)點(diǎn)設(shè)計(jì)角度考慮，減少交換結(jié)構(gòu)的流水處理級(jí)數(shù)是縮短網(wǎng)絡(luò)延時(shí)的有效方法，流水處理級(jí)數(shù)越少，數(shù)據(jù)包通過交換節(jié)點(diǎn)的時(shí)間就越短。

　　不同的NoC交換技術(shù)，對(duì)應(yīng)著不同的網(wǎng)絡(luò)性能和實(shí)現(xiàn)代價(jià)，要根據(jù)實(shí)際要求進(jìn)行選擇。