一種低延時(shí)片上網(wǎng)絡(luò)路由器的設(shè)計(jì)與實(shí)現(xiàn)

山 蕊，蔣 林，杜慧敏，鄧軍勇

（1.西安郵電學(xué)院 電子工程學(xué)院，陜西 西安 710061；2.西安郵電學(xué)院 研究生學(xué)院，陜西 西安 710061）

隨著設(shè)計(jì)復(fù)雜度的提高，以總線為通信基礎(chǔ)設(shè)施的SoC面臨著全局連線增長、延遲增加、擴(kuò)展性能變差、全局同步困難等問題，近些年來，學(xué)術(shù)界提出采用片上網(wǎng)絡(luò)（Network on Chip，NoC）來解決SoC所面臨的問題。 在片上網(wǎng)絡(luò)的研究中，結(jié)點(diǎn)之間的通信延時(shí)一直是研究的熱點(diǎn)，目前普遍采用虛通道流控機(jī)制來降低通信延時(shí)[1-2]。作為片上網(wǎng)絡(luò)的核心部件包交換路由器，其設(shè)計(jì)直接影響整個(gè)NoC的通信效率。一般的路由器設(shè)計(jì)均采用流水線結(jié)構(gòu)[3]；文獻(xiàn)[4]提出了預(yù)先路由的方法來降低路由器的流水線級(jí)數(shù)；文獻(xiàn)[5]對(duì)虛通道（Virtual Channel，VC）分配和交換分配進(jìn)行了改進(jìn)，提出了并行VC分配和交換分配的策略；文獻(xiàn)[6，7]對(duì)快速VC分配和交換分配的方法進(jìn)行了詳細(xì)的解釋。本文在上述方法[5-7]的基礎(chǔ)上，設(shè)計(jì)了一個(gè)具有快速VC分配和交換分配機(jī)制的低延時(shí)的片上網(wǎng)絡(luò)路由器。在相同網(wǎng)絡(luò)負(fù)載情況下，本文所設(shè)計(jì)的路由器能夠極大降低片上網(wǎng)絡(luò)的通信延遲，提高片上網(wǎng)絡(luò)的通信效率。

1 相關(guān)研究

近年來，片上網(wǎng)絡(luò)路由器作為SoC的重要基礎(chǔ)部件，已經(jīng)成為學(xué)術(shù)界研究的熱點(diǎn)問題之一。大量文獻(xiàn)中提出了各種片上路由器的實(shí)現(xiàn)機(jī)制，如文獻(xiàn)[3]中提出了四級(jí)流水線結(jié)構(gòu)的路由器：第一級(jí)流水線完成路由功能；第二級(jí)流水線完成虛通道（Virtual Channel，VC）分配功能；第三級(jí)流水線完成交換分配功能；第四級(jí)流水線完成數(shù)據(jù)包的物理鏈路傳送功能。文獻(xiàn)[4]中提出了一種兩級(jí)流水線結(jié)構(gòu)的路由器：第一級(jí)流水線進(jìn)行預(yù)先路由和預(yù)測(cè)分配，預(yù)先選擇一條最優(yōu)的物理鏈路；第二級(jí)流水線進(jìn)行數(shù)據(jù)包物理鏈路的傳送。同時(shí)，該路由器中的路由算法采用自適應(yīng)路由算法。文獻(xiàn)[7]中提出了一種無流水線結(jié)構(gòu)的路由器，該路由器采用預(yù)先路由，預(yù)測(cè)分配，快速分配，全響應(yīng)，沖突檢測(cè)等機(jī)制，使得該路由器能夠在單時(shí)鐘周期內(nèi)完成數(shù)據(jù)包的轉(zhuǎn)發(fā)功能。

文獻(xiàn)[7]中指出資源預(yù)分配而產(chǎn)生的沖突情況只會(huì)出現(xiàn)在網(wǎng)絡(luò)負(fù)載很輕的情況下，對(duì)于網(wǎng)絡(luò)負(fù)載較重的情況下，全響應(yīng)和沖突檢測(cè)的功能則被閑置。因此，在文獻(xiàn)[7]的基礎(chǔ)上，本文提出的片上路由器去除了全響應(yīng)和沖突檢測(cè)的機(jī)制，對(duì)關(guān)鍵路徑和設(shè)計(jì)模塊進(jìn)行了優(yōu)化，提高片上路由器的工作頻率，滿足技術(shù)指標(biāo)要求。

2 低延時(shí)路由器的設(shè)計(jì)

文中設(shè)計(jì)的低延遲路由器是單周期的路由器，總體結(jié)構(gòu)如圖1所示。路由器主要包括輸入模塊、虛通道（Virtual Channel，VC）分配模塊、交換分配模塊，交叉開關(guān)和輸出模塊。其中輸入模塊包含4個(gè)虛通道，每個(gè)虛通道由4個(gè)40位的數(shù)據(jù)片深度的FIFO構(gòu)成；虛通道分配模塊采用快速分配機(jī)制實(shí)現(xiàn)；交換分配模塊采用快速交換分配機(jī)制；交叉開關(guān)和輸出模塊采用crossbar構(gòu)成。為了降低數(shù)據(jù)轉(zhuǎn)發(fā)的延時(shí)，在輸入模塊中采用了提前路由策略，VC分配和交換分配采用了并行機(jī)制和快速響應(yīng)機(jī)制。路由器在單個(gè)時(shí)鐘周期內(nèi)完成整個(gè)路由轉(zhuǎn)發(fā)過程，大大降低了數(shù)據(jù)轉(zhuǎn)發(fā)的延遲，提高了網(wǎng)絡(luò)性能。

圖1 低延時(shí)路由器結(jié)構(gòu)框圖Fig.1 Implementation architecture of low latency router

2.1預(yù)先路由機(jī)制

路由的功能是根據(jù)本級(jí)路由器網(wǎng)絡(luò)地址及目標(biāo)網(wǎng)絡(luò)地址，利用路由算法計(jì)算出本級(jí)應(yīng)該輸出的端口號(hào)。從流水線結(jié)構(gòu)路由器[3-4]中我們可以看出，路由算法占用一級(jí)流水，只有完成了路由的功能后才能夠進(jìn)行后續(xù)的VC分配、交換分配以及物理鏈路傳送。所以，降低流水線級(jí)數(shù)應(yīng)該從路由算法開始。在本文的設(shè)計(jì)中，目標(biāo)網(wǎng)絡(luò)地址信息可以從數(shù)據(jù)中獲得（與具體包格式有關(guān)），根據(jù)一定的編碼規(guī)則，可以通過上一級(jí)路由器來完成本級(jí)的路由計(jì)算。這樣，在本級(jí)所需要的路由信息在上一級(jí)路由器中可預(yù)先得到，并將路由計(jì)算結(jié)果隨著數(shù)據(jù)一起下發(fā)到本級(jí)路由器。通過提前路由，可以減少路由器一級(jí)流水線，從而降低網(wǎng)絡(luò)延遲。

2.2 VC分配和交換分配并行工作機(jī)制

在虛通道路由器的設(shè)計(jì)中，必須獲得了下一級(jí)虛通道資源時(shí)才能進(jìn)行交換分配。即交換分配等待VC分配的結(jié)果。VC分配是利用下一級(jí)路由器中虛通道的可用資源作為分配依據(jù)；交換分配是利用輸出端口號(hào)來控制交換開關(guān)為交換請(qǐng)求分配輸出帶寬，VC分配和交換分配的計(jì)算并沒有直接的關(guān)系，所以文獻(xiàn)[5]提出了一種將VC分配和交換分配并行執(zhí)行的算法，即假設(shè)VC是在已經(jīng)分配好的情況下，對(duì)交換請(qǐng)求進(jìn)行分配。

在并行執(zhí)行的過程中，為了避免交換分配器在存在已經(jīng)分配好VC的請(qǐng)求的情況下對(duì)等待VC分配的請(qǐng)求進(jìn)行響應(yīng)，文中將交換請(qǐng)求標(biāo)記為2種請(qǐng)求：1）已經(jīng)分配好VC號(hào)的請(qǐng)求；2）等待VC分配的請(qǐng)求。交換分配器只有在沒有1）的情況下，才會(huì)對(duì)2）進(jìn)行響應(yīng)。而對(duì)于2）是否最終分配好VC號(hào)，則在數(shù)據(jù)進(jìn)入交叉開關(guān)時(shí)進(jìn)行檢查。這樣就可以將流水級(jí)數(shù)降低一級(jí)，從而進(jìn)一步降低網(wǎng)絡(luò)延遲。

2.3 VC分配和交換分配快速工作機(jī)制

雖然VC分配和交換分配已經(jīng)并行執(zhí)行，但是其仍然要占用一級(jí)流水，為了將整個(gè)路由器的流水級(jí)數(shù)降為一級(jí)即無流水線工作方式，必須將VC分配，交換分配及物理鏈路傳送并為一級(jí)。文獻(xiàn)[7]提出了一種快速VC分配和交換分配的工作機(jī)制，通過利用緩存在輸入虛通道中數(shù)據(jù)片的信息，提前仲裁出下一個(gè)時(shí)鐘周期對(duì)VC和物理鏈路資源的分配結(jié)果并暫存，當(dāng)下一個(gè)時(shí)鐘周期到來時(shí)，將緩存的分配結(jié)果和當(dāng)前的請(qǐng)求信號(hào)進(jìn)行相應(yīng)的組合邏輯操作，快速的產(chǎn)生輸入端口和物理鏈路所需的控制信息。

2.4 VC分配和交換分配內(nèi)部模塊說明

2.4.1 快速響應(yīng)模塊

VC分配模塊的快速響應(yīng)單元主要是利用當(dāng)前VC請(qǐng)求和上一個(gè)時(shí)鐘周期緩存的分配結(jié)果進(jìn)行相應(yīng)的組合邏輯操作，產(chǎn)生當(dāng)前請(qǐng)求的響應(yīng)信號(hào)，以及分配好的VC號(hào)。其工作過程為：當(dāng)前請(qǐng)求信號(hào)到達(dá)VC分配模塊后，與上一個(gè)時(shí)鐘周期緩存的預(yù)先分配使能信號(hào)進(jìn)行對(duì)應(yīng)位（如虛通道1的請(qǐng)求信號(hào)對(duì)應(yīng)于各個(gè)時(shí)能信號(hào)的最低位）的“與”邏輯操作，然后對(duì)各個(gè)操作結(jié)果，進(jìn)行對(duì)應(yīng)位（如所有操作結(jié)果的最低位）的“或”邏輯操作，操作的結(jié)果即為所要產(chǎn)生的響應(yīng)信號(hào)。根據(jù)所請(qǐng)求的輸出端口號(hào)，通過“多路選擇電路”產(chǎn)生分配好的VC號(hào)。具體實(shí)現(xiàn)結(jié)構(gòu)，詳見圖2。

圖2 VC分配快速響應(yīng)模塊Fig.2 VC allocation fast response unit

交換分配模塊的快速響應(yīng)單元主要是利用當(dāng)前交換請(qǐng)求和上一個(gè)時(shí)鐘周期緩存的分配結(jié)果進(jìn)行相應(yīng)的組合邏輯操作，產(chǎn)生分配好的兩級(jí)控制信息：第一級(jí)控制信號(hào)，用于產(chǎn)生從輸入端口中請(qǐng)求輸出的四個(gè)虛通道之間的仲裁信息；第二級(jí)控制信號(hào)，用于產(chǎn)生端口與端口之間的對(duì)于請(qǐng)求同一個(gè)輸出端口的仲裁信息。需特別注意，對(duì)于某一個(gè)輸出端口，兩級(jí)控制信號(hào)應(yīng)該能夠同時(shí)得到響應(yīng)。其工作過程為：當(dāng)請(qǐng)求信號(hào)到達(dá)交換分配模塊后，與上一個(gè)時(shí)鐘周期緩存的第一級(jí)預(yù)先分配使能信號(hào)進(jìn)行對(duì)應(yīng)位（如輸入端口1中虛通道1，2，3，4的請(qǐng)求信號(hào)對(duì)應(yīng)于輸入端口1的預(yù)先分配使能信號(hào)）的“與”邏輯操作，利用操作的結(jié)果，通過“多路選擇電路”，選擇出第一級(jí)允許輸出虛通道所請(qǐng)求的端口，利用該端口號(hào)和第二級(jí)預(yù)先分配使能信號(hào)進(jìn)行對(duì)應(yīng)位的“與”邏輯操作，從而產(chǎn)生第二級(jí)控制信號(hào)。利用第二級(jí)控制信號(hào)和第一級(jí)“與”的操作結(jié)果，產(chǎn)生第一級(jí)控制信號(hào)。從而保證兩級(jí)控制信號(hào)應(yīng)該能夠同時(shí)得到響應(yīng)的要求。具體實(shí)現(xiàn)結(jié)構(gòu)，詳見圖3。

圖3 交換分配快速響應(yīng)模塊Fig.3 Switch allocation fast response unit

2.4.2 下一個(gè)時(shí)鐘周期請(qǐng)求計(jì)算模塊

此模塊的主要功能是精確地計(jì)算下一個(gè)時(shí)鐘周期所需要的請(qǐng)求信號(hào)（VC請(qǐng)求和交換請(qǐng)求），以便于預(yù)先分配器模塊能夠?qū)τ?jì)算出來的請(qǐng)求信號(hào)進(jìn)行仲裁。

對(duì)于VC請(qǐng)求而言，我們利用當(dāng)前請(qǐng)求信號(hào)，請(qǐng)求響應(yīng)信號(hào)、下一個(gè)被緩存數(shù)據(jù)片是否頭片信息和輸出端口信息，精確的計(jì)算出下一個(gè)時(shí)鐘周期是否會(huì)有VC請(qǐng)求信號(hào)，電路的實(shí)現(xiàn)結(jié)構(gòu)詳見圖4。而對(duì)于交換請(qǐng)求信號(hào)，出于對(duì)時(shí)鐘頻率和設(shè)計(jì)復(fù)雜度的考慮，只是利用目標(biāo)VC空/滿狀態(tài)來進(jìn)行計(jì)算，電路的實(shí)現(xiàn)結(jié)構(gòu)詳見圖5。

圖4 計(jì)算下一節(jié)拍VC請(qǐng)求電路Fig.4 Computing next cycle’s VC request circuit

圖5 計(jì)算下一節(jié)拍交換請(qǐng)求電路Fig.5 Computing next cycle’s switch request circuit

2.4.3 預(yù)先分配器模塊

預(yù)先分配器模塊主要由一組仲裁器構(gòu)成，其能夠在多個(gè)請(qǐng)求之間進(jìn)行裁決，將目標(biāo)資源分配給一個(gè)確定的請(qǐng)求，仲裁的原則我們采用輪循的方式。

2.5 時(shí)鐘頻率優(yōu)化

如圖6所示，該電路的關(guān)鍵路徑：請(qǐng)求信號(hào)產(chǎn)生—＞VC請(qǐng)求快速響應(yīng)/交換請(qǐng)求快速響應(yīng)—＞輸入端口選擇輸出數(shù)據(jù)片—＞輸出端口選擇輸出數(shù)據(jù)片。產(chǎn)生請(qǐng)求信號(hào)所需要的信息為輸出端口號(hào)和VC是否分配信號(hào)，這些信號(hào)均可以提前一個(gè)時(shí)鐘周期得到。為了提高時(shí)鐘頻率，將請(qǐng)求信號(hào)產(chǎn)生電路提前到上一個(gè)時(shí)鐘周期，這樣關(guān)鍵路徑更新為：VC請(qǐng)求快速響應(yīng)/交換請(qǐng)求快速響應(yīng)—＞輸入端口選擇輸出數(shù)據(jù)片—＞輸出端口選擇輸出數(shù)據(jù)片，詳見圖7。為了進(jìn)一步優(yōu)化時(shí)序，減少不必要的譯碼電路，關(guān)鍵路徑上的信號(hào)均采用獨(dú)熱碼譯碼。由于減少了產(chǎn)生請(qǐng)求信號(hào)和電路進(jìn)行譯碼所需耗費(fèi)的時(shí)間，電路的時(shí)鐘頻率得到顯著提高。

圖6 關(guān)鍵路徑Fig.6 Key path

圖7 更新后的關(guān)鍵路徑Fig.7 Improved key path

3 ASIC實(shí)現(xiàn)與測(cè)試

本文設(shè)計(jì)的低延時(shí)路由器芯片采用SMIC 0.13um Mixedsignal/RF 1.2V/3.3V工藝進(jìn)行流片，其中核心邏輯采用基于標(biāo)準(zhǔn)單元的方法。由于SMIC的IO PAD最高支持27 MHz的時(shí)鐘[8]，故在芯片內(nèi)部設(shè)計(jì)了一個(gè)中心頻率260 MHZ，最高頻率320 MHz的環(huán)振。因此整個(gè)芯片屬于數(shù)模混合設(shè)計(jì)，芯片布局圖如圖8所示。

圖8 路由器芯片布局圖Fig.8 Layout of router chip

為了測(cè)試芯片功能的正確性，增加了必要的外圍電路：流量產(chǎn)生器和數(shù)據(jù)包收集器。在300 MHz的工作頻率下，采用軟件控制寄存器配置，通過ARM LPC2214芯片產(chǎn)生讀寫配置寄存器時(shí)序，經(jīng)串口發(fā)送給PC機(jī)，完成芯片性能的測(cè)試。測(cè)試結(jié)果如圖9顯示：當(dāng)吞吐量較低時(shí)，數(shù)據(jù)包長度對(duì)于網(wǎng)絡(luò)的平均延遲影響較小；當(dāng)吞吐量較高時(shí)，數(shù)據(jù)包的片數(shù)決定了網(wǎng)絡(luò)的平均延遲。數(shù)據(jù)包片數(shù)較少時(shí)，隨著吞吐量的增加，網(wǎng)絡(luò)平均延遲變化不大；當(dāng)數(shù)據(jù)包的片數(shù)增加到一定程度，數(shù)據(jù)包網(wǎng)絡(luò)平均延遲隨著吞吐量的增加而急劇增加。

圖9 芯片測(cè)試結(jié)果Fig.9 Test result of chip

4 結(jié)束語

與流水線結(jié)構(gòu)的片上路由器相比，本文提出的路由器結(jié)構(gòu)在一個(gè)時(shí)鐘周期內(nèi)完成數(shù)據(jù)片的傳送，降低了網(wǎng)絡(luò)延遲；同時(shí)，通過對(duì)關(guān)鍵路徑的優(yōu)化，時(shí)鐘頻率得到顯著提高。與文獻(xiàn)[7]中所提出的低延遲路由器相比較，考慮文獻(xiàn)[7]中所提到的由于資源預(yù)分配而產(chǎn)生的沖突情況只會(huì)出現(xiàn)在網(wǎng)絡(luò)負(fù)載很輕的情況下，對(duì)于網(wǎng)絡(luò)負(fù)載較重的情況下，全響應(yīng)和沖突檢測(cè)的功能則被閑置，根據(jù)這樣的情況，本文通過對(duì)電路的結(jié)構(gòu)進(jìn)行優(yōu)化，去掉了文獻(xiàn)[7]中的全響應(yīng)和沖突檢測(cè)的模塊，這樣不僅減小了電路規(guī)模，同時(shí)降低了電路實(shí)現(xiàn)的復(fù)雜度，但是其網(wǎng)絡(luò)性能卻沒有降低。同時(shí)，通過對(duì)電路關(guān)鍵路徑和部分內(nèi)部模塊（快速分配模塊，仲裁器等）的優(yōu)化設(shè)計(jì)，使得本文所設(shè)計(jì)的低延遲路由器，在所有輸入端口在相同負(fù)載的情況下，可以穩(wěn)定工作在300 MHz；在只有一個(gè)端口接收數(shù)據(jù)的情況下，時(shí)鐘頻率可以達(dá)到355 MHz。

[1]Salminen E，Kulmala A，Inen TDHML.Survey of Networkon-chip Proposals[C]//White Paper，OCP－IP，MARCH，2008.

[2]Brackenbury L E M，Plana L A.Jeffrey Pepper.System-on-Chip and Implementation[J].IEEE Transactions on Education，2010，53（2）：272－281.

[3]Kumar，A.A 4.6 Tbits/s 3.6 GHz single-cycle NoC router with a novel switch allocator in 65nm CMOS[C]//Computer Design，2007：63－70.

[4]Kim J，Park D，T.Theocharides et al.A low latency router supporting adaptivity for on-chip interconnects[C]//The 42nd annual Design Automation Conference，2005：559－564.

[5]Peh L S，Dally W J.A delay model and speculative architecture for pipelined routers [C]//In International Symposiumon High-Performance Computer Architecture，Jan 2001：255－266.

[6]Mullins，R.，West A，Moore S.Low-latency virtual-channel routers for on-chip networks[C]//The 31st annual international symposium on Computer Architecture，2004：188－197.

[7]Mullins，West R A，Moore S.The design and implementation of a low-latency on-chip network [C]//ASP-DAC ’06 Proceeding of the 2006 Asia and South Pacific Design Automation Conference，2006：164－169.

[8]VeriSilicon SMIC 0.13m 1.2V/3.3V I/O Cell Library Databook[S].Semiconductor Manufacturing International Corporation，2006.