基于蟲孔直通交換片上網絡的共享優先級機制

吳陶迪, 孫自強(華東理工大學化工過程先進控制和優化技術教育部重點實驗室,上海 200237 )

基于蟲孔直通交換片上網絡的共享優先級機制

吳陶迪, 孫自強
(華東理工大學化工過程先進控制和優化技術教育部重點實驗室,上海 200237 )

基于傳統蟲孔直通交換(Conventional Wormhole Cut-Through Switching,Con-WCTS)的片上網絡系統(Network-on-Chip,NoC)無法直接實現基于優先級的仲裁邏輯,不適用于對信息傳輸實時性要求較高的多核片上系統。引入虛擬通道技術,提出了共享優先級蟲孔直通交換(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)的網絡結構,并給出了該網絡信息最壞傳輸時間的計算方法。通過實驗對比了Con-WCT網絡、共享優先級蟲孔交換(Shared Priority Wormhole Switching,SP-WS)網絡、SP-WCTS網絡以及輪詢蟲孔交換 (Round Robin Wormhole Switching,RR-WS)網絡的可調度性,并探究了虛擬通道數量和總網絡利用率對網絡可調度性的影響。實驗結果表明:SP-WCTS的可調度性要明顯優于另外3種網絡;虛擬通道數量和總網絡利用率對SP-WS網絡可調度性的影響大于共享優先級SP-WCTS網絡。

片上網絡; 蟲孔直通交換; 共享優先級; 可調度性分析

隨著多核片上系統(Multiprocessor System-on-Chip,MPSoC)上計算單元(Processing Element,PE)數量的增多,PE之間頻繁、大量的數據交換已經成為MPSoC技術發展中需要解決的一個重要問題[1-2]。目前,用于多核間通信的方法主要有基于總線的網絡和片上網絡(Network-on-Chip,NoC)[3]。其中,NoC克服了總線在大量并行通信環境中存在的長延時、高功耗等問題[4],成為目前MPSoC中主要的通信方式。

交換機制是NoC的關鍵技術之一,定義了數據從源節點傳輸到目標節點的方式[4]。目前常用的交換機制有:包交換、蟲孔交換、電路交換、虛擬直通交換,其中,蟲孔交換機制有著優良的延時性能和較小的緩存要求,已經成為當前片上網絡的主流交換機制[5-6]。

在蟲孔交換機制中,每個報文被劃分成許多固定大小的微片(Flit)。報文的路由信息存儲在頭微片中,其余微片跟隨頭微片的路徑傳輸。當頭微片被阻塞時,該報文的所有微片就地存儲,直至阻塞結束。蟲孔交換有著通信延時短、緩存小和易實現等優點,但同時也存在排頭阻塞的問題。引入虛擬通道(Virtual Channel,VC)[7]技術可以有效地解決排頭阻塞,但也增加了緩存的消耗。目前,已經有很多的NoC設計被提出[8-9]。Schoeberl等[10]改進了時分多路復用NoC,使其適用于通用硬件平臺。Lee等[11]設計了一種自適應指令解碼NoC結構,允許多報文的融合傳輸,提高了網絡的利用率和吞吐量。文獻[12]提出了一種蟲孔直通交換機制,在不引入虛擬通道的情況下解決了傳統蟲孔交換的排頭阻塞問題,減少了片上網絡所需的緩存。

為了解決來自不同輸入口的報文競爭同一個輸出端口的問題,NoC路由的每個輸出端口都會設有一個仲裁器,實現端口的共享[13]。目前常用的仲裁設計有輪詢機制和基于優先級機制。在實時性要求較高的應用中,常采用基于優先級的仲裁機制。然而在蟲孔直通交換機制下使用基于優先級的仲裁機制時,可能造成優先級反轉,高優先級的信息的阻塞時間變得不可預測。針對這一弊端,本文提出了一種基于虛擬通道技術改進的共享優先級蟲孔直通交換(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)機制,消除了共享優先級仲裁機制中存在的優先級反轉問題，并給出了信息最壞傳輸時間(Worst-Case Traversing Time,WCTT)的計算方法。另外,本文對比了不同網絡參數對傳統蟲孔交換網絡和SP-WCTS實時性分析的影響,對設計者在不同的應用場景中選擇合適的片上網絡交換機制有一定的參考意義。

1 基于優先級共享的蟲孔直通交換

1.1 蟲孔直通交換

蟲孔直通交換融合了蟲孔交換和直通交換技術。如圖1所示,路由為各微片設置一個本地ID,來自同一個報文的微片,其本地ID相同。傳輸過程中,各輸出端口對發出傳輸請求的輸入端口輪流接通,從而使得來自不同輸入端口的微片交錯地從同一個輸出端口輸出。為保證來自不同報文的微片正確地選擇其路徑,蟲孔直通交換路由設置有一個路徑保留表,存儲了每個本地ID及其對應的輸出端口。每個報文的本地ID在頭微片傳入路由時分配,尾微片傳出時回收。

圖1 蟲孔直通交換

傳統蟲孔直通交換中,來自不同輸入端口的報文在同一輸出端口公平地輸出,不適用于實時性要求較高的場合。為了保證實時報文在截止期限之前到達目的節點,需要采用基于優先級的仲裁機制,而在蟲孔直通交換機制下直接使用優先級仲裁可能會導致優先級反轉。假設圖1中的業務優先級順序為A>C>B,若A恰好在B的某個微片后傳入,則C會搶占B,從而阻塞A,造成優先級反轉,高優先級業務A被阻塞的時間難以預測。

1.2 共享優先級蟲孔直通交換

為了解決優先級反轉問題,本文引入虛擬通道技術,提出了一種共享優先級蟲孔直通交換(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)網絡。虛擬通道技術是將每個網絡通道的緩存劃分為若干獨立的小片,從而將網絡中單個的物理連接劃分成若干個邏輯上獨立的虛擬通道,每個虛擬通道擁有獨立的緩存隊列。虛擬通道技術主要用來避免死鎖(Deadlock),提高帶寬使用率[4]。

SP-WCTS網絡的傳輸機制如圖2所示。每個輸入端口的緩存被劃分為幾個獨立的小片,每一個小片都可以作為一個虛擬通道。SP-WCTS網絡為每一個優先級分配一個虛擬通道,各虛擬通道有獨立的先進先出隊列,優先級為i的業務只能使用優先級為i的虛擬通道。不同優先級業務間的搶占發生在微片級,即高優先級業務可以在低優先級業務傳輸完一個微片后搶占輸出端口。當一個網絡連接上的高優先級業務被阻塞時,低優先級的業務可以使用該連接進行傳輸。

圖2 共享優先級蟲孔直通交換網絡仲裁機制

虛擬通道的引入會增加路由緩存的消耗,為了兼顧實時性能和資源消耗,SP-WCTS允許多個傳輸任務共享同一個優先級,以減少虛擬通道的數目。同優先級的報文在微片級相互交錯傳輸,避免了同優先級傳輸任務之間的長時間阻塞。網絡中,優先級標號越大表示優先級別越低,優先級1為最高優先級。τ1與τ2共享優先級1,該輸入端緩存中微片被讀取的順序如圖2中Output所示。每個輸出端在發出請求的輸入端選擇最高優先級的虛擬通道進行傳輸。

2 網絡最壞延時分析

2.1 實時通信模型

設一個蟲孔直通交換網絡Γ中存在n個業務:

(1)

其中τi代表業務i,并假設所有的業務都是周期性地發送報文。每個業務可以用如下5個屬性來表示:

(2)

2.2 業務之間關系分析

圖3 片上網絡業務示例

當不同的業務共享同一個物理連接時,信息傳輸的過程中可能發生資源競爭的現象。在SP-WCTS網絡的同一連接上,來自同優先級業務的報文在微片級別相互交錯傳輸,共享帶寬;來自高優先級業務的報文可以在微片級別搶占低優先級的業務進行傳輸,在當前報文傳輸結束時,低優先級的業務繼續傳輸。高優先級業務搶占低優先級進行傳輸的現象稱為干擾(Interference)。

(3)

若高優先級業務j不與業務i共享物理連接,但存在一個中介業務k,分別與業務j和業務i共享物理連接,且k的優先級滿足Pj≥Pk>Pi,則業務j可能通過業務k依然對業務i造成間接干擾。業務i的間接干擾集合為

(4)

(5)

2.3 信息最壞傳輸時間計算

實時性能分析在片上網絡系統的設計中有著至關重要的作用[16],WCTT是衡量系統實時性能的一個重要參數。在實時系統中,各實時業務的報文必須在其截止期限前完整傳輸至目的節點。當某一報文不能滿足實時性要求時,可能會造成系統的降級運行,甚至災難性后果。

信息的WCTT是指在最壞情況下,該業務的報文從釋放到完整地被目的節點接收所需要的傳輸時間。根據2.2節的分析可知,在共享優先級蟲孔直通交換網絡中,業務會受到來自高優先級業務的干擾,同時與同優先級的業務共享帶寬。所以,對任意一個業務i的報文,其傳輸的最壞情況是:所有高優先級數據流與之同時競爭共享資源,并且所有同優先級的業務在其完成傳輸任務前不間斷地進行數據傳輸,占用帶寬。

(6)

來自業務i的報文在傳輸過程中會受到來自高優先級報文的干擾,由2.2節可知,在最壞情況下,高優先級報文的干擾如圖4所示,業務τi受到來自高優先級業務τj的直接干擾。當業務τi的同優先級業務被其他高優先級業務的傳輸任務搶占時,業務τi同時會被該同優先級業務阻塞。這一阻塞現象可近似看成業務τi受到來自該高優先級數據流的直接干擾。

圖4 高優先級業務的干擾

由上述分析可得出業務τi的最壞傳輸時間為

(7)

(8)

(9)

3 仿真實驗與分析

3.1 實驗設計

針對共享優先級蟲孔交換 (Shared Priority Wormhole Switching,SP-WS) 網絡[15]、輪詢蟲孔交換 (Round Robin Wormhole Switching,RR-WS)網絡[19]、傳統蟲孔直通交換 (Conventional Wormhole Cut-Through Switching,Con-WCTS) 網絡[12]以及本文SP-WCTS網絡設計了仿真實驗,比較了業務數目、虛擬通道個數以及總網絡利用率對片上網絡可調度性的影響。當系統中存在業務不能滿足其截止期限時,該系統不可調度。可調度性采用每組實驗中可調度的系統數占總系統數的比例表示:

(10)

其中:Ras為可調度性;Ns為可調度系統數目;Nt為實驗中總的系統數目。

實驗中采用的片上網絡結構為常用的4×4 的2D mesh 結構。為了不失一般性,實驗中業務的各參數均隨機生成,具體生成方法如下:

(1) 報文長度。實驗前給定報文長度的范圍,各數據流的數據長度在該范圍內,采用均勻分布的方式隨機生成。本文實驗使用的報文長度范圍為[5,100],網絡中微片的長度為1。

(2) 網絡利用率。設置網絡利用率的范圍,各業務在該范圍內采用均勻分布的方式隨機生成網絡利用率,業務的網絡利用率計算公式為Ui=Ci/Ti。

(3) 路徑。隨機生成各業務的源節點和目的節點,并采用XY路由算法生成路徑,XY路由算法是目前常用的路由算法之一,可避免死鎖和活鎖問題[4]。

各業務發送單個報文所需要的基本傳輸時間可根據式(7)計算,需要注意的是,基本傳輸時間是在不考慮網絡中其他業務的干擾,該業務享有全部帶寬的情況下,單個報文從源節點傳輸至目的節點所需要的時間。實驗中,各業務的截止期限等于其周期,即Di=Ti。

3.2 業務數量的影響

將網絡中業務數量從10增加到50,各業務網絡利用率的范圍設為[0.001,0.01],圖5展示了不同數量業務對網絡可調度性的影響。實驗比較了RR-WS、Con-WCTS、SP-WS以及SP-WCTS 4種網絡,其中SP-WS和SP-WCTS同時考慮了在3VC和6VC下的可調度性。由圖5可知:

(1) 隨著業務數量的增加,各網絡的可調度性下降。其原因是隨著業務數量的增加,網絡的負載增大,導致網絡延時增加,可調度性下降。

(2) 在相同的業務數量下,不同網絡的可調度性存在差異。 其中,6VC的SP-WCTS網絡可調度性最優,RR-WS最差。這是由于在RR-WS網絡中存在嚴重的排頭阻塞,當某個報文在一個連接上被阻塞,則其上游的所有與之相關的報文都會被相應阻塞,從而導致了嚴重的網絡延時。

(3) 在相同數目的VC下,SP-WCTS的可調度性明顯優于SP-WS。其原因是,在SP-WCTS網絡中,同優先級業務之間交錯傳輸,其阻塞時間要遠遠小于SP-WS網絡。此外,Con-WCTS網絡的可調度性介于6VC和3VC的SP-WCTS之間,其主要原因是當虛擬通道較少時,同優先級業務之間的阻塞比較大,而在Con-WCTS網絡中所有業務共享帶寬,沒有排頭阻塞,從而導致了VC數目較少時,SP-WCTS網絡的可調度性劣于Con-WCTS網絡。但是,由于SP-WCTS 采用了基于優先級的仲裁邏輯,可以更好地滿足高優先級業務的實時性要求,比Con-WCTS網絡更加適用于實時性應用。

圖5 不同業務數量下的可調度性

3.3 虛擬通道數目的影響

本實驗研究了VC數目對SP-WCTS網絡和SP-WS網絡可調度性的影響。實驗網絡的業務數量為30,各業務的參數設置同3.2節,VC數目從2增加到8,對不同虛擬通道數目下的網絡各進行200組實驗。

圖6示出了兩種網絡在不同數目VC下的可調度性。可以看出,隨著VC數目的增加,SP-WS網絡中的可調度性增強,SP-WCTS網絡的可調度性先降低后增強,并在3VC時最低。造成這一現象的原因是,在SP-WCTS網絡中,隨著VC數目的增加,同優先級業務之間的阻塞減少,而來自高優先級業務的干擾增多。然而SP-WCTS網絡中的阻塞本質來源于高優先級業務的干擾,阻塞和干擾相互影響,導致了SP-WCTS網絡的可調度性隨著VC數目的增加,先降低后增加。

3.4 平均網絡利用率的影響

為了研究SP-WCTS網絡和SP-WS網絡的負載能力,本文在不同網絡利用率下對兩種網絡進行了可調度性實驗。各組實驗的業務的網路利用率范圍分別為[0.001 0,0.009 0],[0.001 4,0.012 6],[0.001 8,0.016 2],[0.002 2,0.019 8],[0.002 6,0.023 4],[0.003,0.027]。業務集合中的業務數量為30,其余參數設置同3.2節,實驗結果如圖7所示。圖中橫坐標為總網絡利用率,為所有業務的網絡利用率之和,采用如下計算公式:

(11)

其中:Umax和Umin分別為業務網絡利用率的上下限;Nflow為網絡中業務的數目。

圖6 不同虛擬通道數下的可調度性

圖7 不同總網絡利用率下的可調度性

由圖7可知,隨著總網絡利用率的增加,各網絡的可調度性降低,且SP-WS網絡的下降速度明顯快于SP-WCTS網絡,表明SP-WCTS網絡相對于SP-WS網絡可承受更大的業務負載。在相同的網絡利用率下,SP-WCTS網絡的可調度性基本上優于SP-WS網絡。在網絡利用率為0.4時,6VC的SP-WS網絡的可調度性高于3VC 的SP-WCTS網絡,但隨著網路利用率的增加,前者的可調度性下降劇烈,在網絡利用率為0.5時,其可調度性已經低于3VC的SP-WCTS網路。

4 結論與展望

蟲孔直通交換網絡實現了業務之間的交錯傳遞,解決了傳統蟲孔交換網絡的排頭阻塞問題,但其無法滿足較高的實時性要求。本文引入了虛擬通道技術,在蟲孔直通交換網絡中使用了基于優先級的仲裁機制,提出了共享優先級蟲孔直通交換網絡結構,并給出了信息最壞網絡延時的計算方法,方便設計人員對網絡的實時性能進行分析。

為了研究共享優先級蟲孔直通交換網絡的實時性能,通過一系列實驗對比了Con-WCTS網絡、RR-WS網絡以及SP-WS網絡。由實驗結果可知,共享優先級蟲孔直通網絡交換網絡有著良好的實時性能,可以承擔更大的網絡負載。在未來工作中,還可以對SP-WCTS網絡的資源和能源消耗進行更加深入的研究。

[1]周君,王天成,李華偉,等.多核處理器片上網絡的驗證技術綜述[J].計算機科學,2013,40(專刊):33-39.

[2]黃國睿,張平,魏廣博,等.多核處理器的關鍵技術及其發展趨勢[J].計算機工程與設計,2009,30(10) :2414-2418.

[3]李麗,許居衍.片上網絡技術發展現狀及趨勢淺析[J].電子產品世界,2009,16(1):32-37.

[4]COTA é,DE MORAIS AMORY A,LUBASZEWSKI M S.Reliability,Availability and Serviceability of Networks-on-Chip[M].USA: Springer Science & Business Media,2011.

[5]王崢,顧華璽,楊燁,等.片上網絡交換機制的研究[J].中國集成電路,2007,16(12):22-27.

[6]NI L M,MCKINLEY P K.A survey of wormhole routing techniques in direct networks[J].Computer,1993,26(2):62-76.

[7]KAVALDJIEV N,SMIT G J M,JANSEN P G,etal. A virtual channel network-on-chip for GT and BE traffic[C]//IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures (ISVLSI′06).USA:IEEE,2006:211-217.

[8]DINECHIN B D,DURAND Y,VAN AMSTEL D,etal.Guaranteed services of the NoC of a manycore processor[C]//Proceedings of the 2014 International Workshop on Network on Chip Architectures.USA: ACM,2014:11-16.

[9]POLURI P,LOURI A.Shield:A reliable network-on-chip router architecture for chip multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(10):3058-3070.

[10]SCHOEBERL M,BRANDNER F,SPARS? J,etal.A statically scheduled time-division-multiplexed network-on-chip for real-time systems[C]//2012 Sixth IEEE/ACM International Symposium on Networks on Chip (NoCS).USA:IEEE,2012:152-160.

[11]LEE T Y,HUANG C H,LIU M J,etal.Adaptive instruction codec architecture design for network-on-chip[J].Computers & Electrical Engineering,2016,51(4):207-224.

[12]SAMMAN F A,HOLLSTEIN T,GLESNER M.Wormhole cut-through switching:Flit-level messages interleaving for virtual-channelless network-on-chip[J].Microprocessors and Microsystems,2011,35(3):343-358.

[13]官錚,錢文華,杜長青,等.具有服務質量保障的片上網絡路由仲裁控制[J].計算機科學,2015,42(2):55-59.

[14]LU Z,JANTSCH A,SANDER I.Feasibility analysis of messages for on-chip networks using wormhole routing [C]//Proceedings of the ASP-DAC 2005,Asia and South Pacific Design Automation Conference.USA:IEEE,2005:960-964.

[15]SHI Z,BURNS A,INDRUSIAK L S.Schedulability analysis for real time on-chip communication with wormhole switching[J].International Journal of Embedded and Real-Time Communication Systems,2010,1(2):1-22.

[16]ABDALLAH L,JAN M,ERMONT J,etal.Wormhole networks properties and their use for optimizing worst case delay analysis of many-cores[C]//10th IEEE International Symposium on Industrial Embedded Systems (SIES).USA:IEEE,2015:1-10.

[17]SHI Z,BURNS A.Real-time communication analysis for on-chip networks with wormhole switching [C]//Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip.USA: IEEE Computer Society,2008:161-170.

[18]AUDSLEY N,BURNS A,RICHARDSON M,etal.Applying new scheduling theory to static priority pre-emptive scheduling[J].Software Engineering Journal,1993,8(5):284-292.

[19]LIU M,BECKER M,BEHNAM M,etal.Using segmentation to improve schedulability of real-time packets on NoCs with mixed traffic[R].Sweden:M?lardalen University,2016.

A Shared Priority Policy in Wormhole Cut-Through Switching Based Network-on-Chip

WU Tao-di, SUN Zi-qiang

(Key Laboratory of Advanced Control and Optimization for Chemical Process,Ministry of Education, East China University of Science and Technology,Shanghai 200237,China)

Network-on-Chip (NoC) based conventional wormhole cut-through switching (Con-WCTS) cannot employ the priority based arbitration logic directly,so it is not suitable for the multiprocessor system-on-chip with high real-time requirements.By utilizing the virtual channel technique,this paper constructs a shared priority wormhole cut-through switching (SP-WCTS) network and proposes a method to calculate the worst-case traversing time for the traffic-flow of the SP-WCTS NoC.Furthermore,some experiments are made for comparing the schedulability of Con-WCT,shared priority wormhole switching (SP-WS),SP-WCTS and round robin wormhole switching (RR-WS) NoCs and analyzing the effect of the number of VCs and the total network utilization on the schedulability of these different NoCs.It is shown that the SP-WCTS NoCs can achieves the best schedulability and the number of VCs has a greater effect on the schedulability of the SP-WS than SP-WCTS NoCs.

network-on-chip; wormhole cut-through switching; shared priority; schedulability analysis

1006-3080(2017)02-0254-06

10.14135/j.cnki.1006-3080.2017.02.016

2016-09-06

上海市重點學科建設基金(B504)

吳陶迪(1992-),男,碩士生,研究方向為實時嵌入式系統。E-mail:taodi_wu@foxmail.com

孫自強,E-mail:sunziqiang@ecust.edu.cn

TP302

A