康子揚，彭凌輝，周 干，林 博，王 蕾

(國防科技大學計算機學院,湖南 長沙 410073)

1 引言

在摩爾定律[1]驅(qū)動下，單位面積芯片可承載的晶體管數(shù)量不斷增多，計算機的計算能力與存儲能力呈指數(shù)級上升?；隈T·諾依曼體系結(jié)構(gòu)的處理器時鐘頻率和性能不斷上升，但是存儲器訪問速度卻增長緩慢，導致處理器與存儲器之間的鴻溝越來越大，造成“存儲墻”瓶頸。因此，亟需新的計算模式及其體系結(jié)構(gòu)來滿足日益增長的計算性能需求。

類腦計算[2]沒有沿用經(jīng)典的馮·諾依曼體系結(jié)構(gòu)，而是從全新的角度出發(fā)，探索更高效的計算方法。類腦計算以腦科學研究為基礎(chǔ)，參考人類大腦皮層神經(jīng)細胞的工作機制，并將其映射為實際的物理器件。

脈沖神經(jīng)網(wǎng)絡(luò)SNN(Spiking Neural Network)[3]的提出讓類腦處理器的計算模式上升到了一個新的高度。在20世紀90年代，神經(jīng)生物學家們發(fā)現(xiàn)，神經(jīng)元細胞的軸突會發(fā)射出一系列電脈沖，這些脈沖通過軸突傳遞給其它的神經(jīng)元，其它神經(jīng)元在接收到脈沖后，或是被抑制，或是被激活，被激活的神經(jīng)元照此繼續(xù)向下傳遞脈沖。大腦通過這些突發(fā)的電脈沖，讓神經(jīng)元細胞相互激活和抑制，進行著復(fù)雜信息的傳遞。這種采用脈沖進行信息傳遞的模式被發(fā)現(xiàn)后，脈沖神經(jīng)網(wǎng)絡(luò)的概念被提出。這種網(wǎng)絡(luò)模式具有更真實的生物特性，并能更好地凸顯人腦低功耗的特點。

大部分類腦處理器上運行的是SNN[4]。一個路由器節(jié)點下面會掛載一個神經(jīng)元核，而一個神經(jīng)元核里面會包含數(shù)千個神經(jīng)元。我們將成千上萬的神經(jīng)元進行實際的物理硬件映射，將通信量大的神經(jīng)元放在一起封裝成神經(jīng)元核，從而盡可能地增加核內(nèi)通信，減少核間通信。但是，神經(jīng)元核并不能包含太多的神經(jīng)元，否則單核內(nèi)的布局布線互連會成為問題。所以，核間通信仍然大量存在。

對于類腦處理器，當有神經(jīng)元被觸發(fā)后，會向所有與它連接的神經(jīng)元發(fā)送脈沖報文，類腦處理器會花費若干個邏輯時鐘去處理當前時間步產(chǎn)生的事件，將所有的脈沖發(fā)送到目標神經(jīng)元核并完成相應(yīng)的計算。圖1為不同時間步下神經(jīng)元的放電行為統(tǒng)計?？梢钥闯鯯NN有著短時猝發(fā)的通信特點。在這些時間步內(nèi)，大量的神經(jīng)元同時發(fā)出脈沖，核間通信出現(xiàn)短時猝發(fā)激增情況，使片上網(wǎng)絡(luò)短時間內(nèi)發(fā)生擁塞。所以，如何快速解決短時猝發(fā)情況是類腦處理器的片上網(wǎng)絡(luò)NoC(Network on Chip)[5]設(shè)計亟待解決的問題。

Figure 1 Discharge behavior of neurons at different time steps圖1 不同時間步下神經(jīng)元的放電行為

本文針對類腦計算由于短時、猝發(fā)而導致片上網(wǎng)絡(luò)擁塞的情況，提出了基于哈密爾頓路徑[6]的擁塞感知自適應(yīng)路由算法。相對于沒有擁塞感知的哈密爾頓最短路徑算法，在數(shù)量猝發(fā)模式和概率猝發(fā)模式下，本文提出的擁塞感知路由算法使得片上網(wǎng)絡(luò)NoC的平均延遲分別降低了13.9%和15.9%，吞吐率分別提高了21.6%和16.8%。

2 背景

2.1 片上網(wǎng)絡(luò)

SoC(System on Chip)即片上系統(tǒng)[7]，它是信息系統(tǒng)核心的芯片集成，將系統(tǒng)關(guān)鍵部件集成在一塊芯片上。這樣不僅能更加充分地利用芯片的資源，而且還能縮短組件之間的連線，從而降低系統(tǒng)的延遲，提高系統(tǒng)的穩(wěn)定性。

一個系統(tǒng)里有許多組件，這些組件稱為處理單元PE(Processing Element)。以高性能處理器為例，PE不僅指處理器核，還包括片上其它組件,如IO接口和內(nèi)存接口。任意2個PE均有可能通信，比如處理器核就一定會和內(nèi)存進行通信。若每一個核都與內(nèi)存接口互連，那么將會使用大量的資源去連線，這是極不合理的。為了使SoC高效互連，片上網(wǎng)絡(luò)NoC的通信模式被提出。NoC是片上專門負責PE之間通信的組件，將系統(tǒng)中所有的組件都掛載在NoC上，PE間再根據(jù)不同的通信協(xié)議進行通信。這樣的通信模式，能極大地優(yōu)化布局布線和減少功耗。

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

基本的NoC設(shè)計空間[8]包括拓撲結(jié)構(gòu)、路由算法、流控機制和路由器微體系結(jié)構(gòu)設(shè)計。

常用的拓撲結(jié)構(gòu)有環(huán)網(wǎng)、二維Mesh和二維Torus[9]等，圖2為二維Mesh結(jié)構(gòu)。網(wǎng)絡(luò)的拓撲結(jié)構(gòu)決定了網(wǎng)絡(luò)節(jié)點的實際物理分布和節(jié)點間的連接關(guān)系。為了使芯片能更好地布局布線，結(jié)構(gòu)規(guī)整的二維Mesh網(wǎng)絡(luò)被廣泛應(yīng)用在多核領(lǐng)域。

Figure 2 2D Mesh network圖2 二維Mesh網(wǎng)絡(luò)結(jié)構(gòu)

路由算法[10]是根據(jù)網(wǎng)絡(luò)上數(shù)據(jù)包所攜帶的信息及當前路由器坐標信息，對數(shù)據(jù)包進行路由計算，得到下一跳的路徑。路由算法必須與網(wǎng)絡(luò)結(jié)構(gòu)相適應(yīng)，否則容易產(chǎn)生死鎖。路由算法包括確定性路由和自適應(yīng)路由。確定性路由中當前節(jié)點到目的節(jié)點的路徑是確定的。如XY路由，在二維Mesh的XY路由算法下，數(shù)據(jù)包先進行X方向傳輸，當X方向匹配時再進行Y方向傳輸。XY路由存在的問題也很明顯[11],在網(wǎng)絡(luò)規(guī)模較大時，網(wǎng)絡(luò)一旦擁堵，邊緣和角落節(jié)點的吞吐率大大降低，網(wǎng)絡(luò)的負載大部分由中部區(qū)域承擔，從而增大了延遲，且降低了吞吐率。與確定性路由相比，自適應(yīng)路由的路徑選擇則不是固定的[12]，算法會根據(jù)當前網(wǎng)絡(luò)節(jié)點的狀態(tài)進行路徑選擇，但會更容易出現(xiàn)死鎖問題。

流控機制為數(shù)據(jù)包分配資源。常用的流控機制包括虛通道、存儲轉(zhuǎn)發(fā)和蟲孔路由[13]。

路由器微體系結(jié)構(gòu)直接決定了路由器節(jié)點所需要的資源、面積、功耗和延遲等。圖3為一個簡單的片上網(wǎng)絡(luò)節(jié)點路由器結(jié)構(gòu)，其組成包括5個輸入端口緩沖(分別連接東南西北4個方向的路由器，以及本地PE)、交叉開關(guān)和輸出端口等部件。

Figure 3 Router structure of NoC圖3 片上網(wǎng)絡(luò)路由器結(jié)構(gòu)

網(wǎng)絡(luò)拓撲結(jié)構(gòu)一旦確定，其物理連接和物理實現(xiàn)便不能再改變。所以，更靈活的路由算法能夠使網(wǎng)絡(luò)在相同的拓撲結(jié)構(gòu)、不同的應(yīng)用場景下都能取得更好的性能，以最小的代價獲得相對最大的收益。

2.3 哈密爾頓最短路徑路由算法

哈密爾頓路徑[14]對網(wǎng)絡(luò)中的每個節(jié)點只訪問一次。如圖4所示，每個節(jié)點都會有唯一的坐標Rnum(x，y)。對于m×n的網(wǎng)絡(luò)，會給每一個節(jié)點都分配一個編號num。對于每個節(jié)點的num，我們可以根據(jù)坐標(x，y)計算獲得。若y為偶數(shù)，則num=x+y×n;若y為奇數(shù)，則num=(y+1)×n-x-1。

Figure 4 Node coordinates and Hamilton labels圖4 節(jié)點坐標與哈密爾頓標簽

在二維Mesh NoC中，任意2個路由節(jié)點之間存在通信需求，可以按照哈密爾頓路徑傳輸數(shù)據(jù)包。與此同時，任意2個路由節(jié)點通過雙向鏈路連接，可以同時相互傳遞信息。因此，根據(jù)每個路由節(jié)點的編號，我們將網(wǎng)絡(luò)分成2個子網(wǎng)，即高通道子網(wǎng)H和低通道子網(wǎng)L。在高通道子網(wǎng)中，數(shù)據(jù)包沿著節(jié)點編號嚴格增大的方向進行傳輸。在低通道子網(wǎng)中，數(shù)據(jù)包沿著節(jié)點編號嚴格減小的方向進行傳輸。

圖5a中,R2到R9經(jīng)過的路徑可以是(2-3-4-5-6-7-8-9)。此時能清楚地看到，這樣的傳輸路徑并不是最短路徑。R2到R9一共走了7跳，在XY路由中，只需要3跳,即(2-1-6-9)，顯然該傳輸方法的效果不盡人意。于是按最小路徑的決策，并且依然按照num嚴格增大的規(guī)則，便產(chǎn)生了“捷徑路徑”。如圖5b的最短路徑中，從R2到R9，捷徑路徑是(2-5-6-9),同樣是3跳，且沒有打破num嚴格增大的規(guī)則。捷徑路徑并不唯一，比如從R1到R11，就有3條捷徑路徑，分別是(1-2-3-4-11)、(1-2-5-10-11)和(1-6-9-10-11),都是4跳。低通道子網(wǎng)L同理。

Figure 5 Two transmission paths in high channel subnet圖5 高通道子網(wǎng)中的2種傳輸路徑

對于捷徑的選擇，本文按照某一方式來選擇。本文采用先進行列匹配，再進行行匹配的方法。仍以R1到R11為例，數(shù)據(jù)包先從R1橫向傳輸?shù)絉3，再縱向傳輸?shù)絉11。值得注意的是，基于這樣的最短路徑選擇方法，并沒有將網(wǎng)絡(luò)約束為單純的XY路由。以R2到R6為例，其捷徑路徑為(2-5-6)，是先進行Y方向路由，再進行X方向路由。本文按照以上最短路徑的策略來設(shè)計路由算法，比不走捷徑的策略效果要好，而且不同于傳統(tǒng)的XY路由。

2.4 死鎖

死鎖[15]是片上網(wǎng)絡(luò)設(shè)計必須解決的問題。死鎖的本質(zhì)問題，就是依賴關(guān)系產(chǎn)生了環(huán)。如圖6所示，各個節(jié)點分別向箭頭所指節(jié)點發(fā)送請求。R0的資源釋放取決于R1的資源釋放，R1的資源釋放取決于R2，R2的資源釋放取決于R3,R3的資源釋放取決于R0，依次形成環(huán)路。當前資源無法釋放導致下一級資源無法釋放，導致網(wǎng)絡(luò)出現(xiàn)死鎖。

Figure 6 Deadlock圖6 死鎖

3 擁塞感知路由算法

本文基于哈密爾頓單播路由算法，研究擁塞感知的路由算法，優(yōu)化類腦處理器片上網(wǎng)絡(luò)的通信性能。

最短路徑策略的路由算法以捷徑為優(yōu)先，在所有節(jié)點猝發(fā)的情況下，網(wǎng)絡(luò)會在短時間內(nèi)陷入擁塞。所以，如何在擁塞的情況下高效地進行傳輸，是本文要解決的問題。

本文以擁塞感知[16]為出發(fā)點，當前節(jié)點路由器會感知自己相鄰節(jié)點路由器的鏈路buffer是否空閑。如圖7所示，當前節(jié)點會獲得相鄰節(jié)點輸入FIFO的full信號。然后路由算法會根據(jù)4個相鄰方向full信號的情況，實時選擇下一跳出口。路由算法會在符合算法策略的前提下選擇full信號為0的方向進行傳輸。

Figure 7 Congestion-aware mechanism圖7 擁塞感知機制

本文提出的擁塞感知路由算法是在哈密爾頓最短路徑路由算法基礎(chǔ)上進行了優(yōu)化。傳統(tǒng)的哈密爾頓最短路徑路由算法嚴格按照節(jié)點標簽增加或減少的方向進行數(shù)據(jù)傳輸。當網(wǎng)絡(luò)產(chǎn)生擁塞時，路由器不能進行傳輸方向調(diào)整，限制了NoC的性能。為了提升數(shù)據(jù)包的傳輸效率，本文對這一規(guī)則進行了優(yōu)化，允許路由器在選擇最短路徑時，根據(jù)網(wǎng)絡(luò)狀態(tài)及時調(diào)整傳輸方向。本文在算法優(yōu)化后選擇的路徑也是最短路徑。

上述優(yōu)化是指一個通道到另一個通道的單向通信，即高通道進入低通道或者低通道進入高通道。若2個通道之間可以互相進行傳輸，則會產(chǎn)生死鎖。

因此，本文的算法優(yōu)化采用的是從低通道進入高通道的優(yōu)化方案。以圖5中R10到R6為例，數(shù)據(jù)包在R10，數(shù)據(jù)包目的地為R6，若按照本文提到的先列匹配，再行匹配的哈密爾頓最短路徑路由算法，路徑將是(10-9-6)。加入擁塞檢測優(yōu)化后，R10將對通向R9和R5的鏈路進行比較，當R10西面方向擁塞時，便將數(shù)據(jù)包向北傳輸,然后再由R5傳輸?shù)絉6。(10-5-6)的路徑打破了嚴格增大或減小的規(guī)則，但是不會死鎖，后面將會進行證明。同理，從R6到R2，R6根據(jù)東面方向和北面方向擁塞情況進行選擇。路徑原本應(yīng)該是(6-5-2)，當東面方向擁塞時，則向北方向傳輸?shù)絉1，再到R2。當網(wǎng)絡(luò)面對擁塞時，為了提高鏈路利用率，降低延遲，選擇將數(shù)據(jù)包跳轉(zhuǎn)到另一個子網(wǎng)進行路由，以緩解當前子網(wǎng)壓力。

當網(wǎng)絡(luò)不擁塞時，路由算法按照節(jié)點標簽增加或減少的方向傳輸數(shù)據(jù)。當網(wǎng)絡(luò)出現(xiàn)擁塞時，數(shù)據(jù)包從低通道進入高通道進行傳輸，以緩解當前子網(wǎng)的通信壓力。因此，當路由器接收到數(shù)據(jù)包后，它會根據(jù)路由器的坐標的奇偶行，選擇不同的路由算法確定其傳輸方向，以避免路由死鎖的出現(xiàn)。具體的算法實現(xiàn)如算法1和算法2所示。

算法1擁塞感知路由算法(偶數(shù)行)Routing_even

輸入:(Cx,Cy), (Dx,Dy),eastfull,westfull,southfull,northfull。/*(Cx,Cy)為當前節(jié)點坐標;(Dx,Dy)為目的節(jié)點坐標;eastfull,westfull,southfull,northfull為buffer滿信號*/

輸出:Dout。

1:Δx=Dx-Cx,Δy=Dy-Cy;

2://當前處于偶數(shù)行

3:ifCy==0then

4:ifΔy> 0then

5:ifΔx< 0then

6:ifsouthfull==1 ANDwestfull==0then

7:Dout=WEST;

8:else

9:Dout=SOUTH;

10:endif;

11:endif;

12:ifΔx> 0then

13:Dout=EAST;

14:endif;

15:ifΔx==0then

16:Dout=SOUTH;

17:endif;

18:endif;

19:ifΔy== 0then

把兩種根本對立的角色放在一起進行描述，對比鮮明，好壞鮮明，使讀者很容易分辨出好壞、分辨是非、明確立場。運用這種手法，有利于充分展示雙方的矛盾立場，突現(xiàn)事物的本質(zhì)特征，加強文章的藝術(shù)效果和感染力，有效地傳遞了人物的情感特點，從而把感情抒發(fā)得淋漓盡致，凸顯人物特點。

20:ifΔx< 0then

21:Dout=WEST;

22:endif;

23:ifΔx> 0then

24:Dout=EAST;

25:endif;

27:Dout=LOCAL;

28:endif;

29:endif;

30:ifΔy< 0then

31:ifΔx< 0then

32:ifwestfull==1 ANDnorthfull==0then

33:Dout=NORTH;

34:else

35:Dout=WEST;

36:endif;

37:else

38:Dout=NORTH;

39:endif;

40:endif;

41:endif

算法2擁塞感知路由算法(奇數(shù)行)Routing_odd

輸入:(Cx,Cy), (Dx,Dy),eastfull,westfull,southfull,northfull。/*(Cx,Cy)為當前節(jié)點坐標；(Dx,Dy)為目的節(jié)點坐標;eastfull,westfull,southfull,northfull為buffer滿信號*/

輸出:Dout。

1:Δx=Dx-Cx,Δy=Dy-Cy；

2://當前處于奇數(shù)行

3:ifCy==0then

4:ifΔy> 0then

5:ifΔx> 0then

6:ifsouthfull==1 ANDeastfull==0then

7:Dout=EAST；

8:else

9:Dout=SOUTH；

10:endif；

11:endif；

12:ifΔx< 0then

13:Dout=WEST；

14:endif；

15:ifΔx==0then

16:Dout=SOUTH；

17:endif；

18:endif；

19:ifΔy== 0then

20:ifΔx< 0then

21:Dout=WEST；

22:endif；

23:ifΔx> 0then

24:Dout=EAST；

25:endif；

26:ifΔx== 0then

27:Dout=LOCAL；

28:endif；

29:endif；

30:ifΔy< 0then

31:ifΔx> 0then

32:ifeastfull==1 ANDnorthfull==0then

33:Dout=NORTH；

34:else

35:Dout=EAST；

36:endif；

37:else

38:Dout=NORTH；

39:endif；

40:endif；

41:endif

4 無死鎖證明

本文通過證明通道依賴圖CDG(Channel Dependence Graph)是無環(huán)的[17]來證明優(yōu)化算法是無死鎖的。首先，將相鄰的2個節(jié)點構(gòu)建成2個通道，如0號節(jié)點和1號節(jié)點構(gòu)建的通道為(0,1)和(1,0)。然后,再根據(jù)本文算法判斷相鄰的通道間是否存在通道依賴。例如，路徑(10-5-6)符合算法策略，則通道(10,5)和通道(5,6)存在通道依賴；路徑(6-9-8)不符合算法策略，則通道(6,9)和通道(9,8)不存在通道依賴。最后統(tǒng)計出所有的通道依賴得到算法的CDG。本文以4×4規(guī)模NoC為例構(gòu)造了所提算法的CDG,如圖8所示?？梢钥闯?，通道依賴圖是無環(huán)的，即表明本文所提算法無死鎖。

Figure 8 Channel dependence graph圖8 通道依賴圖

5 實驗與結(jié)果

本文為了驗證提出的擁塞感知的哈密爾頓單播路由算法的可行性和有效性，采用Verilog HDL搭建網(wǎng)絡(luò)，NoC的設(shè)置如表1所示。

Table 1 Experimental setup

為了更好地模擬類腦計算應(yīng)用中的短時猝發(fā)情況，本文模擬2種發(fā)包情況。第1種情況是數(shù)量猝發(fā)模式，以單節(jié)點注入數(shù)量為變量;第2種情況是概率猝發(fā)模式，以單節(jié)點注入概率為變量。在16×16的NoC上，分別測得哈密爾頓最短路徑路由算法和實現(xiàn)擁塞感知哈密爾頓路由算法的平均延遲和吞吐率。

圖9和圖10是第1種情況下每個節(jié)點連續(xù)、隨機發(fā)送100～2 000個數(shù)據(jù)包得到的優(yōu)化前后平均延遲和吞吐率的結(jié)果。

Figure 9 Average delay comparison under different packet numbers圖9 不同數(shù)據(jù)包數(shù)量下平均延遲對比

Figure 10 Throughput comparison under different packet numbers圖10 不同數(shù)據(jù)包數(shù)量下吞吐率對比

圖11和12是第2種情況下每個節(jié)點分別以相同的概率隨機發(fā)送數(shù)據(jù)包得到的優(yōu)化前后平均延遲和吞吐率的結(jié)果。

Figure 11 Average delay comparison under different probability burst modes圖11 不同概率猝發(fā)模式下平均延遲對比

Figure 12 Throughput comparison under different probability burst modes圖12 不同概率猝發(fā)模式下吞吐率對比

從圖9～圖12可以看出，隨著網(wǎng)絡(luò)注入壓力的增大，擁塞檢測機制能夠提高鏈路利用率，從而有效緩解網(wǎng)絡(luò)壓力，減少平均延遲，增大網(wǎng)絡(luò)吞吐率。

6 結(jié)束語

本文針對類腦處理器的片上網(wǎng)絡(luò)報文猝發(fā)問題，研究了類腦處理器的片上網(wǎng)絡(luò)擁塞控制方法，并基于哈密爾頓最短路徑路由算法，提出了一種實時擁塞感知、無死鎖的哈密爾頓路由算法，在網(wǎng)絡(luò)猝發(fā)、短時間內(nèi)陷入擁堵時更好地緩解了網(wǎng)絡(luò)壓力，提升了網(wǎng)絡(luò)性能。最后，通過Verilog HDL建模，實現(xiàn)了路由算法，通過行為級仿真，與沒有擁塞感知的情況進行了對比。實驗結(jié)果表明，加入擁塞感知對網(wǎng)絡(luò)性能會有較大提升。本文的研究成果能夠應(yīng)用到類腦計算等通信量大、通信模式較為復(fù)雜的通信場景，具有廣泛的應(yīng)用前景。由于SNN具有一到多的通信特點，單播路由算法能力有限，因此，在未來的工作中，將設(shè)計并實現(xiàn)擁塞感知的多播哈密爾頓路由算法，以進一步提升類腦處理器片上網(wǎng)絡(luò)的性能。