胡海洋，李悅瑤，李 陽，趙玉來，李建華

（1 合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，合肥 230601；2 合肥工業(yè)大學(xué) 情感計(jì)算與先進(jìn)智能機(jī)器安徽省重點(diǎn)實(shí)驗(yàn)室，合肥 230601）

0 引言

隨著半導(dǎo)體工業(yè)的不斷發(fā)展，芯片上集成了越來越多的處理器核，這些集成在芯片上的處理器核在提高性能的同時(shí)，各處理核間的通信也帶來了高延遲和高能耗的問題，因此芯片上多個(gè)處理器核之間的通信延遲成為制約芯片性能提高的重要因素。當(dāng)下，片上互聯(lián)網(wǎng)絡(luò)正在發(fā)生巨變，計(jì)算機(jī)體系結(jié)構(gòu)專家提出了一種叫做片上網(wǎng)絡(luò)（NoC）的具有高擴(kuò)展性的資源管理方案。NoC 逐漸取代了像總線（Bus）和交叉開關(guān)（Crossbar）這樣的傳統(tǒng)片上互聯(lián)方案［1-6］。

同步屏障（Barrier）是并行計(jì)算的一種方法。對(duì)于一組線程，程序中的一個(gè)同步屏障意味著任何線程執(zhí)行到此后必須等待，直到所有線程都到達(dá)此點(diǎn)才可以繼續(xù)執(zhí)行下面的程序。同步屏障（Barrier）是用來將程序分段而被設(shè)計(jì)出來的。舉一個(gè)例子，在任何線程使用步驟t ＋1 中的值作為輸入之前，步驟t中的共享矩陣中的值已經(jīng)被更新［7-10］。

對(duì)于基于NoC 的多核處理器來說，數(shù)據(jù)包在網(wǎng)絡(luò)中的路由過程占據(jù)了較多的線程執(zhí)行時(shí)間。有的線程由于缺失地址較多，需要在NoC 傳輸?shù)臄?shù)據(jù)包較多，因此這個(gè)線程執(zhí)行得較慢。而同步屏障（Barrier）的存在，使得其他執(zhí)行進(jìn)度快的處理器需要等待這個(gè)執(zhí)行進(jìn)度慢的處理器，不僅影響性能、且浪費(fèi)功耗。

同步屏障示例如圖1 所示。由圖1 可看到，線程A產(chǎn)生了一個(gè)藍(lán)色的數(shù)據(jù)包A，線程B產(chǎn)生了2 個(gè)紅色數(shù)據(jù)包B和C。在傳統(tǒng)沒有線程感知的NoC中，數(shù)據(jù)包A和數(shù)據(jù)包B會(huì)平等地競爭路由器10 和路由器15 的端口和虛擬通道。實(shí)際上，由于線程B缺失2 塊地址，需要等待2 個(gè)請(qǐng)求的回復(fù)都收到才能繼續(xù)執(zhí)行，所以這是一個(gè)進(jìn)度較慢的線程。而同步屏障（Barrier）的存在，使得線程A需要等待線程B。此時(shí)，數(shù)據(jù)包A不必與數(shù)據(jù)包C競爭路由器10和路由器15 的端口和虛擬通道，因?yàn)榧幢銛?shù)據(jù)包A優(yōu)先到達(dá)終點(diǎn)，其線程依舊需要等待數(shù)據(jù)包C的線程，對(duì)程序的執(zhí)行進(jìn)度沒有影響。

圖1 同步屏障示例Fig. 1 Barrier demo

Das 等人［11］通過將影響應(yīng)用程序執(zhí)行的重要的數(shù)據(jù)包重新路由來解決這個(gè)問題，即挑選另外一條路由來避開擁塞區(qū)域，從而使影響應(yīng)用程序執(zhí)行的重要數(shù)據(jù)包可以更快地到達(dá)終點(diǎn)。這種方法可以使應(yīng)用程序執(zhí)行進(jìn)度更快，同時(shí)解決饑餓、活鎖、死鎖等問題，但是當(dāng)網(wǎng)絡(luò)負(fù)載較高，由于沒有可選的重新路由的路徑，導(dǎo)致這種方法的效果達(dá)不到預(yù)期。

Das 等人［12］通過為每個(gè)數(shù)據(jù)包頭部添加一個(gè)叫做CFI（Critical Flit Identifier）的標(biāo)簽來使影響程序順利執(zhí)行的數(shù)據(jù)優(yōu)先仲裁成功。其中，CFI 表示重要的數(shù)據(jù)存儲(chǔ)在這個(gè)數(shù)據(jù)包的第幾個(gè)flit 當(dāng)中。這種方法可以使程序執(zhí)行進(jìn)度更快，但是卻會(huì)導(dǎo)致沒有重要數(shù)據(jù)的flit 發(fā)生饑餓。

本文提出AVCA（Adaptive Virtual Channel Allocation）機(jī)制和CTCAR（Critical Thread Congestion-Avoid Routing）算法來優(yōu)化這個(gè)問題。AVCA 機(jī)制，即動(dòng)態(tài)地為執(zhí)行進(jìn)度慢的線程分配更多的虛擬通道。CTCAR 路由算法選擇策略會(huì)計(jì)算當(dāng)下節(jié)點(diǎn)到目的節(jié)點(diǎn)每一條備選路徑中，從當(dāng)下路由器開始下2 跳路由器中空的只能存儲(chǔ)執(zhí)行進(jìn)度慢的線程數(shù)據(jù)包的緩沖區(qū)槽數(shù)之和，然后選擇這2 跳空閑緩沖區(qū)槽數(shù)之和最大的那條路徑傳輸數(shù)據(jù)包。圖2 展示線程感知和非線程感知的比較，當(dāng)NoC 有線程感知時(shí)，會(huì)減少處理器A因?yàn)橥狡琳希˙arrier）等待處理器B的時(shí)間。

圖2 線程感知和非線程感知比較Fig. 2 Thread-aware and thread-unaware comparison

實(shí)驗(yàn)結(jié)果表明，本文方案在4×4 mesh random流量模式下，注入率為0.023 packets／node／cycle 時(shí)相比SAR［11］可以降低19%的平均延遲。

本文內(nèi)容第1 節(jié)對(duì)相關(guān)工作進(jìn)行介紹，包括本地感知自適應(yīng)路由算法、區(qū)域感知自適應(yīng)路由算法和全局感知自適應(yīng)路由算法。第2 節(jié)，對(duì)AVCA 和SSA 的設(shè)計(jì)與實(shí)現(xiàn)進(jìn)行詳細(xì)描述。第3 節(jié)，提出了CTCAR 路由算法選擇策略。第4 節(jié)，通過實(shí)驗(yàn)的方式將本文方案和對(duì)比方案進(jìn)行比較。第5 節(jié)，總結(jié)全文。

1 相關(guān)工作

在NoC 中，國內(nèi)外學(xué)者設(shè)計(jì)了大量的路由算法來解決NoC 擁塞的問題［13］。本文通過一種基于動(dòng)態(tài)分配虛擬通道的路由算法，來平衡不同線程執(zhí)行進(jìn)度。

Jerger 等人［4］提到由于確定維度的路由算法（dimension-ordered routing）很簡單，因而成為應(yīng)用最為廣泛的路由算法。然而，由于確定維度路由算法從源點(diǎn)到終點(diǎn)只有一條路徑，所以不能有效繞開NoC 中故障區(qū)域或者擁塞區(qū)域，從而降低了NoC 的吞吐量，以及提高了NoC 的延遲。自適應(yīng)路由算法（Adaptive routing）有效解決了確定維度路由算法（Dimension-ordered routing）的缺點(diǎn)，給NoC 增加了路徑多樣性，可以有效避開NoC 中的擁塞區(qū)域，從而提高NoC 的性能。自適應(yīng)路由算法可以分為3類，分別是：本地感知自適應(yīng)路由算法、區(qū)域感知自適應(yīng)路由算法和全局感知自適應(yīng)路由算法。

1.1 本地感知自適應(yīng)路由算法

在本地感知自適應(yīng)路由算法中，僅僅使用當(dāng)前路由器所在節(jié)點(diǎn)的局部信息作為衡量NoC 是否擁塞的標(biāo)志。

Dally 等人［14］選擇空的虛擬通道的數(shù)量作為某個(gè)端口是否擁塞的標(biāo)志，當(dāng)數(shù)據(jù)包到達(dá)NoC 中某個(gè)節(jié)點(diǎn)時(shí)，會(huì)比較相鄰節(jié)點(diǎn)的輸入端口的空的虛擬通道的數(shù)量，隨后選擇具有最多空的虛擬通道的端口傳輸數(shù)據(jù)。

Kim 等人［15］選擇空緩沖區(qū)的數(shù)量作為某個(gè)端口是否擁塞的標(biāo)志。Singh 等人［16-17］使用輸出隊(duì)列長度作為某個(gè)端口是否擁塞的標(biāo)志。當(dāng)本地感知自適應(yīng)路由算法被應(yīng)用在不擁塞的區(qū)域時(shí)，由于本地感知自適應(yīng)路由算法需要額外的邏輯來決定哪一條路徑更好，從而導(dǎo)致本地感知自適應(yīng)路由算法相比確定維度路由算法擁有更高的延遲。

Hu 等人［18］設(shè)計(jì)了一種叫做DyAD 的路由算法，這種路由算法集合了確定維度路由算法和本地感知自適應(yīng)路由算法的優(yōu)點(diǎn)，能夠根據(jù)NoC 的擁塞情況在確定維度路由算法和本地感知自適應(yīng)路由算法之間切換。當(dāng)網(wǎng)絡(luò)不擁塞時(shí)，路由器在確定維度的路由算法下運(yùn)行；當(dāng)網(wǎng)絡(luò)變得擁塞下，路由器會(huì)轉(zhuǎn)換為在本地感知自適應(yīng)路由算法的情況下運(yùn)行。

1.2 區(qū)域感知自適應(yīng)路由算法

根據(jù)NoC 局部擁塞情況做出的路由判斷，可能會(huì)由于缺乏對(duì)更遠(yuǎn)處節(jié)點(diǎn)的擁塞情況的了解，做出不合理的判斷。區(qū)域感知自適應(yīng)路由算法的提出就是為了解決這個(gè)問題。

Gratz 等人［19］提出區(qū)域擁塞感知路由算法、簡稱RCA，這是第一個(gè)跳出相鄰節(jié)點(diǎn)觀察更遠(yuǎn)處節(jié)點(diǎn)擁塞情況的路由算法。RCA 通過使用一個(gè)低帶寬的監(jiān)控網(wǎng)絡(luò)在相鄰路由器之間傳輸擁塞信息，在NoC 的每一跳中，傳輸進(jìn)入的擁塞信息與本地?fù)砣畔⒕酆虾笤僖黄饌鬏數(shù)骄W(wǎng)絡(luò)中。為了減少非最短路線上節(jié)點(diǎn)的擁塞信息的干擾，RCA 使用與本地節(jié)點(diǎn)的相對(duì)距離來對(duì)擁塞值進(jìn)行加權(quán)。

在RCA 中使用一個(gè)擁塞傳遞網(wǎng)絡(luò)來綜合本地?fù)砣畔⒑头潜镜負(fù)砣畔ⅲ瑥亩筃oC 做出合理的路由選擇。但是卻因沒有隔離不同的應(yīng)用程序，從而導(dǎo)致過多的擁塞信息會(huì)對(duì)NoC 路由選擇做出干擾。

Ma 等人［20］設(shè)計(jì)了一種叫做DBAR 的路由算法。在這種路由算法中，NoC 路由器做出路由選擇時(shí)只會(huì)考慮起點(diǎn)路由器到終點(diǎn)路由器該二維象限的擁塞情況，不會(huì)考慮這個(gè)二維象限之外的擁塞情況。如此一來，當(dāng)本應(yīng)用程序做出路由選擇時(shí)，就減少了被不同應(yīng)用程序在NoC 執(zhí)行時(shí)擁塞情況的干擾。然而，在不分區(qū)的NoC 中，DBAR 的性能和RCA 的性能很接近。

區(qū)域感知自適應(yīng)路由算法會(huì)形成一個(gè)用來專門傳輸非本地?fù)砣畔⒌膿砣麄鬏斁W(wǎng)。當(dāng)NoC 的負(fù)載很大時(shí)，擁塞傳輸網(wǎng)將會(huì)以消耗不可忽視的線路和功耗開銷為代價(jià)來提高NoC 的性能。

Liu 等人［21］設(shè)計(jì)了一種把非本地的擁塞信息通過二進(jìn)制位的形式嵌入到數(shù)據(jù)包的頭flit 中的路由算法來解決這個(gè)問題。這種叫做FreeRider 的路由算法通過3 步來選擇輸出線路。第一步，檢查備選線路是不是熱點(diǎn)，及這條線路是不是有一半以上的虛擬通道被占用。如果第一步?jīng)]有選擇成功，第二步會(huì)比較這2 條備選線路的“后院”。如果第二步?jīng)]有選擇成功，第三步會(huì)比較這2 條備選線路空的虛擬通道的數(shù)目，并選擇空的虛擬通道最多的那條線路來傳輸數(shù)據(jù)。

1.3 全局感知自適應(yīng)路由算法

區(qū)域感知自適應(yīng)路由算法使數(shù)據(jù)包到達(dá)某個(gè)節(jié)點(diǎn)做出路由選擇時(shí)，除了會(huì)考慮相鄰節(jié)點(diǎn)的擁塞情況，還可以考慮更遠(yuǎn)處節(jié)點(diǎn)的擁塞情況，從而做出更合理的路由選擇。但是因?yàn)閰^(qū)域感知自適應(yīng)路由算法只考慮了NoC 一部分節(jié)點(diǎn)的擁塞情況，就使得可能會(huì)因?yàn)閷?duì)整個(gè)NoC 的擁塞情況了解并不全面而做出不合理的路由選擇。

全局感知自適應(yīng)路由算法在選擇路由路線時(shí)，綜合考慮整個(gè)NoC 每一個(gè)節(jié)點(diǎn)的擁塞情況，從而做出合理的路由選擇。

Manevich 等人［22］提出自適應(yīng)切換確定維度路由（ATDOR）的NoC 架構(gòu)，在這種NoC 架構(gòu)中通過使用一個(gè)二級(jí)網(wǎng)絡(luò)，可將每一個(gè)節(jié)點(diǎn)的擁塞信息傳輸?shù)揭粋€(gè)專用節(jié)點(diǎn)，從而使每一個(gè)源點(diǎn)／終點(diǎn)對(duì)自適應(yīng)地切換為XY 確定維度路由算法或者YX 確定維度路由算法。

Ramakrishna 等人［23］提出了GCA 全局感知自適應(yīng)路由算法。在這種路由算法中，擁塞信息被嵌入到數(shù)據(jù)包頭部，NoC 的每一個(gè)路由器讀取到達(dá)這個(gè)路由器頭flit 的擁塞信息，并嵌入到自己本地的圖當(dāng)中。GCA 通過為每個(gè)節(jié)點(diǎn)構(gòu)建一個(gè)專屬于該節(jié)點(diǎn)的圖，從而使數(shù)據(jù)包到達(dá)某個(gè)節(jié)點(diǎn)時(shí)會(huì)根據(jù)全局網(wǎng)絡(luò)的情況做出合理的路由選擇。一個(gè)全局感知路由算法可以知道這條備選線路的擁塞值是多少，而不是只大概地了解這個(gè)方向的擁塞情況。

2 AVCA 和SSA 的設(shè)計(jì)與實(shí)現(xiàn)

2.1 SSA 仲裁機(jī)制

文獻(xiàn)［13］提到盡管系統(tǒng)中有大量未解決的負(fù)載缺失，但不是每一塊負(fù)載缺失都會(huì)導(dǎo)致性能瓶頸。假設(shè)，一個(gè)線程有2 個(gè)同時(shí)發(fā)出的網(wǎng)絡(luò)請(qǐng)求，第一個(gè)向網(wǎng)絡(luò)中較遠(yuǎn)的節(jié)點(diǎn)發(fā)送請(qǐng)求，第二個(gè)向網(wǎng)絡(luò)中較近的節(jié)點(diǎn)發(fā)送請(qǐng)求。由于到更遠(yuǎn)處節(jié)點(diǎn)的數(shù)據(jù)包比到更近處節(jié)點(diǎn)的數(shù)據(jù)包有更高的延遲，所以到更近處節(jié)點(diǎn)的數(shù)據(jù)包是不重要的數(shù)據(jù)包。

文獻(xiàn)［13］定義了一個(gè)參數(shù)Slack，用來表示在不影響程序整體執(zhí)行時(shí)間的情況下，一個(gè)數(shù)據(jù)包的最大延遲是多少個(gè)周期。因此，網(wǎng)絡(luò)中Slack等于0的數(shù)據(jù)包越多，線程的執(zhí)行進(jìn)度越慢。

Slack流程如圖3 所示。圖3 中，數(shù)據(jù)包A到路由器20 有4 跳，數(shù)據(jù)包B到路由器21 有5 跳。只有節(jié)點(diǎn)8 收到請(qǐng)求數(shù)據(jù)包A和請(qǐng)求數(shù)據(jù)包B的回復(fù)，線程才可以繼續(xù)執(zhí)行。因此數(shù)據(jù)包A的Slack是1，數(shù)據(jù)包B的Slack是0。

圖3 Slack 流程圖Fig. 3 Slack flow chart

本文引入SSA（Slack Switch Allocation）仲裁機(jī)制，將每個(gè)數(shù)據(jù)包的Slack嵌入到數(shù)據(jù)包頭flit 的空閑位中，2 個(gè)數(shù)據(jù)包不再是平等地競爭同一個(gè)端口，而是根據(jù)數(shù)據(jù)包的Slack仲裁同一個(gè)端口。

2.2 數(shù)據(jù)包格式

傳統(tǒng)數(shù)據(jù)包［21］中，頭flit 通常含有2 bits flit 種類信息，31 bits 路由信息，3 bits 請(qǐng)求種類信息和40 bits 物理地址信息。數(shù)據(jù)包格式如圖4 所示。圖4表明頭flit 至少還有52 bits 空閑位。

圖4 數(shù)據(jù)包格式Fig. 4 Packet format

本文在數(shù)據(jù)包頭flit 的空閑位中添加1 位線程識(shí)別（Thread Identification，TI）信息和6 位Slack信息。為了區(qū)分不同種類的線程，本文將線程隨機(jī)地分為2 類，將一類線程數(shù)據(jù)包的TI信息標(biāo)記為0，另一類線程數(shù)據(jù)包的TI信息標(biāo)記為1。

2.3 AVCA 機(jī)制

由于已經(jīng)為不同線程的數(shù)據(jù)包標(biāo)有不同的標(biāo)記，虛擬通道分配如圖5 所示。圖5 中，白色的虛擬通道只傳輸TI值為0 的數(shù)據(jù)包，紫色的虛擬通道只傳輸TI值為1 的數(shù)據(jù)包，藍(lán)色的虛擬通道會(huì)根據(jù)NoC 中實(shí)際流量情況動(dòng)態(tài)地傳輸TI值為0 或者TI值為1 的數(shù)據(jù)包。

圖5 虛擬通道分配圖Fig. 5 Virtual channel allocation diagram

假設(shè)開始情況下2 個(gè)藍(lán)色的虛擬通道傳輸TI值為0 的數(shù)據(jù)包，當(dāng)NoC 中某一路由器某一個(gè)端口紫色虛擬通道滿載，這說明網(wǎng)絡(luò)中TI值為1 的數(shù)據(jù)包不再是低優(yōu)先級(jí)的數(shù)據(jù)包，此時(shí)網(wǎng)絡(luò)中藍(lán)色的虛擬通道需要做出調(diào)整。

發(fā)生擁塞的紫色虛擬通道所在的路由器，通過信號(hào)線發(fā)送VCAI（VC Adjustment Information）虛擬通道調(diào)整信息到網(wǎng)絡(luò)中所有其他的路由器，所有其他路由器收到VCAI 后，將2 個(gè)藍(lán)色的虛擬通道轉(zhuǎn)換為只能傳輸TI值為1 的數(shù)據(jù)包。

2.4 流水線變更

傳統(tǒng)流水線如圖6 所示。由圖6 可知，傳統(tǒng)的五級(jí)流水線有固定的虛擬通道分配階段，及頭flit經(jīng)過路由計(jì)算確定輸出端口以后，還需要仲裁成功一個(gè)與該輸出端口相應(yīng)的虛擬通道。

圖6 傳統(tǒng)流水線Fig. 6 Traditional pipeline

由于本文為數(shù)據(jù)包做了不同的標(biāo)記，故而也得匹配不同的虛擬通道。在本文中，與傳統(tǒng)的虛擬通道分配階段相比，本文添加了一個(gè)數(shù)據(jù)包識(shí)別（Packet Identification，PI）階段。如果識(shí)別出來的數(shù)據(jù)包是低優(yōu)先級(jí)線程數(shù)據(jù)包，由于低優(yōu)先級(jí)線程數(shù)據(jù)包只匹配一個(gè)虛擬通道，所以將沒有VA（VC Allocation）階段，可以直接進(jìn)行ST（Switch Traversal）階段。如果識(shí)別出來的數(shù)據(jù)包是高優(yōu)先級(jí)線程數(shù)據(jù)包，由于高優(yōu)先級(jí)線程數(shù)據(jù)包匹配3 個(gè)虛擬通道，所以就還要進(jìn)行VA 階段。圖7 展示了本文設(shè)計(jì)的流水線。

圖7 本文流水線Fig. 7 The pipeline in this paper

仲裁策略是指，當(dāng)多個(gè)程序的數(shù)據(jù)包都要請(qǐng)求使用相同的輸出端口時(shí)，哪一個(gè)線程的數(shù)據(jù)包可以優(yōu)先使用這個(gè)輸出端口。傳統(tǒng)的仲裁策略包括Round-robin 和Age-based，都是沒有程序感知的。

本文在數(shù)據(jù)包頭flit 中嵌入Slack信息，使數(shù)據(jù)包仲裁時(shí)變成程序感知，及Slack小的數(shù)據(jù)包可以優(yōu)先使用輸出端口。本文的頭flit SA（Switch Allocation）階段變成了SSA（Slack Switch Allocation）階段，即根據(jù)Slack數(shù)值的大小進(jìn)行仲裁。

當(dāng)需要仲裁的2 個(gè)數(shù)據(jù)包的Slack不同時(shí)，用Slack進(jìn)行仲裁。當(dāng)需要仲裁的2 個(gè)數(shù)據(jù)包Slack相同時(shí)，用Round-robin 進(jìn)行仲裁。同時(shí)，如果數(shù)據(jù)包經(jīng)過SSA 階段，仲裁成功的輸出端口會(huì)專供這個(gè)數(shù)據(jù)包來使用，因此Body 和Tail flit 無需再仲裁這個(gè)輸出端口，直到相應(yīng)的Tail flit 離開這個(gè)端口。而如果沒有經(jīng)過SSA 階段，那么Body 和Tail flit 還需要繼續(xù)再仲裁這個(gè)輸出端口。

2.5 AVCA 和SSA 總體設(shè)計(jì)與實(shí)現(xiàn)

路由器基礎(chǔ)架構(gòu)如圖8 所示。由圖8 可知，本文提出的路由器基礎(chǔ)架構(gòu)，主要由5 部分組成，分別是：輸入／輸出端口、輸入緩沖區(qū)、AVCA、交叉開關(guān)（Crossbar）和SSA。

圖8 路由器基礎(chǔ)架構(gòu)Fig. 8 Router architecture

AVCA 的靈活分配虛擬通道和SSA 的基于Slack的仲裁策略，相互作用，促使制約程序執(zhí)行進(jìn)度重要的數(shù)據(jù)包在路由器中傳輸時(shí)得到更多資源。

圖9 是有關(guān)AVCA 的詳細(xì)設(shè)計(jì)，本文為每個(gè)路由器添加了一個(gè)虛擬通道控制器（VC Controller，VCC）。VCC 會(huì)通過多路復(fù)用器（Multiplexer）收集每個(gè)端口4 個(gè)虛擬通道的信息。例如，北端口的紫色虛擬通道滿載，北端口會(huì)將VCAI（VC Adjustment Information）信息傳輸?shù)奖韭酚善鱒CC 中，VCC 通過信號(hào)線將VCAI 傳輸?shù)骄W(wǎng)絡(luò)所有其他路由器中。其他路由器的VCC 收到VCAI 后，將VCAI 傳輸?shù)矫總€(gè)端口的藍(lán)色虛擬通道中，藍(lán)色虛擬通道收到VCAI 做出調(diào)整，改為只傳輸TI值為1 的數(shù)據(jù)包。

圖9 AVCA 詳細(xì)設(shè)計(jì)Fig. 9 AVCA detailed design

2.6 AVCA 舉例

數(shù)據(jù)包傳輸實(shí)例如圖10 所示。在圖10（a）中，假設(shè)有一個(gè)低優(yōu)先級(jí)線程數(shù)據(jù)包A的路由路徑是從起點(diǎn)路由器1 通過中間路由器4 傳輸?shù)浇K點(diǎn)路由器3，預(yù)期則應(yīng)從路由器1 的北端口傳輸?shù)铰酚善?，再從路由器4 的西端口傳輸?shù)铰酚善?。

但是此時(shí)，路由器4 的西端口沒有空閑的緩沖區(qū)可以傳輸數(shù)據(jù)，所以數(shù)據(jù)包A不能傳輸?shù)铰酚善?，只能在路由器1 的北端口停留。在圖10（a）中，紅色的虛擬通道，代表這個(gè)虛擬通道已經(jīng)被數(shù)據(jù)包占據(jù)，不能傳輸數(shù)據(jù)。

隨后，路由器1 又需要分別傳輸3 個(gè)和數(shù)據(jù)包A的路由路徑相同的低優(yōu)先級(jí)線程數(shù)據(jù)包B，C和D，由圖10（b）可知，這時(shí)數(shù)據(jù)包A，B，C和D將占據(jù)路由器1 北端口的4 個(gè)虛擬通道。

當(dāng)路由器1 需要把高優(yōu)先級(jí)線程的數(shù)據(jù)包E從路由器1 傳輸?shù)铰酚善? 時(shí)，即便路由器4 的北端口有空緩沖區(qū)可以傳輸數(shù)據(jù)，但是因?yàn)槁酚善? 的北端口的4 個(gè)虛擬通道已經(jīng)被4 個(gè)低優(yōu)先級(jí)線程數(shù)據(jù)包占據(jù)，所以路由器1 此時(shí)不能傳輸數(shù)據(jù)包E。

如果使用本文方案，數(shù)據(jù)包傳輸具體見圖10（c）。在圖10（c）中，每個(gè)端口只有一個(gè)虛擬通道可以傳輸?shù)蛢?yōu)先級(jí)線程的數(shù)據(jù)包。每個(gè)端口藍(lán)色的虛擬通道表示只能傳輸高優(yōu)先級(jí)線程數(shù)據(jù)包的虛擬通道，白色的虛擬通道表示只能傳輸?shù)蛢?yōu)先級(jí)線程數(shù)據(jù)包的虛擬通道。當(dāng)數(shù)據(jù)包A占據(jù)了路由器1 北端口唯一一個(gè)可以傳輸?shù)蛢?yōu)先級(jí)線程數(shù)據(jù)包的虛擬通道時(shí)，由于數(shù)據(jù)包B，C和D都是低優(yōu)先級(jí)線程的數(shù)據(jù)包，因此數(shù)據(jù)包B，C和D不會(huì)再占據(jù)路由器1 北端口剩余3 個(gè)空的虛擬通道。隨后，當(dāng)路由器1 需要傳輸高優(yōu)先級(jí)線程的數(shù)據(jù)包E時(shí)，因?yàn)槁酚善? 的北端口有3 個(gè)空的虛擬通道，所以路由器1 可以將數(shù)據(jù)包E順利地傳輸?shù)浇K點(diǎn)。

圖10 數(shù)據(jù)包傳輸實(shí)例圖Fig. 10 Packets transmission instance diagram

3 CTCAR 路由算法選擇策略

3.1 CTCAR 概述

本文提出一種專門為高優(yōu)先級(jí)線程優(yōu)化的路由算法選擇策略，即重要線程擁塞避免（Critical Thread Congestion-Avoided Routing，CTCAR）路由算法選擇策略。

CTCAR 實(shí)例如圖11 所示。在圖11（a）中，這是一個(gè)4 行4 列的mesh 拓?fù)浣Y(jié)構(gòu)，其中每一個(gè)節(jié)點(diǎn)中的數(shù)字表示這是第幾個(gè)節(jié)點(diǎn)。圖11 中，實(shí)例的數(shù)據(jù)包傳輸起始路由器為節(jié)點(diǎn)5，終點(diǎn)路由器為節(jié)點(diǎn)15。

當(dāng)高優(yōu)先級(jí)線程的數(shù)據(jù)包要從起點(diǎn)路由器5 傳輸?shù)浇K點(diǎn)路由器15 時(shí)，有路由器6 和路由器9 兩個(gè)路由器可以選擇。本文通過計(jì)算路由器6 和路由器6 的下一跳路由器的空閑緩沖區(qū)之和以及路由器9和路由器9 的下一跳路由器的空閑緩沖區(qū)之和，然后比較這兩者的大小，最終指定這兩跳緩沖區(qū)之和最大的那條線路為選擇成功的線路。在圖11（b）中的黑色虛線表明，路由器5 在選擇下一跳是路由器6、還是路由器9 時(shí)，會(huì)根據(jù)路由器6 和路由器9 發(fā)回來的信息作為判斷。

紹圣元年（1094），山谷50歲，居家待命，宥《書自作草后》：“紹圣甲戌在黃龍山中，忽得草書三昧，覺前所作太露芒角。若得明窗凈幾，筆墨調(diào)利，可作數(shù)千字不倦，但難得此時(shí)會(huì)爾?！保ā渡焦阮}跋》卷五）山谷與黃龍諸禪師請(qǐng)益參禪，于書法亦別有心得，以前所作書鋒芒畢露，似應(yīng)內(nèi)斂含蓄。山谷以后遭遇證明，此時(shí)山谷實(shí)未得草書三昧。

圖11 CTCAR 實(shí)例圖Fig. 11 CTCAR instance diagram

本文定義了2 個(gè)參數(shù)，分別是Vc_reservation和Slot_number。因?yàn)楸疚臑楦邇?yōu)先級(jí)線程數(shù)據(jù)包分配了3 個(gè)虛擬通道，所以一個(gè)路由器在收集相鄰路由器的信息時(shí)，會(huì)得到相鄰路由器專門存儲(chǔ)高優(yōu)先級(jí)線程數(shù)據(jù)包的虛擬通道是否被其他數(shù)據(jù)包預(yù)定的信息，及Vc_reservation是1、還是0。如果Vc_reservation是1 代表這個(gè)虛擬通道已經(jīng)被預(yù)定，不能傳輸數(shù)據(jù)；如果Vc_reservation是0，代表這個(gè)虛擬通道沒有被預(yù)定，可以傳輸數(shù)據(jù)。

Slot_number代表這個(gè)沒有被預(yù)定的虛擬通道有多少個(gè)空閑緩沖區(qū)槽。信息傳輸示意如圖12 所示。在圖12 中，路由器9 收集與其相鄰的3 個(gè)路由器，即路由器8、路由器10 和路由器13 的每個(gè)專門存儲(chǔ)高優(yōu)先級(jí)線程數(shù)據(jù)包虛擬通道的Vc_reservation和Slot_number。

圖12 信息傳輸圖Fig. 12 Information transmission diagram

圖11（b）中，藍(lán)色虛線表示下一跳存在沒有被預(yù)定的專門傳輸高優(yōu)先級(jí)線程數(shù)據(jù)包的虛擬通道，可以傳輸數(shù)據(jù)。圖11（b）中，紅色虛線表示下一跳的3 個(gè)專門傳輸高優(yōu)先級(jí)線程數(shù)據(jù)包的虛擬通道已經(jīng)被預(yù)定，不能傳輸數(shù)據(jù)。

圖11（c）中，3 條深黑色實(shí)線表示路由算法計(jì)算出路由器6 和路由器9 的下一跳可以到達(dá)哪個(gè)路由器。

在本文中，用的路由算法是基于奇偶轉(zhuǎn)向模型的自適應(yīng)路由算法。當(dāng)高優(yōu)先級(jí)線程的數(shù)據(jù)包由路由器5 傳輸?shù)铰酚善? 時(shí)，因?yàn)檫@是奇數(shù)列不能做由向北到向西的轉(zhuǎn)向和由向南到向西的轉(zhuǎn)向，及路由器9 的下一跳可以到達(dá)路由器10 和路由器13。因?yàn)槁酚善? 位于偶數(shù)列，不能做由向東到向北的轉(zhuǎn)向和由向東到向南的轉(zhuǎn)向，及路由器6 的下一跳只能到達(dá)路由器7，不能到達(dá)路由器10。

在圖11（d）中，由于路由器10 和路由器13 專門傳輸高優(yōu)先級(jí)線程數(shù)據(jù)包的虛擬通道，已經(jīng)被其他數(shù)據(jù)包預(yù)定。而路由器7 專門傳輸高優(yōu)先級(jí)線程的虛擬通道沒有被其他數(shù)據(jù)包預(yù)定，所以本例應(yīng)該選擇路由器6，因?yàn)槁酚善? 的下一跳路由器7 可以傳輸高優(yōu)先級(jí)線程的數(shù)據(jù)包。

3.2 CTCAR 詳細(xì)設(shè)計(jì)

以圖11 為例CTCAR 流程如圖13 所示。首先，確定當(dāng)下網(wǎng)絡(luò)中，TI值為1 是高優(yōu)先級(jí)線程數(shù)據(jù)包，還是TI值為0 是高優(yōu)先級(jí)線程數(shù)據(jù)包。如果數(shù)據(jù)包是高優(yōu)先級(jí)線程數(shù)據(jù)包，使用CTCAR。如果數(shù)據(jù)包不是高優(yōu)先級(jí)線程數(shù)據(jù)包，退出流程，使用XY 路由算法。

圖13 CTCAR 流程圖Fig. 13 CTCAR flow chart

其次，計(jì)算當(dāng)下節(jié)點(diǎn)到目的節(jié)點(diǎn)每一條備選線路中，從當(dāng)下路由器開始下2 跳路由器中，空的只能存儲(chǔ)高優(yōu)先級(jí)線程數(shù)據(jù)包的緩沖區(qū)槽數(shù)之和，再選擇這2 跳空閑緩沖區(qū)槽數(shù)之和最大的那條線路傳輸數(shù)據(jù)包。CTCAR 算法設(shè)計(jì)代碼見如下。

4 實(shí)驗(yàn)

4.1 仿真環(huán)境配置

表1 實(shí)驗(yàn)參數(shù)表Tab.1 Experimental parameters table

在本文中，每經(jīng)過10 000 個(gè)周期設(shè)置一個(gè)同步屏障（Barrier），即低優(yōu)先級(jí)的線程每仿真10 000個(gè)周期就會(huì)停下等待高優(yōu)先級(jí)的線程。

在本文中為每個(gè)路由器的輸入端口設(shè)置了4 個(gè)邏輯大小為8 個(gè)flit 的虛擬通道。

本文采用3 種流量模式進(jìn)行仿真，分別是Random、Transpose1 和Transpose2。對(duì)此可做闡釋分述如下。

（1）Random 流量模式中，NoC 中每個(gè)節(jié)點(diǎn)向NoC 中任意其他節(jié)點(diǎn)隨機(jī)地發(fā)送數(shù)據(jù)包。

（2）Transpose1 流量模式中，假設(shè)準(zhǔn)備發(fā)送數(shù)據(jù)包的起始節(jié)點(diǎn)的坐標(biāo)是（x，y），那么這個(gè)數(shù)據(jù)包將會(huì)被發(fā)送到的終點(diǎn)是（mesh_dim_x -1-y，mesh_dim_y -1-x），其 中mesh_dim_x和mesh_dim_y表示這個(gè)NoC 設(shè)置的橫坐標(biāo)和縱坐標(biāo)上分別有多少個(gè)節(jié)點(diǎn)。這種流量模式的特點(diǎn)是：越靠近中間區(qū)域的路由節(jié)點(diǎn)注入網(wǎng)絡(luò)的數(shù)據(jù)包的跳數(shù)就越小，但是從整體上來看，長距離多跳數(shù)據(jù)包占的比重更大。

（3）在Transpose2 流量模式中，假設(shè)準(zhǔn)備發(fā)送數(shù)據(jù)包的起始節(jié)點(diǎn)的坐標(biāo)是（x，y），那么這個(gè)數(shù)據(jù)包將會(huì)被發(fā)送到的終點(diǎn)是（y，x）。在本文中，每次仿真包括1 000個(gè)周期的預(yù)熱階段和20 000個(gè)周期的仿真階段。

4.2 性能分析

4.2.1 平均延遲

圖14～圖16 是4×4 mesh 拓?fù)浣Y(jié)構(gòu)3 種流量模式下的延遲對(duì)比圖。圖17 是8×8 mesh 拓?fù)浣Y(jié)構(gòu)random 流量模式下的延遲對(duì)比圖。4 幅圖中，橫坐標(biāo)是網(wǎng)絡(luò)的注入率，縱坐標(biāo)是以周期為單位的數(shù)據(jù)包平均延遲。

圖14 random 流量模式下4×4 mesh 網(wǎng)絡(luò)延遲Fig. 14 Latency of 4 × 4 mesh in random traffic

圖15 Transpose1 流量模式下4×4 mesh 網(wǎng)絡(luò)延遲Fig. 15 Latency of 4 × 4 mesh in Transpose1 traffic

圖16 Transpose2 流量模式下4×4 mesh 網(wǎng)絡(luò)延遲Fig. 16 Latency of 4 × 4 mesh in Transpose2 traffic

圖17 random 流量模式下8×8 mesh 網(wǎng)絡(luò)延遲Fig. 17 Latency of 8 × 8 mesh in random traffic

本文對(duì)4 種方案進(jìn)行對(duì)比分析。方案一是Baseline 方案及沒有采用AVCA 機(jī)制、SSA 機(jī)制和CTCAR 路由算法選擇策略。方案二采用了傳統(tǒng)的沒有程序感知的路由算法，即Freerider 路由算法。方案三采用了程序感知的路由算法，及SAR 路由算法。方案四采用了本文方案，及應(yīng)用了AVCA、SSA和CTCAR。各對(duì)比方案的比較結(jié)果見表2。

表2 各對(duì)比方案比較Tab.2 Comparison of different schemes

SAR 和本文所提出的CTCAR 都是程序感知的路由算法。從圖14～圖17 可以看出，在不同的流量模式下CTCAR 較SAR 在高注入率或低注入率下都有一定的延遲改善。

在4×4 mesh random 流量模式下，注入率大于0.021 packets／node／cycle 小于0.025 packets／node／cycle 時(shí)，CTCAR 與對(duì)比方案相比有較大的延遲改善。其中，注入率為0.023 packets／node／cycle 時(shí)，CTCAR 效果達(dá)到最佳，相比SAR 可以降低19%的平均延遲。

在8×8 mesh random 流量模式下，注入率大于0.012 packets／node／cycle 小于0.014 packets／node／cycle時(shí)，CTCAR 與對(duì)比方案相比有較大的延遲改善。其中，注入率為0.014 packets／node／cycle 時(shí)，CTCAR 效果達(dá)到最佳，相比SAR 可以降低16%的平均延遲。

這是由于CTCAR 引入Slack，在仲裁階段是程序感知的。同時(shí)CTCAR 考慮到同步屏障的存在，可以動(dòng)態(tài)為不同線程數(shù)據(jù)包分配不同的虛擬通道，從而平衡各個(gè)線程的執(zhí)行進(jìn)度。CTCAR 在靈活分配虛擬通道的基礎(chǔ)上，還引入了區(qū)域擁塞感知的思想，從而進(jìn)一步降低了網(wǎng)絡(luò)的平均延遲。

4.2.2 吞吐率

4×4 mesh 和8×8 mesh 拓?fù)浣Y(jié)構(gòu)random 流量模式下，CTCAR 和對(duì)應(yīng)的3 種對(duì)比方案的吞吐率比較結(jié)果如圖18、圖19 所示。圖18、圖19 中，橫坐標(biāo)表示網(wǎng)絡(luò)注入率，縱坐標(biāo)表示網(wǎng)絡(luò)中平均每個(gè)節(jié)點(diǎn)的吞吐率。

從圖18、圖19 中可以看出，CTCAR 具有更高的網(wǎng)絡(luò)吞吐率，這是因?yàn)楸疚奶岢龅腁VCA 機(jī)制可以動(dòng)態(tài)地為不同優(yōu)先級(jí)線程數(shù)據(jù)包分配不同的虛擬通道，同時(shí)CTCAR 可以有效避免高優(yōu)先級(jí)線程數(shù)據(jù)包發(fā)生擁塞。

圖18 random 流量模式下4×4 mesh 吞吐率Fig. 18 Throughput of 4×4 mesh in random traffic

圖19 random 流量模式下8×8 mesh 吞吐率Fig. 19 Throughput of 8×8 mesh in random traffic

圖18 中，當(dāng)注入率為0.03 packets／node／cycle時(shí)，4×4 mesh random 流量模式下4 種方案均達(dá)到飽和狀態(tài)。在飽和注入率下，CTCAR 與SAR、DBAR和Baseline 相比分別降低了2.8%、4.2%和5.6%的飽和吞吐率。

圖19 中，當(dāng)注入率為0.016 packets／node／cycle時(shí)，8×8 mesh random 流量模式下4 種方案均達(dá)到飽和狀態(tài)。在飽和注入率下，CTCAR 與SAR、DBAR和Baseline 相比分別降低了1.9%、5.6%和8%的飽和吞吐率。

4.2.3 面積及功耗分析

本文采用的實(shí)驗(yàn)工具是Synopsys 公司的Design Compiler，所采用的工藝庫為45 nm 標(biāo)準(zhǔn)單元庫，對(duì)相同規(guī)模的4 種方案進(jìn)行邏輯綜合。

表3 為本文方案與對(duì)比方案的硬件開銷。由于CTCAR 中添加了AVCA 模塊、SSA 模塊和VCC 模塊，使得本文的面積和功耗開銷都有微小的增加。但是，通過SSA 仲裁機(jī)制，AVCA 動(dòng)態(tài)為高優(yōu)先級(jí)線程分配虛擬通道，CTCAR 防止高優(yōu)先級(jí)線程數(shù)據(jù)包發(fā)生局部擁塞，可以有效降低網(wǎng)絡(luò)的平均延遲，以及提高網(wǎng)絡(luò)的吞吐量。考慮到CTCAR 整體性能優(yōu)勢，CTCAR 中額外面積和功耗開銷所帶來的影響是可以接受的。

表3 面積與功耗開銷Tab.3 Area and power consumption overhead

5 結(jié)束語

對(duì)基于NoC 的多核處理器來說，數(shù)據(jù)包在網(wǎng)絡(luò)中的路由過程占據(jù)了較多的線程執(zhí)行時(shí)間。有的線程由于缺失地址較多，需要在NoC 傳輸?shù)臄?shù)據(jù)包較多，因此這個(gè)線程執(zhí)行得較慢。而同步屏障（Barrier）的存在，使得其他執(zhí)行進(jìn)度快的處理器需要等待這個(gè)執(zhí)行進(jìn)度慢的處理器，不僅影響性能且浪費(fèi)功耗。

本文首先引入文獻(xiàn)［13］中Slack參數(shù)，提出了基于Slack的仲裁機(jī)制SSA。其次，本文通過在數(shù)據(jù)包頭flit 中嵌入標(biāo)簽的方式，將不同線程的數(shù)據(jù)包分類，用VCC 為不同類別的線程分配不同數(shù)量的虛擬通道。最后，本文提出了CTCAR 路由算法選擇策略，可以有效降低高優(yōu)先級(jí)線程數(shù)據(jù)包發(fā)生擁塞的可能性。

實(shí)驗(yàn)結(jié)果表明，與SAR 相比，本文方案在增加可接受的硬件開銷、功耗開銷下，可以有效降低網(wǎng)絡(luò)平均延遲，提高網(wǎng)路吞吐率。