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

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

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

中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

1 低延遲路由器

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

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

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

的實(shí)現(xiàn)

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

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

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

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

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

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

3 性能評(píng)估

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

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

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

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

為了對(duì)性能進(jìn)行進(jìn)一步評(píng)測(cè)，我們對(duì)非均勻負(fù)載下方法的性能也進(jìn)行了評(píng)測(cè).圖8顯示了延遲的評(píng)測(cè)結(jié)果.對(duì)于不同的流量模型，開關(guān)分配方法的性能差異很大，雖然低延遲路由器中分配方法的性能普遍優(yōu)于普通路由器，但是不同的分配方法在同一種流量模型下，以及同一種分配方法在不同的流量模型下性能的差異也是很大的.可以看出當(dāng)數(shù)據(jù)包的注入速率較大時(shí)，TS方法的性能優(yōu)勢(shì)也較明顯，這是因?yàn)樵谳^高注入速率下TS可以獲取更多的下一周期的請(qǐng)求信息.而PC方法則會(huì)在注入速率較大時(shí)出現(xiàn)饑餓（starvation）現(xiàn)象，這是由于PC方法在當(dāng)前請(qǐng)求跟上一周期請(qǐng)求相同時(shí)會(huì)盡可能地保留當(dāng)前分配情況，這樣初始時(shí)未分配到資源的請(qǐng)求可能要等待很長(zhǎng)時(shí)間來得到它所請(qǐng)求的資源，從而導(dǎo)致這些請(qǐng)求經(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方法在時(shí)間維度上對(duì)開關(guān)分配進(jìn)行了擴(kuò)展，實(shí)現(xiàn)了高效的單周期可實(shí)現(xiàn)的分配方法.但是在報(bào)文長(zhǎng)度較長(zhǎng)的網(wǎng)絡(luò)中，在時(shí)間維度上獲取的信息對(duì)當(dāng)前分配的影響并不大或者會(huì)產(chǎn)生負(fù)面的影響（如進(jìn)一步增加某些報(bào)文的等待時(shí)間，加劇饑餓現(xiàn)象），因此在報(bào)文長(zhǎng)度較長(zhǎng)時(shí)，這種基于時(shí)間維度設(shè)計(jì)的分配方法性能并不具有優(yōu)勢(shì)，甚至比其他分配方法性能更低.圖9顯示了均勻通信模式下，在低延遲路由器中，數(shù)據(jù)包長(zhǎng)度從1（flits）到16（flits）時(shí)，網(wǎng)絡(luò)的最大吞吐率的變化情況.從圖中可以看出，當(dāng)數(shù)據(jù)包長(zhǎng)度不斷變長(zhǎng)時(shí)，各種分配策略的性能均有所降低，但是PC和TS方法降低的速度比其他分配方法要快.這兩種方法在短報(bào)文，特別是單切片報(bào)文情況下性能很高，而當(dāng)報(bào)文長(zhǎng)度逐漸增加到16時(shí)，最大吞吐率與其他分配方法相差不多，或者比某些分配方法的性能更低.

Packet length in flits

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

最大吞吐率隨報(bào)文長(zhǎng)度的變化

Fig.9 Maximum throughput by packet length for the

different allocators under uniform traffic pattern

4 結(jié) 論

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

參考文獻(xiàn)

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