李存祿　董德尊　吳際　雷斐　王克非　廖湘科

摘 要：開關(guān)分配位于片上網(wǎng)絡(luò)路由器流水線的關(guān)鍵路徑上，對路由器以至整個片上網(wǎng)絡(luò)的性能都會產(chǎn)生很大影響.已有的開關(guān)分配方法主要針對標準流水線路由器進行分析改進，缺乏對低延遲路由器中基于時間序列的開關(guān)分配方法的研究.本文首次在低延遲路由器上實現(xiàn)了基于時間序列的開關(guān)分配機制，并針對分配過程中優(yōu)先矩陣的構(gòu)造特點進行了優(yōu)化改進.仿真實驗結(jié)果表明在低延遲路由器中采用基于時間序列的開關(guān)分配策略可以使片上網(wǎng)絡(luò)的性能得到很大提升.

關(guān)鍵詞：片上網(wǎng)絡(luò)；開關(guān)分配；時間序列；低延遲路由器；短報文

中圖分類號：TP391.9 文獻標識碼：A

隨著芯片制造工藝的提高，單個芯片上所能集成的處理器核的數(shù)目也在不斷增加[1].這些處理器核通過片上網(wǎng)絡(luò)進行互連，并通過片上網(wǎng)絡(luò)的數(shù)據(jù)交互來協(xié)同完成計算任務(wù)，因此片上互連網(wǎng)絡(luò)的性能將極大地影響多核系統(tǒng)的整體性能.

開關(guān)分配位于片上網(wǎng)絡(luò)路由器流水線的關(guān)鍵路徑上，對路由器以至整個片上網(wǎng)絡(luò)的性能都會產(chǎn)生很大影響.通常的開關(guān)分配方法通過提高當前周期內(nèi)匹配的最大個數(shù)來提高性能[2]，以使分配過程實現(xiàn)極大匹配或最大匹配.基于這一理念設(shè)計的分配方法有iSLIP[3]，Wavefront[4]，Augmenting Paths（增量路徑）[1]等.

但是單個周期內(nèi)的最大匹配并不一定就能實現(xiàn)整個系統(tǒng)上的性能最優(yōu)，并且單個周期內(nèi)的最大匹配往往使得硬件復(fù)雜度較高，功耗和時延也會相應(yīng)增加.因此，新的開關(guān)分配方法在時間維度上進行了優(yōu)化.George發(fā)現(xiàn)[5]，當前片上網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包很多都是長度較短的包，例如在實際系統(tǒng)中有很大部分（78.7%）的數(shù)據(jù)包都是單切片報文（Single Flit Packet）[6]，而且這些單切片報文所請求的輸出端口往往和上一周期該端口成功分配的輸出端口相同.基于此觀察， Packet Chaining[5]和 PseudoCircuit[2]方法發(fā)現(xiàn)，加入前一周期成功分配的信息可以提高吞吐率；而TSRouter的方法進一步引入了時間序列（TimeSeries， TS）的概念，提出將未來多個周期的開關(guān)請求信息加入分配過程會進一步提高性能.雖然TSRouter中的方法使資源分配的性能得到很大提高，但是該方法只在普通路由器體系結(jié)構(gòu)（General Router Architecture）[7]上進行了實現(xiàn)，而當前的路由器結(jié)構(gòu)已經(jīng)在普通路由器上進行了很大改進，一個典型的例子就是低延遲路由器（Lowlatency Router）[8] ，該結(jié)構(gòu)極大地減少了路由器流水線的級數(shù)，使得數(shù)據(jù)包在路由器中的處理時間更短.為了使片上網(wǎng)絡(luò)中路由器的整體性能最佳，我們將這兩種技術(shù)進行了結(jié)合，在低延遲路由器上實現(xiàn)了TSRouter中提出的時間序列的方法，并對該方法進行了一些改進，降低了方法的復(fù)雜性，同時保證了性能.

本文首先介紹片上網(wǎng)絡(luò)中低延遲路由器的體系結(jié)構(gòu)，然后說明低延遲路由器上基于時間序列方法的實現(xiàn)過程和我們所做的改進工作，最后給出我們的方法在Booksim模擬器下的仿真結(jié)果以及對今后工作的展望.

1 低延遲路由器

普通路由器體系結(jié)構(gòu)由5個流水階段組成：路由計算（Routing Computation），虛通道分配（Virtualchannel Allocation），開關(guān)分配（Switch Allocation），開關(guān)通過（Switch Traversal）和鏈路通過（Link Traversal）.圖1（a）展示了這種路由器的結(jié)構(gòu)[1].每個輸入端和輸出端可以有多個虛通道，數(shù)據(jù)包要從輸入端口到達特定的輸出端口，必須由開關(guān)分配器（Switch Allocator）分配一個時鐘周期，以使數(shù)據(jù)包在這個時鐘周期內(nèi)從開關(guān)中通過.每一個輸入端首先通過路由計算模塊確定當前數(shù)據(jù)包所需要到達的輸出端口和允許的虛通道集合，然后再由虛通道分配器分配下一跳路由器輸入端的一個空閑虛通道供數(shù)據(jù)包的輸入.數(shù)據(jù)包要從輸入端口到達特定的輸出端口，必須由開關(guān)分配器（Switch Allocator）分配一個時鐘周期，以使數(shù)據(jù)包在這個時鐘周期內(nèi)從開關(guān)中通過，開關(guān)分配器就是要在不產(chǎn)生資源沖突的前提下，決定當前周期哪個輸入端可以向分配的輸出端傳輸數(shù)據(jù).在同一時鐘周期內(nèi)，每個輸入端只能向一個輸出端傳輸數(shù)據(jù)，每個輸出端也只能接收一個輸入端的數(shù)據(jù).

為了減少數(shù)據(jù)包在片上網(wǎng)絡(luò)的傳輸時間，提高吞吐率，路由器的結(jié)構(gòu)進行了很多改進.圖1（b）是一種低延遲路由器體系結(jié)構(gòu)[2]，我們將在此結(jié)構(gòu)上實現(xiàn)改進后的基于時間序列的開關(guān)分配方法.該結(jié)構(gòu)采用了適應(yīng)性的超前路由（Lookahead Routing）[9]技術(shù)以及分配預(yù)測技術(shù)[10-12]，省去了路由計算的流水階段并將開關(guān)分配和虛通道分配并行執(zhí)行.這種低延遲路由器比原來普通路由器減少了兩個流水周期.

2 低延遲路由器中基于時間序列分配方法

的實現(xiàn)

時間序列分配的主要策略是優(yōu)先分配可能和下一周期的請求沖突的當前請求.該方法首先獲取下一周期的請求信息，如果當前周期資源的請求矩陣[1]中存在可能和下一周期的請求相沖突的請求，則優(yōu)先分配這些可能發(fā)生沖突的請求.具體的說，就是在資源請求矩陣中將與下一周期的請求在同一行同一列的其他請求的優(yōu)先級升高一級，這樣在資源分配的時候就可以優(yōu)先分配這些可能和下一周期請求發(fā)生沖突的請求.

在低延遲路由器下實現(xiàn)時間序列分配方法需要對路由器進行新的設(shè)計，關(guān)鍵是如何在當前周期內(nèi)獲取下一周期將要到達的請求信息.圖2（a）所示的是TSRouter的數(shù)據(jù)流，它在普通路由器五級流水的基礎(chǔ)上，通過增加一條從路由計算階段到開關(guān)分配階段的通路，將路由信息提前傳遞給開關(guān)分配階段，而正常的數(shù)據(jù)流則要先通過虛通道分配后才能到達開關(guān)分配階段，這樣在開關(guān)分配階段就可以提前一個周期知道下一周期要到達的請求的信息.

但是對低延遲路由器來說，通過增加新的通路來提前獲取下一周期請求信息的方法卻很難實現(xiàn).圖2（b）是低延遲路由器的數(shù)據(jù)流圖，該結(jié)構(gòu)路由器的流水線由路由計算/虛通道分配/開關(guān)分配（NRC/VA/SA）、開關(guān)通過（ST）和鏈路通過（LT）3部分組成.由于采用了超前路由和預(yù)測技術(shù)，路由計算、虛通道和開關(guān)分配可以并行執(zhí)行.當數(shù)據(jù)包從輸入緩存中讀出后，如果是頭切片（Head Flit）則會在下一周期同時進行超前路由計算、虛通道分配和開關(guān)分配，路由信息會和數(shù)據(jù)包一起到達路由器并立即進入開關(guān)分配階段，因此我們無法提前一個周期獲取路由信息.但是在進行開關(guān)分配的時候，我們可以知道哪個輸入端的請求是新到達的，也就是說，這個請求在上一周期沒有出現(xiàn)過.當一個新請求到達時，它之后的請求很可能申請的是和它相同的資源，即對同一個資源的請求可能連續(xù)多次出現(xiàn).這樣，我們雖然不能得到下一周期的請求情況，但是我們可以利用當前周期新加入請求的信息.如果一個新到達的請求和當前周期的任何一個請求具有相同的輸入端或輸出端，則優(yōu)先分配這些可能發(fā)生沖突的請求.具體來說，就是將當前周期中沖突請求的優(yōu)先級升高一級，使得這些請求可以被優(yōu)先分配.因為新到達的請求所申請的輸出端口被連續(xù)申請的次數(shù)很可能大于其他輸入端口連續(xù)申請同一個輸出端口的次數(shù)，所以如果其他輸入端口上的請求優(yōu)先分配的話，就可以使這些可能產(chǎn)生沖突的請求盡早分配完，以避免在接下來的周期與新到達的請求發(fā)生沖突.這種方法的有效性在片上網(wǎng)絡(luò)的模擬實驗中得到進一步驗證.圖3顯示了利用這種改進后的時間序列方法（TS）進行開關(guān)分配的原理.圖3（a）表示的是在低延遲路由器（RouterL）中使用改進后的TS方法進行開關(guān)分配的過程，圖3（b）顯示的是在普通路由器（RouterG）中使用改進后的TS方法進行開關(guān)分配的過程，圖3（c）顯示的是在低延遲路由器中使用PacketChaining（PC）方法進行開關(guān)分配的過程.圖中將開關(guān)分配的請求通過矩陣表示，矩陣的每行代表一個輸入端，每列代表一個輸出端，行列相交的小方塊則表示該輸入端對輸出端的請求狀態(tài).圖中灰色方塊表示該請求在上一周期被成功分配，圓圈表示當前周期的請求或資源分配情況，而圓圈內(nèi)的數(shù)字則表示該請求在隨后的多少個周期內(nèi)會連續(xù)產(chǎn)生.這3種不同的分配過程使用相同的請求矩陣，該請求矩陣表示的是周期i中路由器開關(guān)輸入端的所有請求的狀態(tài).為了更清楚地說明問題，我們沒有考慮在每個周期中不斷加入的數(shù)據(jù)包對分配過程的影響.我們給出了3種不同的分配方法將這些請求全部分配完所經(jīng)歷的過程，并給出了每個周期中成功分配的請求情況.圖中請求矩陣中坐標為（2，2）的請求是新到達的，有兩個連續(xù)的請求，該周期其他請求不是新到達的，只有一個連續(xù)的請求.圖3（a）中，由于在低延遲路由器中，數(shù)據(jù)包剛到達路由器就可以進行開關(guān)分配，TS方法在3個周期內(nèi)就可以分配完所有請求.而圖3（b）中，由于普通路由器數(shù)據(jù)包達到后需要先經(jīng)過路由計算和虛通道分配兩個步驟才能開始進行開關(guān)分配，所以數(shù)據(jù)包到達后的前兩個周期內(nèi)沒有成功分配的開關(guān)請求，直到第三個周期才開始按照TS方法進行開關(guān)分配，這樣普通路由器就比低延遲路由器多出兩個周期的延遲.從圖3（c）中可以看出，同樣是在低延遲路由器中，TS方法的性能明顯優(yōu)于PC，PC優(yōu)先分配與前一周期分配結(jié)果相同的請求，需要4個周期才能分配完所有請求，而TS方法則只需要3個周期就能分配完所有請求.

但是對低延遲路由器來說，通過增加新的通路來提前獲取下一周期請求信息的方法卻很難實現(xiàn).圖2（b）是低延遲路由器的數(shù)據(jù)流圖，該結(jié)構(gòu)路由器的流水線由路由計算/虛通道分配/開關(guān)分配（NRC/VA/SA）、開關(guān)通過（ST）和鏈路通過（LT）3部分組成.由于采用了超前路由和預(yù)測技術(shù)，路由計算、虛通道和開關(guān)分配可以并行執(zhí)行.當數(shù)據(jù)包從輸入緩存中讀出后，如果是頭切片（Head Flit）則會在下一周期同時進行超前路由計算、虛通道分配和開關(guān)分配，路由信息會和數(shù)據(jù)包一起到達路由器并立即進入開關(guān)分配階段，因此我們無法提前一個周期獲取路由信息.但是在進行開關(guān)分配的時候，我們可以知道哪個輸入端的請求是新到達的，也就是說，這個請求在上一周期沒有出現(xiàn)過.當一個新請求到達時，它之后的請求很可能申請的是和它相同的資源，即對同一個資源的請求可能連續(xù)多次出現(xiàn).這樣，我們雖然不能得到下一周期的請求情況，但是我們可以利用當前周期新加入請求的信息.如果一個新到達的請求和當前周期的任何一個請求具有相同的輸入端或輸出端，則優(yōu)先分配這些可能發(fā)生沖突的請求.具體來說，就是將當前周期中沖突請求的優(yōu)先級升高一級，使得這些請求可以被優(yōu)先分配.因為新到達的請求所申請的輸出端口被連續(xù)申請的次數(shù)很可能大于其他輸入端口連續(xù)申請同一個輸出端口的次數(shù)，所以如果其他輸入端口上的請求優(yōu)先分配的話，就可以使這些可能產(chǎn)生沖突的請求盡早分配完，以避免在接下來的周期與新到達的請求發(fā)生沖突.這種方法的有效性在片上網(wǎng)絡(luò)的模擬實驗中得到進一步驗證.圖3顯示了利用這種改進后的時間序列方法（TS）進行開關(guān)分配的原理.圖3（a）表示的是在低延遲路由器（RouterL）中使用改進后的TS方法進行開關(guān)分配的過程，圖3（b）顯示的是在普通路由器（RouterG）中使用改進后的TS方法進行開關(guān)分配的過程，圖3（c）顯示的是在低延遲路由器中使用PacketChaining（PC）方法進行開關(guān)分配的過程.圖中將開關(guān)分配的請求通過矩陣表示，矩陣的每行代表一個輸入端，每列代表一個輸出端，行列相交的小方塊則表示該輸入端對輸出端的請求狀態(tài).圖中灰色方塊表示該請求在上一周期被成功分配，圓圈表示當前周期的請求或資源分配情況，而圓圈內(nèi)的數(shù)字則表示該請求在隨后的多少個周期內(nèi)會連續(xù)產(chǎn)生.這3種不同的分配過程使用相同的請求矩陣，該請求矩陣表示的是周期i中路由器開關(guān)輸入端的所有請求的狀態(tài).為了更清楚地說明問題，我們沒有考慮在每個周期中不斷加入的數(shù)據(jù)包對分配過程的影響.我們給出了3種不同的分配方法將這些請求全部分配完所經(jīng)歷的過程，并給出了每個周期中成功分配的請求情況.圖中請求矩陣中坐標為（2，2）的請求是新到達的，有兩個連續(xù)的請求，該周期其他請求不是新到達的，只有一個連續(xù)的請求.圖3（a）中，由于在低延遲路由器中，數(shù)據(jù)包剛到達路由器就可以進行開關(guān)分配，TS方法在3個周期內(nèi)就可以分配完所有請求.而圖3（b）中，由于普通路由器數(shù)據(jù)包達到后需要先經(jīng)過路由計算和虛通道分配兩個步驟才能開始進行開關(guān)分配，所以數(shù)據(jù)包到達后的前兩個周期內(nèi)沒有成功分配的開關(guān)請求，直到第三個周期才開始按照TS方法進行開關(guān)分配，這樣普通路由器就比低延遲路由器多出兩個周期的延遲.從圖3（c）中可以看出，同樣是在低延遲路由器中，TS方法的性能明顯優(yōu)于PC，PC優(yōu)先分配與前一周期分配結(jié)果相同的請求，需要4個周期才能分配完所有請求，而TS方法則只需要3個周期就能分配完所有請求.

對每個請求的優(yōu)先級的記錄，是通過和TSRouter中相同的優(yōu)先級矩陣[9]來實現(xiàn)的，圖4說明了這種優(yōu)先級矩陣的構(gòu)造方法.圖中黑點代表新到達的請求，圓圈表示當前的請求.對于每個新到達的請求，我們將與它在同一行和同一列的其他請求的優(yōu)先級升高一位，這樣每個請求都有自己對應(yīng)的優(yōu)先級，然后在開關(guān)分配的過程中選取優(yōu)先級最高的請求優(yōu)先分配.如圖所示，由于（1，1）請求的優(yōu)先級為0，小于（1，2）請求的優(yōu)先級1，所以在開關(guān)分配中會優(yōu)先選擇（1，2）進行分配；同樣，（2，4）的優(yōu)先級2高于（3，4）的優(yōu)先級1，所以也會優(yōu)先選擇（2，4）進行分配.

通過實驗我們發(fā)現(xiàn)，構(gòu)造優(yōu)先級矩陣時可以不考慮一個新到達請求的輸出端是多少，而直接根據(jù)這個新到達請求的輸入端來進行決策，即選擇一個固定的輸出端口.雖然這種策略只根據(jù)輸入端口的信息來決定各個請求的優(yōu)先級，但是依然可以達到較理想的性能.基于以上觀察，我們對TS分配方法進行了簡化，只需要在每個輸入端口處判斷該端口的數(shù)據(jù)包是否是新到達的，如果是則將其他端口的請求的優(yōu)先級升高后再進行開關(guān)分配.這種方法實現(xiàn)起來比較簡單，硬件復(fù)雜度較低，我們只需要在每個輸入端口增加一個判斷邏輯，檢測是否有新的請求到達并以此來更新優(yōu)先級矩陣即可，該方法的性能評測結(jié)果將在下一章進行介紹.

3 性能評估

為了測試改進后的TS方法在低延遲路由器中的效果，本文使用修改后的BookSim模擬器進行實驗仿真.實驗在一個擁有64個節(jié)點的8×8二維Mesh網(wǎng)絡(luò)[1]中進行，每個節(jié)點都連接有一個路由器，負責數(shù)據(jù)產(chǎn)生、轉(zhuǎn)發(fā)或接收.每個路由器有5個端口（網(wǎng)絡(luò)邊緣端口數(shù)可能不足5個），其中4個端口與相鄰的路由器連接，一個端口負責接收和向網(wǎng)絡(luò)中注入數(shù)據(jù)包.網(wǎng)絡(luò)中的每條鏈路由不同方向的兩條鏈路組成，鏈路傳輸?shù)难舆t是一個周期.實驗采用確定性維序路由（Deterministic dimensionorder routing，DOR）以及經(jīng)典的VC流控策略[10]，每個端口設(shè)有4個VC，每個VC的緩存長度是8個flit.我們將迭代一次的iSLIP（iSLIP1）分配器作為基準進行比較.實驗中使用只有一個Flit的報文，并采用多種合成負載（synthetic traffic）進行評測.我們還與兩種可以實現(xiàn)極大匹配的分配器進行了比較：maxsize和wavefront，maxsize分配方法采用Augmenting paths的策略實現(xiàn)最大分配，wavefront方法采用復(fù)雜的硬件邏輯實現(xiàn)極大匹配.

我們首先對方法的吞吐率進行了評測.圖5給出了均勻負載下吞吐率隨注入率的變化情況，我們將TS方法和一次迭代的iSLIP（iSLIP1）、兩次迭代的iSLIP（iSLIP2）以及PC進行了比較.從圖中可以看出，當注入速率小于0.4的時候，4種方法的吞吐率都呈直線上升，而當注入速率繼續(xù)增大時，不同的分配器的性能開始有了明顯差異.各個分配器的吞吐率均在約0.45的位置達到最大值，隨后開始下降或保持不變.在整個過程中TS的性能最優(yōu)，而PC優(yōu)于iSLIP2和iSLIP1.iSLIP1方法作為其余三種方法實現(xiàn)的基礎(chǔ)，性能最低.在飽和注入速率下，和iSLIP1相比，TS方法性能的提高比PC性能的提高高出27%.iSLIP2并沒有比TS和PC有更優(yōu)的性能，這是因為兩次的迭代增加了路由器中開關(guān)分配所需的時鐘周期數(shù)，并且迭代帶來的分配效率的提高也并不明顯.

圖6比較了低延遲路由器與普通路由器的最大吞吐率.從圖中可以看出，在均勻通信模式下，低延遲路由器中開關(guān)分配方法所能達到的最大吞吐率均優(yōu)于普通路由器.對于特定的路由器結(jié)構(gòu)，TS方法的性能均優(yōu)于其他分配方法.我們發(fā)現(xiàn)在低延遲路由器中，maxsize的分配方法可以達到和TS方法相近的性能，這是因為maxsize方法在每個周期都分配最多的請求.這種只根據(jù)當前周期請求狀況進行最大分配的策略，在請求數(shù)量較多的情況下具有很高的性能優(yōu)勢，而低延遲路由器由于縮短了路由器流水線長度，使得報文可以更快到達開關(guān)輸入端，也就使得開關(guān)輸入端能夠有更多的請求等待分配，進而使得maxsize的性能得到很大提升.

圖7顯示的是不同注入速率時在均勻負載下兩種路由器結(jié)構(gòu)中不同開關(guān)分配方法的延遲.圖7（a）顯示的是在普通路由器結(jié)構(gòu)下的評測結(jié)果，圖7（b）顯示的是在低延遲路由器中的評測結(jié)果，圖7（c）顯示的是網(wǎng)絡(luò)低注入率時，采用不同分配器時的數(shù)據(jù)包平均延遲在普通路由器和低延遲路由器下的變化情況的比較.圖中注入速率從0.1一直變化到1，數(shù)據(jù)包的延遲呈增長趨勢.從圖中可以看到，注入速率小于0.4時，由于網(wǎng)絡(luò)中數(shù)據(jù)包較少而不會發(fā)生阻塞，數(shù)據(jù)包的延遲也相應(yīng)的很小.而當注入速率大于0.4時，延遲開始快速增加.這是由于當注入速率超過飽和點時，在網(wǎng)絡(luò)中某些節(jié)點上，數(shù)據(jù)包到達的速度可能超過節(jié)點的處理速度，造成數(shù)據(jù)包在該節(jié)點的阻塞，并且這種阻塞的情況還可以以樹形的形式向數(shù)據(jù)包的源節(jié)點擴散，形成飽和樹（Tree Saturation）[1].而在注入速率不斷增加的過程中，TS的性能總是優(yōu)于其他分配器，PC，maxsize，wavefront，iSLIP2和iSLIP1這3種方法的延遲依次升高.在注入速率大于飽和點時，與iSLIP1相比，TS分配性能的提高比PC性能的提高最高可以高出39%.

為了對性能進行進一步評測，我們對非均勻負載下方法的性能也進行了評測.圖8顯示了延遲的評測結(jié)果.對于不同的流量模型，開關(guān)分配方法的性能差異很大，雖然低延遲路由器中分配方法的性能普遍優(yōu)于普通路由器，但是不同的分配方法在同一種流量模型下，以及同一種分配方法在不同的流量模型下性能的差異也是很大的.可以看出當數(shù)據(jù)包的注入速率較大時，TS方法的性能優(yōu)勢也較明顯，這是因為在較高注入速率下TS可以獲取更多的下一周期的請求信息.而PC方法則會在注入速率較大時出現(xiàn)饑餓（starvation）現(xiàn)象，這是由于PC方法在當前請求跟上一周期請求相同時會盡可能地保留當前分配情況，這樣初始時未分配到資源的請求可能要等待很長時間來得到它所請求的資源，從而導(dǎo)致這些請求經(jīng)常處于饑餓狀態(tài).

（a） bitcomp

（b） neighbor

（c） tornado

圖8 非均勻通信模式下網(wǎng)絡(luò)延遲與注入速率的關(guān)系

Fig.8 Injection ratelatency under

different traffic patterns

PC和TS方法在時間維度上對開關(guān)分配進行了擴展，實現(xiàn)了高效的單周期可實現(xiàn)的分配方法.但是在報文長度較長的網(wǎng)絡(luò)中，在時間維度上獲取的信息對當前分配的影響并不大或者會產(chǎn)生負面的影響（如進一步增加某些報文的等待時間，加劇饑餓現(xiàn)象），因此在報文長度較長時，這種基于時間維度設(shè)計的分配方法性能并不具有優(yōu)勢，甚至比其他分配方法性能更低.圖9顯示了均勻通信模式下，在低延遲路由器中，數(shù)據(jù)包長度從1（flits）到16（flits）時，網(wǎng)絡(luò)的最大吞吐率的變化情況.從圖中可以看出，當數(shù)據(jù)包長度不斷變長時，各種分配策略的性能均有所降低，但是PC和TS方法降低的速度比其他分配方法要快.這兩種方法在短報文，特別是單切片報文情況下性能很高，而當報文長度逐漸增加到16時，最大吞吐率與其他分配方法相差不多，或者比某些分配方法的性能更低.

Packet length in flits

圖9 均勻通信模式下低延遲路由器網(wǎng)絡(luò)

最大吞吐率隨報文長度的變化

Fig.9 Maximum throughput by packet length for the

different allocators under uniform traffic pattern

4 結(jié) 論

本文在一種低延遲路由器上實現(xiàn)了改進后的時間序列分配方法.時間序列分配方法能夠使路由器中開關(guān)分配的效率得到很大提高，低延遲路由器極大地減少了路由器流水線的長度，通過將這兩種技術(shù)進行結(jié)合，能夠更好地提升片上網(wǎng)絡(luò)的性能.實驗證明，在低延遲路由器中，時間序列分配方法能夠使網(wǎng)絡(luò)的吞吐率得到很大提高，同時降低了數(shù)據(jù)包在網(wǎng)絡(luò)中的延遲.

參考文獻

[1] DALLY W J， TOWLES B P. Principles and practices of interconnection networks[M]. San Francisco， USA： Elsevier， 2004.

[2] AHM M， KIM E J. Pseudocircuit： Accelerating communication for onchip interconnection networks[C]//Proceedings of the 43rd Annual IEEE/ACM International Symposium on Microarchitecture. USA： 2010 IEEE Computer Society： 399-408.

[3] MCKEOWN N. The iSLIP scheduling algorithm for inputqueued switches[J]. IEEE/ACM， 1999， 7（2）： 188-201.

[4] TAMIR Y， CHI H C. Symmetric crossbar arbiters for VLSI communication switches[J]. Parallel and Distributed Systems， 1993， 4（1）： 13-27.

[5] MICHELOGIANNAKIS G， JIANG N， BECKER D， et al. Packet chaining： efficient singlecycle allocation for onchip networks[C]//Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture. USA： 2011 ACM： 83-94.

[6] MA S， JERGER N E， WANG Z. Whole packet forwarding： Efficient design of fully adaptive routing algorithms for networksonchip[C]//High Performance Computer Architecture （HPCA）. USA： 2012 IEEE： 1-12.

[7] AGARWAL N， KRISHNA T， PEH L S， et al. GARNET： a detailed onchip network model inside a fullsystem simulator[C]//Performance Analysis of Systems and Software. USA： 2009 IEEE： 33-42.

[8] MULLINS R， WEST A， MOORE S. Lowlatency virtualchannel routers for onchip networks[C]//ACM SIGARCH Computer Architecture News. USA： 2004 IEEE Computer Society， 32（2）： 188.

[9] GALLES M. Scalable pipelined interconnect for distributed endpoint routing： the SGI SPIDER chip[C]//Hot Interconnects. USA： 1996 IEEE： 96.

[10]PEH L S， DALLY W J. A delay model and speculative architecture for pipelined routers[C]//HighPerformance Computer Architecture. Mexico： 2001 IEEE： 255-266.

[11]CHANG Y Y， HUANG Y S C， POREMBA M， et al. Tsrouter： On maximizing the qualityofallocation in the onchip network[C]//High Performance Computer Architecture （HPCA2013）. China： 2013 IEEE： 390-399.

[12]DALLY W J. Virtualchannel flow control[J]. Parallel and Distributed Systems， 1992， 3（2）： 194-205.