片上網(wǎng)絡(luò)擁塞感知算法研究

才華，楊勇，李洋

（長春理工大學(xué)，長春 130022）

半導(dǎo)體技術(shù)的發(fā)展使一塊芯片上集成了越來越多的功能，可以在一片芯片上實現(xiàn)系統(tǒng)級功能，形成片上系統(tǒng)。但是，隨著深亞微米技術(shù)的發(fā)展，芯片內(nèi)互聯(lián)延時、信號線上碼間干擾、芯片功耗和散熱問題等日益嚴(yán)重。片上網(wǎng)絡(luò)技術(shù)（Network on Chip NoC）［1］作為一種有效的解決問題新方法，日益得到人們的重視，通過基于互聯(lián)的分布式處理，提高了處理性能，同時降低了現(xiàn)在集中式處理。

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

片上網(wǎng)絡(luò)改變了以往數(shù)字系統(tǒng)基于總線結(jié)構(gòu)和全局時鐘樹的設(shè)計模式，采用片內(nèi)分布式設(shè)計，片上網(wǎng)絡(luò)系統(tǒng)由節(jié)點和節(jié)點間鏈路構(gòu)成網(wǎng)絡(luò)系統(tǒng)，其中節(jié)點除了具有處理器、存儲器等具體硬件功能外，還包含一個具有轉(zhuǎn)發(fā)功能的路由器。片上網(wǎng)絡(luò)中的通信數(shù)據(jù)，以包的形式經(jīng)過路由器和鏈路在節(jié)點間傳遞，網(wǎng)絡(luò)拓?fù)?、路由算法、流量控制是其片上網(wǎng)絡(luò)體系中關(guān)鍵技術(shù)［2］。

1.1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)定義為在NoC網(wǎng)絡(luò)環(huán)境下，鏈路和節(jié)點在物理結(jié)構(gòu)上的組織排列，常用的拓?fù)浣Y(jié)構(gòu)如圖1所示。拓?fù)浣Y(jié)構(gòu)決定了數(shù)據(jù)包交換的路徑，是路由算法和流控策略得以實現(xiàn)的基礎(chǔ)。

在拓?fù)浣Y(jié)構(gòu)中，每個節(jié)點與鏈路連接的數(shù)目，直接影響了片上網(wǎng)絡(luò)中有效路徑數(shù)量，路徑豐富的拓?fù)浣Y(jié)構(gòu)，在相同注入率下，可以得到更短的時延，反之，網(wǎng)絡(luò)容易發(fā)生擁塞，致使網(wǎng)絡(luò)飽和。但是，在設(shè)計網(wǎng)絡(luò)拓?fù)鋾r，除了考慮網(wǎng)絡(luò)性能外，還需要考慮實際制造的成本，尤其是片上互聯(lián)線的密度和長度，以及由此帶來的功耗和面積等問題。所以，在二維結(jié)構(gòu)中，mesh和torus結(jié)構(gòu)是常用的拓?fù)浣Y(jié)構(gòu)，現(xiàn)在也在研究三維拓?fù)浣Y(jié)構(gòu)［3］。

圖1 片上網(wǎng)絡(luò)常用的拓?fù)浣Y(jié)構(gòu)Fig.1 Topology in the network on chip

1.2 路由算法

路由算法是在特定的拓?fù)浣Y(jié)構(gòu)下為一條數(shù)據(jù)流選擇從源節(jié)點到目的節(jié)點通過的路徑。路由算法的選擇是影響片上網(wǎng)絡(luò)性能的重要因素之一，在設(shè)計路由算法時，要盡量使每個數(shù)據(jù)流在片上網(wǎng)絡(luò)的鏈路上均勻分布，避免數(shù)據(jù)集中到某個節(jié)點或鏈路，產(chǎn)生擁塞，這樣才能達(dá)到網(wǎng)絡(luò)設(shè)計的最大吞吐率，常用的路由方法有X-Y路由，顯式路由和自適應(yīng)路由［4］，Mesh拓?fù)浣Y(jié)構(gòu)下由節(jié)點A到節(jié)點B的三種路由如圖2所示。其中黑色實心節(jié)點代表擁塞節(jié)點。

圖2 片上網(wǎng)絡(luò)常用的路由算法Fig.2 Network-on-chip routing algorithm

X-Y路由算法是一種簡單的路由策略，數(shù)據(jù)流首先由源節(jié)點沿著一維方向（X維或Y維）到達(dá)目的節(jié)點所在的此維終點，然后再沿著另一維方向前進(jìn)。顯式路由算法在路由之前已經(jīng)確定了源節(jié)點和目的節(jié)點之的多條路由路徑，每次路由時隨機(jī)選取其中

一條路徑。X-Y路由算法和顯式路由算法都沒有考慮網(wǎng)絡(luò)當(dāng)前的狀態(tài)，屬于簡單路由算法，即使是前進(jìn)的節(jié)點發(fā)生擁塞，也按照既定的路由策略尋找路徑。自適應(yīng)路由是復(fù)雜的路由算法，自適應(yīng)路由會根據(jù)當(dāng)前網(wǎng)絡(luò)擁塞狀態(tài)，按照路由規(guī)則選擇最佳路由路徑。由于自適應(yīng)路由算法只是根據(jù)當(dāng)前節(jié)點信息判斷路由策略，可能會引起死鎖或活鎖現(xiàn)象。因此，具有全局擁塞信息和擁塞感知機(jī)制的路由算法成為研究熱點，本論文提出的就是具有全局網(wǎng)絡(luò)狀態(tài)信息的擁塞感知算法。

1.3 流控策略

流控策略定義為在片上網(wǎng)絡(luò)環(huán)境中，如何為數(shù)據(jù)包在傳輸過程中分配帶寬、緩沖容量等片上資源。一個節(jié)點中的流控過程如圖3所示。

圖3 一個節(jié)點內(nèi)流控示意圖Fig.3 Diagram of flow control in one node

在片上網(wǎng)絡(luò)中，片上資源為緩存器、鏈路、狀態(tài)寄存器等內(nèi)容，流控策略就是要高效的分配這些資源，構(gòu)成數(shù)據(jù)流傳輸時的邏輯鏈路，達(dá)到網(wǎng)絡(luò)最大的吞吐量和數(shù)據(jù)包傳輸時最小的時延。根據(jù)緩沖使用程度，流控策略可分為［4］，最簡單的流控機(jī)制是無緩存機(jī)制，由于不能暫時存儲，一次只能處理一個數(shù)據(jù)包，多余的數(shù)據(jù)包或者丟棄或者采用隨機(jī)路由處理。電路交換是簡單存儲流控，電路交換機(jī)制中，只是存儲數(shù)據(jù)包的頭信息，通過數(shù)據(jù)包的頭信息建立通信路徑，在發(fā)生擁塞的節(jié)點，數(shù)據(jù)包的頭信息會一直等到資源釋放，直至建立完整的通信路徑；最為高效的流控機(jī)制是基于緩存的存儲-轉(zhuǎn)發(fā)機(jī)制的流控，利用緩存去處數(shù)據(jù)的耦合性，同時可以采用蟲洞交換和虛通道等技術(shù)，提高網(wǎng)絡(luò)吞吐量。

2 基于神經(jīng)網(wǎng)絡(luò)的擁塞控制算法

片上網(wǎng)絡(luò)中的諸多關(guān)鍵技術(shù)，目標(biāo)都是追求網(wǎng)絡(luò)的最大吞吐率和數(shù)據(jù)包傳輸最小延時。但是，當(dāng)網(wǎng)絡(luò)發(fā)生擁塞，會直接影響網(wǎng)絡(luò)性能，因此，在擁塞控制中，會綜合考慮網(wǎng)絡(luò)拓?fù)洹⒙酚伤惴ê土骺夭呗浴?/p>

2.1 現(xiàn)有擁塞控制算法分析

文獻(xiàn)［5］提出了一種近似擁塞感知技術(shù)進(jìn)行擁塞控制，這種方法是由路由節(jié)點的交換機(jī)接收臨近節(jié)點交換機(jī)的流量壓力信息，根據(jù)周圍節(jié)點的通信狀態(tài)，再做出本節(jié)點路由和流控的判斷，采用這種方法避免擁塞區(qū)域的發(fā)生。但是，這種方法缺少全局信息，不能充分利用整個網(wǎng)絡(luò)的整體資源和性能。文獻(xiàn)［6］提出在緩沖區(qū)控制和帶寬分配上進(jìn)行擁塞控制，雖然這種方法能夠在容錯控制上分為不同級別，導(dǎo)致不同區(qū)域和功耗的權(quán)衡，但是邏輯控制稍顯復(fù)雜。一個高效的擁塞控制機(jī)制，要能夠根據(jù)網(wǎng)絡(luò)中全局狀態(tài)，使數(shù)據(jù)流均勻分布在節(jié)點和鏈路間，避免“熱點”及其區(qū)域的出現(xiàn)。本文根據(jù)片上網(wǎng)絡(luò)關(guān)鍵技術(shù)和神經(jīng)網(wǎng)絡(luò)可以并行化處理信息的特點，采用神經(jīng)網(wǎng)絡(luò)感知網(wǎng)絡(luò)上數(shù)據(jù)分布狀態(tài)，根據(jù)此信息，調(diào)整路由及流控策略，降低擁塞發(fā)生概率，達(dá)到網(wǎng)絡(luò)最大的吞吐率。

2.2 基于神經(jīng)網(wǎng)絡(luò)的擁塞預(yù)測算法分析

神經(jīng)網(wǎng)絡(luò)提供一種可以進(jìn)行并行信息處理的機(jī)制，由神經(jīng)元及其之間互聯(lián)構(gòu)成。神經(jīng)元是計算節(jié)點，互聯(lián)完成計算節(jié)點之間的連接［7］。本論文采用采用兩個步驟選擇擁塞節(jié)點，第一部分是判斷擁塞節(jié)點所在的維，利用多感知層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，第一層為漢明網(wǎng)絡(luò)，計算片上網(wǎng)絡(luò)中每一維鏈路的資源使用狀況，第二層競爭網(wǎng)，從漢明網(wǎng)中尋找資源使用最大的一維，第二個步驟是在確定的維中尋找擁塞節(jié)點。擁塞控制如圖4所示。

圖4 擁塞感知控制流程圖Fig.4 Diagram of congestion aware control

擁塞感知網(wǎng)絡(luò)結(jié)構(gòu)如圖5所示。

圖5 擁塞感知神經(jīng)網(wǎng)絡(luò)Fig.5 Congestion-aware neural network

神經(jīng)網(wǎng)絡(luò)的輸入為片上網(wǎng)絡(luò)中某一維節(jié)點擁塞狀態(tài)，權(quán)矩陣W為輸入擁塞狀態(tài)前一時刻狀態(tài)值，初始狀態(tài)為0，hamming網(wǎng)計算兩者上取整差之后的hamming距離，得到中間節(jié)點，后面的競爭網(wǎng)絡(luò)是除了反饋的權(quán)值為1外，其余的為-ε的Maxnet，經(jīng)過Maxnet算子可以得到中間節(jié)點的一個最大輸出［8］，即得到片上網(wǎng)絡(luò)通信過程中，數(shù)據(jù)流量增加最大的一維，然后在這維中，依次找到占用資源最多的節(jié)點，即可得到潛在的最可能發(fā)生擁塞的節(jié)點。

3 仿真結(jié)果與分析

在仿真分析中，采用SystemC建模，構(gòu)建8×8 Mesh NoC模型，片上網(wǎng)絡(luò)數(shù)據(jù)流模型采用均勻分布模型，即每個節(jié)點等概率發(fā)送數(shù)據(jù)包，路由算法采用改進(jìn)的X-Y路由，當(dāng)擁塞節(jié)點與路由方向在第一個前進(jìn)維同向時，數(shù)據(jù)包臨時轉(zhuǎn)向另一維一次，避開擁塞節(jié)點；當(dāng)擁塞節(jié)點與路由方向在第二個前進(jìn)維同向時，路由算法令數(shù)據(jù)流暫存于所在節(jié)點，等待直至擁塞釋放。

圖6 數(shù)據(jù)包平均延時曲線Fig.6 Average delay of packet transmission

仿真比較了兩種片上網(wǎng)絡(luò)性能曲線，圖6顯示的是數(shù)據(jù)包傳輸延時與注入率關(guān)系，圖7顯示的是網(wǎng)絡(luò)吞吐率與注入率關(guān)系，分別于標(biāo)準(zhǔn)X-Y路由進(jìn)行比較。

圖7 片上網(wǎng)絡(luò)吞吐率曲線Fig.7 Throughput of Network on Chip

在圖6中，當(dāng)在較低注入率時，由于網(wǎng)絡(luò)空間很大，兩者性能接近，在較高注入率時，網(wǎng)絡(luò)接近飽和，網(wǎng)絡(luò)平均時延都急劇增加，當(dāng)處于中間狀態(tài)時，能夠進(jìn)行擁塞感知的算法性能優(yōu)于標(biāo)準(zhǔn)X-Y路由。在圖7中，擁塞感知控制算法，帶來15%關(guān)于網(wǎng)絡(luò)吞吐率性能提高。

4 結(jié)語

本文提出的感知全局擁塞狀態(tài)的方法，可以更加有效的提高片上網(wǎng)絡(luò)性能，在中度飽和的網(wǎng)絡(luò)環(huán)境，可以降低數(shù)據(jù)包傳輸時延，同時提高網(wǎng)絡(luò)的吞吐率。

［1］K Goossens，J Dielissen.Aethereal network on chip：Concepts，architectures，and implementations ［J］.IEEE Des.Test Comput.，2005，22（5）：414-421.

［2］A Hansson，K Goossens.A unified approach to constrained mapping and routing on network-on-chip architectures［J］.in Proc.Int.Conf.Hardware/Software Codesign and System Synthesis，Sep，2005.

［3］JongmanKim.A noveldimensionally-decomposed router for on-chip communication in 3D architectures［J］.Proceedings of the 34th annual internationalsymposium on Computer architecture，2007：138-149.

［4］William James Dally.Principles and Practices of Interconnection Networks［J］.Morgan Kaufmann Publishers，2004.

［5］Nilsson E，Millberg M，Oberg J.Jantsch，A.Load distribution with the proximity congestion awareness in a network on chip［J］.Design，Automation and Test in Europe Conference and Exhibition 2003：1126-1127.

［6］Pullini，A，Angiolini，F(xiàn)，Bertozzi，D，Benini，L.Fault Tolerance Overhead in Network-on-Chip Flow Control Schemes［J］.18th Symposium on Integrated Circuits and Systems Design，pp，224-229，4-7 Sept.2005

［7］SmithsR.Adaptive Hybrid Learning forNeural Networks［J］.Neural Computation，2004，16：139-157.

［8］Schmid，A.，Leblebici，Y.，Mlynek，D.Hardware realization of a Hamming neural network with on-chip learning［M］.IEEE InternationalSymposium on Circuits and Systems.ISCAS，'98.pp.191-194，31 May-3 Jun 1998.