一種新穎的面向數(shù)據(jù)流量特征的片上網(wǎng)絡(luò)設(shè)計*

胡森森**，陳皇吉

(1.重慶工商大學(xué) 電子商務(wù)系，重慶400067；2.中國西南電子技術(shù)研究所，成都610036)

1 引 言

William J. Dally提出采用片上網(wǎng)絡(luò)(Network-on-Chip，NoC)連接多個處理器核芯，并采用路由和分組交換技術(shù)進(jìn)行數(shù)據(jù)通信，使得片上網(wǎng)絡(luò)開始成為計算機(jī)系統(tǒng)結(jié)構(gòu)領(lǐng)域中的一個研究熱點(diǎn)[1]。片上網(wǎng)絡(luò)成功地實(shí)現(xiàn)了多核系統(tǒng)的計算功能與通信功能的分離。在片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方面，研究人員提出了多種拓?fù)浣Y(jié)構(gòu)，如二維環(huán)網(wǎng)(Ring)、二維Mesh和二維Torus等結(jié)構(gòu)。片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不僅決定了節(jié)點(diǎn)和鏈路的物理布局，而且緊密耦合著構(gòu)建在其上的路由算法、流量控制等機(jī)制和策略[2]。

另一方面，目前主流的瓦片結(jié)構(gòu)(Tile)的多核處理器設(shè)計中，大容量的Cache被劃分成多個小的Bank(或者Slice)，并以二維Mesh的拓?fù)浣Y(jié)構(gòu)分布在片上網(wǎng)絡(luò)中。因此，處理器對各個Bank的訪問延遲會因物理拓?fù)渚嚯x的差異，造成非一致 Cache 訪問現(xiàn)象(Non-uniform Cache Access，NUCA)[3-4]。在對片上網(wǎng)絡(luò)中的流量研究發(fā)現(xiàn)，網(wǎng)絡(luò)流量由請求消息和應(yīng)答消息交織在一起,處理器核與處理器核之間(Core-Core)、處理器與緩存之間(Core-Cache)的數(shù)據(jù)流量存在巨大的差異。在核間通信中，請求消息占絕大多數(shù)，數(shù)據(jù)流量小,而在處理器與緩存通信中占絕大多數(shù)的是應(yīng)答消息，需要承載大量的緩存數(shù)據(jù)的讀/寫，數(shù)據(jù)流量大。因此，處理器核的不同通信模式需要不同的的網(wǎng)絡(luò)帶寬來降低網(wǎng)絡(luò)延遲,提高網(wǎng)絡(luò)吞吐量，從而提高通信效率。

本文探討了將傳統(tǒng)的片上網(wǎng)絡(luò)分離為雙片上網(wǎng)絡(luò)的設(shè)計，即核間通信網(wǎng)絡(luò)和片上存儲網(wǎng)絡(luò)，分別用于核間通信和核-緩存之間的通信。本文提出的方案針對片上網(wǎng)絡(luò)中處理器核和緩存數(shù)據(jù)流量的特點(diǎn)進(jìn)行了網(wǎng)絡(luò)優(yōu)化。對比實(shí)驗(yàn)表明，該方案具有較低的網(wǎng)絡(luò)延遲和較高的網(wǎng)絡(luò)吞吐量，提升了系統(tǒng)整體性能。

2 片上網(wǎng)絡(luò)流量特征

為了評估系統(tǒng)中各種消息所攜帶的數(shù)據(jù)流量，我們選擇了真實(shí)的服務(wù)器工作負(fù)載，使用GEM5[5]全系統(tǒng)模擬器進(jìn)行了仿真。對片上網(wǎng)絡(luò)流量研究發(fā)現(xiàn)，處理器核與處理器核之間通信(Core-Core)和處理器與緩存之間通信(Core-Cache)存在不同的通信模式。片上網(wǎng)絡(luò)的流量主要由請求消息和響應(yīng)消息組成，請求消息和應(yīng)答消息交織在一起。

請求流量主要由取指(Fetch)、內(nèi)存驅(qū)逐(Evict)請求和緩存一致性(Cache Coherence)請求組成，具有短消息的特征，而響應(yīng)流量主要由讀/寫數(shù)據(jù)塊構(gòu)成，具有長消息的特征。圖1給出了對常見的四種服務(wù)器工作負(fù)載的仿真結(jié)果，統(tǒng)計結(jié)果顯示，短消息流量平均占總請求流量的91.8%，長消息流量平均占總響應(yīng)流量的89.2%。在核間通信中，請求消息占絕大多數(shù)，因此具有信息量小的特點(diǎn)(短消息)，而在處理器與緩存通信中占絕大多數(shù)的是應(yīng)答消息。由于應(yīng)答消息一般需要承載緩存數(shù)據(jù)塊，具有信息量大的特點(diǎn)(長消息)。不同消息對網(wǎng)絡(luò)帶寬的需求是不一樣的，因此需要根據(jù)數(shù)據(jù)的特征進(jìn)行網(wǎng)絡(luò)設(shè)計的優(yōu)化。

圖1 常見的四種服務(wù)器工作負(fù)載片上網(wǎng)絡(luò)流量分布Fig.1 Four kinds breakdown of server workload on-chip network traffic

3 雙片上網(wǎng)絡(luò)設(shè)計

網(wǎng)絡(luò)拓?fù)涠x了節(jié)點(diǎn)如何布局和連接，影響著網(wǎng)絡(luò)的延遲、吞吐量和系統(tǒng)整體性能。因此在多核處理器設(shè)計中，片上網(wǎng)絡(luò)的結(jié)構(gòu)起著至關(guān)重要的作用。本文針對片上網(wǎng)絡(luò)流量的特征，設(shè)計了一種異構(gòu)非對稱雙片上網(wǎng)絡(luò)，即核間互連網(wǎng)絡(luò)和片上緩存網(wǎng)絡(luò)，分別用于核間通信和核-緩存通信。

3.1 核間互連網(wǎng)絡(luò)

2D Mesh在布局布線方面的優(yōu)勢，使得其在多核處理器設(shè)計中被廣泛采用。最常見的基于Mesh拓?fù)浣Y(jié)構(gòu)的多核處理器絕大多數(shù)采用瓦片設(shè)計方案。WK-Recursive[6]遞歸網(wǎng)絡(luò)拓?fù)渚哂袑哟涡?Hierarchy)、可擴(kuò)展性(Scalability)、規(guī)整性(Regularity)、魯棒性(Robust)和對稱性(Symmetry)等優(yōu)點(diǎn)[7]。在這些屬性中，對于超大規(guī)模集成電路(Very Large Scale Integrated Circuits，VLSI)設(shè)計來說，遞歸層次結(jié)構(gòu)和規(guī)整性是最有價值的屬性。核間互連拓?fù)浣Y(jié)構(gòu)采用4度網(wǎng)絡(luò)，既有利于采用傳統(tǒng)的2D Mesh布局，又可利用其遞歸性帶來的設(shè)計優(yōu)勢。本文設(shè)計的核間互連結(jié)構(gòu)中，每4個核全互連構(gòu)成1個基本簇。每個核都擁有1個私有L1緩存，基本簇內(nèi)的4個核共享1個L2，以此方式逐步進(jìn)行擴(kuò)展，進(jìn)而形成相互包含的層次化分組結(jié)構(gòu)。

WK-recursive網(wǎng)絡(luò)記為WK(D,L)，其中D表示節(jié)點(diǎn)的連接度，L表示網(wǎng)絡(luò)的層數(shù)。2D Mesh結(jié)構(gòu)的核間互連網(wǎng)絡(luò)屬于連接度為4的一種特例，記為WK(4,L)。核間網(wǎng)絡(luò)拓?fù)渚幋a如下：

定義1 對于一個給定的節(jié)點(diǎn)總數(shù)為4L的WK-recursive網(wǎng)絡(luò)拓?fù)鋀K(4,L)，其網(wǎng)絡(luò)上各節(jié)點(diǎn)的編碼為Ak-1Ak-2…A1A0，其中Ai∈(0,1,2,3)，0≤i≤k-1。Ai的取值根據(jù)以下規(guī)則確定：0代表左上節(jié)點(diǎn)，1代表右上節(jié)點(diǎn)，2代表右下節(jié)點(diǎn)，3代表左下節(jié)點(diǎn)。

根據(jù)定義1，i代表了節(jié)點(diǎn)所在的層次。當(dāng)L為1、2、3時，核間網(wǎng)絡(luò)分別對應(yīng)4核、16核、64核處理器。在度為4的2D Mesh網(wǎng)絡(luò)中，每4個節(jié)點(diǎn)構(gòu)成一個簇，簇節(jié)點(diǎn)以4的指數(shù)級增長。如圖2所示，圖中描述了L值分別為1、2、3時，核間互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和每個節(jié)點(diǎn)的編碼方案。L代表層次數(shù)，L=0時，代表單個節(jié)點(diǎn)；L=1時，代表由4個內(nèi)核構(gòu)成的基本簇。在該拓?fù)渲芯W(wǎng)絡(luò)節(jié)點(diǎn)劃分為4個區(qū)域，每個區(qū)域分配1個固定代碼，每個區(qū)域可以進(jìn)一步劃分直到一個基本的節(jié)點(diǎn)。如節(jié)點(diǎn)302，代表在第3層編號為3的簇內(nèi)，在第2層編號為0的簇內(nèi)，在第1層右下角位置，因此節(jié)點(diǎn)編碼過程也是一個迭代的過程。

圖2 4核、16核、64核處理器的核間互連網(wǎng)絡(luò)Fig.2 Core-core interconnection network of 4-core, 16-core and 64-core

3.2 片上緩存網(wǎng)絡(luò)

緩存一致性問題源于Cache的組織結(jié)構(gòu)和使用方式，包括了數(shù)據(jù)在存儲器中的存放策略、片上網(wǎng)絡(luò)的結(jié)構(gòu)、Cache的組織方式等[8]。在水平方向，本文設(shè)計的每層網(wǎng)絡(luò)都是WK-Recursive拓?fù)浣Y(jié)構(gòu)，而在垂直方向，該網(wǎng)絡(luò)的拓?fù)錇樗牟鏄浣Y(jié)構(gòu)，如圖3所示。該網(wǎng)絡(luò)構(gòu)造出一個層次化分組共享的高性能片上存儲系統(tǒng)，而且其分組特色與核間網(wǎng)絡(luò)的層次特征相契合。片上緩存網(wǎng)絡(luò)中節(jié)點(diǎn)的編碼規(guī)則如下：

定義2 對于一個給定的片上緩存網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)的垂直高度為L+1層,其內(nèi)核節(jié)點(diǎn)的編碼為LxL-1…x1x0，xn{0,1,2}(0≤n≤L-1),n表示該節(jié)點(diǎn)所在的L級緩存。同樣,xn的取值根據(jù)以下規(guī)則：0代表左上節(jié)點(diǎn),1代表右上節(jié)點(diǎn),2代表右下節(jié)點(diǎn),3代表左下節(jié)點(diǎn)。

以16核結(jié)構(gòu)為例，片上網(wǎng)絡(luò)層次化存儲器主要由3個存儲層次構(gòu)成：私有L1 Cache片上存儲層次、分簇共享L2 Cache片上存儲層次以及簇間共享L3 Cache存儲層次。在垂直方向，所有的節(jié)點(diǎn)通過樹狀網(wǎng)絡(luò)鏈接。隨著水平層次的上升，節(jié)點(diǎn)數(shù)目逐級減少，最終形成一個尖端節(jié)點(diǎn)(0)。L1片上存儲器訪問速度最快，但容量小、成本高。3個存儲層次的訪問速度從下至上逐級遞減，容量則逐漸增加。根據(jù)程序及運(yùn)算局域性原理，片上網(wǎng)絡(luò)結(jié)構(gòu)將緊密耦合的對象和進(jìn)程映射到同組處理核內(nèi)，而松散耦合的對象和進(jìn)程映射到鄰近組的處理核內(nèi)。這樣處理核訪問同組內(nèi)的存儲器用時比跨組訪問時間要大大縮短，共享存儲器在時間和空間上取得了一個平衡。

圖3 16核處理器的片上緩存網(wǎng)絡(luò)Fig.3 On-chip network of 16-core processor memory

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

針對本文提出的非對稱雙片上策略，我們評估采用合成流量和真實(shí)負(fù)載兩種方法評估網(wǎng)絡(luò)性能。

4.1 實(shí)驗(yàn)設(shè)計及方法

GEM5是美國威斯康星大學(xué)(University of Wisconsin)開發(fā)的一款開源的全系統(tǒng)模擬器，它集成了多種商用 ISA，具備高度可配置的特性。為了評估非對稱雙片上網(wǎng)絡(luò)的性能，我們擴(kuò)展了GEM5模擬器搭建了一個功能豐富的片上網(wǎng)絡(luò)性能測試平臺。本實(shí)驗(yàn)的GEM5模擬器運(yùn)行環(huán)境為Linux操作系統(tǒng)(內(nèi)核版本2.6.38)、GCC編譯器(版本4.5.2)，仿真前對模擬器進(jìn)行了預(yù)熱以獲得穩(wěn)定可靠的結(jié)果。表1列出了實(shí)驗(yàn)平臺的系統(tǒng)配置參數(shù)。

表1 實(shí)驗(yàn)平臺的系統(tǒng)配置參數(shù)Tab.1 System configuration

本實(shí)驗(yàn)設(shè)計了兩種雙網(wǎng)絡(luò)方案，一種是同構(gòu)對稱的雙網(wǎng)絡(luò)，另一種是異構(gòu)非對稱雙網(wǎng)絡(luò)。同構(gòu)對稱的雙網(wǎng)絡(luò)設(shè)計采用核間互連網(wǎng)絡(luò)和緩存網(wǎng)絡(luò)各96 bit帶寬；非對稱雙網(wǎng)絡(luò)設(shè)計中，核間互連網(wǎng)絡(luò)帶寬為64 bit，而緩存網(wǎng)絡(luò)帶寬為128 bit。同時本實(shí)驗(yàn)對比了192 bit帶寬的單網(wǎng)絡(luò)設(shè)計方案。

合成流量模式可以模擬消息在片上網(wǎng)絡(luò)中的空間分布情況，它是研究人員對實(shí)際應(yīng)用程序中通信方式的抽象。我們建立了一個抽象的通信事務(wù)來反映緩存一致性問題，具體的策略是：

(1)讀請求被發(fā)送到系統(tǒng)最遠(yuǎn)端的Tile中，當(dāng)收到來自其L1的數(shù)據(jù)后事務(wù)完成；

(2)寫請求傳輸?shù)阶钸h(yuǎn)端的Tile中，當(dāng)收到來自其核的應(yīng)答后事務(wù)完成。

4.2 網(wǎng)絡(luò)延遲分析

在合成流量模式測試中，網(wǎng)絡(luò)平均通信延遲隨著網(wǎng)絡(luò)數(shù)據(jù)包注入速率的增長而增長。在數(shù)據(jù)包注入速率較低時，網(wǎng)絡(luò)平均通信延遲增長較緩慢，而當(dāng)網(wǎng)絡(luò)達(dá)到飽和后，數(shù)據(jù)包平均延遲急劇上升。圖4顯示了采用Uniform Random合成流量模式時三種設(shè)計方案對網(wǎng)絡(luò)延遲的影響。從合成流量模式測試結(jié)果來看，異構(gòu)非對稱雙網(wǎng)絡(luò)的平均網(wǎng)絡(luò)延遲最低，本文方案的平均網(wǎng)絡(luò)延遲比同構(gòu)對稱雙網(wǎng)絡(luò)和單網(wǎng)絡(luò)平均低27.14%和58.83%。實(shí)驗(yàn)數(shù)據(jù)表明，本文的異構(gòu)非對稱雙網(wǎng)絡(luò)結(jié)構(gòu)由于將片上網(wǎng)絡(luò)細(xì)分了核間通信網(wǎng)絡(luò)和片上緩存網(wǎng)絡(luò)，從而有效提高了數(shù)據(jù)的并行傳輸能力，減少了平均通信延遲。

圖4 網(wǎng)絡(luò)平均延時比較Fig.4 Average network latency

4.3 網(wǎng)絡(luò)吞吐量分析

網(wǎng)絡(luò)的吞吐量定義為每個周期接收的Flit的數(shù)目，吞吐量越大網(wǎng)絡(luò)在單位時間內(nèi)接收的數(shù)據(jù)包越多，網(wǎng)絡(luò)帶寬就越大。在理想情況下，片上網(wǎng)絡(luò)的帶寬隨著數(shù)據(jù)包注入速率的增長呈線性增長。然而，受到片上網(wǎng)絡(luò)路由資源(路由器和片上互連線)等限制，網(wǎng)絡(luò)在一定的數(shù)據(jù)包注入速率下達(dá)到飽和。圖5顯示了采用Uniform Random合成流量模式時三種設(shè)計方案對網(wǎng)絡(luò)延遲的影響，圖中橫軸表示每時鐘周期向網(wǎng)絡(luò)中注入Flit的數(shù)量，縱軸表示每時鐘周期接收的Flit數(shù)量。本文方案的吞吐量比同構(gòu)對稱雙網(wǎng)絡(luò)和單網(wǎng)絡(luò)平均分別提升了14.86%和28.78%。

圖5 網(wǎng)絡(luò)吞吐量比較Fig.5 Average network throughput

4.4 系統(tǒng)性能分析

在真實(shí)負(fù)載測試中，本實(shí)驗(yàn)選擇了常見的DB2、Oracle、APACHE、ZEUS四種服務(wù)器工作負(fù)載[9]。圖6顯示了系統(tǒng)整體性能，可見本文提出的異構(gòu)非對稱雙網(wǎng)絡(luò)設(shè)計優(yōu)于同構(gòu)對稱雙網(wǎng)絡(luò)和單網(wǎng)絡(luò)設(shè)計，分別是4.3%和6.1%，這充分說明針對網(wǎng)絡(luò)數(shù)據(jù)流量特征的優(yōu)化片上網(wǎng)絡(luò)設(shè)計的必要性。

圖6 系統(tǒng)整體性能比較Fig.6 Overall system performance

5 結(jié)束語

片上網(wǎng)絡(luò)是多核處理器系統(tǒng)中的重要部件之一，直接關(guān)系著系統(tǒng)的整體性能。本文針對片上網(wǎng)絡(luò)數(shù)據(jù)流量不平衡的特點(diǎn)，提出了一種異構(gòu)非對稱雙片上網(wǎng)絡(luò)的設(shè)計。區(qū)別于傳統(tǒng)的單片上網(wǎng)絡(luò)的設(shè)計，本文根據(jù)數(shù)據(jù)消息的種類，利用核間互連網(wǎng)來處理核間的短消息通信，利用緩存片上網(wǎng)絡(luò)來響應(yīng)數(shù)據(jù)請求。通過擴(kuò)展的GEM5模擬器，分別搭建了同構(gòu)雙網(wǎng)絡(luò)和異構(gòu)雙網(wǎng)絡(luò)的實(shí)驗(yàn)平臺，進(jìn)行了高層次仿真，結(jié)果表明，異構(gòu)雙網(wǎng)絡(luò)方案具有低網(wǎng)絡(luò)延遲、高網(wǎng)絡(luò)帶寬的優(yōu)點(diǎn)，對提升系統(tǒng)整體性能具有重要意義。

本文目前只對服務(wù)器負(fù)載程序進(jìn)行了測試，后續(xù)還將對具有其他訪存特征的工作負(fù)載進(jìn)行測試。另外，后續(xù)研究還將考慮一種自適應(yīng)的非對稱網(wǎng)絡(luò)調(diào)節(jié)方案，以更大程度提升系統(tǒng)性能。

：

[1] 李晨,馬勝,王璐,等. 三維片上網(wǎng)絡(luò)體系結(jié)構(gòu)研究綜述[J].計算機(jī)學(xué)報,2016,39(9):1812-1828.

LI Chen,MA Sheng,WANG Lu,et al.A survey on architecture for three-dimensional network-on-chip[J].Chinese Journal of Computers,2016,39(9):1812-1828.(in Chinese)

[2] 徐昌彪,王華,王珩,等. 信息中心網(wǎng)絡(luò)中基于節(jié)點(diǎn)緩存命中貢獻(xiàn)率的緩存替換方案[J].電訊技術(shù),2017(3):311-315.

XU Changbiao,WANG Hua,WANG Heng,et al.A cache replacement scheme based on contribution to hit ratio of node in content-centric networking[J].Telecommunication Engineering,2017(3):311-315.(in Chinese)

[3] 胡森森,計衛(wèi)星,王一拙,等. 片上多核處理器Cache一致性協(xié)議優(yōu)化研究綜述[J].軟件學(xué)報,2017,28(4):1027-1047.

HU Sensen,JI Weixing,WANG Yizhuo,et al.Survey on cache coherence protocol and performance optimization for chip multiprocessor[J].Journal of Software,2017,28(4):1027-1047.(in Chinese)

[4] XU C,NIU D,MURALIMANOHAR N,et al.Overcoming the challenges of crossbar resistive memory architectures[C]//Proceedings of 2015 International Symposium on High Performance Computer Architecture. Burlingame,CA,USA:IEEE,2015:476-488.

[5] BINKERT N,BECKMANN B,BLACK G,et al.The GEM5 simulator[J].ACM SIGARCH Computer Architecture News,2011,39(2):1-7.

[6] WANG Y,JUAN S. Hamiltonicity of the basic WK-recursive pyramid with and without faulty nodes[J].Theoretical Computer Science,2015,562(C):542-556.

[7] HU S S,SHI F,CHEN X. Hybrid WK-recursive on-chip network for multi-core system[J].Electronics Letters,2017,53(13):839-841.

[8] BECKMANN N,TSAI P A,SANCHEZ D. Scaling distributed cache hierarchies through computation and data co-scheduling[C]//Proceedings of 2015 IEEE 21st International Symposium on High Performance Computer Architecture. Burlingame,CA,USA:IEEE,2015:538-550.

[9] JALEEL A,NUZMAN J,MOGA A,et al.High performing cache hierarchies for server workloads:Relaxing inclusion to capture the latency benefits of exclusive caches[C]//Proceedings of 2015 IEEE 21st International Symposium on High Performance Computer Architecture.Burlingame,CA,USA:IEEE,2015:343-353.