一種帶優化約束的分布式NoC設計與實現

王正茂, 宋宇鯤, 侯 寧, 王澤中, 張多利

(1.合肥工業大學 微電子學院,安徽 合肥 230601; 2.河南城建學院 電氣與控制工程學院,河南 平頂山 467036)

隨著工藝進步,單個芯片內已能集成數以百計的內核,此時,傳統總線或分段總線結構的擴展性差、并行通信能力弱的缺陷使得其無法滿足現代多核芯片對內部通訊性能的要求[1]。誕生于20世紀末的片上網絡(network-on-chip,NoC)技術被業界認為是一種從體系結構上解決上述問題的有效技術途徑[2]。目前多核芯片通常集成有多種功能定制化網絡,即網絡功能正交化,將不同功能分置于專用定制網絡上,例如,Tilera公司的Tile系列多核處理器集成有靜態網絡(STN)、單元動態網絡(TDN)、用戶動態網絡(UDN)、存儲動態網絡(MDN)、IO動態網絡(IDN)等5種獨立功能網絡[3];TI公司的多核DSP TMS320C6678內部任務控制網絡和數據網絡也是相互對立的[4];TRIPS處理器內部設置了指令、數據和控制通道分離的設計結構[5]。NoC作為片上通訊載體,其性能是決定整個多核系統運算性能的重要因素,因此有關NoC拓撲結構、路由算法和交換機制等相關技術始終是研究的主要熱點。

1 相關研究

依據鏈路建立過程,NoC可分為集中控制和分布式控制兩大類[6]。

集中控制由一個中央節點負責定期收集網絡狀態,再計算產生各條鏈路的全路徑路由配置信息,管理各個路由節點的路由方向;分布式控制是網絡中的各個節點根據目的節點的相對位置和自身周邊節點狀態,在本地獨立地計算后繼有限范圍內的節點位置。綜合考慮實現復雜性和網絡性能后,目前多數NoC采用分布式結構[6]。

分布式控制網絡的鏈路分為有效鏈路和無效鏈路2種情況,前者指完成了數據傳輸的鏈路,后者指鏈路建立失敗或鏈路成功而目的端無效的情況,稱此鏈路為無效鏈路。為保證數據傳輸時效性,發起端在檢測到無效鏈路后,應等待若干時間后再次嘗試建立鏈路,直至數據傳輸成功[7]。

對鏈路擁堵造成NoC性能下降的問題,文獻[8]提出一種可以根據當前路由負載狀態進行算法切換的動態混合路由設計,該路由可根據負載狀態,在確定路由和多負載均衡路由間自行切換,在一定程度上降低關鍵路由的繁忙率,緩解路由擁塞;文獻[9]針對NoC中存在多種與時間相關的流量負載情況,設計了一種針對特定拓撲結構的全局鏈路管理機制,通過監視網絡狀態,動態調整每個鏈路的具體路由算法,來獲得高負載平衡和高吞吐量;文獻[10]提出了一種基于曼哈頓距離的多播自適應路由方案,該方案通過引入的特定約束,避免了死鎖和活鎖的影響,實現更好的平均流量分配,提高了網絡性能;文獻[11]提出一種新型路由內部優先級仲裁方法,該方法有效提高了NoC飽和流量值;Spider-Donut網絡半徑小于2D網絡,文獻[12]研究了一種用于Spider-Donut網絡的無死鎖路由算法,實現均衡的片上流量,進而提高整個網絡性能;文獻[13]在NoC路由器中使用基于遺傳算法的鏈路負載平衡技術,實現快速流量均衡分配,避免負載不均衡帶來的鏈路擁堵狀況。

上述研究工作的重心集中于通過優化路由算法平衡網絡負載,緩解NoC中擁堵問題,處理對象是有效鏈路,沒有考慮無效鏈路因素,隨著NoC規模不斷擴展,節點布局密度趨近1,高注入率下,無效鏈路對整個網絡性能的影響已無法被忽視。為此,本文在已有NoC相關研究的基礎上,從減少無效鏈路數量的角度出發,提出了一種受約束分布式片上網絡機制(constrained distributed NoC mechanism,CDNM),設計出一種目的端狀態追蹤機制和鏈路維持協議,進一步降低NoC片上擁堵率,提升大通訊量NoC系統的整體性能。本文提出的受約束分布式NoC可以用于不同路由方式,具有良好的適用性。

2 改進分布式網絡設計實現

本文從面向計算密集型和數據密集型任務的多核系統內部數據交互需求出發,結合多核系統編程模型規范,通過將目的端狀態引入分布式網絡,構建了一種基于兩端狀態條件約束的分布式NoC,包括一種目的端狀態快速傳輸方案和基于這一方案的鏈路建立規則,以及一種鏈路維持協議。

2.1 改進網絡概述

本文設計的NoC采用三重網絡結構組成,包括數據網絡、狀態網絡和配置網絡。狀態網絡將網絡中各功能節點狀態信息上傳至主控制器,各功能節點的配置和管理信息通過配置網下行到各功能節點,形成一個閉環的管理機制。數據網絡采用“包-電路交換”(packet-connected circuit,PCC)機制、Mesh拓撲結構和回退轉向路由算法。

改進的分布式網絡結構如圖1所示。

圖1 改進的分布式網絡結構

PCC通過包交換方式建立鏈路,再通過電路交換方式傳輸數據,是一種適合大批量數據傳輸任務的NoC機制。

本文設計的數據網絡中數據傳輸是由源端主導,即源端負責鏈路的建立,配置目的端坐標,而目的端無需知道源端坐標。當源端單元數據就緒,通過發送控制單元獲得當前數據的目的端坐標和數量信息,并將數據打包后經數據網絡傳遞至目的單元的接收控制器進行解包操作,最終解包后的數據寫入目的單元。

2.2 改進的分布式鏈路機制

本文設計的數據網絡工作流程如圖2所示,這里使用數據網Feedback操作在鏈路建立成功后獲取目的端狀態,用狀態廣播的方法在未建立鏈路時獲取目的端從無效變為有效的事件,從而實現對目的端的狀態追蹤。

圖2 數據傳輸流程

源端在有效后建立鏈路,一旦鏈路建立成功,使用Feedback操作判斷目的端的狀態。若目的端也有效,則開始一次數據傳輸;否則撤銷鏈路,并且監聽配置網的廣播信息,直到收到目的端變為有效的信號,才重新建立鏈路。

源端在一次傳輸完成后,再次使用Feedback操作,獲取目的端是否有效的狀態。若此時雙端都依然有效,則直接開始下一次的數據傳輸;否則撤銷鏈路,直到雙端都有效后才重新建立鏈路。

2.2.1 鏈路反饋機制

本文在傳統網絡的單向鏈路的基礎上增加了鏈路反饋能力,允許從目的端到源端的信息反饋。該機制可以使源端利用建立好的鏈路快速獲取目的端狀態。

2.2.2 狀態追蹤機制

本文使用源端控制為主的數據傳輸機制,該機制的工作效果受對目的端狀態監測效率的影響,因此需要建立一套實時追蹤目的端狀態變化信號的策略。前述提到的狀態廣播機制和鏈路反饋機制用于解決這一問題,實現源端對目的端的狀態追蹤。

源端、目的端的狀態表在以下情況更新:

(1) 收到某個節點準備好的廣播,且廣播信息中的坐標與當前目的節點坐標相同,更新目的端狀態dst-ready=true。

(2) 在鏈路建立成功后或者發送完一個數據包后，收到目的端利用鏈路反饋機制通過數據網鏈路反饋的信號,根據此反饋信號更新目的端狀態dst-ready=true或者dst-ready=false。

(3) 在源端切換目的之后，由于之前未在狀態網監聽該坐標,此時無法知道目的端狀態,默認dst-ready=true;對應圖2中開始后,如果源端有效直接建立鏈路,那么通過一次嘗試連接來確定目的節點狀態。

2.2.3 Keep-alive機制

包-電路交換策略雖然結合了包交換和電路交換的優點,但過多的鏈路建立和撤銷影響通訊效率。為解決此問題,本文提出一種Keep-alive機制，即在一次包傳輸完成后，若條件滿足,則直接傳輸下一個包,省去了鏈路重建過程。在傳統架構中,傳輸多個數據包過程如圖3所示。

圖3 NoC傳輸多個數據包示意圖

該過程包括源端發送頭包(H)請求建立鏈路,目的端應答(A)、數據傳輸(D)、發送結束信號(E)、鏈路取消(C)。傳統結構需要執行2次完整的鏈路建立/數據傳輸/撤銷的過程才能完成2次獨立的數據傳輸。這勢必會造成一定的網絡性能損失。

本文設計的數據網為了提高效率,引入Keep-alive機制,允許一次建立鏈路發送多個數據包,其原理是在當前數據傳輸完成后,直接利用鏈路反饋機制獲取目的端是否準備的信號,再由源端結合本地輸出數據狀態和當前地址隊列輸出判斷是否滿足繼續傳輸的條件;若滿足,則繼續傳輸,省去了撤銷鏈路再重新建立鏈路的過程。

具體的改進是將原本“包-電路連接”協議中的Cancel信號改為反饋(Feedback)信號,用于目的端向源端反饋是目的端當前狀態信息,如果目的端處于有效狀態,那么源端直接發送,在此過程中既有鏈路不會被撤銷。Keep-alive協議的執行過程包括以下步驟:

(1) 目的端收到當前數據包的最后一個數據時,通過數據網反饋通道通知源端、目的端當前是否處于有效狀態。

(2) 源端收到數據網反饋回來的目的端狀態后,同時檢測源端數據有效、目的端有效、目的端地址等于目標隊列輸出地址等3個條件;若3個條件成立，則開始新的一輪數據發送操作。

3 硬件設計

3.1 信號定義

為實現分布式鏈路控制機制和鏈路生命延長協議,本文在經典PCC網絡基礎上進行硬件改進設計,使用發送控制器和接收控制器完成功能節點到數據網之間的數據格式轉換工作，因此數據網絡協議適用于發送控制器與路由節點之間、路由節點之間、路由節點與接收控制器之間。發送控制器和接收控制器,既可單獨使用,也可成對使用。所設計的片上數據網絡協議由Cmd信號、Data信號和Feedback信號共同實現,其在數據網絡中的組織連接關系如圖4所示。

圖4 數據網組織連接關系

(1) Cmd信號。3位位寬，用于源端向目的端的指令發送,包括源端向路由節點發起的鏈路建立請求、數據有效信號和數據包發送完成信號等。

(2) Data信號。64位位寬，根據Cmd[2]=1時Data信號有效,Data數據有2個功能,在鏈路建立階段低16位承載目的節點坐標,此時Cmd[1:0]=1;在數據傳輸階段用于承載數據,此時Cmd[1:0]=2或3。

(3) Feedback信號。3位位寬，用于目的端向源端的反饋,包括目的端節點向源端節點的狀態反饋、下游路由節點向上游路由節點的反饋、路由節點向源端發送控制器的反饋等。

3.2 硬件實現

由3.1節的介紹可知,本文設計的片上數據網硬件部分由發送控制器、接收控制器和路由器3個部分組成。

3.2.1 發送控制器

發送控制器根據數據網絡協議對功能節點輸出數據進行封包和發送操作,同時完成與路由器之間的握手操作,以及接收主控制器通過配置網下發的目標隊列和其他控制。作為數據傳輸的發起方和傳輸控制方,發送控制器必須能夠應對復雜的傳輸協議,本文設計的發送控制器的核心是一個狀態機,其狀態轉移圖如圖5所示,共設置了10個狀態。

圖5 發送控制器狀態轉移圖

發送控制器復位后處于IDLE狀態,當目標隊列非空且源節點有數據需要發送,即valid信號為高時,進入TRY-TO-CONNECT狀態,此過程中從目標隊列FIFO中取出一個目標的信息,包括目標坐標、包大小和包數量。在TRY-TO-CONNECT狀態等待接收反饋信號,收到的反饋有3種可能:

(1) 鏈路建立失敗,進入CONNECT-FAILED狀態。

(2) 目標節點無效,進入WAIT-CONNECT狀態。

(3) 目標節點有效,進入SEND-BEGIN狀態。

SEDN-BEGIN狀態用于計數包個數,該狀態直接進入SENDING狀態。SENDING狀態用于發送數據,直到當前數據包發送完成進入SEND-END狀態。在SEND-END狀態,若當前節點的包數量達到,則進入NEXT-DST狀態;若源端無效,則進入WAIT-VALID狀態;否則進入WAIT-SEND狀態;在WAIT-SEND狀態等待接收來自目標節點的反饋,若目標節點未準備好接收下一個數據包,則進入WAIT-CONNECT狀態;否則進入TRY-TO-CONNECT狀態。在WAIT-VALID狀態等待源端有數據發送,進入TRY-TO-CONNECT狀態。在WAIT-CONNECT狀態等待收到目的節點準備好的廣播,進入TRY-TO-CONNECT狀態。在NEXT-DST狀態直接進入IDLE狀態。在CONNECT-FAILED狀態等待一定周期數,進入TRY-TO-CONNECT狀態。

3.2.2 路由節點

本文設計的數據網沿用了“包-電路連接”協議,每個路由節點有5個輸入端和5個輸出端,每個方向的輸入/輸出端口連接二維網格中一個方向的相鄰路由器的輸出/輸入端口,每個輸入端有1個輸入控制器用于控制路由方向,其結構如圖6所示。

圖6 路由節點結構

每個方向的Input-controller在需要請求輸出端口時向Arbiter發送請求信號,經過Arbiter裁決后將相應的輸出端口分配給該輸入控制器。若一個輸入控制器請求的端口被別的輸入控制器搶先占用,則無法申請到該輸出端口,裁決器會反饋相應的失敗信號。

Input-controller負責地址的解碼和路由方向選擇,以實現回退轉向路由的功能,其狀態轉移圖如圖7所示,該模塊的狀態機共有8種狀態。

圖7 路由節點狀態轉移圖

路由器復位后進入IDLE狀態,在任何一個狀態如果收到源端的鏈路撤銷請求,即發現源端口斷開,都進入IDLE狀態。在IDLE狀態收到鏈路建立請求進入START-CONNECTING狀態。在START-CONNECTING狀態,若目標地址為本地地址,則進入CONNECT-LOCAL狀態；若目標地址與本地地址在同一行,則進入CONNECT-2nd狀態;否則進入CONNECT-1st狀態。在CONNECT-1st狀態請求左或右端口,若一定周期后未請求到端口,或者收到鏈路失敗的反饋,則進入SWITCH狀態；若收到來自目的端的取消鏈路反饋,則進入CONNECT-CANCELED狀態。在SWITCH狀態判斷若目標地址與本地地址在同一列,則進入FAILED狀態;否則進入CONNECT-2nd狀態。在CONNECT-2nd狀態請求上或下端口,若一定周期后未請求到端口,或者收到鏈路失敗的反饋,則進入FAILED狀態；若收到來自目的端的取消鏈路反饋,則進入CONNECT-CANCELED狀態。在FAILED狀態向上級路由節點反饋鏈路失敗信息,進入IDLE狀態。在CONNECT-CANCELED狀態向上級路由節點反饋鏈路取消的信息,進入IDLE狀態。在CONNECT-LOCAL狀態請求本地端口,若未請求到端口,即裁決器沒有響應,則進入FAILED狀態；若收到來自目的端的未準備反饋,則進入CONNECT-CANCELED狀態。

3.2.3 接收控制器

本文設計的數據網的接收控制器負責將網絡上的數據解包成功能節點可識別的格式并傳輸至功能節點,同時將功能節點的當前狀態送入數據網絡的反饋通道。接收控制器內狀態轉移如圖8所示,共有6個狀態。

圖8 接收控制器狀態轉移圖

接收控制復位后進入IDLE狀態,在任何一個狀態收到源端的鏈路撤銷請求都進入IDLEING狀態；在IDLE狀態收到鏈路建立請求進入CONNECTING狀態。在CONNECTING狀態判斷功能節點是否準備好接收數據,若準備好,則進入SUCCESS狀態;否則進入CANCELED狀態。在CANCELED狀態向路由節點發送鏈路取消的信息,直接進入IDLE狀態。在SUCCESS狀態向路由節點發送鏈路成功的信息,直接進入RECEVING狀態。在RECEVING狀態接收數據并發送給功能節點,直到收到包結束的信號,進入REPORT狀態。在REPORT狀態判斷功能節點是否準備好接收數據。若準備好,則直接進入SUCCESS狀態；若沒有準備好,則進入CANCELED狀態。

4 實驗分析

本文在Xilinx xcuv440-flga2892 FPGA上搭建8×8的網絡用于測試,資源消耗見表1所列。

表1 資源消耗

為了測試該網絡的性能,本文使用傳輸效率、平均延遲和鏈路效率作為性能指標。其中傳輸效率指數據傳輸時間與鏈路占用時間的比值,鏈路占用時間包括鏈路建立時間、數據傳輸時間和鏈路撤銷時間。傳輸效率的計算公式為:

傳輸效率=

(1)

在理想狀態下傳輸效率趨向于1,在負載增大時由于網絡節點出現擁堵,回退轉向路由建立鏈路時間增加會造成傳輸效率下降,傳輸效率越高說明網絡能夠承受越大的負載,網絡吞吐量越大。

平均延遲指從數據準備好發送到開始傳輸的平均時間,平均延遲的計算公式為:

(2)

總延遲為源端和目的端同時準備好到鏈路建立成功之間的時間,平均延遲越低網絡的實時性越高。

鏈路效率指有效鏈路數量與總鏈路數量的比值,為方便統計,本文定義鏈路效率為:

(3)

一般情況下數據包數量即為有效鏈路數量,理想狀態下網絡不發生擁堵，鏈路建立次數等于總鏈路數量,在網絡負載很高的情況下由于發生擁堵導致鏈路失敗重連,鏈路成功率下降。鏈路成功率下降的趨勢反映了網絡負載能力,下降得越慢代表網絡負載能力越高。

針對目標系統的傳輸需求,本實驗將原先網絡與優化后的網絡進行對比測試,分別測試在不同通訊負載下的各個性能指標。

實驗在8×8的NoC上進行,分別測試負載為1～64條鏈路下的性能。原先網絡和優化后的網絡采用相同的隨機負載,模擬資源節點接收緩沖區大小為1 024,數據包長度為512,資源節點運算性能為接口帶寬的1/2,鏈路失敗后重連的等待周期數為256,每批量運算數據量為4 096。由于負載的位置對網絡性能有影響,使用隨機負載的統計結果存在一定的波動,不影響整體性能的分析。

原先網絡和優化后網絡在不同負載下的傳輸效率如圖9所示。

圖9 不同負載下的傳輸效率比較

當負載較小時,網絡不發生擁堵,傳輸效率較為平穩,優化后的網絡傳輸效率略高。當負載較小時，狀態廣播機制可以有效避免目的端未準備時無效的鏈路建立,傳輸效率提升明顯,而Keep-alive通過減小鏈路建立次數也有一定的提升。當負載增加到13/64后，網絡發生擁堵,傳輸效率開始降低,在高負載下，由于鏈路建立成功率降低,Keep-alive協議能夠盡可能高效地使用鏈路,傳輸效率明顯提高,隨著負載增大優化后的網絡優勢越來越明顯,當負載達到100%時，優化后的網絡傳輸效率依然有67%,而優化前的網絡在滿負載時傳輸效率只剩下58%。優化后相比優化前傳輸效率最高提升15%。

在不同負載下平均延遲的比較如圖10所示。

圖10 不同負載下的平均延遲比較

當負載較低時，網絡未發生擁堵,延遲較為穩定。在低負載時，狀態廣播機制可以在目的端準備好后，通過廣播的方式通知源端,從而避免了輪詢機制的高延遲。而沒有狀態廣播機制的網絡需要通過輪詢的方式,延遲有較大不確定性,平均延遲較高。當網絡發生擁堵，平均延遲都顯著提高,而Keep-alive能夠在條件允許時重復使用之前建立的鏈路,從而在再次傳輸時有著極低的延遲,顯著降低了平均延遲。優化后的網絡滿負載下延遲僅為原先的54%。

不同負載下的鏈路效率結果如圖11所示。

圖11 不同負載下的鏈路效率比較

Keep-alive機制通過復用鏈路,在網絡負載較低時鏈路效率有著極高的提升,甚至可以超過100%的鏈路效率。狀態廣播機制在網絡發生擁堵時減少目的端未準備時無效的鏈路嘗試,避免加劇網絡擁堵,從而提升一部分鏈路效率。綜合2種方法優化后的網絡在各種負載下都有較為明顯的鏈路效率的提升。

在滿負載下測試不同數據包長度下的網絡效率，結果如圖12所示。在數據包長度極小時傳輸效率都趨向于0,在數據包長度較小時傳輸效率主要受鏈路建立時間影響,Keep-alive協議通過減少鏈路建立次數而獲得一定的優勢;在數據包長度極大的時候傳輸效率主要受鏈路成功率的影響,狀態廣播機制通過減小無效嘗試次數減輕網絡擁堵,鏈路成功率較高。優化后的網絡在不同數據包長度下的傳輸效率都有不同程度的提升。

5 結 論

本文在傳統包-電路交換技術框架的網絡下,增加了Keep-alive協議和狀態廣播機制,利用網絡中現有的配置網和狀態網提高了網絡傳輸性能。Keep-alive協議通過省去向同一個目的節點發包的鏈路建立過程,減小了后續數據包的傳輸延遲,也避免了建立鏈路過程中對網絡的占用,減緩網絡擁堵情況。狀態廣播機制解決傳統網絡中失敗后輪詢的弊端,減小網絡中非有效數據傳輸行為的占用率,從而極大地提高了網絡性能。

實驗表明,新的機制有完整的功能,應對復雜的網絡狀況有足夠的魯棒性,不會產生死鎖,其性能相比傳統方案有最多13%的提升。