才 華 劉廣文 陳廣秋 姜 俊

（長(zhǎng)春理工大學(xué)電子信息工程學(xué)院，吉林 長(zhǎng)春 130022）

技術(shù)能力和實(shí)際應(yīng)用的復(fù)雜性使得基于總線的片上系統(tǒng)（SoC，system-on-chip）向片上網(wǎng)絡(luò)（NoC，network-on-chip）發(fā)展。NoC提供了一個(gè)整體的多層次的通信平臺(tái)，允許網(wǎng)絡(luò)節(jié)點(diǎn)之間的通信傳輸。

1 片上網(wǎng)絡(luò)虛擬通道

片上網(wǎng)絡(luò)有能力解決總線在帶寬，時(shí)鐘頻率，功率的可擴(kuò)展性方面的問題。然而由于網(wǎng)絡(luò)中通道和緩沖資源的共享，數(shù)據(jù)包的傳輸帶來了不可預(yù)測(cè)的情況。為了解決片上網(wǎng)絡(luò)數(shù)據(jù)包傳輸過程中帶來的不確定性，提出了多種資源預(yù)約和基于優(yōu)先級(jí)的調(diào)度機(jī)制，提供延遲和帶寬的保證。?thereal[1]和Nostrum[2]采用資源預(yù)留策略以提供有保證的服務(wù)。具體來說，在網(wǎng)絡(luò)同步運(yùn)行中都確定有時(shí)分多路復(fù)用（TDM，time-division-multiplexing）的虛擬電路（VC，virtual circuit）。VC上的數(shù)據(jù)包是通過VC路線節(jié)點(diǎn)在通道中連續(xù)傳輸?shù)摹?/p>

總的來說，一個(gè)VC可能包括多個(gè)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)（多向性的）。配置VCs包含以下方面。

(1)路徑選擇：設(shè)計(jì)網(wǎng)絡(luò)路徑的多樣性

(2)時(shí)隙分配：交換器為每個(gè)VC分配一個(gè)間隙

本文提出基于LN時(shí)隙分配方法的多級(jí)時(shí)隙控制分配方法，根據(jù)網(wǎng)絡(luò)不同情況下的數(shù)據(jù)傳輸路徑設(shè)置提供更好的選擇。

2.基于LN時(shí)隙分配方法的VC設(shè)置

2.1 NoC中的基于TDM的虛擬電路

圖1.系統(tǒng)運(yùn)行示意圖

片上TDM VC假設(shè)網(wǎng)絡(luò)是分組交換和有時(shí)間時(shí)隙的，VC數(shù)據(jù)包在每一個(gè)時(shí)間間隙前進(jìn)一跳。如圖1所示，VC v通過交換機(jī)SW1，SW2和SW3{b1→b2→b3}。在v上，每六個(gè)間隙網(wǎng)絡(luò)中會(huì)注入兩個(gè)數(shù)據(jù)包（我們說窗口的大小為6）。最開始，通過數(shù)據(jù)包流在第一個(gè)被占用的交換機(jī)SW1的緩沖區(qū)b1間隙是0和2。之后，重復(fù)這個(gè)模式，b1的間隙6和8，12和14，等等被占用。在第二個(gè)交換機(jī)SW2，數(shù)據(jù)包占用b2的間隙1和3，7和9，13和15，等等。在交換機(jī)SW3，它們占用了b3的間隙2和4，8和10，14和16，等等。

這是VC的配置模式，為VC數(shù)據(jù)包確定確切的準(zhǔn)許進(jìn)入形式，并在節(jié)點(diǎn)中設(shè)定路徑選擇表。在這種情況下，VC數(shù)據(jù)包在頭文件中不需要攜帶路由信息?？梢怨?jié)省每一個(gè)VC數(shù)據(jù)包的通訊能量消耗。

2.2 使用LN的VC配置

LN是一個(gè)相關(guān)函數(shù)的集合（時(shí)間間隙，緩沖區(qū)），其與一個(gè)給定的VC（虛擬通道）上的緩沖區(qū)是相對(duì)應(yīng)的。即VC中一組緩沖區(qū)邏輯網(wǎng)絡(luò)的間隙集合作為一個(gè)LN。

多節(jié)點(diǎn)VC配置的步驟，包括兩個(gè)順序階段：路徑選擇和間隙分配及間隙映射。在第一個(gè)階段，VC的路徑是確定的。在第二個(gè)階段，基于VC路徑，分配給VC的間隙取決于是否可以避免相互干擾以及帶寬是否可以滿足。我們?cè)趫D2中利用一對(duì)封閉式 VCs（v1，v2）來描述它們。

(1)間隙分配：由于在一個(gè)共享緩沖區(qū)中可能發(fā)生沖突，我們有規(guī)律地將共享緩沖區(qū)的間隙分隔成間隙組。在圖2中，b0是v1和v2唯一的共享緩沖區(qū)，v1∩v2={b0}。我們把b0的間隙分隔成兩組，一個(gè)偶數(shù)集s20(b0)關(guān)于t=2k和一個(gè)奇數(shù)集s21(b0)關(guān)于t=2k+1。

(2)間隙映射：分段的間隙組可以規(guī)律和準(zhǔn)備地被映射到VC上其他緩沖區(qū)的間隙組。例如，在緩沖區(qū)b0間隙t的一個(gè)v1數(shù)據(jù)包，即（t，b0），將連續(xù)占據(jù)間隙t+1在b1(狀態(tài)（t+1，b1）)，間隙 t+2在 b2(狀態(tài)（t+2，b2）)，間隙 t+3 在 b3(狀態(tài)（t+3，b3）)。在v1和v2分別映射完間隙組s20(b0)和s21(b0)后，我們得到兩個(gè)狀態(tài)集{s20(b0)，s21(b1)，s20(b2)s21(b3)}以及{s21(b0)，s21(b4)}。我們指在 VC中一組緩沖區(qū)邏輯網(wǎng)絡(luò)的間隙集合作為一個(gè)LN。因此，LN是一個(gè)在VC相關(guān)緩沖區(qū)上由（時(shí)間間隙，緩沖區(qū)）相關(guān)聯(lián)的組成。

總結(jié)來說，就是1）通過配置間隙細(xì)化路由表建立VC；2）分隔間隙并映射進(jìn)LN；3）分配不同的LN到VC。這些步驟必須承諾保證無沖突和提供足夠的帶寬。

本文提出了基于LN時(shí)隙分配的多級(jí)控制VC設(shè)置。該方法根據(jù)網(wǎng)絡(luò)中的實(shí)時(shí)情況在數(shù)據(jù)傳輸中設(shè)置更加準(zhǔn)確的間隙配置，以避免網(wǎng)絡(luò)中的數(shù)據(jù)傳輸擁堵情況，更好的利用網(wǎng)絡(luò)資源，提升網(wǎng)絡(luò)效率。

3 基于LN時(shí)隙分配方法的多級(jí)控制VC設(shè)置

下面為基于LN時(shí)隙分配方法的多級(jí)控制VC設(shè)置。步驟如下：

（1）給定一個(gè)多節(jié)點(diǎn)VC網(wǎng)絡(luò)。

（2）根據(jù)數(shù)據(jù)傳輸要求進(jìn)行路徑選擇。

（3）對(duì)下一步節(jié)點(diǎn)發(fā)送訪問命令，檢查節(jié)點(diǎn)狀態(tài)。

（4）假定下一節(jié)點(diǎn)有兩個(gè)方向，判斷X/Y方向節(jié)點(diǎn)擁擠情況。若為輕度擁擠，選擇擁擠度較輕的路徑。若為中度以及重度擁擠，比較X/Y方向的等待時(shí)間。若大于設(shè)定值，則選擇等待時(shí)間短的路徑。若小于設(shè)定值，則根據(jù)網(wǎng)絡(luò)狀況進(jìn)行等待或回溯，或沿相對(duì)較輕方向傳輸。

（5）選定VC后，進(jìn)行間隙映射，同時(shí)避免VC之間的沖突。

（6）若映射未完成，則返回路徑選擇重新開始配置。

（7）若映射完成，則VC設(shè)置完成。

VC的設(shè)置是一個(gè)基本問題，我們采用[9]中給出的方法予以解決。

算法 VC配置算法的偽代碼

輸入：I：所有可能設(shè)置的VC隊(duì)列

輸出：O：VC設(shè)置可以采用的隊(duì)列（s：一個(gè)可用vc設(shè)置）

初始狀態(tài)，cur_level=0；O.size=m；O 和 s初始為空；即暫時(shí)沒有可用VC設(shè)置；利用優(yōu)先標(biāo)準(zhǔn)對(duì)O進(jìn)行分類排序；

在構(gòu)建VC時(shí)，設(shè)置與VC相對(duì)應(yīng)的LN是關(guān)鍵的一步。如果VC到LN的設(shè)置對(duì)所有VC都能夠成功執(zhí)行，則返回1；否則返回0。

結(jié)語(yǔ)

在NoC的應(yīng)用設(shè)計(jì)中，關(guān)于TDM的服務(wù)保證和VC設(shè)置是一個(gè)普遍的問題。它的復(fù)雜性產(chǎn)生于網(wǎng)絡(luò)路徑的多樣性和各種路徑重疊的情景，以及網(wǎng)絡(luò)資源利用情況的變化。研究結(jié)果表明，使用基于LN時(shí)隙分配方法的多級(jí)控制VC設(shè)置能夠更好地適應(yīng)網(wǎng)絡(luò)中復(fù)雜情況，有效地利用網(wǎng)絡(luò)資源，提升系統(tǒng)效率。

[1]K.Goossens，J.Dielissen，and A.R?adulescu，"The ?thereal network on chip:Concepts，architectures，and im-plementations，"IEEE Des.Test Comput.，vol.22，no.5，pp.21-31，Sep.-Oct.2005.

[2]M.Millberg，E.Nilsson，R.Thid，and A.Jantsch，"Guaranteed bandwidth using looped containers in temporally disjoint networks within the Nostrum network on chip，"in Proc.Design Automation and Test in Europe Conf.，F(xiàn)eb.2004.