柚子快報激活碼778899分享：片上網(wǎng)絡(luò)NoC

http://yzkb.51969.com/

本文大部分內(nèi)容來源于參考文獻內(nèi)容以及互聯(lián)網(wǎng)，部分內(nèi)容是本人理解所得，若有不當之處請指教

一、概述

隨著MPSoC（multi-processor System-on-chip）的發(fā)展，片上核的數(shù)量越來越多，片上互聯(lián)架構(gòu)從總線結(jié)構(gòu)逐漸演變?yōu)楦訌?fù)雜的網(wǎng)絡(luò)拓撲，片上網(wǎng)絡(luò)（Network on chip，NoC）的概念也隨之出現(xiàn)，眾核處理器中各節(jié)點通過某種互聯(lián)拓撲構(gòu)成的網(wǎng)絡(luò)系統(tǒng)即為片上系統(tǒng)。

片上網(wǎng)絡(luò)的思想

芯片的片上網(wǎng)絡(luò)和數(shù)據(jù)中的網(wǎng)絡(luò)有一定的相似性，其將報文交換的思想引入芯片內(nèi)部通信機制中；盡管如此，但二者在延遲、功耗和面積等方面有本質(zhì)區(qū)別。

片上網(wǎng)絡(luò)要與計算核一起競爭芯片寶貴的功耗和面積資源。為了在有限的功耗和面積開銷下獲得較高的性能，設(shè)計者更應(yīng)關(guān)注片上網(wǎng)絡(luò)的優(yōu)化，包括底層邏輯實現(xiàn)的優(yōu)化，網(wǎng)絡(luò)層路由和流控的優(yōu)化，以及面向高層編程模式的優(yōu)化。

片上網(wǎng)絡(luò)解決的問題

1）如何設(shè)計網(wǎng)絡(luò)拓撲將一定數(shù)量的設(shè)備互聯(lián)起來

2）如何保證網(wǎng)絡(luò)通信的正確性

考慮的方向包括路由算法，路由器結(jié)構(gòu)的設(shè)計避免死鎖，解決活鎖、饑餓、擁塞等問題； 計算節(jié)點間cache一致性問題

3）如何保證系統(tǒng)的設(shè)計指標

包括算力、訪存延遲、訪存帶寬、芯片面積、功耗等。 如果在有限的面積和功耗要求下，權(quán)衡各種設(shè)計要素，以此達到目標算力，符合訪存延遲和帶寬。

片上網(wǎng)絡(luò)的設(shè)計空間

片上網(wǎng)絡(luò)的設(shè)計空間包括拓撲結(jié)構(gòu)、路由算法、流控機制和路由器結(jié)構(gòu)的設(shè)計。

拓撲結(jié)構(gòu)

拓撲結(jié)構(gòu)決定了網(wǎng)絡(luò)節(jié)點和鏈路的物理分布以及它們之間的連接關(guān)系，也決定了消息的傳輸跳數(shù)和每跳鏈路長度，因此拓撲結(jié)構(gòu)對延遲和功耗影響很大；同時由于拓撲結(jié)構(gòu)決定了節(jié)點之間的可用傳輸路徑條數(shù)，因此還影響了網(wǎng)絡(luò)流量的分布，以及網(wǎng)絡(luò)帶寬和傳輸性能。

路由算法

一旦確定了片上網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，路由算法便負責為報文計算源節(jié)點到目的節(jié)點之間的傳輸路徑。好的路由算法有更高的飽和吞吐率，可以降低報文傳輸延遲，實現(xiàn)全局負載均衡和網(wǎng)絡(luò)容錯，在一定程度上可以避免網(wǎng)絡(luò)擁塞和死鎖。

路由算法可以根據(jù)傳輸路徑長度分為最短路由和非最短路由，也可以根據(jù)路徑條數(shù)分為確定性路由算法和非確定性路由算法，非確定性路由算法又可以根據(jù)是否考慮網(wǎng)絡(luò)狀態(tài)分為非感知路由算法和自適應(yīng)路由算法。

流控機制

流控為報文分配網(wǎng)絡(luò)資源，包括鏈路帶寬、路由器緩存和控制狀態(tài)

網(wǎng)絡(luò)節(jié)點路由器設(shè)計

鏈路架構(gòu)

二、NoC拓撲結(jié)構(gòu)

三、NoC路由算法

蟲孔路由

蟲孔路由利用流水線思想將一個要傳送的報文劃分為多個大小相等的消息微片（即flit），并在網(wǎng)絡(luò)上進行傳輸。這些flit是消息傳輸?shù)淖钚∵壿媶卧?/p>

偏轉(zhuǎn)路由

供基于封包交換的網(wǎng)絡(luò)使用的路由策略。 定義：每個數(shù)據(jù)包都有自己的首選輸出口離開路由，若同時有兩個或以上數(shù)據(jù)包于同一個輸出口離開，偏轉(zhuǎn)路由會確保僅有一個數(shù)據(jù)包被路由到指定的鏈路上，而其他的數(shù)據(jù)包則會被路由到非最短路由的通路上。

產(chǎn)生的原因：

普遍存在的微秒級擁塞整體網(wǎng)絡(luò)利用率較低router的緩沖區(qū)較小

偏轉(zhuǎn)路由主要存在以下幾個方面的問題：

隨著偏轉(zhuǎn)網(wǎng)絡(luò)負載的增加，偏轉(zhuǎn)路由的作用快速下降。 一方面，丟包是網(wǎng)絡(luò)擁塞的主要信息之一，許多擁塞控制算法都依賴于此，阻止路由器進行丟包推遲了此信息到達終端的時間。另一方面，路由偏轉(zhuǎn)本身會造成網(wǎng)絡(luò)利用率的進一步升高，從而加劇網(wǎng)絡(luò)擁塞。路由偏轉(zhuǎn)會導(dǎo)致小流（mice flows）的延遲增加。阻止丟包還會導(dǎo)致大流的傳輸窗口持續(xù)增長，這些大流的突發(fā)行為會導(dǎo)致小流的隊頭阻塞。路由偏轉(zhuǎn)導(dǎo)致大量的數(shù)據(jù)包失序。由于進行了偏轉(zhuǎn)，同一條流不同數(shù)據(jù)包的傳輸路徑是不確定的，這大大增加數(shù)據(jù)包失序的現(xiàn)象。即使網(wǎng)絡(luò)在輕負載的情況下，路由偏轉(zhuǎn)也會造成大量的丟包。偏轉(zhuǎn)路由算法可能選擇了一個不恰當?shù)钠D(zhuǎn)路徑，導(dǎo)致數(shù)據(jù)包在網(wǎng)絡(luò)中循環(huán)傳輸。如果這種循環(huán)路徑?jīng)]有被正確檢測和處理，就可能導(dǎo)致死鎖

四、NoC流量控制

流控的策略

此文講的比較全面，且采用案例說明7。

bufferless：對于阻塞的報文不緩存，直接丟棄或者錯誤路由電路交換（circuit switching）：報文header 會先于 data 首先在網(wǎng)絡(luò)中傳輸。在 header 經(jīng)過的路徑上，所有需要的資源都會被保留。如果 header 暫時不能被分配資源，原地等待直到資源空閑。當整條路徑的資源都被取得后，data 開始源源不斷地在這條路徑上傳輸，直到發(fā)送結(jié)束，斷開電路連接，釋放全部資源。bufferable：當報文沒有被分配資源時全部被緩存

bufferable

當前大部分NoC的設(shè)計都是bufferable的，但是這種設(shè)計存在幾種缺點6：

buffer消耗了極大的能量增加了網(wǎng)絡(luò)設(shè)計的復(fù)雜度，需要控制報文在buffer中擺放和輸出buffer占據(jù)了極大的芯片面積

bufferless

是最簡單的流控策略，當多個報文到達端口時，需進行仲裁，未獲得資源的報文則被丟棄或者錯誤路由。

需要ACK/NAK應(yīng)答機制，告知發(fā)送端接收端是否成功接收報文，若接收失敗，則報文重新發(fā)送。

bufferless的流控會造成大量資源的浪費，報文的丟棄再重發(fā)會導(dǎo)致傳輸?shù)托А?/p>

五、NoC中節(jié)點的設(shè)計

router的結(jié)構(gòu)

每個網(wǎng)絡(luò)節(jié)點包含一個計算核和一個路由器，計算核也可以是加速器或者存儲控制器等其他硬件；路由器包括輸入單元、交叉開關(guān)、交叉開關(guān)分配器、虛通道分配器和路由計算單元。

每個網(wǎng)絡(luò)節(jié)點中的路由器（router）硬件結(jié)構(gòu)9：

輸入單元

輸入單元由輸入緩存和對應(yīng)的控制邏輯組成。 緩存單元被組織成多個隊列，每個隊列是一條虛通道。

計算單元

根據(jù)報文攜帶的目的節(jié)點信息，計算出輸出端口和輸出虛通道

虛通道分配器

完成路由計算后，報文頭申請輸出虛通道，虛通道分配器手機所有輸入虛通道的請求，并將輸出虛通道分配給提出請求的輸入虛通道。 虛通道分配器和交叉開關(guān)分配器都有多個仲裁器組成。

交叉開關(guān)分配器

當輸入虛通道獲得輸出虛通道的授權(quán)后，路由器會檢查授權(quán)的輸出虛通道是否由空閑的緩存單元； 如果有，報文會向交叉開關(guān)分配器提出交叉開關(guān)傳輸?shù)恼埱蟆?/p>

交叉開關(guān)

交叉開關(guān)通常由多個多路選擇器組成，這些墮落選擇器的控制信號由交叉開關(guān)分配器生成。 一旦一個報文傳輸?shù)浇徊骈_關(guān)的輸出端口，交叉開關(guān)就向上有路由器反饋一個信元消息，通知已經(jīng)釋放了一個緩存單元。

輸出單元

輸出單元使用多個寄存器記錄下游虛通道狀態(tài)

網(wǎng)絡(luò)中cache一致性的設(shè)計

此文8對cache對網(wǎng)絡(luò)性能的影響闡述的比較清晰。

六、網(wǎng)絡(luò)的堵塞

網(wǎng)絡(luò)擁塞原因

片上網(wǎng)絡(luò)的報文戶通過時分復(fù)用和空分復(fù)用等方式共享使用片上資源，當網(wǎng)絡(luò)處于重負載情況是，有限的片上資源無法為大量的報文提供服務(wù)，從而導(dǎo)致?lián)砣F(xiàn)象。

此時需通過擁塞管理機制來優(yōu)化網(wǎng)絡(luò)性能。即根據(jù)網(wǎng)絡(luò)復(fù)雜情況動態(tài)調(diào)整報文優(yōu)先級與網(wǎng)絡(luò)資源分配方式，將網(wǎng)絡(luò)資源有限分配給一些特殊報文使用，避免或者延遲網(wǎng)絡(luò)進入飽和狀態(tài)，達到提高網(wǎng)絡(luò)性能的目的。

七、網(wǎng)絡(luò)的死鎖

死鎖、活鎖、饑餓鎖、無鎖在多線程、片上網(wǎng)絡(luò)等領(lǐng)域概念基本一樣，可參考這篇文章的描述。 多線程中死鎖、活鎖、饑餓鎖、無鎖問題

死鎖的定義和原因

死鎖指在系統(tǒng)中的多個資源彼此等待對方釋放資源而無法繼續(xù)執(zhí)行的狀態(tài)。當網(wǎng)絡(luò)中的路由依賴形成一個環(huán)時，互相阻塞而無法前進，就發(fā)生了路由死鎖。在沒有死鎖回復(fù)機制的情況下，死鎖會導(dǎo)致網(wǎng)絡(luò)癱瘓。 無死鎖要求網(wǎng)格資源之間沒有循環(huán)依賴，這些資源包括緩存和鏈路。

死鎖產(chǎn)生的條件：

互斥條件：所謂互斥就是節(jié)點在某一時間內(nèi)獨占資源。請求與保持條件：一個節(jié)點因請求資源而阻塞時，對已獲得的資源保持不放。不剝奪條件：節(jié)點已獲得資源，在末使用完之前，不能強行剝奪。循環(huán)等待條件：若干節(jié)點之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。

活鎖的定義和原因

活鎖指的是在嘗試解決問題時，任務(wù)或執(zhí)行者沒有被阻塞，但由于某些條件沒有滿足，導(dǎo)致它們不斷地重復(fù)嘗試、失敗、再嘗試、再失敗。 活鎖中的實體是在不斷地改變狀態(tài)，而不是像死鎖那樣表現(xiàn)為等待狀態(tài)?；铈i有可能在一定時間后自行解開，因為進程沒有阻塞，但它們無法取得任何實際的進展，這通常會占用網(wǎng)絡(luò)帶寬?；铈i可以看作是一種特殊的饑餓狀態(tài)，即資源并沒有被別人持有，但由于某些原因而無法得到。

解決死鎖的方法

通過虛通道將請求分流

完全自適應(yīng)算法允許報文使用源節(jié)點和目標節(jié)點間的所有傳輸路徑，通過虛通道消除路由子函數(shù)內(nèi)部的資源循環(huán)依賴，從而消除網(wǎng)絡(luò)死鎖。 通過虛通道解除死鎖除了需要一個虛擬網(wǎng)絡(luò)，還需要協(xié)議級的避免死鎖方法1。

限制報文傳輸?shù)牟糠洲D(zhuǎn)向消除資源循環(huán)依賴

即設(shè)計路由函數(shù)打破CDG中所有環(huán)

知乎中的死鎖描述博客

參考文獻

Jieming Yin, Zhifeng Lin, “Modular Routing Design for Chiplet-based Systems” ISCA.片上網(wǎng)絡(luò)之Channel Dependency Graph（一）片上網(wǎng)絡(luò)之Channel Dependency Graph（二）片上網(wǎng)絡(luò)之Channel Dependency Graph（三）知乎：CoNEXT’21—Burst-tolerant Datacenter Networks with VertigoT. Moscibroda and O. Mutlu, “A case for bufferless routing in on-chip networks,” in Proceedings of the 36th annual international symposium on Computer architecture, 2009, pp. 196–207.知乎：Li Shi：《片上網(wǎng)絡(luò)》筆記（五）：流量控制知乎：Li Shi：《片上網(wǎng)絡(luò)》筆記（二）：系統(tǒng)架構(gòu)與接口《片上網(wǎng)絡(luò)原理與設(shè)計》王志英主編

柚子快報激活碼778899分享：片上網(wǎng)絡(luò)NoC

http://yzkb.51969.com/

文章來源