針對多線程應用程序的片上網(wǎng)絡優(yōu)化設計

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

（1 合肥工業(yè)大學 計算機與信息學院，合肥 230601；2 合肥工業(yè)大學 情感計算與先進智能機器安徽省重點實驗室，合肥 230601）

0 引言

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

1.1 本地感知自適應路由算法

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

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

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

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

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

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

Gratz 等人［19］提出區(qū)域擁塞感知路由算法、簡稱RCA，這是第一個跳出相鄰節(jié)點觀察更遠處節(jié)點擁塞情況的路由算法。RCA 通過使用一個低帶寬的監(jiān)控網(wǎng)絡在相鄰路由器之間傳輸擁塞信息，在NoC 的每一跳中，傳輸進入的擁塞信息與本地擁塞信息聚合后再一起傳輸?shù)骄W(wǎng)絡中。為了減少非最短路線上節(jié)點的擁塞信息的干擾，RCA 使用與本地節(jié)點的相對距離來對擁塞值進行加權。

在RCA 中使用一個擁塞傳遞網(wǎng)絡來綜合本地擁塞信息和非本地擁塞信息，從而使NoC 做出合理的路由選擇。但是卻因沒有隔離不同的應用程序，從而導致過多的擁塞信息會對NoC 路由選擇做出干擾。

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

區(qū)域感知自適應路由算法會形成一個用來專門傳輸非本地擁塞信息的擁塞傳輸網(wǎng)。當NoC 的負載很大時，擁塞傳輸網(wǎng)將會以消耗不可忽視的線路和功耗開銷為代價來提高NoC 的性能。

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

1.3 全局感知自適應路由算法

區(qū)域感知自適應路由算法使數(shù)據(jù)包到達某個節(jié)點做出路由選擇時，除了會考慮相鄰節(jié)點的擁塞情況，還可以考慮更遠處節(jié)點的擁塞情況，從而做出更合理的路由選擇。但是因為區(qū)域感知自適應路由算法只考慮了NoC 一部分節(jié)點的擁塞情況，就使得可能會因為對整個NoC 的擁塞情況了解并不全面而做出不合理的路由選擇。

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

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

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

2 AVCA 和SSA 的設計與實現(xiàn)

2.1 SSA 仲裁機制

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

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

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

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

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

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

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

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

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

2.3 AVCA 機制

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

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

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

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

2.4 流水線變更

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

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

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

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

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

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

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

2.5 AVCA 和SSA 總體設計與實現(xiàn)

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

圖8 路由器基礎架構Fig. 8 Router architecture

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

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

圖9 AVCA 詳細設計Fig. 9 AVCA detailed design

2.6 AVCA 舉例

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

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

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

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

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

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

3 CTCAR 路由算法選擇策略

3.1 CTCAR 概述

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

CTCAR 實例如圖11 所示。在圖11（a）中，這是一個4 行4 列的mesh 拓撲結構，其中每一個節(jié)點中的數(shù)字表示這是第幾個節(jié)點。圖11 中，實例的數(shù)據(jù)包傳輸起始路由器為節(jié)點5，終點路由器為節(jié)點15。

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

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

圖11 CTCAR 實例圖Fig. 11 CTCAR instance diagram

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

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

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

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

圖11（c）中，3 條深黑色實線表示路由算法計算出路由器6 和路由器9 的下一跳可以到達哪個路由器。

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

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

3.2 CTCAR 詳細設計

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

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

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

4 實驗

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

表1 實驗參數(shù)表Tab.1 Experimental parameters table

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

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

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

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

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

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

4.2 性能分析

4.2.1 平均延遲

圖14～圖16 是4×4 mesh 拓撲結構3 種流量模式下的延遲對比圖。圖17 是8×8 mesh 拓撲結構random 流量模式下的延遲對比圖。4 幅圖中，橫坐標是網(wǎng)絡的注入率，縱坐標是以周期為單位的數(shù)據(jù)包平均延遲。

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

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

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

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

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

表2 各對比方案比較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 時，CTCAR 與對比方案相比有較大的延遲改善。其中，注入率為0.023 packets／node／cycle 時，CTCAR 效果達到最佳，相比SAR 可以降低19%的平均延遲。

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

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

4.2.2 吞吐率

4×4 mesh 和8×8 mesh 拓撲結構random 流量模式下，CTCAR 和對應的3 種對比方案的吞吐率比較結果如圖18、圖19 所示。圖18、圖19 中，橫坐標表示網(wǎng)絡注入率，縱坐標表示網(wǎng)絡中平均每個節(jié)點的吞吐率。

從圖18、圖19 中可以看出，CTCAR 具有更高的網(wǎng)絡吞吐率，這是因為本文提出的AVCA 機制可以動態(tài)地為不同優(yōu)先級線程數(shù)據(jù)包分配不同的虛擬通道，同時CTCAR 可以有效避免高優(yōu)先級線程數(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 中，當注入率為0.03 packets／node／cycle時，4×4 mesh random 流量模式下4 種方案均達到飽和狀態(tài)。在飽和注入率下，CTCAR 與SAR、DBAR和Baseline 相比分別降低了2.8%、4.2%和5.6%的飽和吞吐率。

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

4.2.3 面積及功耗分析

本文采用的實驗工具是Synopsys 公司的Design Compiler，所采用的工藝庫為45 nm 標準單元庫，對相同規(guī)模的4 種方案進行邏輯綜合。

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

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

5 結束語

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

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

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