基于維序路由算法的自適應(yīng)算法

談俊燕 華迪

（1.常州市工學(xué)院電氣信息工程學(xué)院 江蘇省常州市 213032 2.常州市信息技術(shù)學(xué)院電子工程學(xué)院 江蘇省常州市 213000）

科技的發(fā)展使得單個(gè)芯片能夠集成更多的IP 核，但是IP 核數(shù)量的逐漸增加使得片上系統(tǒng)（System On Chip, SoC）難以滿足設(shè)計(jì)需求。而片上網(wǎng)絡(luò)（Network On Chip, NoC）能使系統(tǒng)更好地適應(yīng)復(fù)雜多核SoC 設(shè)計(jì)中使用的全局異步局部同步的時(shí)鐘機(jī)制，優(yōu)化網(wǎng)絡(luò)的性能。因此NoC 憑借其可升級(jí)性和易擴(kuò)展性，逐漸成為了一種熱門的新興通訊結(jié)構(gòu)。

維序算法是一種經(jīng)典的3D 片上網(wǎng)絡(luò)的確定性路由算法，它的路由路徑僅由源節(jié)點(diǎn)和目的節(jié)點(diǎn)的地址決定，該算法根據(jù)偏移量來(lái)決定在哪個(gè)維度上進(jìn)行數(shù)據(jù)傳送，當(dāng)數(shù)據(jù)包在一個(gè)維度內(nèi)傳送完成后不會(huì)再次在該維度內(nèi)傳送，因此維序路由可以有效的防止死鎖的產(chǎn)生。但是由于其算法的路由路徑是固定的，不能根據(jù)路徑中各節(jié)點(diǎn)情況進(jìn)行路徑調(diào)整和自適應(yīng)，容易產(chǎn)生節(jié)點(diǎn)阻塞而降低效率。因此本研究提出了一種改進(jìn)的自適應(yīng)算法，當(dāng)數(shù)據(jù)在傳送過(guò)程中遇到阻塞時(shí)，算法會(huì)判斷當(dāng)前情況，并且改變數(shù)據(jù)的傳送路徑，從而避開(kāi)阻塞的數(shù)據(jù)傳送通道，而在其他空閑通道完成數(shù)據(jù)傳送，由此顯著降低等待通信通道恢復(fù)通暢狀態(tài)所額外增加的延遲和時(shí)間，極大地提高運(yùn)行的效率。

1 數(shù)據(jù)傳輸狀態(tài)對(duì)比

數(shù)據(jù)的傳輸通道可分為阻塞狀態(tài)和正常狀態(tài)。為了得到兩種狀態(tài)下數(shù)據(jù)傳輸通道的特點(diǎn)，可將分別處于阻塞狀態(tài)和正常狀態(tài)的數(shù)據(jù)傳輸通道節(jié)點(diǎn)100 和節(jié)點(diǎn)000 的SwitchContorl 模塊中的所有變量進(jìn)行仿真對(duì)比，得到圖1 所示的仿真波形圖。可以看出當(dāng)數(shù)據(jù)傳輸通道正常時(shí)，節(jié)點(diǎn)100 的SwitchContorl 模塊中auxfree 變量的0端口在數(shù)據(jù)傳送時(shí)變?yōu)榈碗娖?，而?7 個(gè)時(shí)鐘周期后又恢復(fù)到高電平；當(dāng)數(shù)據(jù)傳送通道阻塞時(shí)，節(jié)點(diǎn) 100 的 SwitchContorl 模塊中auxfree 變量的 0 端口在數(shù)據(jù)傳送時(shí)變?yōu)榈碗娖剑笫冀K保持該狀態(tài)不變。

分析數(shù)據(jù)傳輸過(guò)程中通道節(jié)點(diǎn)的活動(dòng)后可以發(fā)現(xiàn)，在數(shù)據(jù)傳送時(shí)，節(jié)點(diǎn)100 由于阻塞而無(wú)法接收到來(lái)自節(jié)點(diǎn) 200 的發(fā)送請(qǐng)求信號(hào)的應(yīng)答信號(hào)，因此其一直處于請(qǐng)求狀態(tài)，即auxfree 的0 端口長(zhǎng)期處于低電平狀態(tài)而無(wú)法恢復(fù)。

2 自適應(yīng)算法原理

由數(shù)據(jù)傳輸通道阻塞時(shí)的特點(diǎn)可得知，阻塞節(jié)點(diǎn)SwitchContorl模塊中的auxfree 變量的0 端口低電平持續(xù)脈沖數(shù)大于27 個(gè)周期。因此本算法通過(guò)統(tǒng)計(jì)當(dāng)前節(jié)點(diǎn)SwitchContorl 模塊中auxfree 變量的0 端口低電平持續(xù)的脈沖數(shù)以判定該節(jié)點(diǎn)是否出現(xiàn)阻塞情況。

2.1 算法步驟

算法的流程如圖2 所示，具體分為以下四個(gè)步驟：

（1）設(shè)定閾值為 30 個(gè)時(shí)鐘周期脈沖，以此作為目標(biāo)節(jié)點(diǎn)auxfree 變量0 端口低電平脈沖數(shù)的比較標(biāo)準(zhǔn)值。

圖1：兩種節(jié)點(diǎn)SwitchContorl 模塊中auxfree 變量的0 端口信號(hào)量仿真波形圖

圖2：算法工作流程圖

圖3：維序路由算法的路由路徑

圖4：自適應(yīng)算法的路由路徑

（2）統(tǒng)計(jì)數(shù)據(jù)傳送時(shí)auxfree 變量0 端口低電平持續(xù)的脈沖數(shù)。

（3）當(dāng)0 端口低電平持續(xù)時(shí)鐘周期脈沖數(shù)小于閾值時(shí)，繼續(xù)該數(shù)據(jù)傳輸x 方向的維序路由算法；當(dāng)脈沖數(shù)達(dá)到設(shè)定閾值時(shí)，即當(dāng)前x 方向中存在阻塞，算法就將數(shù)據(jù)傳送方向轉(zhuǎn)換為 y 方向并且繼續(xù)對(duì)auxfree 變量進(jìn)行判斷。

圖5：總延遲曲線

圖6：總時(shí)間曲線

（4）若y 方向的0 端口低電平持續(xù)時(shí)間小于設(shè)定的閾值，則將數(shù)據(jù)轉(zhuǎn)發(fā)到 y 方向的節(jié)點(diǎn)并繼續(xù)維序路由算法，若低電平持續(xù)時(shí)間達(dá)到 30 個(gè)時(shí)鐘周期，則繼續(xù)將數(shù)據(jù)傳送方向轉(zhuǎn)換為z 方向。

2.2 自適應(yīng)算法與維序路由算法路由路徑的比較

實(shí)驗(yàn)將數(shù)據(jù)從源節(jié)點(diǎn)000 傳送到節(jié)點(diǎn)222，并且把節(jié)點(diǎn)100 與節(jié)點(diǎn)200 之間的數(shù)據(jù)傳輸通道手動(dòng)阻塞，對(duì)維序路由算法和基于維序路由的自適應(yīng)算法進(jìn)行路由路徑的比較，如圖3 和圖4 所示。

3 實(shí)驗(yàn)結(jié)果分析

在實(shí)驗(yàn)測(cè)試中選擇節(jié)點(diǎn) 222 為源節(jié)點(diǎn)，節(jié)點(diǎn) 001 和000 分別為目的節(jié)點(diǎn)，并且阻塞了節(jié)點(diǎn)022 和112。要傳輸?shù)臄?shù)據(jù)包采取單一注入速率的方式，且每次進(jìn)行測(cè)試時(shí)使用不同種的注入速率。為了與維序路由算法對(duì)比，實(shí)驗(yàn)增加了一組維序路由算法的測(cè)試作為對(duì)照，選擇節(jié)點(diǎn) 000 為源節(jié)點(diǎn)，節(jié)點(diǎn) 221 和222 分別為目的節(jié)點(diǎn)，并且將節(jié)點(diǎn) 000 和節(jié)點(diǎn) 100 之間的數(shù)據(jù)傳送通道阻塞 450 個(gè)時(shí)鐘周期。最后將測(cè)試結(jié)果制成折線圖，分析自適應(yīng)算法的性能，如圖5、圖6 所示。

對(duì)圖5 總延遲曲線進(jìn)行分析，發(fā)現(xiàn)注入速率小于40%時(shí)，維序路由算法在阻塞狀態(tài)下的總延遲明顯大于本設(shè)計(jì)實(shí)現(xiàn)的自適應(yīng)路由算法；而注入速率超過(guò) 40%后自適應(yīng)路由算法圖線消失，表示數(shù)據(jù)傳送錯(cuò)誤，經(jīng)分析后發(fā)現(xiàn)是由于自適應(yīng)算法在數(shù)據(jù)傳輸時(shí)需要對(duì)傳輸通道狀態(tài)進(jìn)行一次或者兩次算法判斷，此時(shí)數(shù)據(jù)應(yīng)處于等待狀態(tài)。隨著傳送速度的不斷加快但是判斷速度始終不變，當(dāng)注入速率超過(guò)某一速度時(shí)就導(dǎo)致了數(shù)據(jù)的錯(cuò)誤傳送，因此本設(shè)計(jì)中所實(shí)現(xiàn)的自適應(yīng)算法僅適用于注入速率不高于 40%的情況。

對(duì)圖6 總時(shí)間曲線進(jìn)行分析，發(fā)現(xiàn)注入速率小于40%時(shí)，數(shù)據(jù)傳送完成所需時(shí)間隨注入速率的增大而減少，當(dāng)注入速率為 30%時(shí)，數(shù)據(jù)傳輸所需總時(shí)間趨近于飽和。當(dāng)注入速率為小于10%時(shí)，自適應(yīng)算法完成一次數(shù)據(jù)傳送所需時(shí)間大于維序路由算法中存在阻塞時(shí)完成一次數(shù)據(jù)傳送所需時(shí)間。因此，本設(shè)計(jì)中所實(shí)現(xiàn)的自適應(yīng)算法在注入速率高于10%時(shí)才能具有優(yōu)于維序算法的性能。

4 總結(jié)

綜合上面的測(cè)試結(jié)果和分析，可以看出本設(shè)計(jì)所提出并實(shí)現(xiàn)的基于維序路由算法的自適應(yīng)算法在數(shù)據(jù)包注入速率不小于10%且不大于40%的情況下，能夠解決維序路由算法在片上數(shù)據(jù)傳輸通道阻塞的問(wèn)題，證明了本設(shè)計(jì)路由算法的優(yōu)越性和有效性。