才華，楊勇，李洋

（長春理工大學，長春 130022）

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

1 片上網絡

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

1.1 網絡拓撲結構

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

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

圖1 片上網絡常用的拓撲結構Fig.1 Topology in the network on chip

1.2 路由算法

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

圖2 片上網絡常用的路由算法Fig.2 Network-on-chip routing algorithm

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

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

1.3 流控策略

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

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

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

2 基于神經網絡的擁塞控制算法

片上網絡中的諸多關鍵技術，目標都是追求網絡的最大吞吐率和數(shù)據(jù)包傳輸最小延時。但是，當網絡發(fā)生擁塞，會直接影響網絡性能，因此，在擁塞控制中，會綜合考慮網絡拓撲、路由算法和流控策略。

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

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

2.2 基于神經網絡的擁塞預測算法分析

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

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

擁塞感知網絡結構如圖5所示。

圖5 擁塞感知神經網絡Fig.5 Congestion-aware neural network

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

3 仿真結果與分析

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

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

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

圖7 片上網絡吞吐率曲線Fig.7 Throughput of Network on Chip

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

4 結語

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

［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.