戴啟華,劉勤讓,沈劍良,孫淼,吳鳳陽

(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,450002,鄭州)

?

采用集簇方法的片上網(wǎng)絡(luò)動(dòng)態(tài)映射算法

戴啟華,劉勤讓,沈劍良,孫淼,吳鳳陽

(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心,450002,鄭州)

針對(duì)片上網(wǎng)絡(luò)(NoC)傳統(tǒng)一一對(duì)應(yīng)映射關(guān)系造成的資源節(jié)點(diǎn)利用率不高和通信功耗大等缺陷進(jìn)行了改進(jìn),提出了一種采用集簇方法的NoC動(dòng)態(tài)映射算法(DMA)。首先利用分枝界定算法完成通信量大且相連任務(wù)節(jié)點(diǎn)的集簇,減小了任務(wù)圖通信總量;然后在此基礎(chǔ)上借助自適應(yīng)粒子群算法完成最優(yōu)映射結(jié)果的獲取;最后利用動(dòng)態(tài)遷移策略對(duì)最優(yōu)映射結(jié)果中單獨(dú)占用資源節(jié)點(diǎn)的任務(wù)節(jié)點(diǎn)進(jìn)行集簇。仿真實(shí)驗(yàn)表明,與隨機(jī)映射、動(dòng)態(tài)螺旋映射算法和最優(yōu)鄰居算法相比,DMA算法的通信功耗分別下降了73.93%、46.37%和14.55%,NoC面積占用率分別下降了50%、50%和33.3%。

片上網(wǎng)絡(luò);動(dòng)態(tài)映射;粒子群算法;動(dòng)態(tài)遷移;集簇

隨著晶體管尺寸的不斷縮小,單個(gè)芯片上集成的元器件數(shù)量越來越多[1-3]?；诳偩€架構(gòu)的片上系統(tǒng)(System-on-Chip,SoC)受制于時(shí)鐘頻率和有限的地址空間,芯片性能提升代價(jià)很大[4-5]。片上網(wǎng)絡(luò)(Network-on-Chip,NoC)的出現(xiàn)極大地緩解了SoC的困境,有效地支持了IP核之間高效可靠、高吞吐量、低功耗的通信[6]。

合理有效的映射算法能夠使系統(tǒng)整體性能得到提升,降低NoC運(yùn)行中的代價(jià)成本,如功耗、面積需求等等。如何在給定設(shè)計(jì)約束的基礎(chǔ)上,將已知通信關(guān)系的任務(wù)節(jié)點(diǎn)分配到特征結(jié)構(gòu)圖(architecture characteristic graph,ARCG)中合適的資源節(jié)點(diǎn)上,并且使目標(biāo)函數(shù)最小化,已成為NoC領(lǐng)域需要解決的首要問題。NoC映射過程分為靜態(tài)映射和動(dòng)態(tài)映射[7]:靜態(tài)映射要求在給定任務(wù)圖、拓?fù)浣Y(jié)構(gòu)和帶寬等約束條件下,任務(wù)節(jié)點(diǎn)到資源節(jié)點(diǎn)映射過程中所有的通信特征(如資源節(jié)點(diǎn)之間數(shù)據(jù)傳輸延遲,通信量等)不會(huì)變,所有的映射結(jié)果不會(huì)改變,也不能進(jìn)行遷移;動(dòng)態(tài)映射指的是任務(wù)節(jié)點(diǎn)與ARCG上資源節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系可以隨著通信需求或者ARCG資源占用情況進(jìn)行改變。然而,NoC任務(wù)映射是一個(gè)NP問題。為了更有效地利用資源節(jié)點(diǎn),很多學(xué)者對(duì)NoC動(dòng)態(tài)映射都給予了關(guān)注。針對(duì)任務(wù)節(jié)點(diǎn)之間的通信量不同,文獻(xiàn)[8]采用DSMA將通信量最大的任務(wù)節(jié)點(diǎn)分配至NoC映射平臺(tái)中間節(jié)點(diǎn),以螺旋形的順序依次分配其余任務(wù)節(jié)點(diǎn)直至完成映射。文獻(xiàn)[9-10]采用最優(yōu)鄰居(NN)策略將具有高通信量的任務(wù)節(jié)點(diǎn)映射到同一個(gè)或者相近的資源節(jié)點(diǎn)上,以此減小任務(wù)節(jié)點(diǎn)之間的跳變數(shù),減小運(yùn)行功耗。文獻(xiàn)[11-12]結(jié)合NoC運(yùn)行過程中任務(wù)節(jié)點(diǎn)之間的通信請(qǐng)求和資源節(jié)點(diǎn)之間的鏈路負(fù)載來進(jìn)行動(dòng)態(tài)映射。上述算法均存在評(píng)價(jià)函數(shù)單一的缺陷,動(dòng)態(tài)映射結(jié)果在功耗、面積和鏈路負(fù)載上仍有可繼續(xù)優(yōu)化的空間。

本文針對(duì)NoC上傳統(tǒng)一一對(duì)應(yīng)映射關(guān)系造成的資源節(jié)點(diǎn)利用率不高和任務(wù)圖通信功耗大等缺陷進(jìn)行了改進(jìn),提出了一種基于集簇的NoC動(dòng)態(tài)映射算法——DMA。在任務(wù)圖映射過程中,利用分枝界定算法將通信量大的父子節(jié)點(diǎn)劃分到一個(gè)簇中,減小了任務(wù)圖通信總量;利用自適應(yīng)粒子群算法獲取局部集簇后任務(wù)圖的最優(yōu)映射結(jié)果;獲取最優(yōu)映射結(jié)果中單獨(dú)占用一個(gè)資源節(jié)點(diǎn)的任務(wù)節(jié)點(diǎn)集合S和優(yōu)先遷移集合S內(nèi)通信量大的任務(wù)節(jié)點(diǎn),利用評(píng)價(jià)函數(shù)判斷遷移是否成功。實(shí)驗(yàn)表明:與隨機(jī)映射、最優(yōu)鄰居和動(dòng)態(tài)螺旋映射(DSMA)算法相比,本文所提算法可以有效地減小通信功耗和NoC映射平臺(tái)面積需求,提高資源節(jié)點(diǎn)利用率。

1 問題定義和模型描述

1.1 問題定義

本文主要研究NoC局部集簇動(dòng)態(tài)映射策略。在介紹問題定義和模型描述之前,提出2個(gè)假設(shè)并作出說明。

假設(shè)1 資源節(jié)點(diǎn)最多能夠運(yùn)行2個(gè)任務(wù)節(jié)點(diǎn)。

假設(shè)2 物理鏈路帶寬遠(yuǎn)遠(yuǎn)超過任務(wù)節(jié)點(diǎn)之間的通信需求。

本文采用資源節(jié)點(diǎn)為異構(gòu)體的NoC映射平臺(tái),根據(jù)文獻(xiàn)[9]可知資源節(jié)點(diǎn)在系統(tǒng)約束下可以運(yùn)行多個(gè)任務(wù)節(jié)點(diǎn)。本文中將每個(gè)資源節(jié)點(diǎn)的任務(wù)節(jié)點(diǎn)最高承載量設(shè)置為2,既保證簇的映射可能性,又保證簇的集合不會(huì)太大,超過資源節(jié)點(diǎn)的處理能力。

物理鏈路帶寬不足引起的鏈路競(jìng)爭(zhēng)會(huì)影響最后的功耗計(jì)算,而鏈路擁塞造成的功耗損失沒有確切的數(shù)學(xué)模型,無法獲取其較為準(zhǔn)確的功耗值。為減小客觀因素對(duì)映射結(jié)果造成的影響,設(shè)定物理鏈路帶寬遠(yuǎn)超任意任務(wù)節(jié)點(diǎn)之間的通信帶寬,滿足簇與簇之間的通信需求。

在上文2個(gè)假設(shè)下,給出如下定義。

定義1 任務(wù)圖(task graph,TG)是一個(gè)非循環(huán)有向圖GTG(n,w),頂點(diǎn)ni∈N表示一個(gè)任務(wù)節(jié)點(diǎn),有向弧wi,j∈W表示任務(wù)節(jié)點(diǎn)i、j之間的通信量。以實(shí)際通信任務(wù)圖MPEG-4為例,其TG如圖1所示,任務(wù)節(jié)點(diǎn)之間連線上的數(shù)字即為wi,j。

圖1 MPEG-4任務(wù)圖

定義2 NoC映射平臺(tái)可以看成是一個(gè)特征結(jié)構(gòu)圖GARCG(p,h),由資源節(jié)點(diǎn)、路由節(jié)點(diǎn)、網(wǎng)絡(luò)接口和資源節(jié)點(diǎn)的物理鏈路組成。其中頂點(diǎn)pi∈P表示NoC規(guī)則映射平臺(tái)上的一個(gè)資源節(jié)點(diǎn),有向弧hpi,pj為節(jié)點(diǎn)pi、pj間的物理鏈路,其值為資源節(jié)點(diǎn)pi、pj之間的曼哈頓距離。NoC是一個(gè)參數(shù)化,二維網(wǎng)格結(jié)構(gòu)的模型,假設(shè)其處于一個(gè)xy坐標(biāo)軸中,1號(hào)路由節(jié)點(diǎn)處于坐標(biāo)原點(diǎn),則hpi,pj大小為|xi-xj|+|yi-yj|。資源節(jié)點(diǎn)編號(hào)自下往上、從左往右均依次增大,如圖2所示。

定義3 TG映射結(jié)果用1個(gè)一維數(shù)組表示,數(shù)組元素值為對(duì)應(yīng)任務(wù)節(jié)點(diǎn)占用的資源節(jié)點(diǎn)編號(hào)。任務(wù)圖的映射結(jié)果如圖3所示,1號(hào)任務(wù)節(jié)點(diǎn)占用9號(hào)資源節(jié)點(diǎn),2號(hào)任務(wù)節(jié)點(diǎn)占用5號(hào)資源節(jié)點(diǎn)。任務(wù)圖通信矩陣為C,大小為N×N,如式(1)所示。

圖2 NoC 4×4特征結(jié)構(gòu)圖

(a)任務(wù)圖 (b)映射結(jié)果圖3 任務(wù)圖及映射結(jié)果

(1)

1.2 模型描述

(1)功耗模型。由文獻(xiàn)[13-14]可知,單位比特?cái)?shù)據(jù)從資源節(jié)點(diǎn)pi傳輸?shù)絧j所消耗的能量為

(2)

式中:ES為單位比特?cái)?shù)據(jù)在路由結(jié)構(gòu)所消耗的能量;EL為單位比特?cái)?shù)據(jù)在物理鏈路上傳輸所消耗的能量。TG任務(wù)節(jié)點(diǎn)數(shù)為M,映射結(jié)果所消耗的總能量為

(3)

式中:Wni,nj為任務(wù)節(jié)點(diǎn)ni到nj之間的通信量;pi、pj分別是任務(wù)節(jié)點(diǎn)ni、nj在ARCG上的映射資源節(jié)點(diǎn)。

(2)鏈路負(fù)載模型。鏈路負(fù)載是ARCG物理鏈路承載的通信量,合理的鏈路負(fù)載可以有效提高鏈路帶寬的利用率,減小數(shù)據(jù)傳輸中因鏈路競(jìng)爭(zhēng)所產(chǎn)生的擁塞概率,故將鏈路負(fù)載方差作為評(píng)價(jià)映射結(jié)果好壞的一個(gè)指標(biāo),其計(jì)算公式為

(4)

(3)面積模型。相同任務(wù)圖在更小面積的NoC映射平臺(tái)上成功運(yùn)行,表明該映射平臺(tái)上資源節(jié)點(diǎn)利用率更高。任務(wù)圖的面積模型可以用已映射資源節(jié)點(diǎn)的多少進(jìn)行表征,故將映射結(jié)果資源節(jié)點(diǎn)需求量作為衡量映射結(jié)果優(yōu)劣的一個(gè)指標(biāo),其計(jì)算公式為

(5)

式中:NR為已映射資源節(jié)點(diǎn)數(shù);NT為單個(gè)任務(wù)節(jié)點(diǎn)映射對(duì)應(yīng)的資源節(jié)點(diǎn)數(shù);NC為任務(wù)節(jié)點(diǎn)簇映射對(duì)應(yīng)的資源節(jié)點(diǎn)數(shù)。

2 算法描述

2.1 局部集簇

在任務(wù)圖與NoC映射平臺(tái)產(chǎn)生映射關(guān)系之前,首先對(duì)任務(wù)圖進(jìn)行預(yù)處理,采用分枝界定算法,按照任務(wù)節(jié)點(diǎn)之間的通信量關(guān)系和連接關(guān)系將各任務(wù)節(jié)點(diǎn)劃分到各層上,具體流程如下。

步驟1 計(jì)算TG各任務(wù)節(jié)點(diǎn)通信量,找到通信量最大的任務(wù)節(jié)點(diǎn)A作為根(父)節(jié)點(diǎn)。

步驟2 選擇與上層父節(jié)點(diǎn)相連的任務(wù)節(jié)點(diǎn)作為子節(jié)點(diǎn),子節(jié)點(diǎn)可能與多個(gè)父節(jié)點(diǎn)相連,選擇與其相連且通信量最大的上層節(jié)點(diǎn)作為父節(jié)點(diǎn)。如任務(wù)節(jié)點(diǎn)7同時(shí)和父節(jié)點(diǎn)10和11相連,由于C10,7>C11,7,故選擇任務(wù)節(jié)點(diǎn)10作為節(jié)點(diǎn)7的父節(jié)點(diǎn)。

步驟3 重復(fù)步驟2,直至所有任務(wù)節(jié)點(diǎn)都劃分完畢。

根據(jù)上文假設(shè)可得,每個(gè)資源節(jié)點(diǎn)可運(yùn)行2個(gè)任務(wù)節(jié)點(diǎn)。為提高資源節(jié)點(diǎn)利用率,需要對(duì)部分任務(wù)節(jié)點(diǎn)進(jìn)行局部集簇。從根節(jié)點(diǎn)向下尋找任務(wù)節(jié)點(diǎn),由于每個(gè)節(jié)點(diǎn)都可能連接多個(gè)任務(wù)節(jié)點(diǎn),需要找出每一層中具有最大通信量的父節(jié)點(diǎn)和子節(jié)點(diǎn),將兩者劃分到一個(gè)簇中。如圖4b所示,節(jié)點(diǎn)5是多個(gè)分枝的父節(jié)點(diǎn),對(duì)比多個(gè)與其相連子節(jié)點(diǎn)的通信量,節(jié)點(diǎn)5和節(jié)點(diǎn)10的通信量最大,故將兩者劃分到一個(gè)簇中。第1層根節(jié)點(diǎn)已經(jīng)集簇,以第2層任務(wù)節(jié)點(diǎn)為父節(jié)點(diǎn),尋找通信量最大的父子節(jié)點(diǎn)劃分到一個(gè)簇中,直到第2層所有任務(wù)節(jié)點(diǎn)都遍尋完畢。依次類推,直至找到最后一層,局部集簇結(jié)果如圖4b虛線框所示。集簇造成任務(wù)節(jié)點(diǎn)數(shù)量及連接關(guān)系改變,通信矩陣C也相應(yīng)改變?yōu)?/p>

C=

(6)

(a)任務(wù)圖 (b)集簇結(jié)果圖4 分枝界定流程圖

2.2 映射結(jié)果獲取

利用自適應(yīng)粒子群算法獲取預(yù)處理任務(wù)圖在NoC映射平臺(tái)上的最優(yōu)映射結(jié)果。粒子群算法(particle swarm optimization,PSO)是一種群體智能的優(yōu)化算法,最早由Kennedy和Eberhart在1995年提出[15],快速的收斂速度和簡(jiǎn)單易實(shí)現(xiàn)的特點(diǎn)使其迅速成為解決NoC映射問題的一個(gè)重要方法。標(biāo)準(zhǔn)粒子群算法無法隨著解空間的縮小進(jìn)而動(dòng)態(tài)調(diào)整收斂速度,易陷入早熟陷阱。本文構(gòu)建了一種自適應(yīng)粒子群算法,根據(jù)迭代次數(shù)的增加動(dòng)態(tài)調(diào)整粒子速度的慣性權(quán)重值,消除了尋優(yōu)過程中粒子速度慣性分量的不良影響,減少了算法的迭代次數(shù)。

自適應(yīng)粒子群算法利用粒子自身歷史最優(yōu)位置zi和群體最優(yōu)位置gi來更新下一代粒子的速度和位置。用t表示算法的迭代次數(shù),粒子根據(jù)下式完成速度和位置的更新

(7)

(8)

(9)

式中:c1、c2為非負(fù)常數(shù),稱為加速度因子;r1、r2是分布在[0,1]之間的隨機(jī)數(shù);ω為慣性權(quán)重,表示當(dāng)前粒子繼承先前粒子速度的能力;ωs為初始慣性權(quán)重;ωe為迭代次數(shù)最大時(shí)的慣性權(quán)重;Tm為最大迭代次數(shù)。ω隨著迭代次數(shù)變化而變化,算法前期ω較大,維持算法較好的全局搜索能力;算法中期,ω變化較快,粒子迅速靠近最優(yōu)解區(qū)域;算法后期,ω較小且變化緩慢,極大的提高了算法的局部尋優(yōu)能力,從而取得了很好的求解效果。算法主要包括以下步驟。

步驟1 相關(guān)參數(shù)設(shè)置,粒子速度和位置初始化,并且計(jì)算粒子適應(yīng)值。

步驟2 根據(jù)式(7)(8)更新粒子速度和位置,并計(jì)算適應(yīng)值。

步驟3 對(duì)比新粒子適應(yīng)值,更新z和g。在連續(xù)50次算法迭代中,z未更改,則最優(yōu)解已尋到并顯示結(jié)果,否則轉(zhuǎn)步驟2。算法最大迭代次數(shù)為200。

預(yù)處理任務(wù)圖映射結(jié)果如圖5所示。

圖5 預(yù)處理任務(wù)圖映射結(jié)果

2.3 映射遷移

步驟1 找到自適應(yīng)粒子群算法最優(yōu)映射結(jié)果中一一對(duì)應(yīng)映射的任務(wù)節(jié)點(diǎn)集合S。

步驟2 在S中找到通信量最大的任務(wù)節(jié)點(diǎn),依次遷移到集合S中剩余的任務(wù)節(jié)點(diǎn)映射資源節(jié)點(diǎn)上。

步驟3 若遷移過后的R小于等于遷移之前的R,遷移成立。同一個(gè)任務(wù)節(jié)點(diǎn)若有多個(gè)遷移成立,選取R最小的作為本次遷移路徑。遷移成功,S集合減去集簇成功的2個(gè)任務(wù)節(jié)點(diǎn);遷移失敗,S集合減去該任務(wù)節(jié)點(diǎn)。重復(fù)步驟2、步驟3,直至遷移結(jié)束。

遷移結(jié)果如圖6所示,任務(wù)節(jié)點(diǎn)8、1、2進(jìn)行了映射遷移,任務(wù)節(jié)點(diǎn)811、13、29分別映射到一個(gè)資源節(jié)點(diǎn)上。自適應(yīng)粒子群算法映射結(jié)果占用9個(gè)資源節(jié)點(diǎn),遷移過后的映射結(jié)果占用6個(gè)資源節(jié)點(diǎn),大大減小了資源節(jié)點(diǎn)需求量,既減小了映射結(jié)果對(duì)于NoC映射平臺(tái)的面積需求,同時(shí)也提高了資源節(jié)點(diǎn)的利用率。

圖6 任務(wù)節(jié)點(diǎn)遷移

利用自適應(yīng)粒子群算法獲取MPEG-4原任務(wù)圖和局部集簇后任務(wù)圖映射結(jié)果,并與動(dòng)態(tài)遷移結(jié)果進(jìn)行對(duì)比,如表1所示?？梢钥吹?動(dòng)態(tài)遷移操作相對(duì)于原任務(wù)圖和局部集簇后映射結(jié)果在通信量、資源節(jié)點(diǎn)需求量和跳變數(shù)方面都有不同程度的減小。

表1 自適應(yīng)粒子群算法對(duì)3種任務(wù)圖映射結(jié)果對(duì)比

3 實(shí)驗(yàn)與分析

為了驗(yàn)證上文中的結(jié)論,本文的映射算法程序源代碼用C++編寫,在Linux環(huán)境下進(jìn)行編譯和仿真。為體現(xiàn)算法的實(shí)用性,將實(shí)際任務(wù)通信圖MPEG-4作為測(cè)試樣本,實(shí)驗(yàn)基于4×4NoC系統(tǒng)級(jí)模型展開,其特性如1.1節(jié)所述,同時(shí)借助1.2節(jié)所提模型獲取映射結(jié)果相關(guān)測(cè)試參數(shù)。由于采用啟發(fā)式智能算法,實(shí)驗(yàn)結(jié)果不可避免地有一定的隨機(jī)性,以下數(shù)據(jù)均為3次實(shí)驗(yàn)結(jié)果的平均值。

圖7為自適應(yīng)粒子群算法迭代過程中慣性權(quán)重ω的變化過程?？梢悦黠@地看到,在算法的起始階段ω較大,確保了算法前期較強(qiáng)的全局搜索能力,收斂速度快,求解精度低;在算法的過渡階段,慣性權(quán)重ω隨著迭代次數(shù)的增加,逐漸減小,表明粒子向全局最優(yōu)區(qū)域靠近,空間距離越近,ω越小;在算法后期,慣性權(quán)重值ω減小,速度變緩,在0.2～0.3趨于一個(gè)較小的穩(wěn)定值。此時(shí)算法全局搜索能力弱,收斂速度變慢,局部搜索能力強(qiáng),利于算法跳出局部最優(yōu)而求得全局最優(yōu)。圖8為自適應(yīng)粒子群算法映射結(jié)果適應(yīng)度變化過程,以功耗值為適應(yīng)度,適應(yīng)度越小,映射結(jié)果越好?？梢钥吹?自適應(yīng)粒子群算法映射結(jié)果適應(yīng)度值收斂速度快,下降趨勢(shì)明顯,在較小的迭代次數(shù)里就能找到最優(yōu)映射,算法性能較好。圖9是自適應(yīng)粒子群算法運(yùn)算過程中遷移評(píng)價(jià)函數(shù)R的變化過程。對(duì)比圖8和圖9可以發(fā)現(xiàn),適應(yīng)度和R變化保持一致,R越小映射結(jié)果越好,任務(wù)節(jié)點(diǎn)在NoC映射平臺(tái)上布局越合理,這也證明了R作為任務(wù)節(jié)點(diǎn)遷移評(píng)價(jià)函數(shù)的有效性。

圖7 自適應(yīng)粒子群算法慣性權(quán)重ω的變化過程

圖8 自適應(yīng)粒子群算法映射結(jié)果適應(yīng)度的變化過程

圖9 遷移評(píng)價(jià)函數(shù)R的變化過程

定義θ為各算法映射結(jié)果占隨機(jī)映射結(jié)果比例。圖10為上述4種算法在功耗值、映射面積和鏈路負(fù)載方差的仿真結(jié)果,其中DSMA、NN算法的映射結(jié)果是根據(jù)原文獻(xiàn)算法的描述,在同一實(shí)驗(yàn)環(huán)境下自行建模獲取的。

圖10 4種算法仿真結(jié)果對(duì)比

(1)功耗代價(jià)。NN和DMA算法在映射策略中允許通信量大且連接的任務(wù)節(jié)點(diǎn)能夠集簇并映射到同一個(gè)資源節(jié)點(diǎn)上。在NoC映射平臺(tái)上運(yùn)行的時(shí)候,同一個(gè)簇內(nèi)的任務(wù)節(jié)點(diǎn)通信不需要通過交換開關(guān)和資源節(jié)點(diǎn)之間物理鏈路,大大減小了任務(wù)運(yùn)行時(shí)消耗的功耗,故功耗下降優(yōu)勢(shì)比較明顯。DMA算法相對(duì)于NN算法,更深層次地考慮了無通信關(guān)系任務(wù)節(jié)點(diǎn)之間的集簇可能,構(gòu)建R評(píng)價(jià)函數(shù),擴(kuò)大了任務(wù)節(jié)點(diǎn)集簇范圍,且自適應(yīng)粒子群算法尋優(yōu)效果較好,進(jìn)一步減小了通信功耗。相對(duì)于隨機(jī)映射、DSMA和NN映射算法,本文DMA算法映射后通信功耗下降了73.93%、46.37%和14.55%,本文DMA算法在功耗代價(jià)上優(yōu)勢(shì)明顯。

(2)面積代價(jià)。DSMA采用一一對(duì)應(yīng)的映射關(guān)系,相同的任務(wù)圖運(yùn)行比NN、DMA算法需要更多的資源節(jié)點(diǎn)。集簇策略使得單個(gè)資源節(jié)點(diǎn)利用率提高,減小了資源節(jié)點(diǎn)的需求量。相對(duì)于Random、DSMA和NN映射算法,DMA算法映射后資源節(jié)點(diǎn)需求量減少了50%、50%和33.3%。

(3)鏈路負(fù)載方差。DSMA、NN和DMA算法鏈路負(fù)載方差明顯小于隨機(jī)映射,其中NN鏈路負(fù)載方差最小。NN映射策略減小了通信量大且相連的任務(wù)節(jié)點(diǎn)對(duì)物理鏈路的需求量,集簇的任務(wù)節(jié)點(diǎn)不需要物理鏈路為載體來傳遞數(shù)據(jù)信息,直接在資源節(jié)點(diǎn)中進(jìn)行了交互和處理。DMA算法利用R評(píng)價(jià)函數(shù)將無連接關(guān)系的任務(wù)節(jié)點(diǎn)映射到同一個(gè)資源節(jié)點(diǎn)上,增大了某條物理鏈路上通信負(fù)載。相對(duì)于集簇之前的鏈路負(fù)載方差,集簇之后鏈路負(fù)載方差可能會(huì)增大或減小。DMA與NN算法相比,MPEG-4鏈路負(fù)載方差提升了6.93%。由上文假設(shè)可知,物理鏈路帶寬滿足簇與簇之間的通信需求,物理鏈路負(fù)載的增加不會(huì)造成物理鏈路競(jìng)爭(zhēng)堵塞。

4 結(jié) 論

針對(duì)現(xiàn)存映射算法大都是基于一一對(duì)應(yīng)的靜態(tài)映射,無法根據(jù)資源節(jié)點(diǎn)利用情況而對(duì)映射關(guān)系進(jìn)行動(dòng)態(tài)的調(diào)整,本文提出了一種基于集簇的NoC動(dòng)態(tài)映射算法——DMA,完成了任務(wù)圖與NoC映射平臺(tái)資源節(jié)點(diǎn)新型映射關(guān)系的設(shè)計(jì),減小了NoC映射面積需求和通信功耗輸出,優(yōu)化了硬件資源配置。本文算法利用分枝界定算法完成通信量大且相連任務(wù)節(jié)點(diǎn)的集簇,接著利用自適應(yīng)粒子群算法完成最優(yōu)映射結(jié)果的獲取,最后利用動(dòng)態(tài)遷移策略完成最優(yōu)映射結(jié)果中單獨(dú)占用資源節(jié)點(diǎn)的任務(wù)節(jié)點(diǎn)的集簇。與隨機(jī)映射、DSMA和NN算法相比,DMA算法雖然在鏈路負(fù)載方差考量上稍有欠缺,但是在功耗和NoC面積占用率上都有較大的提升。綜合考慮來看,DMA算法的優(yōu)化優(yōu)勢(shì)明顯,為NoC映射高性能實(shí)現(xiàn)提供了新的數(shù)學(xué)模型和努力方向。

[1] BENINI L, MICHELI G D. Networks on chips: a new SoC paradigm [J]. IEEE Transactions on Computer, 2002, 35(1): 70-78.

[2] KUMAR S, JANTSCH A, SOININEN J P, et al. A network on chip architecture and design methodology [C]∥Proceedings of IEEE Computer Society Annual Symposium on VLSI. Los Alamitos, CA, USA: IEEE Computer Society, 2002: 117-124.

[3] BJERREGAARD T, MAHADEVAN S. A survey of research and practices of network-on-chip [J]. ACM Computing Surveys, 2006, 38(1): 1-51.

[4] 楊盛光, 李麗, 高明倫, 等. 面向能耗和延時(shí)的NoC映射方法 [J]. 電子學(xué)報(bào), 2008, 36(5): 937-942. YANG Shengguang, LI Li, GAO Minglun, et al. An energy- and delay-aware mapping method of NoC [J]. Acta Electronica Sinica, 2008, 36(5): 937-942.

[5] 白海. 片上網(wǎng)絡(luò)映射算法研究和設(shè)計(jì) [D]. 成都: 電子科技大學(xué), 2009.

[6] MAQSOOD T, ALI S, MALIK S U R, et al. Dynamic task mapping for network-on-chip based systems [J]. Journal of Systems Architecture, 2015, 61(7): 293-306.

[7] 楊鵬飛, 王泉. 片上網(wǎng)絡(luò)異構(gòu)多核系統(tǒng)任務(wù)調(diào)度與映射 [J]. 西安交通大學(xué)學(xué)報(bào), 2015, 49(6): 72-76. YANG Pengfei, WANG Quan. An effective scheduling and mapping algorithm of tasks for heterogeneous NoC based MPSoC [J]. Journal of Xi’an Jiaotong University, 2015, 49(6): 72-76.

[8] MEHRAN A, KHADEMZADEH A, SAEIDI S. DSM: a heuristic dynamic spiral mapping algorithm for network on chip [J]. IEICE Electronics Express, 2008, 5(13): 464-471.

[9] CARVALHO E, CALAZANS N, MORAES F. Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs [C]∥Proceedings of 18th IEEE/IFIP International Workshop on Rapid System Prototyping. Piscataway, NJ, SUA: IEEE, 2007: 34-40.

[10]SINGH A K, SRIKANTHAN T, KUMAR A, et al. Communication-aware heuristics for run-time task mapping on NoC-based MPSoC platforms [J]. Journal of Systems Architecture, 2010, 56(7): 242-255.

[11]FALAHATI H, KOOHI S, HESSABI S. Application-based dynamic reconfiguration in optical network-on-chip [J]. Computers & Electrical Engineering, 2015, 45: 417-429.

[12]CARVALHO E, CALAZANS N, MORAES F. Dynamic task mapping for MPSoCs [J]. IEEE Design and Test of Computers, 2010, 27(5): 26-35.

[13]YE T T, MICHELI G D, BENINI L. Analysis of power consumption on switch fabrics in network routers [C]∥Proceedings of the 39th Annual Design Automation Conference. Piscataway, NJ, USA: IEEE, 2002: 524-529.

[14]HU J, MARCULESCU R. Energy- and performance-aware mapping for regular NoC architectures [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(4): 551-562.

[15]BETHART R, KENNEDY J. A new optimizer using particle swarm theory [C]∥Proceeding of the 6th International Symposium on Micro Machine and Human Science. Piscataway, NJ, USA: IEEE, 1995: 39-43.

[本刊相關(guān)文獻(xiàn)鏈接]

馬亞燕,王保云.采用博弈論的認(rèn)知無線網(wǎng)絡(luò)主用戶和不可信任次用戶的協(xié)作策略.2016,50(2):61-67.[doi:10.7652/xjtuxb201602011]

楊鵬飛,王泉.片上網(wǎng)絡(luò)異構(gòu)多核系統(tǒng)任務(wù)調(diào)度與映射.2015,49(6):72-76.[doi:10.7652/xjtuxb201506012]

任向隆,安建峰,高德遠(yuǎn),等.低功耗片上網(wǎng)絡(luò)映射的遺傳及螞蟻融合算法.2012,46(8):65-70.[doi:10.7652/xjtuxb 201208012]

唐軼軒,吳俊敏,陳國(guó)良,等.并行片上網(wǎng)絡(luò)仿真器ParaNSim的設(shè)計(jì)及性能分析.2012,46(2):24-30.[doi:10.7652/xjtuxb201202005]

張瑤,張鴻,李梁,等.時(shí)鐘數(shù)據(jù)恢復(fù)電路中的線性相位插值器.2016,50(2):48-54.[doi:10.7652/xjtuxb201602009]

張尚偉,曾平,羅雪梅,等.具有細(xì)節(jié)補(bǔ)償和色彩恢復(fù)的多尺度Retinex色調(diào)映射算法.2012,46(4):32-37.[doi:10.7652/xjtuxb201204006]

魏倩,蔡遠(yuǎn)利.一種基于神經(jīng)網(wǎng)絡(luò)的中制導(dǎo)改進(jìn)算法.2016,50(7):125-130.[doi:10.7652/xjtuxb201607019]

姜濤,黃偉,王安麟.多路閥閥芯節(jié)流槽拓?fù)浣Y(jié)構(gòu)組合的神經(jīng)網(wǎng)絡(luò)模型.2016,50(6):36-41.[doi:10.7652/xjtuxb201606 006]

孫立遠(yuǎn),周亞東,管曉宏.利用信息傳播特性的中文網(wǎng)絡(luò)新詞發(fā)現(xiàn)方法.2015,49(12):59-64.[doi:10.7652/xjtuxb201512 010]

王安麟,孟慶華,曹巖,等.液力變矩器的葉片數(shù)神經(jīng)網(wǎng)絡(luò)模型.2015,49(7):11-16.[doi:10.7652/xjtuxb201507003]

王麗霞,曲樺,趙季紅,等.軟件定義網(wǎng)絡(luò)中應(yīng)用二值粒子群優(yōu)化的控制器部署策略.2015,49(6):67-71.[doi:10.7652/xjtuxb201506011]

吳杰,馮祖仁,劉恒,等.水下目標(biāo)多元聲傳感陣列網(wǎng)絡(luò)定位方法.2015,49(4):40-45.[doi:10.7652/xjtuxb201504007]

孟憲佳,馬建峰,王一川,等.面向社交網(wǎng)絡(luò)中多背景的信任評(píng)估模型.2015,49(4):73-77.[doi:10.7652/xjtuxb201504 012]

董恩清,劉偉,宋洋.采用三角形節(jié)點(diǎn)塊處理無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法2015,49(4):84-90.[doi:10.7652/xjtuxb201504014]

李季碧,鄧科,任智,等.機(jī)會(huì)網(wǎng)絡(luò)中高效低時(shí)延多擺渡節(jié)點(diǎn)路由算法.2015,49(4):91-97.[doi:10.7652/xjtuxb201504 015]

李劉強(qiáng),桂小林,安健,等.采用模糊層次聚類的社會(huì)網(wǎng)絡(luò)重疊社區(qū)檢測(cè)算法.2015,49(2):6-13.[doi:10.7652/xjtuxb 201502002]

李季碧,李賓,任智,等.自適應(yīng)動(dòng)態(tài)功率控制的機(jī)會(huì)網(wǎng)絡(luò)節(jié)能高效路由算法.2014,48(12):49-56.[doi:10.7652/xjtuxb 201412008]

(編輯 劉楊)

A Dynamic Mapping Algorithm for Network-on-Chip Based on Cluster

DAI Qihua,LIU Qinrang,SHEN Jianliang,SUN Miao,WU Fengyang

(China National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002, China)

A dynamic mapping algorithm (DMA) for network-on-chip (NoC) based on cluster is proposed to solve the problems that the traditional one-to-one mapping relationship causes low utilization ratio of resource nodes and high communication power. Firstly, connected task nodes with high traffic load are clustered using a branch-and-bound approach to reduce the total communication volume of task graphs. Then an adaptive particle swarm algorithm is used to obtain the optimal mapping results. Finally, the dynamic migration strategy is used to cluster the task nodes that occupy an individual resource node in the optimal mapping results. Experimental results and comparisons with the random mapping, the dynamic spiral mapping algorithm (DSMA) and the nearest neighbor (NN) algorithm show that the proposed algorithm respectively reduces the communication power of the task graph by about 73.93%, 46.37% and 14.55%, and the occupancy rate of the NoC area by about 50%, 50% and 33.3%.

network-on-chip; dynamic mapping; particle swarm algorithm; dynamic migration; cluster

10.7652/xjtuxb201608009

2015-12-18。 作者簡(jiǎn)介:戴啟華(1990—),男,碩士生;劉勤讓(通信作者),男,研究員。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61572520)。

時(shí)間:2016-05-17

http:∥www.cnki.net/kcms/detail/61.1069.T.20160517.1725.004.html

TN409

A

0253-987X(2016)08-0052-07