面向片上網(wǎng)絡(luò)延遲優(yōu)化的直通路徑預(yù)構(gòu)機(jī)制

摘要：針對維序路由模式下報文傳輸時表現(xiàn)出的空間局部性，提出了一種適用于報文直向通信優(yōu)化傳輸?shù)闹蓖窂筋A(yù)構(gòu)（SFRP）路由器結(jié)構(gòu).通過在路由器內(nèi)部輸入端口N，S，E，W分別靜態(tài)地預(yù)構(gòu)一條連接其直向通信輸出端口的開關(guān)直通路徑，結(jié)合適當(dāng)?shù)闹赜靡约爸袛鄼C(jī)制，以期實現(xiàn)后續(xù)的報文在滿足匹配條件的情況下可直接利用開關(guān)直通路徑進(jìn)行報文的傳輸，進(jìn)而旁通開關(guān)分配流水站，降低報文傳輸延遲.合成通信負(fù)載下的模擬結(jié)果表明，SFRP路由器在報文注入率飽和前較BASE， BASE_LR， BASE_LR_SPC和PSEUDO_CIRCUIT等四種路由器結(jié)構(gòu)均可獲得非常明顯的性能提升，其性能提升最大可達(dá)到59%， 46%， 25.6%和9.5%.真實應(yīng)用負(fù)載下的模擬結(jié)果表明，SFRP路由器與PSEUDO_CIRCUIT路由器的平均延遲相當(dāng)，但較其他幾種路由器結(jié)構(gòu)可分別獲得57%， 45%和21%的性能提升.

關(guān)鍵詞：片上網(wǎng)絡(luò)；維序路由；空間局部性；直通路徑預(yù)構(gòu)；路由器

中圖分類號：TP302.2 文獻(xiàn)標(biāo)識碼：A

Straight-forwarding Route Preconfiguration Mechanism

for Latency Optimization in NoCs

TANG Xian-tuo1， WANG Feng1， XING Zuo-cheng1， WANG Qing-lin1， FU Gui-tao1，2

（1. College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China；

2. Beijing Satellite Navigation Center， Beijing 100094， China）

Abstract： We proposed a straight-forwarding route pre-configuration （SFRP） router architecture for the communication spatial locality when packets traverse under dimension-ordered routing mode， which was adapted to the latency optimization for the packets straight forwarding traversal. In our SFRP router， a corresponding straight-forwarding route was preconfigured at each input port， which connected the input port with its corresponding straight forwarding output port. Combining appropriate route reuse with termination mechanism， the subsequent packets satisfying the comparative conditions were expected to directly forward to crossbar without SA stage， hence reducing the average latency for packets traversal. Our evaluation with synthetic workload traffic shows that SFRP router can achieve obvious performance improvement by up to 59%， 46%， 25.6% and 9.5% respectively before the packets injection rate is saturated， compared with the BASE， BASE_LR， BASE_LR_SPC and PSEUDO_CIRCUIT routers. In the real application traffic workloads， the performance improvement of the SFRP router is analogous to that of PSEUDO_CIRCUIT router. Compared with other three kinds of routers， SFRP router can achieve obvious performance improvement by up to 57%， 45% and 21% respectively.

Key words： network-on-chip； dimension-ordered routing； spatial locality； straight-forwarding route pre-configuration；routers

半導(dǎo)體技術(shù)以及微處理器體系結(jié)構(gòu)技術(shù)的飛速發(fā)展推動了芯片設(shè)計進(jìn)入多核時代.隨著單片上集成處理核規(guī)模的不斷增大，片上多核處理器的性能越來越敏感于片上核間通信的性能，核間通信已成為當(dāng)前單芯片多處理器（CMP）以及多核片上系統(tǒng)（MPSoC）性能進(jìn)一步提升的瓶頸^[1].傳統(tǒng)的諸如總線、交叉開關(guān)等片上互連結(jié)構(gòu)由于可擴(kuò)展性、帶寬需求以及硬件復(fù)雜度等方面的限制，已無法滿足當(dāng)前片上多核甚至眾核環(huán)境下系統(tǒng)的通信需求[2-3].在應(yīng)用需求的推動下，基于報文交換的片上網(wǎng)絡(luò)（network-on-chips， NoCs）[4-6]應(yīng)運(yùn)而生，并以其高擴(kuò)展性、高帶寬以及硬件開銷適中等方面的優(yōu)勢而很快取代總線、交叉開關(guān)等傳統(tǒng)片上互連方式，成為一種最具前景的多核通信解決方案.

隨著單片上集成處理核數(shù)目的進(jìn)一步增大，基于報文交換的片上網(wǎng)絡(luò)由于報文傳輸跳步數(shù)的相應(yīng)增多，不可避免地帶來片上通信延遲的快速增長[7].一般來說，當(dāng)網(wǎng)絡(luò)規(guī)模及其對應(yīng)的拓?fù)浣Y(jié)構(gòu)一定時，報文傳輸時的平均跳步數(shù)基本確定，其傳輸延遲將主要取決于單個跳步的路由器平均延遲.目前，設(shè)法降低單個跳步路由器的平均延遲已成為片上多核通信研究領(lǐng)域最為直觀的性能優(yōu)化方向.

文獻(xiàn)[8]提出了一種經(jīng)典的四站流水虛通道路由器結(jié)構(gòu)，為報文傳輸?shù)牧魉瘜崿F(xiàn)提供了重要的理論和應(yīng)用參考.此后，許多研究者紛紛從縮短流水線站數(shù)、降低關(guān)鍵路徑延遲等角度對其提出了很多優(yōu)化方案.如文獻(xiàn)[9]提出了一種超前路由技術(shù)（Lookahead），通過將路由計算移除出路由傳輸關(guān)鍵路徑，實現(xiàn)了路由流水延遲的降低.由于超前路由技術(shù)并不需要保留諸如虛通道、開關(guān)連接等片上資源，因此其在目前片上路由器結(jié)構(gòu)設(shè)計中得到了廣泛使用.文獻(xiàn)[10]提出了一種推斷路由技術(shù)（Speculative），通過在路由流水過程中實現(xiàn)虛通道分配（VA）與交叉開關(guān)分配（SA）的并行處理，降低了每跳步路由流水延遲.但推斷路由的性能受推斷成功的概率影響很大，且需要同時針對正常請求以及推斷請求執(zhí)行仲裁，設(shè)計的復(fù)雜度亦會大大增加.文獻(xiàn)[11]從通信時間局部性的角度出發(fā)提出了一種偽電路機(jī)制（PSEUDO_CIRCUIT），通過微片傳輸時重用之前微片的相關(guān)仲裁信息，進(jìn)而實現(xiàn)SA流水站的旁通.偽電路機(jī)制為我們探索路由器內(nèi)部開關(guān)路徑的可重用實現(xiàn)提供了重要的理論參考，但其對于通信性能的提升主要取決于應(yīng)用通信中時間局部性概率的大小，且網(wǎng)絡(luò)注入率較大時某輸入端的偽電路在各輸出端口之間的頻繁切換會導(dǎo)致可重用開關(guān)路徑的有效率快速降低，性能提升幅度亦越為有限.此外，其他新穎的流控機(jī)制諸如令牌流控機(jī)制^[12]、預(yù)測路由機(jī)制^[1]以及快速虛通道機(jī)制^[13]等亦受到了片上網(wǎng)絡(luò)研究領(lǐng)域的廣泛關(guān)注，通過對于路由計算、虛通道分配以及開關(guān)分配等路由過程的優(yōu)化處理，實現(xiàn)了單跳步路由流水延遲的降低.

作為一種新的片上網(wǎng)絡(luò)延遲優(yōu)化技術(shù)，本文擬從通信空間局部性的角度來探索維序路由模式下報文直通傳輸過程的優(yōu)化處理，試圖以最小的額外硬件開銷來降低路由器的平均延遲，進(jìn)而實現(xiàn)報文傳輸延遲的優(yōu)化.

1 維序路由

維序路由算法^[8]因其邏輯實現(xiàn)簡單且無死鎖的特性，是當(dāng)前片上網(wǎng)絡(luò)中使用最為廣泛的一種路由算法.維序路由模式下，報文一次只在一個維度上進(jìn)行傳輸，當(dāng)且僅當(dāng)該報文沿著某個維度到達(dá)恰當(dāng)?shù)淖鴺?biāo)且需要轉(zhuǎn)向時，才按由低維到高維的順序轉(zhuǎn)向另外的維度進(jìn)行傳輸.報文在維序路由模式下的這種通信特性體現(xiàn)在路由器內(nèi)部各輸入端口會表現(xiàn)出較大的空間局部性，即報文進(jìn)入路由器某輸入端口后具有很大的概率向其直向通信輸出端口進(jìn)行路由傳輸.

圖1所示為2D-MESH網(wǎng)絡(luò)結(jié)構(gòu)以及維序路由算法XY下報文的路由傳輸過程.A節(jié)點發(fā)送的報文首先沿著X維度進(jìn)行路由傳輸，當(dāng)報文傳輸至X維度上的轉(zhuǎn)向節(jié)點C后開始轉(zhuǎn)向Y維度進(jìn)行路由傳輸，直至到達(dá)目的節(jié)點B，整個報文的路由傳輸過程最多進(jìn)行一次轉(zhuǎn)向操作.若考慮報文在某中間路由器內(nèi)部的轉(zhuǎn)發(fā)過程，以報文進(jìn)入路由器的輸入端口W為例，則報文進(jìn)入W后將具有4種可能的轉(zhuǎn)發(fā)方向：

1）當(dāng)報文沿著網(wǎng)絡(luò)的X維度傳輸至該節(jié)點且下一跳步需要繼續(xù)沿著該維度傳輸時，報文向輸出端口E進(jìn)行直向傳輸；

2）當(dāng)報文沿著網(wǎng)絡(luò)的X維度傳輸至該節(jié)點且下一跳步需要轉(zhuǎn)向Y維度傳輸時，根據(jù)報文的路由計算結(jié)果具有兩種可能的轉(zhuǎn)發(fā)方向：若路由計算結(jié)果為輸出端口S，則報文向輸出端口S進(jìn)行轉(zhuǎn)向傳輸；若路由計算結(jié)果為輸出端口N，則報文向輸出端口N進(jìn)行轉(zhuǎn)向傳輸.

3）若當(dāng)前節(jié)點即為該報文的目的節(jié)點，則報文向輸出端口L進(jìn)行轉(zhuǎn)向傳輸.

若不考慮算法的傳輸特性，則進(jìn)入輸入端口W的報文向輸出端口S，N，E，L轉(zhuǎn)發(fā)的概率將均等為25%.由于維序路由下報文傳輸時最多進(jìn)行一次轉(zhuǎn)向（不包含報文注入以及流出階段的轉(zhuǎn)向），其余大部分階段均沿著某個初始維度以及轉(zhuǎn)向后的某個維度進(jìn)行直向傳輸，因此報文進(jìn)入W后向輸出端口E直向傳輸?shù)母怕蕦⑦h(yuǎn)遠(yuǎn)大于向S，N，L轉(zhuǎn)向傳輸?shù)母怕?圖2所示為SPLASH-2測試包^[7]中8種蹤跡通信（見3.3節(jié)）的網(wǎng)絡(luò)直向傳輸概率的大小以及中間路由節(jié)點（不包含源節(jié)點以及目的節(jié)點）直向傳輸概率的大小.由圖可知，報文在整個網(wǎng)絡(luò)中直向傳輸?shù)钠骄怕蕿?2.5%，而在中間路由節(jié)點內(nèi)部直向傳輸?shù)钠骄怕矢哌_(dá)81%.

基于以上分析，本文擬針對維序路由模式下報文在中間路由節(jié)點的直向傳輸過程展開專門優(yōu)化，提出一種適用于報文直向路由傳輸?shù)腟FRP路由器結(jié)構(gòu)，試圖以一種非推斷的方式實現(xiàn)維序路由模式下報文直向傳輸延遲以及整體通信延遲的降低.

2 SFRP路由器結(jié)構(gòu)

本節(jié)中我們將首先描述幾種目前在片上互連領(lǐng)域廣泛使用的虛通道路由器結(jié)構(gòu)，并在此基礎(chǔ)上提出一種適用于維序路由的SFRP路由器結(jié)構(gòu)，以期實現(xiàn)報文直向傳輸過程的優(yōu)化處理.

2.1 片上路由器結(jié)構(gòu)

文獻(xiàn)[8]提出了一種經(jīng)典的四站流水虛通道路由器結(jié)構(gòu)，其內(nèi)部結(jié)構(gòu)如圖3所示.路由器內(nèi)部包含5個輸入、輸出端口，分別表示N，S，E，W四個輸入輸出方向以及本地節(jié)點方向，每個輸入端口支持4條虛通道.整個路由器結(jié)構(gòu)由輸入虛通道、路由計算單元、虛通道分配器、開關(guān)分配器以及5×5交叉開關(guān)等模塊組成，采用基于信用的流控機(jī)制.

報文網(wǎng)絡(luò)傳輸經(jīng)歷各中間路由器時，組成報文的各微片以流水的方式依次通過各路由流水站，其流水線結(jié)構(gòu)如圖4（a）所示.頭微片到達(dá)路由器輸入端口后，根據(jù)虛通道編號寫入相應(yīng)的虛通道.從虛通道讀出來的頭微片將路由信息發(fā)給路由計算模塊用以獲取其輸出端口編號.路由計算完成后，根據(jù)輸出端口編號向虛通道分配器發(fā)送請求以獲得下級路由器的輸入虛通道.頭微片獲得授權(quán)后，即可在虛通道狀態(tài)控制邏輯的作用下根據(jù)輸出端口編號向開關(guān)分配器發(fā)出請求，經(jīng)授權(quán)后可使用交叉開關(guān)傳輸1個微片.后續(xù)的體微片或尾微片可直接繼承頭微片的路由以及虛通道分配結(jié)果，經(jīng)開關(guān)分配邏輯依次授權(quán)后即可完成剩余微片的開關(guān)傳輸，直至體微片離開路由器并釋放相應(yīng)的虛通道資源.

為了縮短報文傳輸?shù)牧魉緮?shù)，超前路由技術(shù)^[9]被廣泛地應(yīng)用于片上路由器結(jié)構(gòu)設(shè)計中，通過將路由計算移除出路由傳輸關(guān)鍵路徑，實現(xiàn)了路由流水延遲的降低，其流水線結(jié)構(gòu)如圖4（b）所示.與四站流水路由器結(jié)構(gòu)不同，路由器NRC站的作用是計算下一跳路由器的輸出端口，故其結(jié)構(gòu)設(shè)計時需要增加額外的端口信號用于傳輸下級路由器所需的路由結(jié)果以及額外的寄存器用于寄存來自上級路由器的路由結(jié)果.在此基礎(chǔ)上，文獻(xiàn)[10]提出了一種推斷路由技術(shù)（speculative）用以實現(xiàn)報文傳輸時虛通道分配與開關(guān)分配的并行處理，其流水線結(jié)構(gòu)如圖4（c）所示.與四站流水路由器結(jié)構(gòu)不同，頭微片傳輸時將同時發(fā)送虛通道分配以及開關(guān)分配推斷請求信號，并在開關(guān)分配邏輯設(shè)計時考慮同時針對正常請求以及推斷請求執(zhí)行仲裁，推斷成功時可有效降低路由流水的站數(shù).

2.2 SFRP路由器結(jié)構(gòu)設(shè)計

本文的主要目標(biāo)是通過在路由器內(nèi)部輸入端口E，W，N，S分別靜態(tài)地預(yù)構(gòu)一條連接其直向傳輸輸出端口的直通路徑，結(jié)合相應(yīng)的路徑重用、中斷機(jī)制，以期實現(xiàn)后續(xù)的報文在滿足匹配條件的情況下可以重用所預(yù)構(gòu)的直通路徑，旁通開關(guān)分配流水站，進(jìn)而降低報文傳輸延遲.

2.2.1 直通路徑的預(yù)構(gòu)

直通路徑定義為路由器內(nèi)部連接交叉開關(guān)某直向通信輸入、輸出端口的連接通路，如圖5所示.對于某個路由器而言，可以在其內(nèi)部4個輸入端口分別構(gòu)建一條連接其相應(yīng)直通輸出端口的傳輸路徑，如輸入端E至輸出端W的直通路徑、輸入端W至輸出端E的直通路徑、輸入端N至輸出端S的直通路徑、輸入端S至輸出端N的直通路徑.

為了實現(xiàn)直通路徑的預(yù)構(gòu)，本文擬在路由器輸入端口E，W，N，S分別設(shè)置一個直通路徑寄存項用于保存直通路徑的相關(guān)信息.考慮微片在路由器內(nèi)部的路由傳輸過程并借鑒偽電路機(jī)制^[11]的實現(xiàn)原理，路由器內(nèi)部某輸入端口開關(guān)路徑的預(yù)構(gòu)一般需要為其指明3個方面的信息：

1）輸入VC編號.由于開關(guān)分配的第一階段即對輸入端口中多條VC進(jìn)行仲裁，因此直通路徑的預(yù)構(gòu)需首先指定對應(yīng)的輸入VC.為了簡化實現(xiàn)，本文考慮在每個輸入端口4條VC中固定地選擇一條虛通道（如SVC）用于直通路徑的預(yù)構(gòu)，如圖6所示，SVC與其他虛通道正常地參與虛通道的分配過程，在報文的傳輸過程中優(yōu)先將空閑的SVC分配給請求的微片.因此對于直通路徑而言，不需要設(shè)置額外的寄存器來保存路徑輸入VC的相關(guān)信息.

2）輸出端口編號.對于給定的輸入端口，其所對應(yīng)的直通路徑輸出端口是一個固定的值，因此不需要設(shè)置額外的寄存器用于保存路徑輸出端口的相關(guān)信息.

3）有效性標(biāo)識Valid.Valid標(biāo)識項主要用于指示所保存的直通路徑是否有效.Valid具有兩種可能的取值：當(dāng)Valid為1時，表示當(dāng)前直通路徑可用，處于連接狀態(tài)；當(dāng)Valid為0時，表示當(dāng)前直通路徑不可用，處于中斷狀態(tài).

直通路徑的預(yù)構(gòu)是一個相對靜態(tài)的過程，其不需要任何之前以及當(dāng)前微片的路由以及仲裁信息，因此不會給路由器的關(guān)鍵路徑延遲帶來任何影響.直通路徑的連接與中斷由路徑的有效性標(biāo)識項來決定，結(jié)合適當(dāng)?shù)穆窂街袛鄼C(jī)制，可動態(tài)地實現(xiàn)直通路徑的連接以及中斷.直通路徑建立起來后，將一直保持連接狀態(tài)，當(dāng)且僅當(dāng)滿足相應(yīng)的路徑中斷條件時才對其連接進(jìn)行臨時的中斷，此時Valid標(biāo)識項的值為0.中斷條件釋放后，被中斷的直通路徑將繼續(xù)保持連接狀態(tài)，此時Valid標(biāo)識項的值為1.

2.2.2 直通路徑的重用

直通路徑建立以后，若當(dāng)前微片的路由信息與直通路徑輸出端口信息相匹配，且其開關(guān)路徑已處于連接狀態(tài)，則微片可直接利用該直通路徑進(jìn)行開關(guān)傳輸，旁通開關(guān)分配站.為了判斷當(dāng)前微片是否可以重用所預(yù)構(gòu)的直通路徑，本文擬在路由器各輸入端口E，W，N，S分別設(shè)置一個直通路徑比較邏輯，以輸入端口W為例，如圖7所示.

1）直通路徑比較邏輯首先檢查直通路徑的有效性標(biāo)識項Valid是否為1，若成立，則進(jìn)入2）進(jìn)行繼續(xù)匹配比較.若不成立，則比較邏輯發(fā)送不匹配信號.

2）比較直通路徑所在輸入端口中虛通道SVC中微片的路由信息是否與輸出端口E相匹配.若匹配，則比較邏輯發(fā)送一個匹配信號，表征當(dāng)前周期SVC中的微片可以重用該直通路徑進(jìn)行旁通傳輸.若不匹配，則發(fā)送一個不匹配信號，表征當(dāng)前微片需按照原有的路由流水策略完成交叉開關(guān)的分配，如圖4（c）所示.

直通路徑的可重用比較可以與VA實現(xiàn)并行處理，不會給當(dāng)前微片的VA過程帶來額外的延遲開銷.當(dāng)SA旁通時，由于當(dāng)前微片在到達(dá)下一級路由器之前VA和ST是一個相對獨(dú)立的過程，因此可以將其并行執(zhí)行，其流水線結(jié)構(gòu)如圖4（d）所示.

2.2.3 直通路徑的中斷

為了避免直通路徑的存在給其他報文的傳輸性能帶來消極的影響，需要建立相應(yīng)的中斷機(jī)制來實時地中斷部分直通路徑.為了實現(xiàn)這一目標(biāo)，本文考慮在以下3種情況下對于直通路徑進(jìn)行中斷：

1）直通路徑輸入端口中的微片請求其他輸出端口并獲得其開關(guān)分配授權(quán)時，該輸入端口的直通路徑必須中斷；

2）直通路徑的輸出端口對其他輸入端口中的微片進(jìn)行開關(guān)分配授權(quán)時，該輸出端口的直通路徑必須中斷；

3）下級路由器中所指定的輸入VC發(fā)生擁塞時，由于報文無法通過直通路徑繼續(xù)對其傳輸數(shù)據(jù)，此時直通路徑必須中斷.

直通路徑的中斷僅依賴于前一周期微片的開關(guān)仲裁信息以及下級路由器的VC狀態(tài)信息，因此不會給當(dāng)前微片的路由傳輸帶來任何性能上的開銷.直通路徑的中斷僅需將直通路徑Valid標(biāo)識項置為0即可.直通路徑中斷后，報文按照原有的路由流水策略進(jìn)行傳輸.

3 實驗及性能評價

3.1 實驗平臺

為了評價SFRP路由器的性能，本文基于硬件級網(wǎng)絡(luò)模擬平臺HS^[14]對四站經(jīng)典虛通道路由器（BASE）、超前路由器（BASE_LR）、推斷路由器（BASE_LR_SPC）、偽電路路由器（PSEUDO_CIRCUIT）以及SFRP路由器等5種片上路由器結(jié)構(gòu)進(jìn)行了RTL級硬件描述，并完成其功能驗證.為了獲得均等的比較，以上5種路由器結(jié)構(gòu)均包含5個輸入、輸出端口，每個輸入端口包含4條虛通道且其緩存大小均為4個微片，采用基于信用的流控機(jī)制以及輪轉(zhuǎn)仲裁分配策略.整個網(wǎng)絡(luò)平臺采用8×8 2D Mesh網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行互連.

3.2 合成通信模式

對于合成通信負(fù)載，本文采用了并行計算機(jī)系統(tǒng)中經(jīng)常使用到的4種通信模式，即均勻隨機(jī)（Uniform_random）、位反（Bit_reverse）、混洗（Shuffle）以及置換（transpose）等合成負(fù)載，其形式化見表1.

合成負(fù)載的注入過程采用Bernoulli 過程^[8]，即每個時鐘周期按照特定的概率隨機(jī)地生成報文.具體模擬過程中，本文將網(wǎng)絡(luò)模擬的升溫周期、采樣周期以及排空周期均設(shè)定為1 000個時鐘周期，對于每個合成通信負(fù)載采樣10次后對其相關(guān)信息進(jìn)行平均統(tǒng)計.

對于均勻隨機(jī)通信負(fù)載，SFRP路由器相對于BASE， BASE_LR， BASE_LR_SPC， PSEUDO_CIRCUIT等4種路由器結(jié)構(gòu)在報文注入率飽和之前均可獲得較為明顯的性能提升，且注入率較低時所獲得的性能提升幅度尤為明顯，如注入率為2%時SFRP路由器較以上4種路由器結(jié)構(gòu)可分別獲得59%，46%，25.6%以及9.5%左右的性能提升.對于位反、混洗以及置換等合成通信負(fù)載，SFRP路由器相對于BASE， BASE_LR， BASE_LR_SPC路由器結(jié)構(gòu)在注入率飽和之前均可獲得可觀的性能提升.由于以上3種通信模式中對于確定的源節(jié)點報文傳輸?shù)哪康墓?jié)點是一個固定的值，網(wǎng)絡(luò)中可能會存在大量的適用于偽電路機(jī)制的可重用路徑，因此PSEUDO_CIRCUIT路由器在報文注入率較低時

可以獲得與SFRP路由器相匹配的性能提升.隨著報文注入率的不斷增大，PSEUDO_CIRCUIT路由器各輸入端口的偽電路在多個輸出端口之間的頻繁切換導(dǎo)致可重用開關(guān)路徑的有效率不斷降低，其性能提升幅度亦更為有限.在報文注入率達(dá)到飽和之前，SFRP路由器較PSEUDO_CIRCUIT路由器在以上3種合成通信模式下最大可分別獲得9.6%，7.8%以及9.4%的性能提升.當(dāng)報文注入率飽和時，SFRP路由器與PSEUDO_CIRCUIT路由器均無法再通過開關(guān)路徑的重用來降低路由器的平均延遲，其延遲亦越來越趨近于BASE_LR_SPC路由器的平均延遲.

圖9所示為不同報文注入率下BASE_LR， BASE_LR_SPC， PSEUDO_CIRCUIT以及SFRP四種路由器結(jié)構(gòu)相對于BASE路由器的報文傳輸性能提升概率的大小.為簡化起見，本文僅討論均勻隨機(jī)通信模式下報文的通信情況.在以上4種路由器結(jié)構(gòu)中，BASE_LR路由器對于報文注入率的敏感度最低，當(dāng)報文注入率依次從2%增大到12%時，BASE_LR路由器對于性能的提升概率基本保持在24%.而其余3種依賴于推斷技術(shù)或路徑可重用技術(shù)的路由器結(jié)構(gòu)，諸如BASE_LR_SPC， PSEUDO_CIRCUIT以及SFRP路由器，隨著報文注入率的不斷增大，其所獲得的性能提升概率亦逐步降低，分別從注入率較低時的46%，55%，59%降低到注入率為12%時的38%，43%以及48%的性能提升幅度.在該通信模式下，SFRP路由器在報文注入率飽和前的任何注入率下所獲得的性能提升均優(yōu)于其他3種路由器結(jié)構(gòu)下的性能提升.

圖10所示為報文注入率較低時，SFRP路由器在不同網(wǎng)絡(luò)規(guī)模下相對于BASE_LR_SPC路由器所獲得的性能提升.為簡化起見，本文僅探討SFRP路由器相對于BASE_LR_SPC在不同網(wǎng)絡(luò)規(guī)模下的性能提升對比.在均勻隨機(jī)、位反、混洗以及置換4種通信模式下，隨著網(wǎng)絡(luò)規(guī)模的不斷增大SFRP路由器的性能提升幅度也逐步增加，分別從4×4網(wǎng)絡(luò)規(guī)模下的14%，7.5%，9.5%以及13.9%的性能提升增大為12×12網(wǎng)絡(luò)規(guī)模下的32%，25%，30%以及34%的性能提升幅度.網(wǎng)絡(luò)規(guī)模的大小將極大地影響報文傳輸時中間路由節(jié)點在報文傳輸所經(jīng)路由節(jié)點中所占比例的大小，進(jìn)而影響報文直通傳輸概率的大小.一般來說，網(wǎng)絡(luò)規(guī)模越大，SFRP路由器所獲得的性能提升越為明顯.

3.3 真實應(yīng)用蹤跡通信模式

為了模擬真實應(yīng)用，本文通過全系統(tǒng)模擬器GEMS^[15]模擬產(chǎn)生了Splash-2并行程序套件中8個測試用例運(yùn)行的通信蹤跡信息.模擬過程中配置的多核系統(tǒng)包含64個處理核，采用8×8 2D Mesh網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行互連.每個處理核的私有L1 指令/數(shù)據(jù)Cache 均為32 KB.邏輯上共享的L2 Cache 分為64個物理bank，每個bank 的容量為512 KB.Cache 一致性協(xié)議采用基于MOESI的目錄協(xié)議.

圖11所示為Splash-2測試集8種應(yīng)用蹤跡通信在不同路由器結(jié)構(gòu)下的規(guī)約化延遲對比.本文以四站虛通道路由器BASE的路由延遲作為延遲規(guī)約化的基準(zhǔn)，其余4種路由器結(jié)構(gòu)的延遲在圖中表征為其與基準(zhǔn)延遲的比較系數(shù).在真實應(yīng)用運(yùn)行的網(wǎng)絡(luò)通信蹤跡中，報文注入率一般較小且存在大量的交叉開關(guān)的時間局部性^[11]， PSEUDO_CIRCUIT路由器具有與SFRP路由器相類似的規(guī)約化延遲.在8種應(yīng)用蹤跡通信中，SFRP路由器相對于BASE， BASE_LR以及BASE_LR_SPC等路由器結(jié)構(gòu)均可獲得非常明顯的性能提升，其平均性能提升幅度分別達(dá)到57%， 45%以及21%.一般來說，SFRP路由器的性能提升主要取決于微片在路由器內(nèi)部各輸入端口的重用概率的大小.微片直通可重用概率越高，則利用開關(guān)直通路徑預(yù)構(gòu)機(jī)制可獲得的性能提升越為明顯.

圖12所示為SPLASH-2測試集8種應(yīng)用蹤跡通信中直通路徑重用概率的大小.直通路徑重用概率定義為報文在路由器內(nèi)部傳輸時重用預(yù)構(gòu)的開關(guān)直通路徑，實現(xiàn)SA旁通的概率大小.8種應(yīng)用蹤跡通信中，應(yīng)用程序water_spatial具有最高的直通路徑重用概率，約為52.2%，而平均重用概率約為48.9%.一般來說，應(yīng)用程序所具有的直通路徑可重用概率的大小主要取決于應(yīng)用程序通信時報文注入率的大小以及中間路由節(jié)點報文直通傳輸概率的大小.重用概率的大小亦決定著SFRP路由器可獲得的性能提升幅度的大小.

3.4 真實應(yīng)用蹤跡通信模式

本文在TSMC 40 nm工藝下使用Synopsys Design Compiler對BASE， BASE_LR， BASE_LR_SPC， PSEUDO_CIRCUIT以及SFRP等5種路由器結(jié)構(gòu)進(jìn)行綜合以評估路由器的硬件實現(xiàn)開銷.每個路由器的輸入端口包含4個虛通道，每個虛通道包含1個深度為4的FIFO緩存.微片的尺寸是131位，其中3位代表微片的類型，其余128為攜帶控制信息或者有效負(fù)載.表2給出了路由器的面積開銷和關(guān)鍵路由延時，其中BASE_LR_SPC， PSEUDO_CIRCUIT以及SFRP路由器具有相當(dāng)?shù)年P(guān)鍵路徑延遲，約為0.45 ns.SFRP的面積開銷較PSEUDO_CIRCUIT減少約1.5%，面積減少的原因在于SFRP路由器較PSEUDO_CIRCUIT路由器需要更少的寄存器用于保存預(yù)構(gòu)路徑的相關(guān)信息.

4 總 結(jié)

片上網(wǎng)絡(luò)延遲優(yōu)化技術(shù)是多核處理器研究領(lǐng)域的熱點問題.本文針對維序路由模式下報文傳輸時表現(xiàn)出的空間局部性，提出了一種適用于報文直向傳輸優(yōu)化的SFRP路由器結(jié)構(gòu)，通過在路由器內(nèi)部各輸入端口靜態(tài)地預(yù)構(gòu)對應(yīng)的直通路徑，結(jié)合適當(dāng)?shù)闹赜?、中斷機(jī)制，以期實現(xiàn)后續(xù)的報文在滿足匹配條件情況下旁通SA路由流水站，降低報文傳輸延遲.合成通信負(fù)載下的模擬結(jié)果表明，SFRP路由器在報文注入率飽和前較BASE， BASE_LR， BASE_LR_SPC， PSEUDO_CIRCUIT等4種路由器結(jié)構(gòu)可獲得非常明顯的性能提升，性能提升最大可達(dá)到59%， 46%， 25.6%以及9.5%.而真實應(yīng)用負(fù)載下的模擬結(jié)果表明SFRP路由器與PSEUDO_CIRCUIT路由器的平均延遲相當(dāng)，但較其他幾種路由器結(jié)構(gòu)可分別獲得57%， 45%以及21%的性能提升.

參考文獻(xiàn)

[1] MATSUTANI H， KOIBUCHI M， AMANO H， et al. Prediction router： a low-latency on-chip router architecture with multiple predictors[J]. IEEE Transactions on Computers， 2011， 60（6）：783-799.

[2] JERGER N E， LIPASTI M， PEH L S.Circuit-switched coherence [J]. Computer Architecture Letters， 2007，6（1）： 5-8.

[3] NYCHIS G P， FALLIN C， MOSCIBRODA T， et al. On-chip networks from a networking perspective： congestion and scalability in many-core interconnects[C]//Proceedings of the ACM SIGCOMM 2012 Conference on Applications， Technologies， Architectures， and Protocols for Computer Communication. New York： ACM， 2012： 407-418.

[4] DALLY W J， TOWLES B. Route packets， not wires： on-chip interconnection networks[C]//Proceedings of the 38th Design Automation Conference. New York： IEEE， 2001：684-689.

[5] BENINI L， MICHELI G D. Networks on chips： a new SoC paradigm[J]. IEEE Computer， 2002， 35（1）： 70-78.

[6] GOOSSENS K， DIELISSEN J， RADULESCU A. AEthereal network on chip： concepts， architectures， and implementations [J]. IEEE Design and Test of Computers， 2005， 22 （5）： 414-421.

[7] WOO S C， OHARA M， TORRIE E， et al. The SPLASH-2 programs： characterization and methodological considerations[C]//Proceedings of the 22nd Annual International Symposium on Computer Architecture. New York： IEEE， 1995： 24-36.

[8] DALLY W J， TOWLES B. Principles and practices of interconnection network[M]. San Francisco： Morgan Kaufmann， 2004.

[9] GALLES M. Scalable pipelined Interconnect for distributed endpoint routing： the SGI SPIDER chip[C]//Proceedings of Hot Interconnects Symposium IV. 1996： 141-146.

[10]PEH L S， DALLY W J. A delay model and speculative architecture for pipelined routers[C]//Proceedings of the 7th International Symposium on High-Performance Computer Architecture （HPCA2001）. Washington， DC：IEEE Computer Society， 2001：255-266.

[11]AHN M， KIM E J. Pseudo-circuit： accelerating communication for on-chip interconnection networks[C]//Proceedings of the 43rd Annual IEEE/ACM International Symposium on Microarchitecture （MICRO2010）. New York： IEEE， 2010：399-408.

[12]KUMAR A， PEH L S， JHA N K. Token flow control[C]// Proceedings of the 41st International Symposium on Microarchitecture.Washington， DC：IEEE Computer Society， 2007：342-353.

[13]KUMAR A， PEH L S， KUNDU P， et al. Express virtual channels： towards the ideal interconnection fabric[C]//Proceedings of the 34th Annual International Symposium on Computer Architecture （ISCA'2007）. New York： ACM， 2007：150-161.

[14]CHEN Y， XIE L， LI J， et al. A trace-driven hardware-level simulator for the design and verification of network-on-chips[C]//Proceedings of International Conference on Computers， Communications， Control and Automation， CCCA’11. New York： IEEE， 2011：32-35.

[15]MARTIN M M K， SORIN D J， BECKMANN B M， et al. Multifacet’s general execution-driven multiprocessor simulator （GEMS） toolset[J]. ACM Sigarch Computer Architecture News， 2005， 33（4）：92-99.