時鐘及面積優化的可配置片上網絡路由器

胡東偉，尚德龍，張 勇，王力男

(1.中國電子科技集團公司 第五十四研究所，河北 石家莊 050080；2.南京智能技術研究院，江蘇 南京 211100)

伴隨著半導體工藝技術的飛速發展，在單芯片上能夠集成的處理器數目越來越多，處理器與處理器之間的互連問題和數據交換需求，已不是傳統的總線所能解決或達成。片上網絡(Network-on-Chip，NoC)借鑒互聯網的思維，采用數據包包交換的方式，實現處理器之間的互連和數據交換[1]。采用片上網絡的芯片系統，可以實現成百上千處理器的集成[2-3]。

目前，片上網絡技術的研究如火如荼，但在片上網絡技術的各個方面，例如網絡架構、路由算法、流量控制等問題，都未達到統一。因此，目前大量的片上網絡技術研究，都停留在系統仿真層面[4-6]，電路實現方面的研究相對較少。

片上網絡實現包括網絡接口的實現和片上網絡路由器的實現[7]。網絡接口實現處理器和片上網絡的數據交換，路由器實現數據包的遠程交換和路由。片上網絡實現的核心在于路由器的實現。首先，片上網絡路由器的時鐘，決定了整個網絡的時鐘；其次，片上網絡路由器，直接實現了片上網絡的路由算法和流量控制算法；最后，片上網絡路由器的復雜度，決定了整個網絡的復雜度[7]。

片上網絡路由器主要由輸入/輸出緩沖器和交叉開關組成[8]。交叉開關包括仲裁器和多路選擇器，其結構已經比較成熟。路由器的復雜度，主要由輸入/輸出緩沖器決定[9-10]。因此，路由器中緩存器的研究，引起了業界的極大重視。片上網絡路由器的緩沖器，一般采用先進先出(FIFO)緩存器來實現。根據文獻[9]，采用無緩存器的片上網絡路由器，可以使得片上網絡總面積消耗節約60%以上，功耗節約39%以上。根據文獻[10]，緩存器面積占比達到75%，功耗占比達到22%。然而，無緩存的路由器增加了訪問延時，降低了片上網絡吞吐率[9]，這是所不希望的。因此，有必要尋求新的先進先出緩存器實現技術。

首先，介紹同步先進先出緩存器和異步先進先出緩存器的電路結構[11-12]和延遲特點，及片上網絡組成的系統架構和片上網絡路由器架構；然后，提出一種優化的時鐘布線方案，并按照這種方案，重新設計了路由器，達到了減小復雜度及片上網絡延遲的效果。在此基礎上，筆者提出一種采用鎖存器替代寄存器的方法，以降低路由器中同步或異步先進先出緩存器的復雜度，并提出單時鐘寄存器寫的解決方案，并進一步提出多個先進先出緩存器的共享實現方案。該方案建立在第3節先進先出鎖存器實現方案的基礎上。

1 基礎知識

1.1 同步先進先出和異步先進先出緩存器

1.1.1 先進先出緩存器的接口信號

先進先出緩存器是一種非常常用的數字電路部件，在此對其功能不做過多的描述。圖1(a)給出了一般形式的先進先出緩存器接口信號，圖1(b)將接口信號重新命名，使得接口信號符合AXI總線形式。同步先進先出緩存器是指緩存器的寫入時鐘CLK 1和讀出時鐘CLK 2，采用同一個時鐘。異步先進先出緩存器是指緩存器的寫入時鐘CLK 1和讀出時鐘CLK 2，采用兩個不同的時鐘。這兩個時鐘可以是頻率相同、相位不同的兩個時鐘，也可以是既不同頻、也不同相的兩個時鐘。

1.1.2 先進先出緩存器的電路實現

圖2(a)給出了同步先進先出緩存器的電路實現。圖2(a)中，在寫入側和讀出側，分別維持一個寫地址寄存器和讀地址寄存器，每寫入一個數據包，或讀出一個數據包，對應的地址加1。“DEC”和“MUX”分別是寫地址譯碼器和讀數據多路選擇器。當寫地址和讀地址相同時，先進先出要么為“空”，要么為“滿”狀態。“空”和“滿”狀態分別由一個“FULL”寄存器來分辨。在復位狀態下，先進先出只能為“空”，“FULL”被清零。此后，“FULL”寄存器可以跟蹤“空”和“滿”的狀態變化。

圖2(b)給出了異步先進先出緩存器的電路實現。與同步先進先出緩存器不同的是，由于讀寫地址位于不同的時鐘域，需要對讀寫地址進行格雷編碼，并在對方時鐘域內進行兩次采樣，如此才能獲得穩定的跨時鐘域地址信號。此外，為區分緩存器“空”和“滿”的狀態，在讀寫時鐘域內分別設置“EMPTY”和“FULL”寄存器，以此追蹤緩存器的狀態變化。“組合邏輯1”和“組合邏輯2”進行地址比較。需注意，這里1個地址為二進制編碼，1個地址為格雷編碼。

需要特別強調的是：① FIFO的數據流為單向的；② 根據圖2所示的FIFO實現電路，當輸入輸出的READY都為高，且異步FIFO的兩側使用同一個時鐘時，同步FIFO的輸出相對輸入延遲1個時鐘，異步FIFO的輸出相對輸入延遲3個時鐘，也就是，異步FIFO比同步FIFO具有更大的時延；③ 同步FIFO的最小深度為1，異步FIFO的最小深度為4；④ 通過FIFO與同步FIFO的級聯，可構成4以上任意深度的異步FIFO，這種級聯的異步FIFO輸入輸出延遲為4個時鐘。

圖2 先進先出緩存器的電路實現

1.2 片上網絡及其路由器

1.2.1 片上網絡架構

片上網絡是用于多個處理器單元(Processing Element，PE)互連的一種電路，它由路由器和互連鏈路構成。在NoC之上，PE與PE之間以數據包的形式進行數據交換。文獻[3]指出，在一個路由器上連接一個處理器簇的分層架構，較一個路由器上連接單個PE的全網絡架構，能更好地利用處理器簇內的本地存儲器，從而具有更高的多處理器并行加速比，并且，簇內PE數目以4至8個為宜。因此，考慮圖3所示的片上網絡架構。圖3中，NoC路由器(R)與R由L1鏈路相連，每一個R上連接1個處理器簇，每個簇內包含4個PE。R與PE由L2鏈路相連。簇內4個PE之間，每兩兩由L3鏈路相連(圖3中未示出PE0與PE2、PE1與PE3之間的L3)。圖3示出了1個4×4的NoC，每一個R具有X和Y兩個坐標，可用于R(對應處理器簇)的尋址。每一個PE可通過對應的R和簇內PE編號來尋址。

顯然，在圖3所示的架構中，每一個L1鏈路，至少承擔兩個處理器簇(即8個PE)的互連，因此L1的帶寬要求較高。考慮圖4所示的數據包格式。圖4中，數據包由包頭、地址段和數據段構成。包頭內包括了數據包類型(讀請求、寫請求、讀響應、寫響應)、源、目標PE地址和數據段的大小指示，地址段給出了數據段內數據的起始地址，數據段承載PE間需要交換的數據。由于L1的帶寬要求較高，設計數據段的位寬較寬(例如128、192或256位)，且整個數據包在一個時鐘周期內傳輸[13]，因此，圖4所示數據包格式，與總線有一定的相似性。

以XY靜態路由算法為例[5]。XY靜態路由對數據包首先進行X(Y)方向的路由，再進行Y(X)方向的路由，直至到達目的R(PE)。采用XY路由，從源PE到目的PE只有1條路徑，具有路由簡單、無死鎖的優點，因而被廣泛采納。此外，由于R內采用先進先出緩存器(見2.2.2節)，從源PE到目的PE整個路徑上數據包的先后順序得以保持，這也類似于總線。

圖3所示的4×4 NoC連接了64個PE，但該架構具有向更大規模伸放的可行性。

圖3 片上網絡架構示意圖

1.2.2 路由器架構

根據圖3所示的NoC架構，路由器R的接口信號如圖5(a)所示。圖5(a)中，一個路由器上有4個相鄰NoC(即東e、南s、西w、北n 4個方向)輸入、4個PE輸入，這分別對應圖3中4個L1和4個L2的輸入方向；相應地，路由器有4個相鄰NoC輸出和4個PE輸出，這分別對應圖3中4個L1和4個L2的輸出方向。圖5(b)給出了路由器的電路實現框圖。圖中，每個輸入數據包，首先進入對應的先進先出進行緩存，8個先進先出緩存器的輸出，連接到8個仲裁及多路選擇器，每個仲裁及多路選擇器選擇出一個有效輸出，輸出到輸出端口的先進先出緩存器。

仲裁及多路選擇器由仲裁器和多路選擇器構成，其個數與輸出端口數目相同，且每個仲裁及多路選擇器都相互獨立。所有仲裁及多路選擇器的輸入通道數目，與路由器輸入先進先出通道數目相同。輸出端口的FIFO連接到下一個路由器(或PE)的輸入FIFO，因此可以與下一個路由器(或PE)的輸入FIFO合并。因此文中后面路由器將不再有輸出FIFO。路由器輸入FIFO可以是同步FIFO，也可以是異步FIFO，2.1節將詳細討論FIFO的時鐘要求。

圖5 路由器架構

1.2.3 虛通道和3D NoC

可以將每個物理輸入通道的數據包，根據不同的標記排列到不同的先進先出隊列中，由此形成虛通道。此標記即為虛通道識別號。圖6示出了每個物理通道分為2個虛通道的示意圖。虛通道方法增加了先進先出的個數，從而增加了同時從先進先出中輸出的數據包個數，提高了數據包輸出的并行性，由此對吞吐率有一定的提升；但另一方面，仲裁及多路選擇器的輸入通道數目增多，增大了仲裁及多路選擇器的復雜度。假如仲裁及多路選擇器的輸入通道數目過多，則需要流水實現，這又增加了路由器的延遲，因此，對虛通道的使用需謹慎對待[5，9]。

圖6 基于虛通道的路由器架構

這里需要強調的是，倘若采用虛通道方案，則仲裁及多路選擇器的優先級，需要與時間相關，不可使仲裁器長時間駐留在某個優先級。例如，假如某個輸出端口的數據包阻塞(由于它對應的下一級先進先出滿導致)，且較長時間無法發送出去，此時，如果本地優先級輪轉，則仲裁及多路選擇器會嘗試發送與這個數據包并行的其他數據包(隸屬于其他虛通道)，這會在一定程度上減小阻塞。要使優先級與時間關聯，也是很容易實現的，只要設置一個計數器，當仲裁器駐留在某一優先級超過該計數器閾值時，仲裁器跳轉到下一優先級。

3D NoC在圖5(a)所示的架構上，增加了上下方向NoC的輸入輸出。同樣，這也增加了仲裁及多路選擇器的輸入通道數目，可流水實現仲裁及多路選擇器。

2 片上網絡對FIFO的時鐘要求及優化方案

2.1 時鐘要求及優化方案

如圖3所示，由片上網絡路由器構成的整個芯片，連接的PE較多，面積往往較龐大，因此，倘若整個芯片采用同步時鐘，則從芯片的東南角到芯片的西北角，時鐘的延遲構成一個環路，由于布線的延遲，時鐘布線將很難收斂，或時鐘速率很難提高。此外，由于這樣的芯片功耗往往較高，需要對每個PE進行動態電壓頻率伸縮，這又需要各個PE的時鐘獨立。因此，最簡單的辦法是，對圖5(b)所示的輸入先進先出，采用異步先進先出[7，13]。這可以實現：① 各個PE的時鐘解耦合；② 相鄰NoC路由器的時鐘解耦合。

但是，如2.1.2節所示，異步先進先出的缺陷是，異步先進先出兩端的延遲較大，這將導致整個NoC上數據傳輸時的延遲較大。因此，筆者提出如下優化方案：

(1) PE與R之間，依舊采用異步先進先出，以實現各個PE時鐘獨立。

(2)對所有的R，從R到R，采用兩個獨立的時鐘，從西到東、從北到南為CLK1，從東到西、從南到北為CLK2。

(3)對所有的R，從R到R的先進先出，采用同步先進先出。

圖7為以上時鐘方案的示意圖。按照此時鐘方案，NoC路由器R將涉及到多個時鐘域，圖8給出了此時路由器的總體架構。

圖7 優化的NoC時鐘方案

圖8中，PE到R的數據包，首先分路為2路，一路將向東、南NoC端口輸出，因此需要通過異步先進先出轉換到CLK 1時鐘域；另一路將向西、北NoC端口輸出，因此需要通過異步先進先出轉換到CLK 2時鐘域。CLK 1和CLK 2都只是沿平面的一個方向推進，即東南方向或西北方向推進，時鐘的延遲可以在這個方向逐漸遞增，因此，時鐘布線時，較易做到時鐘收斂。為減小復雜度，在同一個R內，將不再支持由PE到PE路由。由PE到PE的訪問，將全部通過圖3中L3鏈路實現。因此，圖8中，CLK 1時鐘域下的仲裁及多路選擇器陣列和CLK 2時鐘域下的仲裁及多路選擇器陣列，每個時鐘域下均為4個2選1(至PE)，和2個6選1(至NoC)的仲裁和多路選擇，這樣仲裁及多路選擇器的復雜度大大降低。需強調的是，圖8中的PE到R的異步先進先出，和R到PE的異步先進先出，分成了2個，但相應地，它們的數據包流量也減半，因此每一個異步先進先出的深度亦減半，先進先出的復雜度并沒有較圖5(b)方案增加。

2.2 實驗及結果

2.2.1 NoC路由器的實現實驗

分別按照圖5(b)所示的架構和按照圖8所示的架構，對NoC路由器R進行設計實踐。實踐中圖5(b)只有輸入異步先進先出，沒有輸出異步先進先出，先進先出深度選取為8。圖8所示異步先進先出深度為4。為盡量保證比較的公平性，圖8的左側增加4個分路器，將每個PE輸入的數據包由1路分成2路；圖8的右側亦沒有輸出異步先進先出。

表1給出了實現的綜合結果。實驗中先進先出采用寄存器實現，工藝為TSMC 28nm HPC，9Track，RVT。從表1可以看到，采用圖8所示結構，組合邏輯明顯減小，時序邏輯與圖5(b)的相當。這與前面的分析是一致的。

表1 不同結構下的NoC路由器面積對比 μm2

圖9 不同跳數下的鏈路延遲

2.2.2 延遲仿真實驗

為檢驗圖7所示的時鐘優化結果，按照圖3所示架構，從源PE往目的PE發送數據包，檢驗不同跳數(通過1個NoC路由器R，記為1跳)下鏈路的延遲。仿真中，所有的時鐘都設置為同一個時鐘，以該時鐘的時鐘計數來評估鏈路延遲。圖9給出了不同跳數下按照圖5所示R和圖8所示R實現時的鏈路延遲結果。從圖9可以看到，在所有的跳數下，優化的時鐘方案，都減小了鏈路延遲；當跳數為7時，全異步FIFO方案時，鏈路延遲為24個時鐘，優化后，鏈路延遲只有12個時鐘，只有原來的50%。

3 使用鎖存器構建FIFO的存儲陣列

如前所述，數據包的位寬較寬，這導致NoC路由器R內的先進先出占用較多資源。一般情況下，先進先出的深度不夠深，其存儲陣列不足以使用現成的SRAM宏單元，需采用定制電路實現。但定制電路的設計需耗費較長時間，在很多情況下很不方便。此時，最簡單的辦法是采用寄存器實現。如表1所示，此時寄存器占據了整個R內最大部分的面積開銷。

為進一步減小先進先出的實現代價，推薦使用鎖存器來替代寄存器，構建同步或異步先進先出。鎖存器的模型如圖10(a)所示。圖10中，當使能信號EN為高時，輸入數據D將貫通到鎖存器輸出端Q；當EN為低時，鎖存器的輸出值Q將保持不變。當EN、D都是由時鐘CLK驅動時，數據D的延遲有可能比EN大，也可能比EN小，如圖10(b)所示。這將導致鎖存器內鎖存不同時鐘下的數據(D12和D21)，導致錯誤。此外，倘若錯誤地址上的EN信號產生毛刺，則有可能將數據寫到錯誤的地址上。因此，針對鎖存器的寫數據，最簡單的辦法是，數據保持3個時鐘，只在中間時鐘打開EN信號，如圖10(c)所示。

圖10 鎖存器模型及鎖存器寫存在的問題

但NoC路由器內的先進先出需要高吞吐率，使用3個時鐘來完成寫，是不可以接受的。筆者推薦圖11的鎖存器寫方法。圖11(a)示出了鎖存器寫的時序。圖中，鎖存器使能信號只是在時鐘低電平的半周期內有效。鎖存器的輸入數據，是原始輸入數據(見圖10(b))延遲半個時鐘周期。這延遲半個時鐘周期，可以通過一個下降沿采樣的寄存器來實現，如圖11(b)所示。這樣，使用圖11(b)所示電路對先進先出的輸入數據進行處理后，先進先出的存儲陣列即可使用鎖存器來實現。

圖11 單周期鎖存器寫方法

此方法要求，在時鐘的前半個周期內，地址譯碼已經穩定，這樣不至于在鎖存器使能信號打開時，數據寫到錯誤的地址上。由于NoC路由器內的先進先出深度都很小(幾個到幾十個)，地址位寬很小，半個時鐘周期內實現穩定譯碼，是很容易達到的。

需要強調的是，圖11(a)的虛線處，鎖存器可能暫時鎖存前一個數據D10或D20，但由于在鎖存器使能信號的下降沿前后，數據穩定為D11和D21，因此鎖存器能保證鎖存到正確數據。因此，使能信號上升沿的數據振蕩，只是造成輕微的功耗損失，不影響鎖存數據的正確性。

表2給出了圖5(b)和圖8的NoC路由器，使用寄存器和使用鎖存器時的面積對比。綜合時使用的工藝同前。從表2中可以看到，使用鎖存器，大大減小了NoC路由器的面積消耗。

表2 寄存器和鎖存器下的NoC路由器面積對比 μm2

4 可配置的共享先進先出

在圖8中，CLK 1和CLK 2域，分別有兩個同步先進先出，且它們的深度為圖8中異步先進先出深度的2倍。本節進一步提出，將CLK 1域和CLK 2域的4個同步先進先出(FIFO 1、FIFO 2、FIFO 3和FIFO 4)深度進行共享。也就是，FIFO 1可以從FIFO 2借用若干條目(entry)的FIFO單元，FIFO 2可以從FIFO 1、FIFO 3借用若干條目的先進先出單元，FIFO 3可以從FIFO 2、FIFO 4借用若干條目的FIFO單元，FIFO 4可以從FIFO 3借用若干條目的先進先出單元[14]。

圖12(a)給出了兩個先進先出共享的原理框圖。

(a) 兩個FIFO共享存儲陳列示意圖

圖12中有一個大的、基于鎖存器的存儲陣列，它的上半部分為FIFO 1，下半部分為FIFO 2。上半部分和下半部分的分界，由一個寄存器Addr1_E/Addr2_S來指示，該寄存器可配置。倘若FIFO 1和FIFO 2在同一個時鐘域內，則很容易實現存儲陣列同時寫兩個數據、讀兩個數據。這時，存儲陣列相當于多端口寄存器文件。倘若FIFO 1和FIFO 2不在同一個時鐘域內，則由于鎖存器無需時鐘，只有分界地址在兩個時鐘域內都使用，需保證使用該分界地址時，兩個時鐘域內的分界地址都有效。這有很多辦法可實現，例如，可以在一個時鐘域內寫入，在另一個時鐘域內讀出，并等待兩個時鐘域內寫入和讀出的數值相同來保證；也可以在CLK 1域寫入，傳到CLK 2域，然后又從CLK 2域傳回CLK 1域，比較傳回的數值與寫入的數值。

以上方法可實現靜態的先進先出共享。如果設置一個寄存器，記錄分界地址前后(即wr_addr1或rd_addr1到Addr1_E/Addr2_S，和Addr1_E/Addr2_S到wr_addr2或rd_addr2)，先進先出內容是否為空，則可以判斷是否可以進行分界地址的動態修改。只有分界地址前后先進先出內容都為空時，則分界地址的修改方可進行。如此可實現先進先出的動態共享。同樣，分界地址更改后，需保證修改后的地址，在相關時鐘域內都穩定后，相關時鐘域內的讀寫方可繼續。

圖12(b)給出了4個同步先進先出共享的原理框圖。FIFO 2和FIFO 3的分界地址，涉及到跨時鐘域問題。該分界地址前后的狀態，也處于不同的時鐘域。

也可考慮異步先進先出的共享。但非級聯異步先進先出的地址涉及到格雷編碼，地址需連續變化為宜。此外，圖8中的異步先進先出深度只有4，已是異步先進先出的最小深度，共享的意義不大。倘若需要更大深度的異步先進先出共享，則筆者主張以級聯的方式實現：通過深度為4的異步先進先出實現寫到讀時鐘域的轉換，只對讀時鐘域內的同步先進先出實現共享。

在圖8所示NoC路由器實現中，仿真及綜合驗證了這種共享先進先出方法的可行性。綜合時采用的工藝庫同前。表3給出了采用這種共享先進先出和不采用這種共享先進先出的復雜度對比。可以看到，采用共享先進先出的方法，先進先出的組合邏輯復雜度有所增加。這是由于共享先進先出后，所有先進先出的地址位寬都需要加寬，輸入數據地址譯碼器和輸出數據多路選擇器的復雜度將變大。表3中從比例上看，共享先進先出復雜度的提高還較顯著。這在面積容忍度較大，而對數據靈活性要求較高的場合[15-17]，是可以接受的，有較大的現實意義。

表3 不共享和共享先進先出的面積對比 μm2

5 結束語

片上網絡是大規模多處理器互連的一項基礎技術。雖經過多年的研究，在片上網絡的實現上仍然莫衷一是。筆者從實現的角度，提出了片上網絡的時鐘優化技術、基于鎖存器的先進先出實現技術和多個先進先出共享技術。由于直接面向實現，因此具有較大的現實意義，相信會對業界產生一定的推動作用。