針對多線程應用程序的片上網絡優化設計

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

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

0 引言

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

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

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

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

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

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

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

本文提出AVCA（Adaptive Virtual Channel Allocation）機制和CTCAR（Critical Thread Congestion-Avoid Routing）算法來優化這個問題。AVCA 機制，即動態地為執行進度慢的線程分配更多的虛擬通道。CTCAR 路由算法選擇策略會計算當下節點到目的節點每一條備選路徑中，從當下路由器開始下2 跳路由器中空的只能存儲執行進度慢的線程數據包的緩沖區槽數之和，然后選擇這2 跳空閑緩沖區槽數之和最大的那條路徑傳輸數據包。圖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%的平均延遲。

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

1 相關工作

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

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

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

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

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

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

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

1.2 區域感知自適應路由算法

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

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

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

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

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

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

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

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

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

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

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

2 AVCA 和SSA 的設計與實現

2.1 SSA 仲裁機制

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

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

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

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

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

2.2 數據包格式

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

圖4 數據包格式Fig. 4 Packet format

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

2.3 AVCA 機制

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

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

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

發生擁塞的紫色虛擬通道所在的路由器，通過信號線發送VCAI（VC Adjustment Information）虛擬通道調整信息到網絡中所有其他的路由器，所有其他路由器收到VCAI 后，將2 個藍色的虛擬通道轉換為只能傳輸TI值為1 的數據包。

2.4 流水線變更

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

圖6 傳統流水線Fig. 6 Traditional pipeline

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

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

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

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

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

2.5 AVCA 和SSA 總體設計與實現

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

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

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

圖9 是有關AVCA 的詳細設計，本文為每個路由器添加了一個虛擬通道控制器（VC Controller，VCC）。VCC 會通過多路復用器（Multiplexer）收集每個端口4 個虛擬通道的信息。例如，北端口的紫色虛擬通道滿載，北端口會將VCAI（VC Adjustment Information）信息傳輸到本路由器VCC 中，VCC 通過信號線將VCAI 傳輸到網絡所有其他路由器中。其他路由器的VCC 收到VCAI 后，將VCAI 傳輸到每個端口的藍色虛擬通道中，藍色虛擬通道收到VCAI 做出調整，改為只傳輸TI值為1 的數據包。

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

2.6 AVCA 舉例

數據包傳輸實例如圖10 所示。在圖10（a）中，假設有一個低優先級線程數據包A的路由路徑是從起點路由器1 通過中間路由器4 傳輸到終點路由器3，預期則應從路由器1 的北端口傳輸到路由器4，再從路由器4 的西端口傳輸到路由器3。

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

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

當路由器1 需要把高優先級線程的數據包E從路由器1 傳輸到路由器7 時，即便路由器4 的北端口有空緩沖區可以傳輸數據，但是因為路由器1 的北端口的4 個虛擬通道已經被4 個低優先級線程數據包占據，所以路由器1 此時不能傳輸數據包E。

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

圖10 數據包傳輸實例圖Fig. 10 Packets transmission instance diagram

3 CTCAR 路由算法選擇策略

3.1 CTCAR 概述

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

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

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

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

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

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

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

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

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

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

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

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

3.2 CTCAR 詳細設計

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

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

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

4 實驗

4.1 仿真環境配置

表1 實驗參數表Tab.1 Experimental parameters table

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

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

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

（1）Random 流量模式中，NoC 中每個節點向NoC 中任意其他節點隨機地發送數據包。

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

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

4.2 性能分析

4.2.1 平均延遲

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

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

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

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

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

本文對4 種方案進行對比分析。方案一是Baseline 方案及沒有采用AVCA 機制、SSA 機制和CTCAR 路由算法選擇策略。方案二采用了傳統的沒有程序感知的路由算法，即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 考慮到同步屏障的存在，可以動態為不同線程數據包分配不同的虛擬通道，從而平衡各個線程的執行進度。CTCAR 在靈活分配虛擬通道的基礎上，還引入了區域擁塞感知的思想，從而進一步降低了網絡的平均延遲。

4.2.2 吞吐率

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

從圖18、圖19 中可以看出，CTCAR 具有更高的網絡吞吐率，這是因為本文提出的AVCA 機制可以動態地為不同優先級線程數據包分配不同的虛擬通道，同時CTCAR 可以有效避免高優先級線程數據包發生擁塞。

圖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 種方案均達到飽和狀態。在飽和注入率下，CTCAR 與SAR、DBAR和Baseline 相比分別降低了2.8%、4.2%和5.6%的飽和吞吐率。

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

4.2.3 面積及功耗分析

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

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

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

5 結束語

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

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

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