多核系統中NoC通訊架構的關鍵技術（二）

　　圖9是二維Mesh網格中維序路由的一種算法，稱為xy路由。表示不同源節點、目的節點下維序路由算法得出的路由路徑結果以及在二維Mesh網絡中，路由路徑的可能轉向。數據包先在x維度上投遞，然后在y維度上投遞，直至達到目的節點，該路由算法不會出現死鎖現象。

　　5 交換技術

　　交換技術是按照某種方式動態地分配傳輸線路和接口的資源，是影響網絡性能，決定交換節點結構的重要技術。NoC中運用的交換技術可分為兩類：面向連接的和無連接的。面向連接的交換方式主要有電路交換，無連接的方式主要有存儲交換、虛切通和蟲孔交換。

　　（1）電路交換（Circuit Switching）是一種面向連接的交換機制。在通信之前，要通過信息頭按照路由規則選路，然后建立路徑，同時預定所經過路徑的信道資源。目的端在成功收到此信息頭后將沿原路返回一個應答，源節點收到此應答后便開始傳輸數據。數據傳輸之前源節點和目的節點之間建立直接的連接路徑，一旦數據開始傳輸，消息的傳輸不會阻塞。數據部分在網絡中傳輸時將獨占此路徑中各段鏈路的整個帶寬，無需做路由選擇。

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

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

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

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

　　在VLSI實現中，NoC交換節點多采用流水結構設計，一般流水處理結構分為路由計算、通道分配、交換分配、數據交換和傳輸等5級。在NoC設計中，總是希望得到良好的網絡性能，從交換節點設計角度考慮，減少交換結構的流水處理級數是縮短網絡延時的有效方法，流水處理級數越少，數據包通過交換節點的時間就越短。

　　不同的NoC交換技術，對應著不同的網絡性能和實現代價，要根據實際要求進行選擇。