吳陶迪, 孫自強(華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237 )
基于蟲孔直通交換片上網(wǎng)絡(luò)的共享優(yōu)先級機(jī)制
吳陶迪, 孫自強
(華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237 )
基于傳統(tǒng)蟲孔直通交換(Conventional Wormhole Cut-Through Switching,Con-WCTS)的片上網(wǎng)絡(luò)系統(tǒng)(Network-on-Chip,NoC)無法直接實現(xiàn)基于優(yōu)先級的仲裁邏輯,不適用于對信息傳輸實時性要求較高的多核片上系統(tǒng)。引入虛擬通道技術(shù),提出了共享優(yōu)先級蟲孔直通交換(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)的網(wǎng)絡(luò)結(jié)構(gòu),并給出了該網(wǎng)絡(luò)信息最壞傳輸時間的計算方法。通過實驗對比了Con-WCT網(wǎng)絡(luò)、共享優(yōu)先級蟲孔交換(Shared Priority Wormhole Switching,SP-WS)網(wǎng)絡(luò)、SP-WCTS網(wǎng)絡(luò)以及輪詢蟲孔交換 (Round Robin Wormhole Switching,RR-WS)網(wǎng)絡(luò)的可調(diào)度性,并探究了虛擬通道數(shù)量和總網(wǎng)絡(luò)利用率對網(wǎng)絡(luò)可調(diào)度性的影響。實驗結(jié)果表明:SP-WCTS的可調(diào)度性要明顯優(yōu)于另外3種網(wǎng)絡(luò);虛擬通道數(shù)量和總網(wǎng)絡(luò)利用率對SP-WS網(wǎng)絡(luò)可調(diào)度性的影響大于共享優(yōu)先級SP-WCTS網(wǎng)絡(luò)。
片上網(wǎng)絡(luò); 蟲孔直通交換; 共享優(yōu)先級; 可調(diào)度性分析
隨著多核片上系統(tǒng)(Multiprocessor System-on-Chip,MPSoC)上計算單元(Processing Element,PE)數(shù)量的增多,PE之間頻繁、大量的數(shù)據(jù)交換已經(jīng)成為MPSoC技術(shù)發(fā)展中需要解決的一個重要問題[1-2]。目前,用于多核間通信的方法主要有基于總線的網(wǎng)絡(luò)和片上網(wǎng)絡(luò)(Network-on-Chip,NoC)[3]。其中,NoC克服了總線在大量并行通信環(huán)境中存在的長延時、高功耗等問題[4],成為目前MPSoC中主要的通信方式。
交換機(jī)制是NoC的關(guān)鍵技術(shù)之一,定義了數(shù)據(jù)從源節(jié)點傳輸?shù)侥繕?biāo)節(jié)點的方式[4]。目前常用的交換機(jī)制有:包交換、蟲孔交換、電路交換、虛擬直通交換,其中,蟲孔交換機(jī)制有著優(yōu)良的延時性能和較小的緩存要求,已經(jīng)成為當(dāng)前片上網(wǎng)絡(luò)的主流交換機(jī)制[5-6]。
在蟲孔交換機(jī)制中,每個報文被劃分成許多固定大小的微片(Flit)。報文的路由信息存儲在頭微片中,其余微片跟隨頭微片的路徑傳輸。當(dāng)頭微片被阻塞時,該報文的所有微片就地存儲,直至阻塞結(jié)束。蟲孔交換有著通信延時短、緩存小和易實現(xiàn)等優(yōu)點,但同時也存在排頭阻塞的問題。引入虛擬通道(Virtual Channel,VC)[7]技術(shù)可以有效地解決排頭阻塞,但也增加了緩存的消耗。目前,已經(jīng)有很多的NoC設(shè)計被提出[8-9]。Schoeberl等[10]改進(jìn)了時分多路復(fù)用NoC,使其適用于通用硬件平臺。Lee等[11]設(shè)計了一種自適應(yīng)指令解碼NoC結(jié)構(gòu),允許多報文的融合傳輸,提高了網(wǎng)絡(luò)的利用率和吞吐量。文獻(xiàn)[12]提出了一種蟲孔直通交換機(jī)制,在不引入虛擬通道的情況下解決了傳統(tǒng)蟲孔交換的排頭阻塞問題,減少了片上網(wǎng)絡(luò)所需的緩存。
為了解決來自不同輸入口的報文競爭同一個輸出端口的問題,NoC路由的每個輸出端口都會設(shè)有一個仲裁器,實現(xiàn)端口的共享[13]。目前常用的仲裁設(shè)計有輪詢機(jī)制和基于優(yōu)先級機(jī)制。在實時性要求較高的應(yīng)用中,常采用基于優(yōu)先級的仲裁機(jī)制。然而在蟲孔直通交換機(jī)制下使用基于優(yōu)先級的仲裁機(jī)制時,可能造成優(yōu)先級反轉(zhuǎn),高優(yōu)先級的信息的阻塞時間變得不可預(yù)測。針對這一弊端,本文提出了一種基于虛擬通道技術(shù)改進(jìn)的共享優(yōu)先級蟲孔直通交換(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)機(jī)制,消除了共享優(yōu)先級仲裁機(jī)制中存在的優(yōu)先級反轉(zhuǎn)問題,并給出了信息最壞傳輸時間(Worst-Case Traversing Time,WCTT)的計算方法。另外,本文對比了不同網(wǎng)絡(luò)參數(shù)對傳統(tǒng)蟲孔交換網(wǎng)絡(luò)和SP-WCTS實時性分析的影響,對設(shè)計者在不同的應(yīng)用場景中選擇合適的片上網(wǎng)絡(luò)交換機(jī)制有一定的參考意義。
1.1 蟲孔直通交換
蟲孔直通交換融合了蟲孔交換和直通交換技術(shù)。如圖1所示,路由為各微片設(shè)置一個本地ID,來自同一個報文的微片,其本地ID相同。傳輸過程中,各輸出端口對發(fā)出傳輸請求的輸入端口輪流接通,從而使得來自不同輸入端口的微片交錯地從同一個輸出端口輸出。為保證來自不同報文的微片正確地選擇其路徑,蟲孔直通交換路由設(shè)置有一個路徑保留表,存儲了每個本地ID及其對應(yīng)的輸出端口。每個報文的本地ID在頭微片傳入路由時分配,尾微片傳出時回收。
圖1 蟲孔直通交換
傳統(tǒng)蟲孔直通交換中,來自不同輸入端口的報文在同一輸出端口公平地輸出,不適用于實時性要求較高的場合。為了保證實時報文在截止期限之前到達(dá)目的節(jié)點,需要采用基于優(yōu)先級的仲裁機(jī)制,而在蟲孔直通交換機(jī)制下直接使用優(yōu)先級仲裁可能會導(dǎo)致優(yōu)先級反轉(zhuǎn)。假設(shè)圖1中的業(yè)務(wù)優(yōu)先級順序為A>C>B,若A恰好在B的某個微片后傳入,則C會搶占B,從而阻塞A,造成優(yōu)先級反轉(zhuǎn),高優(yōu)先級業(yè)務(wù)A被阻塞的時間難以預(yù)測。
1.2 共享優(yōu)先級蟲孔直通交換
為了解決優(yōu)先級反轉(zhuǎn)問題,本文引入虛擬通道技術(shù),提出了一種共享優(yōu)先級蟲孔直通交換(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)網(wǎng)絡(luò)。虛擬通道技術(shù)是將每個網(wǎng)絡(luò)通道的緩存劃分為若干獨立的小片,從而將網(wǎng)絡(luò)中單個的物理連接劃分成若干個邏輯上獨立的虛擬通道,每個虛擬通道擁有獨立的緩存隊列。虛擬通道技術(shù)主要用來避免死鎖(Deadlock),提高帶寬使用率[4]。
SP-WCTS網(wǎng)絡(luò)的傳輸機(jī)制如圖2所示。每個輸入端口的緩存被劃分為幾個獨立的小片,每一個小片都可以作為一個虛擬通道。SP-WCTS網(wǎng)絡(luò)為每一個優(yōu)先級分配一個虛擬通道,各虛擬通道有獨立的先進(jìn)先出隊列,優(yōu)先級為i的業(yè)務(wù)只能使用優(yōu)先級為i的虛擬通道。不同優(yōu)先級業(yè)務(wù)間的搶占發(fā)生在微片級,即高優(yōu)先級業(yè)務(wù)可以在低優(yōu)先級業(yè)務(wù)傳輸完一個微片后搶占輸出端口。當(dāng)一個網(wǎng)絡(luò)連接上的高優(yōu)先級業(yè)務(wù)被阻塞時,低優(yōu)先級的業(yè)務(wù)可以使用該連接進(jìn)行傳輸。
圖2 共享優(yōu)先級蟲孔直通交換網(wǎng)絡(luò)仲裁機(jī)制
虛擬通道的引入會增加路由緩存的消耗,為了兼顧實時性能和資源消耗,SP-WCTS允許多個傳輸任務(wù)共享同一個優(yōu)先級,以減少虛擬通道的數(shù)目。同優(yōu)先級的報文在微片級相互交錯傳輸,避免了同優(yōu)先級傳輸任務(wù)之間的長時間阻塞。網(wǎng)絡(luò)中,優(yōu)先級標(biāo)號越大表示優(yōu)先級別越低,優(yōu)先級1為最高優(yōu)先級。τ1與τ2共享優(yōu)先級1,該輸入端緩存中微片被讀取的順序如圖2中Output所示。每個輸出端在發(fā)出請求的輸入端選擇最高優(yōu)先級的虛擬通道進(jìn)行傳輸。
2.1 實時通信模型
設(shè)一個蟲孔直通交換網(wǎng)絡(luò)Γ中存在n個業(yè)務(wù):
(1)
其中τi代表業(yè)務(wù)i,并假設(shè)所有的業(yè)務(wù)都是周期性地發(fā)送報文。每個業(yè)務(wù)可以用如下5個屬性來表示:
(2)
2.2 業(yè)務(wù)之間關(guān)系分析
圖3 片上網(wǎng)絡(luò)業(yè)務(wù)示例
當(dāng)不同的業(yè)務(wù)共享同一個物理連接時,信息傳輸?shù)倪^程中可能發(fā)生資源競爭的現(xiàn)象。在SP-WCTS網(wǎng)絡(luò)的同一連接上,來自同優(yōu)先級業(yè)務(wù)的報文在微片級別相互交錯傳輸,共享帶寬;來自高優(yōu)先級業(yè)務(wù)的報文可以在微片級別搶占低優(yōu)先級的業(yè)務(wù)進(jìn)行傳輸,在當(dāng)前報文傳輸結(jié)束時,低優(yōu)先級的業(yè)務(wù)繼續(xù)傳輸。高優(yōu)先級業(yè)務(wù)搶占低優(yōu)先級進(jìn)行傳輸?shù)默F(xiàn)象稱為干擾(Interference)。
(3)
若高優(yōu)先級業(yè)務(wù)j不與業(yè)務(wù)i共享物理連接,但存在一個中介業(yè)務(wù)k,分別與業(yè)務(wù)j和業(yè)務(wù)i共享物理連接,且k的優(yōu)先級滿足Pj≥Pk>Pi,則業(yè)務(wù)j可能通過業(yè)務(wù)k依然對業(yè)務(wù)i造成間接干擾。業(yè)務(wù)i的間接干擾集合為
(4)
(5)
2.3 信息最壞傳輸時間計算
實時性能分析在片上網(wǎng)絡(luò)系統(tǒng)的設(shè)計中有著至關(guān)重要的作用[16],WCTT是衡量系統(tǒng)實時性能的一個重要參數(shù)。在實時系統(tǒng)中,各實時業(yè)務(wù)的報文必須在其截止期限前完整傳輸至目的節(jié)點。當(dāng)某一報文不能滿足實時性要求時,可能會造成系統(tǒng)的降級運行,甚至災(zāi)難性后果。
信息的WCTT是指在最壞情況下,該業(yè)務(wù)的報文從釋放到完整地被目的節(jié)點接收所需要的傳輸時間。根據(jù)2.2節(jié)的分析可知,在共享優(yōu)先級蟲孔直通交換網(wǎng)絡(luò)中,業(yè)務(wù)會受到來自高優(yōu)先級業(yè)務(wù)的干擾,同時與同優(yōu)先級的業(yè)務(wù)共享帶寬。所以,對任意一個業(yè)務(wù)i的報文,其傳輸?shù)淖顗那闆r是:所有高優(yōu)先級數(shù)據(jù)流與之同時競爭共享資源,并且所有同優(yōu)先級的業(yè)務(wù)在其完成傳輸任務(wù)前不間斷地進(jìn)行數(shù)據(jù)傳輸,占用帶寬。
(6)
來自業(yè)務(wù)i的報文在傳輸過程中會受到來自高優(yōu)先級報文的干擾,由2.2節(jié)可知,在最壞情況下,高優(yōu)先級報文的干擾如圖4所示,業(yè)務(wù)τi受到來自高優(yōu)先級業(yè)務(wù)τj的直接干擾。當(dāng)業(yè)務(wù)τi的同優(yōu)先級業(yè)務(wù)被其他高優(yōu)先級業(yè)務(wù)的傳輸任務(wù)搶占時,業(yè)務(wù)τi同時會被該同優(yōu)先級業(yè)務(wù)阻塞。這一阻塞現(xiàn)象可近似看成業(yè)務(wù)τi受到來自該高優(yōu)先級數(shù)據(jù)流的直接干擾。
圖4 高優(yōu)先級業(yè)務(wù)的干擾
由上述分析可得出業(yè)務(wù)τi的最壞傳輸時間為
(7)
(8)
(9)
3.1 實驗設(shè)計
針對共享優(yōu)先級蟲孔交換 (Shared Priority Wormhole Switching,SP-WS) 網(wǎng)絡(luò)[15]、輪詢蟲孔交換 (Round Robin Wormhole Switching,RR-WS)網(wǎng)絡(luò)[19]、傳統(tǒng)蟲孔直通交換 (Conventional Wormhole Cut-Through Switching,Con-WCTS) 網(wǎng)絡(luò)[12]以及本文SP-WCTS網(wǎng)絡(luò)設(shè)計了仿真實驗,比較了業(yè)務(wù)數(shù)目、虛擬通道個數(shù)以及總網(wǎng)絡(luò)利用率對片上網(wǎng)絡(luò)可調(diào)度性的影響。當(dāng)系統(tǒng)中存在業(yè)務(wù)不能滿足其截止期限時,該系統(tǒng)不可調(diào)度??烧{(diào)度性采用每組實驗中可調(diào)度的系統(tǒng)數(shù)占總系統(tǒng)數(shù)的比例表示:
(10)
其中:Ras為可調(diào)度性;Ns為可調(diào)度系統(tǒng)數(shù)目;Nt為實驗中總的系統(tǒng)數(shù)目。
實驗中采用的片上網(wǎng)絡(luò)結(jié)構(gòu)為常用的4×4 的2D mesh 結(jié)構(gòu)。為了不失一般性,實驗中業(yè)務(wù)的各參數(shù)均隨機(jī)生成,具體生成方法如下:
(1) 報文長度。實驗前給定報文長度的范圍,各數(shù)據(jù)流的數(shù)據(jù)長度在該范圍內(nèi),采用均勻分布的方式隨機(jī)生成。本文實驗使用的報文長度范圍為[5,100],網(wǎng)絡(luò)中微片的長度為1。
(2) 網(wǎng)絡(luò)利用率。設(shè)置網(wǎng)絡(luò)利用率的范圍,各業(yè)務(wù)在該范圍內(nèi)采用均勻分布的方式隨機(jī)生成網(wǎng)絡(luò)利用率,業(yè)務(wù)的網(wǎng)絡(luò)利用率計算公式為Ui=Ci/Ti。
(3) 路徑。隨機(jī)生成各業(yè)務(wù)的源節(jié)點和目的節(jié)點,并采用XY路由算法生成路徑,XY路由算法是目前常用的路由算法之一,可避免死鎖和活鎖問題[4]。
各業(yè)務(wù)發(fā)送單個報文所需要的基本傳輸時間可根據(jù)式(7)計算,需要注意的是,基本傳輸時間是在不考慮網(wǎng)絡(luò)中其他業(yè)務(wù)的干擾,該業(yè)務(wù)享有全部帶寬的情況下,單個報文從源節(jié)點傳輸至目的節(jié)點所需要的時間。實驗中,各業(yè)務(wù)的截止期限等于其周期,即Di=Ti。
3.2 業(yè)務(wù)數(shù)量的影響
將網(wǎng)絡(luò)中業(yè)務(wù)數(shù)量從10增加到50,各業(yè)務(wù)網(wǎng)絡(luò)利用率的范圍設(shè)為[0.001,0.01],圖5展示了不同數(shù)量業(yè)務(wù)對網(wǎng)絡(luò)可調(diào)度性的影響。實驗比較了RR-WS、Con-WCTS、SP-WS以及SP-WCTS 4種網(wǎng)絡(luò),其中SP-WS和SP-WCTS同時考慮了在3VC和6VC下的可調(diào)度性。由圖5可知:
(1) 隨著業(yè)務(wù)數(shù)量的增加,各網(wǎng)絡(luò)的可調(diào)度性下降。其原因是隨著業(yè)務(wù)數(shù)量的增加,網(wǎng)絡(luò)的負(fù)載增大,導(dǎo)致網(wǎng)絡(luò)延時增加,可調(diào)度性下降。
(2) 在相同的業(yè)務(wù)數(shù)量下,不同網(wǎng)絡(luò)的可調(diào)度性存在差異。 其中,6VC的SP-WCTS網(wǎng)絡(luò)可調(diào)度性最優(yōu),RR-WS最差。這是由于在RR-WS網(wǎng)絡(luò)中存在嚴(yán)重的排頭阻塞,當(dāng)某個報文在一個連接上被阻塞,則其上游的所有與之相關(guān)的報文都會被相應(yīng)阻塞,從而導(dǎo)致了嚴(yán)重的網(wǎng)絡(luò)延時。
(3) 在相同數(shù)目的VC下,SP-WCTS的可調(diào)度性明顯優(yōu)于SP-WS。其原因是,在SP-WCTS網(wǎng)絡(luò)中,同優(yōu)先級業(yè)務(wù)之間交錯傳輸,其阻塞時間要遠(yuǎn)遠(yuǎn)小于SP-WS網(wǎng)絡(luò)。此外,Con-WCTS網(wǎng)絡(luò)的可調(diào)度性介于6VC和3VC的SP-WCTS之間,其主要原因是當(dāng)虛擬通道較少時,同優(yōu)先級業(yè)務(wù)之間的阻塞比較大,而在Con-WCTS網(wǎng)絡(luò)中所有業(yè)務(wù)共享帶寬,沒有排頭阻塞,從而導(dǎo)致了VC數(shù)目較少時,SP-WCTS網(wǎng)絡(luò)的可調(diào)度性劣于Con-WCTS網(wǎng)絡(luò)。但是,由于SP-WCTS 采用了基于優(yōu)先級的仲裁邏輯,可以更好地滿足高優(yōu)先級業(yè)務(wù)的實時性要求,比Con-WCTS網(wǎng)絡(luò)更加適用于實時性應(yīng)用。
圖5 不同業(yè)務(wù)數(shù)量下的可調(diào)度性
3.3 虛擬通道數(shù)目的影響
本實驗研究了VC數(shù)目對SP-WCTS網(wǎng)絡(luò)和SP-WS網(wǎng)絡(luò)可調(diào)度性的影響。實驗網(wǎng)絡(luò)的業(yè)務(wù)數(shù)量為30,各業(yè)務(wù)的參數(shù)設(shè)置同3.2節(jié),VC數(shù)目從2增加到8,對不同虛擬通道數(shù)目下的網(wǎng)絡(luò)各進(jìn)行200組實驗。
圖6示出了兩種網(wǎng)絡(luò)在不同數(shù)目VC下的可調(diào)度性。可以看出,隨著VC數(shù)目的增加,SP-WS網(wǎng)絡(luò)中的可調(diào)度性增強,SP-WCTS網(wǎng)絡(luò)的可調(diào)度性先降低后增強,并在3VC時最低。造成這一現(xiàn)象的原因是,在SP-WCTS網(wǎng)絡(luò)中,隨著VC數(shù)目的增加,同優(yōu)先級業(yè)務(wù)之間的阻塞減少,而來自高優(yōu)先級業(yè)務(wù)的干擾增多。然而SP-WCTS網(wǎng)絡(luò)中的阻塞本質(zhì)來源于高優(yōu)先級業(yè)務(wù)的干擾,阻塞和干擾相互影響,導(dǎo)致了SP-WCTS網(wǎng)絡(luò)的可調(diào)度性隨著VC數(shù)目的增加,先降低后增加。
3.4 平均網(wǎng)絡(luò)利用率的影響
為了研究SP-WCTS網(wǎng)絡(luò)和SP-WS網(wǎng)絡(luò)的負(fù)載能力,本文在不同網(wǎng)絡(luò)利用率下對兩種網(wǎng)絡(luò)進(jìn)行了可調(diào)度性實驗。各組實驗的業(yè)務(wù)的網(wǎng)路利用率范圍分別為[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]。業(yè)務(wù)集合中的業(yè)務(wù)數(shù)量為30,其余參數(shù)設(shè)置同3.2節(jié),實驗結(jié)果如圖7所示。圖中橫坐標(biāo)為總網(wǎng)絡(luò)利用率,為所有業(yè)務(wù)的網(wǎng)絡(luò)利用率之和,采用如下計算公式:
(11)
其中:Umax和Umin分別為業(yè)務(wù)網(wǎng)絡(luò)利用率的上下限;Nflow為網(wǎng)絡(luò)中業(yè)務(wù)的數(shù)目。
圖6 不同虛擬通道數(shù)下的可調(diào)度性
圖7 不同總網(wǎng)絡(luò)利用率下的可調(diào)度性
由圖7可知,隨著總網(wǎng)絡(luò)利用率的增加,各網(wǎng)絡(luò)的可調(diào)度性降低,且SP-WS網(wǎng)絡(luò)的下降速度明顯快于SP-WCTS網(wǎng)絡(luò),表明SP-WCTS網(wǎng)絡(luò)相對于SP-WS網(wǎng)絡(luò)可承受更大的業(yè)務(wù)負(fù)載。在相同的網(wǎng)絡(luò)利用率下,SP-WCTS網(wǎng)絡(luò)的可調(diào)度性基本上優(yōu)于SP-WS網(wǎng)絡(luò)。在網(wǎng)絡(luò)利用率為0.4時,6VC的SP-WS網(wǎng)絡(luò)的可調(diào)度性高于3VC 的SP-WCTS網(wǎng)絡(luò),但隨著網(wǎng)路利用率的增加,前者的可調(diào)度性下降劇烈,在網(wǎng)絡(luò)利用率為0.5時,其可調(diào)度性已經(jīng)低于3VC的SP-WCTS網(wǎng)路。
蟲孔直通交換網(wǎng)絡(luò)實現(xiàn)了業(yè)務(wù)之間的交錯傳遞,解決了傳統(tǒng)蟲孔交換網(wǎng)絡(luò)的排頭阻塞問題,但其無法滿足較高的實時性要求。本文引入了虛擬通道技術(shù),在蟲孔直通交換網(wǎng)絡(luò)中使用了基于優(yōu)先級的仲裁機(jī)制,提出了共享優(yōu)先級蟲孔直通交換網(wǎng)絡(luò)結(jié)構(gòu),并給出了信息最壞網(wǎng)絡(luò)延時的計算方法,方便設(shè)計人員對網(wǎng)絡(luò)的實時性能進(jìn)行分析。
為了研究共享優(yōu)先級蟲孔直通交換網(wǎng)絡(luò)的實時性能,通過一系列實驗對比了Con-WCTS網(wǎng)絡(luò)、RR-WS網(wǎng)絡(luò)以及SP-WS網(wǎng)絡(luò)。由實驗結(jié)果可知,共享優(yōu)先級蟲孔直通網(wǎng)絡(luò)交換網(wǎng)絡(luò)有著良好的實時性能,可以承擔(dān)更大的網(wǎng)絡(luò)負(fù)載。在未來工作中,還可以對SP-WCTS網(wǎng)絡(luò)的資源和能源消耗進(jìn)行更加深入的研究。
[1]周君,王天成,李華偉,等.多核處理器片上網(wǎng)絡(luò)的驗證技術(shù)綜述[J].計算機(jī)科學(xué),2013,40(專刊):33-39.
[2]黃國睿,張平,魏廣博,等.多核處理器的關(guān)鍵技術(shù)及其發(fā)展趨勢[J].計算機(jī)工程與設(shè)計,2009,30(10) :2414-2418.
[3]李麗,許居衍.片上網(wǎng)絡(luò)技術(shù)發(fā)展現(xiàn)狀及趨勢淺析[J].電子產(chǎn)品世界,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]王崢,顧華璽,楊燁,等.片上網(wǎng)絡(luò)交換機(jī)制的研究[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]官錚,錢文華,杜長青,等.具有服務(wù)質(zhì)量保障的片上網(wǎng)絡(luò)路由仲裁控制[J].計算機(jī)科學(xué),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
上海市重點學(xué)科建設(shè)基金(B504)
吳陶迪(1992-),男,碩士生,研究方向為實時嵌入式系統(tǒng)。E-mail:taodi_wu@foxmail.com
孫自強,E-mail:sunziqiang@ecust.edu.cn
TP302
A