劉蓓

(安徽工程大學(xué)現(xiàn)代教育技術(shù)中心, 安徽 蕪湖 241000)

基于MMAS的NoC低功耗映射

劉蓓

(安徽工程大學(xué)現(xiàn)代教育技術(shù)中心, 安徽 蕪湖 241000)

隨著芯片集成度的提高, 網(wǎng)絡(luò)通信流量與通信功耗也隨之遞增.片上網(wǎng)絡(luò)在設(shè)計(jì)階段就要考慮到通信功耗問題,因此提出一種可以降低通信功耗的映射方法, 該方法是一種改進(jìn)的最大最小蟻群算法, 通過優(yōu)化權(quán)重系數(shù)、狀態(tài)轉(zhuǎn)移規(guī)則以及信息素更新來提高算法的性能.實(shí)驗(yàn)表明, 該方法能加速搜索進(jìn)化過程, 避免搜索的停滯, 具有較好的收斂性,能有效的降低系統(tǒng)的映射功耗.

片上網(wǎng)絡(luò); 低功耗; 映射

1 引言

隨著半導(dǎo)體技術(shù)的發(fā)展, 人們開始研究將越來越多的晶體管集成在單一芯片上, 通過構(gòu)建多個(gè)IP核(處理器、存儲(chǔ)器、輸入輸出控制器等)來提高系統(tǒng)整體性能, 然而, 芯片性能的提高也使得設(shè)計(jì)復(fù)雜度不斷加大, 片上系統(tǒng)(System on Chip, SoC)的發(fā)展遇到了難以逾越的障礙.片上網(wǎng)絡(luò)(Network on Chip, NoC)的出現(xiàn)徹底解決了SoC所面臨的可擴(kuò)展性差、并行通信能力低、時(shí)鐘不同步等問題, 為芯片的設(shè)計(jì)提供了一種新的范例[1-4].

NoC設(shè)計(jì)包括平臺(tái)設(shè)計(jì)和映射技術(shù)兩方面內(nèi)容, 低功耗映射NoC系統(tǒng)是促進(jìn)NoC應(yīng)用發(fā)展的關(guān)鍵技術(shù)之一, 旨在將各個(gè)并行化子任務(wù)分配到各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)上, 使得系統(tǒng)通信成本或能耗最低.文獻(xiàn)[5]提出一種分枝定界算法, 將任務(wù)映射到NoC的IP核, 在滿足帶寬約束下, 最小化系統(tǒng)功耗, 但是這種方法的通信成本很高; 文獻(xiàn)[6]提出了一種啟發(fā)式隨機(jī)搜索算法, 通過構(gòu)造禁忌表來避免陷入循環(huán), 最終找到NoC低功耗映射方案, 但是該算法的收斂性效果不太理想.文獻(xiàn)[7]提出了一種NoC 低功耗映射遺傳算法, 該算法的復(fù)雜度較高, 全局搜索能力低.本文提出一種改進(jìn)的最大最小蟻群算法(Max Min Ant Colony Optimization Algorithm, MMAS), 通過優(yōu)化權(quán)重系數(shù)、狀態(tài)轉(zhuǎn)移規(guī)則以及信息素更新來提高算法的性能.實(shí)驗(yàn)表明, 該方法能加速搜索進(jìn)化過程, 避免搜索的停滯, 具有較好的收斂性, 能有效的降低系統(tǒng)的映射功耗.

2 NoC映射

2.1 映射過程

NoC映射就是在給定通信任務(wù)圖上, 把處理單元P通過映射函數(shù)分配到NoC結(jié)構(gòu)特征圖資源節(jié)點(diǎn)IP核上的過程[8], 如圖1所示.任務(wù)特征圖中有4個(gè)處理單元, 連接各處理單元之間有向邊上的權(quán)值為通信量, 通過映射函數(shù)構(gòu)建NoC的結(jié)構(gòu)特征圖, 在NoC結(jié)構(gòu)特征圖中各IP核之間通過路由器R進(jìn)行通信.不同的映射函數(shù)會(huì)產(chǎn)生不同的映射結(jié)果, 而映射結(jié)果對(duì)于系統(tǒng)的硬件代價(jià)、性能以及芯片功耗[9]等都有不同的影響, 因此要根據(jù)具體需求定義映射函數(shù).

2.2 映射函數(shù)

定義2： 給定NoC結(jié)構(gòu)特征圖NAV(V, P), 頂點(diǎn)為圖中的一個(gè)資源節(jié)點(diǎn), 通信路徑為節(jié)點(diǎn)到節(jié)點(diǎn)的通信路徑, 邊上的權(quán)值是節(jié)點(diǎn)到節(jié)點(diǎn)的通信流量.

文獻(xiàn)[10]定義了NoC通信功耗模型, 每bit通信數(shù)據(jù)從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj通信功耗為：

綜上所述, 確定低功耗映射模型的關(guān)鍵在于找到合適的映射算法, 映射算法的優(yōu)劣直接影響到系統(tǒng)的通信流量.本文從低功耗映射算法入手, 通過對(duì)映射算法的優(yōu)化計(jì)算出映射時(shí)最小通信流量, 從而降低NoC的映射功耗.

3 基于MMAS優(yōu)化的映射算法

蟻群算法是一種在圖中尋找優(yōu)化路徑的幾率型算法, 通過螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為演變而來.當(dāng)一只螞蟻找到食物后, 會(huì)采用向周邊環(huán)境釋放信息素的方式來吸引其他螞蟻過來, 經(jīng)過一段時(shí)間后, 會(huì)有越來越多的螞蟻找到食物.但總有些螞蟻會(huì)重新尋找新的路徑, 開辟新的道路, 如果新開辟的道路比之前找到食物的路徑更短, 那么螞蟻就會(huì)被漸漸吸引到新路上來, 一段時(shí)間之后可能會(huì)出現(xiàn)一條最短路徑.

本文提出的低功耗NoC映射問題采用最大最小蟻群算法(MMAS)實(shí)現(xiàn), 為了統(tǒng)計(jì)數(shù)據(jù)的可靠性, 采用MPEG4[11]真實(shí)用例作為模型.算法為了抑制搜索路徑過早陷入局部最優(yōu)解, 使用輪盤機(jī)制, 并對(duì)環(huán)境信息素設(shè)臵了上下限.整個(gè)算法的主要步驟如下：

3.1 初始化

將M只螞蟻分別隨機(jī)放在N個(gè)節(jié)點(diǎn)上, 初始時(shí)刻各條路徑上的信息素為τ設(shè)臵為一常數(shù)1, 其他參數(shù)詳見表1.

表1 初始化參數(shù)分配Table1 Initialization Parameter

3.2 狀態(tài)轉(zhuǎn)移規(guī)則

螞蟻k根據(jù)信息素和啟發(fā)式信息, 采用輪盤機(jī)制在第i個(gè)IP核節(jié)點(diǎn)選擇第j個(gè)IP核的規(guī)則為式(6)所示：

Pijk (t)代表節(jié)點(diǎn)i的第k個(gè)螞蟻選擇下個(gè)節(jié)點(diǎn)j的概率,(t)是節(jié)點(diǎn)i和j之間的信息素值,是殘留信息的重要程度,是啟發(fā)式因子的重要程度,表示螞蟻k可選擇的資源節(jié)點(diǎn),用于記錄螞蟻k已經(jīng)分配過的IP核, {1,2,…, n}表示所有可映射的n個(gè)節(jié)點(diǎn)的全集.

輪盤選擇算法是根據(jù)適應(yīng)度的大小進(jìn)入下一代的概率, 可以避免貪婪方式選擇造成的映射解陷入局部最優(yōu),算法流程圖見圖2所示：

通過輪盤選擇算法, 螞蟻雖然選擇概率值大的路徑可能性大, 但是也有一定的可能性往概率小的路徑走,這樣就可以使螞蟻探索新的路徑, 避免算法停滯或者陷入局部最優(yōu)解.

3.3 信息素更新

隨著進(jìn)化的不斷推進(jìn), 以前留下的信息素會(huì)逐漸消失, 在所有螞蟻完成一次循環(huán)后要更新信息素.每次循環(huán)之后, 只有最優(yōu)的螞蟻進(jìn)行信息素更新.最優(yōu)解可以是迭代最優(yōu)解, 也可以是全局最優(yōu)解, 還可以是兩者的混合策略, 本文中采用全局最優(yōu)解更新信息素, 更新公式如下, 其中是最優(yōu)螞蟻?zhàn)哌^的路徑長(zhǎng)度

圖2 輪盤選擇算法Fig.2 Roulette Algorithm

為了防止某條路徑上的信息素出現(xiàn)過大或過小導(dǎo)致的搜索停滯狀況發(fā)生, 本方案采用將每個(gè)解元素的信息素濃度限制在內(nèi), 一旦超過上限或者低于下限時(shí), 就采用強(qiáng)制手段對(duì)其調(diào)整, 以提高算法的有效性.為螞蟻一次搜索找到最優(yōu)解的概率, 本文中設(shè)臵為0.05[12].

本算法采用了信息素平滑策略, 當(dāng)算法的迭代次數(shù)較多的時(shí)候, 算法容易陷入停滯狀態(tài), 式(11)可以重新設(shè)臵環(huán)境信息素：

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

為了證明本文提出的算法可以有效的降低通信功耗, 本文在Microsoft Visual C++ 6.0環(huán)境下完成一系列實(shí)驗(yàn).

4.1 MPEG4解碼器任務(wù)圖

考慮到實(shí)際應(yīng)用, 本文提出的驗(yàn)證方案為采用任務(wù)規(guī)模為12的MPEG4真實(shí)用例, 將MPEG4解碼器任務(wù)劃分成12個(gè)子任務(wù), 并將其劃分到12個(gè)IP核上, 通信狀況如圖3所示.考慮到實(shí)驗(yàn)具有隨機(jī)性, 本文將實(shí)驗(yàn)重復(fù)20次, 迭代次數(shù)設(shè)臵為1000,

圖3 MPEG4解碼器各IP核間通信圖Fig.3 Communications between IP cores on MPEG4 Decoder

4.2 本方案實(shí)驗(yàn)結(jié)果

本方案由于采用了輪盤選擇算法, 避免陷入局部最優(yōu), 隨著迭代次數(shù)的增加每次實(shí)驗(yàn)后得到的映射功耗都是逐步收斂的, 并最終趨于一個(gè)穩(wěn)定的結(jié)果.

圖4是本方案和文獻(xiàn)[13]所提方案實(shí)驗(yàn)20次的結(jié)果, 相比文獻(xiàn)[13], 雖然兩種方案都具有一定的隨機(jī)性, 但是本方案在實(shí)驗(yàn)中得到的映射功耗變化幅度更小, 全局搜索能力更強(qiáng), 算法整體穩(wěn)定性更好.此外, 從圖中可以看出, 本方案能調(diào)整解的生成方式, 通過設(shè)臵信息素濃度的范圍以及調(diào)整信息素平滑策略, 能更快搜索到最優(yōu)解, 有效降低映射功耗, 相比文獻(xiàn)[13]提出的模擬退火映射算法SASA相比, 映射功耗至少低了5.1%.

圖4 本方案與SASA算法性能比較Fig.4 Energy consumption comparisons

5 小結(jié)

NoC的出現(xiàn)為越來越多IP核集成在單顆芯片上提供了有效的解決方案.為了降低通信功耗, 在NoC映射設(shè)計(jì)階段需要采用特定的映射算法來實(shí)現(xiàn)通信任務(wù)圖與NoC結(jié)構(gòu)圖的匹配.因此低映射功耗已成為NoC設(shè)計(jì)的關(guān)鍵技術(shù)之一.本文通過分析NoC的通信功耗與通信流量, 得到它們之間的數(shù)學(xué)關(guān)系模型, 利用最大最小蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新策略來優(yōu)化映射函數(shù), 并在算法實(shí)現(xiàn)階段引入輪盤選擇算法避免映射結(jié)果陷入局部最優(yōu)等一系列方案來降低映射過程的通信量.實(shí)驗(yàn)通過MPEG4真實(shí)用例進(jìn)行驗(yàn)證, 結(jié)果表明本文提出的方法具有智能搜索、全局優(yōu)化、穩(wěn)健性強(qiáng)等優(yōu)點(diǎn), 可以有效降低NoC的通信功耗, 確保片上系統(tǒng)的服務(wù)質(zhì)量, 為即將步入應(yīng)用的NoC平臺(tái)設(shè)計(jì)提供了有益的參考.

[1]LUCA BENINI, GIOVANNI DE MICHELI.Network on chips: A new SoC paradigm[J].IEEE Computer, 2002, 35(1): 70-78.

[2]AXEL JANTSCH, HANNU TENHUNENTORS.Networks on Chip[M].Kluwer Academic Publishers, 2003, 38: 3-18.

[3]WILLIAM J, DALLY, BRIAN, TOWLEs.Route Packets, Not Wires: On-Chip Inter-connection Networks[C].DAC Proceedings, Las Vegas, Nevada, USA: IEEE, 2001.684-689

[4]SHASHI, KUMAR.A network on chip architecture and design methodology[C].VLSI Proceedings, IEEE Computer Society Annual Symposium, Pittsburgh, PA, USA: IEEE, 2002.

[5]HU J, MARCULESCU R.Energy-Aware Mapping for Tile-Based NoC Architectures Under Performance Constraints[C].DAC Proceedings, Anaheim, CA, USA: IEEE, 2003.

[6]CHANG ZHENGWEI, XIE XIAONA, SANG NAN, et al.An Improved Tabu Search Algorithm for Network-on—Chip Mapping[J].Journal of Computer-Aided Design and Computer Graphics, 2008, 20(2): 155-160.

[7]孫榕, 林正浩.基于遺傳算法的NoC處理單元映射研究[J].計(jì)算機(jī)科學(xué), 2008, 35(4): 51-54

[8]BJERREGARD T, MAHADEVAN S.A Survey of Research and Practice of Network on Chip[J].ACM, 2006, 38(1):1-51.

[9]HU JINGCAO.Design Methodologies for Application Specific Network-on-Chip[C].Proceedings of IEEE Computer Society Annual Symposium, Washington, DC, USA,2002.

[10] LEI T, KUMAR S.A two-step genetic algorithm for mapping task graphs to a network on chip architecture[C].Proceedings of the Euromicro Symposium on Digital System Design, Belek-Antalya, Turkey , 2003.

[11] ZHOU H, TIE L, LI J, et al.Improved proxy multi-signature scheme[J].Journal of Shanghai JiaoTong University, 2004, 38(1): 83-86.

[12] 吳春明, 陳治, 姜明.蟻群算法中系統(tǒng)初始化及系統(tǒng)參數(shù)的研究[J].電子學(xué)報(bào), 2006, 34(8): 1530-1534.

[13] 車晶, 張瑛.基于自適應(yīng)模擬退火的NoC映射算法[J].計(jì)算機(jī)工程與應(yīng)用, 2012, 48(23): 58-62.

Mapping method with low power for NoC based on MMAS

LIU Bei
(Modern Education Technology Center, Anhui Polytechnic University, Wuhu 241000, P.R.C.)

Traffic and power of communication on chips has been increasing with the improvement of chip integration.The power consumption must be considered in the stage of design.The new mapping algorithm is proposed on how to reduce the communication power on NoC.The improved max-min ant system method can get a better performance by updating the pheromone, optimizing the weight coefficients and the state transition rules.Experimental results showed that the proposed algorithm could reduce the power consumption of the system with the compared method and had a good convergence which could accelerate the search process and avoid the stagnation.

network on chip; low power; mapping algorithm

TN47;TP18

A

1003-4271(2014)06-0889-06

10.3969/j.issn.1003-4271.2014.06.16

2014-09-23

劉蓓(1980-), 女, 漢族, 安徽蕪湖人, 助理工程師, 碩士.

安徽省教育廳教研基金資助項(xiàng)目(2012jyxm280、2012jyxm870); 高校省級(jí)自然科學(xué)研究基金資助項(xiàng)目(KJ2012B022); 安徽工程大學(xué)青年科研基金資助項(xiàng)目(2013YQ32)