0 引言

　　隨著單芯片上集成的IP核數(shù)量不斷增加,，傳統(tǒng)總線的通信方式已經(jīng)不能滿足通信的需求,，在功耗、可靠性及延遲等方面都面臨著非常嚴(yán)峻的挑戰(zhàn)[1],。在這種情況下,，新型芯片體系架構(gòu)就成為亟待研究的方向。新型芯片體系架構(gòu)片上網(wǎng)絡(luò)（Network on Chip,，NoC）[2-3]就在這樣的背景下應(yīng)運而生,。通過借鑒計算機網(wǎng)絡(luò)技術(shù)，引入新的體系結(jié)構(gòu),，從根本上克服了片上系統(tǒng)（System on Chip,，SoC）總線架構(gòu)的種種弊端?？傮w說來,，影響NoC性能的因素主要包括網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、路由算法以及應(yīng)用映射等,。本文主要研究NoC的應(yīng)用映射問題,，以減少系統(tǒng)的能量及延時消耗，提高系統(tǒng)性能,。

　　目前,，很多文獻(xiàn)對NoC映射算法進(jìn)行了研究，例如，TOSUN S提出了一種映射優(yōu)化算法[4],，該算法將通信頻繁的任務(wù)映射到物理位置接近的網(wǎng)絡(luò)節(jié)點中,，以減少數(shù)據(jù)包傳輸?shù)木嚯x，但該算法容易陷入局部最優(yōu),，而難以得到最優(yōu)解,。陳亦鷗等人針對面向?qū)崟r復(fù)雜系統(tǒng)的片上網(wǎng)絡(luò)架構(gòu)及映射技術(shù)展開研究[5]，提出了面向?qū)崟r復(fù)雜系統(tǒng)的NoC多目標(biāo)映射模型,。文獻(xiàn)[6]采用了分支定界法實現(xiàn)NoC的映射,。文獻(xiàn)[7]提出一個均衡優(yōu)化時延模型和一種基于Boltzmann-NSGAⅡ的映射算法，時延模型從宏觀鏈路負(fù)載和單個節(jié)點排隊時延進(jìn)行優(yōu)化,，避免了傳統(tǒng)NSGAⅡ算法在解決NoC映射問題時容易出現(xiàn)局部最優(yōu)和種群多樣性的問題,。文獻(xiàn)[8]采用多目標(biāo)自適應(yīng)免疫算法對NoC映射問題進(jìn)行研究，旨在減少系統(tǒng)延時和能量消耗,。文獻(xiàn)[9]采用多目標(biāo)免疫算法作為NoC映射算法，有效降低了系統(tǒng)功耗,，提高了可靠性,。文獻(xiàn)[10]以互連任務(wù)之間的通信量作為映射順序優(yōu)先級的判定標(biāo)準(zhǔn)，提出一種啟發(fā)式算法,，通信量大的任務(wù)先被映射到NoC拓?fù)渲?，接著將與已映射任務(wù)之間有通信的任務(wù)按照通信量大小依次映射至網(wǎng)絡(luò)拓?fù)渲校钡綉?yīng)用程序中的所有任務(wù)都完成映射為止,。由于算法每一次迭代都考慮了已映射任務(wù)所有鄰節(jié)點的情況,，使得算法復(fù)雜度極高，達(dá)到了O（n5logn）,，n為任務(wù)數(shù)量,。

　　本文在文獻(xiàn)[10]的基礎(chǔ)上，提出一種基于通信鏈路的改進(jìn)映射算法（Improved Mapping Algorithms based on Communication Links,，IMACL）,，IMACL算法通過將通信量較大的任務(wù)映射到網(wǎng)絡(luò)跳數(shù)較近的NoC核上，達(dá)到減少系統(tǒng)能耗和延時的目的,。但與文獻(xiàn)[10]中的算法不同,，IMACL算法不采用逐個搜索的映射方式，而是通過改進(jìn)的多目標(biāo)遺傳算法完成映射,。實驗通過NoC仿真平臺NIRGAM進(jìn)行,，結(jié)果表明，該算法在能耗和延時方面具有較好的優(yōu)化效果,，并降低了算法復(fù)雜度,，提高了算法收斂速度。

1 映射問題分析

　　NoC映射的目的是在滿足約束條件（能量、延時最?。┑那闆r下,，將給定的任務(wù)分配到NoC處理核上。該過程中使用的一些名詞定義如下：

　　定義1：任務(wù)通信圖(Task Communication Graph,，TCG),，圖G(T，E)中,，ti∈T代表應(yīng)用中的任務(wù),，ei，j∈E代表任務(wù)ti與任務(wù)tj之間的通信量,。實際應(yīng)用VOPD對應(yīng)的任務(wù)圖如圖1所示,。

圖1  VOPD任務(wù)圖

　　定義2：拓?fù)鋱D(Topology Graph，TG),，圖T(P,，L)中，pi∈P代表網(wǎng)絡(luò)拓?fù)渲械奶幚砗?，li,，j∈L代表核pi與核pj之間的通信鏈路。一個4×4 Mesh結(jié)構(gòu)的拓?fù)淙鐖D2所示,。

圖2  4×4拓?fù)鋱D

　　在本文中,，優(yōu)化目標(biāo)為系統(tǒng)能耗和延時，采用TERRY T Y在文獻(xiàn)[11]中提出的能量建模方式：

　　其中,，Ebit表示相鄰路由器之間傳輸1 bit數(shù)據(jù)消耗的能量,，ESbit、EBbit,、EWbit和ELbit分別代表被處理核消耗的能量,、緩存消耗的能量、線路和數(shù)據(jù)在鏈路中傳輸消耗的能量,。網(wǎng)絡(luò)較大時,，EBbit和EWbit可以忽略，因此能耗模型可表示為：

　　其中,，代表從pi傳輸1 bit數(shù)據(jù)到pj的能量消耗,，ni，j表示從節(jié)點pi到節(jié)點pj的最短路徑的路由跳數(shù)(曼哈頓距離),。因此,，網(wǎng)絡(luò)總的能量消耗由式(3)計算：

　　其中，vi,，j表示節(jié)點pi與pj之間的通信量,。

　　延時(D)為系統(tǒng)關(guān)鍵路徑(從輸入到輸出的最長鏈路)延時,，其計算式為：

　　其中，di,，j和qi,，j分別表示從節(jié)點pi到節(jié)點pj的數(shù)據(jù)傳輸延時和等待延時。

　　映射過程中,，將能耗和延時作為兩個優(yōu)化目標(biāo),，即目標(biāo)函數(shù)為：

2 IMACL算法

　　IMACL算法將TCG中的任務(wù)映射到TG處理核上，算法實現(xiàn)過程中,，遵循任務(wù)與處理核一一對應(yīng)的原則,。IMACL算法的主要思想是將相互之間通信量大的任務(wù)映射至路由跳數(shù)少的處理核上，以此降低系統(tǒng)的通信能耗和延時,。算法以多目標(biāo)遺傳算法為原型,，但避免了傳統(tǒng)的多目標(biāo)遺傳算法存在的收斂速度慢、易陷入局部最優(yōu)等缺陷,， IMACL算法流程圖如圖3所示,。

圖3  IMACL算法流程圖

　　2.1 種群初始化

　　遺傳算法的基本單元為染色體，一條染色體代表一種映射方案,，傳統(tǒng)的遺傳算法初始種群都是隨機產(chǎn)生一個染色體組,，而初始種群的優(yōu)劣直接影響算法的收斂速度，隨機產(chǎn)生的初始種群可能導(dǎo)致算法收斂過慢,。因此,，IMACL算法初始種群中的染色體按照通信鏈路的通信量大小來產(chǎn)生,，描述如下：

　　(1)對TCG中的通信鏈路按照通信量進(jìn)行排序,，找到通信量最大的通信鏈路e=(ti，tj),，圖1中通信量最大的通信鏈路e=(t8,，t10)；

　　(2)分別計算任務(wù)ti和tj總的通信量,，即與任務(wù)節(jié)點相鄰的通信鏈路通信量的總和,，比較任務(wù)ti和tj的總通信量，較大的任務(wù)即為第一個將被映射的任務(wù),，圖1中通信總量較大的任務(wù)為t8,；

　　(3)產(chǎn)生一個1~M（處理核對應(yīng)的編號）之間的隨機數(shù)p1，將任務(wù)ti和tj中總通信量較大的任務(wù)（圖1中為t8）映射至該處理核,；

　　(4)接下來將最大通信量對應(yīng)鏈路(e=(t8,，t10))另一端的任務(wù)(圖1中為t10)映射至與p1相鄰的處理核p2上，p2為p1任意一個相鄰位置的處理核,；

　　(5)找出剩余任務(wù)與已映射任務(wù)之間通信量最大的任務(wù),，將該任務(wù)映射至與已經(jīng)映射的任務(wù)對應(yīng)的處理核任意一個相鄰的處理核上,；

　　(6)如果所有任務(wù)都映射完成，則得到了一條可用的染色體,，否則返回步驟(5),。設(shè)種群大小為N。

　　2.2 遺傳操作

　　傳統(tǒng)的多目標(biāo)遺傳算法產(chǎn)生子種群需要進(jìn)行選擇,、交叉和變異3個遺傳操作,，但I(xiàn)MACL算法僅僅通過選擇、變異來獲取子種群,。其中選擇操作目的是保持種群中的優(yōu)良基因,，而變異操作可以增加種群的多樣性，但同時也存在使種群產(chǎn)生退化的危險,，為了保持種群質(zhì)量和多樣性,，IMACL算法讓部分個體參與變異，減小種群退化的概率,，具體實現(xiàn)步驟如下：

　　(1)計算初始種群的目標(biāo)函數(shù),，對計算結(jié)果進(jìn)行非支配排序；

　　(2)將排在后50%的個體按變異概率pm（為了避免算法陷入局部最優(yōu),，變異概率相對傳統(tǒng)遺傳操作而言取值較大）進(jìn)行變異操作,。隨機產(chǎn)生一個變異位置，保持染色體變異位置之前的基因不變,，按2.1節(jié)中的方式找到下一個待映射的任務(wù)tnext,，將任務(wù)tnext映射至新產(chǎn)生的處理核上，直到所有任務(wù)映射完成為止,；

　　(3)將父種群與子種群合并,，計算新種群的目標(biāo)函數(shù)并進(jìn)行非支配排序，選擇出序值靠前的N條染色體作為新種群,，進(jìn)入下一代進(jìn)化,；

　　(4)判斷是否滿足終止條件，若滿足,，找出最優(yōu)解,，若不滿足，返回步驟(2),。

　　2.3 算法復(fù)雜度

　　IMACL算法的主要復(fù)雜度體現(xiàn)在初始種群產(chǎn)生,、目標(biāo)函數(shù)計算、選擇,、變異以及非支配排序上,。N表示種群大小，M表示染色體長度,，產(chǎn)生初始種群的復(fù)雜度為O(NM),，計算目標(biāo)函數(shù)的復(fù)雜度為O（NM2）,，選擇操作的復(fù)雜度為O（N/2），變異的復(fù)雜度為O（NM/2）,，非支配排序的復(fù)雜度為O（N2）,。所以，IMACL算法的總復(fù)雜度為上述各步驟復(fù)雜度累積和乘以迭代次數(shù),，遠(yuǎn)遠(yuǎn)小于O（M5logM）,，即算法復(fù)雜度低于文獻(xiàn)[10]中的算法。

3 實驗結(jié)果及分析

　　3.1 實驗結(jié)果

　　針對系統(tǒng)能耗和通信延時兩個目標(biāo)函數(shù),，在NIRGAM[12]上進(jìn)行IMACL算法的仿真實驗,。NIRGAM是一個離散獨立、周期精確的NoC仿真器,，它能為NoC中路由算法的設(shè)計和不同拓?fù)浣Y(jié)構(gòu)下的應(yīng)用提供大量的技術(shù)支持,。仿真針對DVOPD、VOPD,、MWD和MEPG-4 4種實際應(yīng)用程序進(jìn)行,，拓?fù)浣Y(jié)構(gòu)為常見的2D Mesh結(jié)構(gòu)，采用XY路由算法,。實驗中,，取種群大小N=60，變異概率pm=0.3,，最大進(jìn)化代數(shù)max_gen=200,，DVOPD的染色體長度(任務(wù)數(shù)量)M=32，VOPD的染色體長度M=16,，MEPG-4和MWD的染色體長度均為M=12,。

　　為了驗證IMACL算法的性能，每組實驗分別將該算法與傳統(tǒng)多目標(biāo)遺傳算法（MOGA）,、模擬退火算法（SA）得到的映射方案獲得的通信能耗和延時進(jìn)行對比,。4種算法實際應(yīng)用的通信能耗和延時結(jié)果如表1所示,，結(jié)果比較如圖4所示,。

(a)通信能耗實驗結(jié)果比較        (b)通信延時實驗結(jié)果比較

圖4  實際應(yīng)用3種算法的實驗結(jié)果比較

　　由表1和圖4可知，IMACL算法與MOGA和SA兩種算法相比,，通信能耗和延時優(yōu)化效果均十分明顯,。相較于MOGA，在DVOPD應(yīng)用中,，系統(tǒng)通信能耗減少了49.76%,，通信延時減少了53.23%；在VOPD應(yīng)用中,，系統(tǒng)通信能耗減少了29.54%,，通信延時減少了32.45%,；對于應(yīng)用MWD，系統(tǒng)通信能耗和延時分別減少了25.93%和28.38%,；在MPEG-4應(yīng)用中,，系統(tǒng)通信能耗減少了45.72%，通信延時減少了49.40%,。而與SA相比,，IMACL算法在DVOPD應(yīng)用中，系統(tǒng)通信能耗減少了45.93%,，通信延時減少了48.50%,；在VOPD應(yīng)用中，系統(tǒng)通信能耗減少了14.40%,，通信延時減少了16.22%,；對于應(yīng)用MWD，系統(tǒng)通信能耗和延時分別減少了4.76%和5.36%,；在MPEG-4應(yīng)用中,，系統(tǒng)通信能耗減少了43.43%，通信延時減少了44.36%,。

　　從實驗結(jié)果可以看出,，IMACL算法對于通信鏈路簡單（任務(wù)之間通信不頻繁）的應(yīng)用在能耗和延時兩方面只有較低的提高，但對于通信鏈路復(fù)雜（任務(wù)之間通信頻繁）的應(yīng)用則具有明顯的優(yōu)化效果,。

　　3.2 算法收斂性

　　IMACL算法與其他兩種算法相比,，在通信能耗和延時上均有很大優(yōu)化效果，圖5為MPEG-4通信能耗的收斂曲線,。MPEG-4延時,、DVOPD、VOPD以及MWD能耗和延時的收斂曲線與圖5相似,。

圖5  通信能耗收斂曲線

　　由圖5可知,，IMACL算法在迭代次數(shù)為100時便已進(jìn)入全局最優(yōu)，且優(yōu)化過程中不易陷入局部最優(yōu),；MOGA算法在迭代次數(shù)為50時就進(jìn)入了局部最優(yōu),，優(yōu)化過程中更是多次進(jìn)入局部最優(yōu)，而全局最優(yōu)則是在迭代次數(shù)為350代之后,。相比而言,，IMACL算法具有極好的收斂性。

4 結(jié)論

　　針對系統(tǒng)通信能耗和延時,，本文提出一種基于通信鏈路的改進(jìn)映射算法IMACL解決NoC映射優(yōu)化問題,。算法遵循通信量大的任務(wù)映射至物理位置接近的處理核上的原則，以減少任務(wù)相互之間通信消耗的能量和延時,，從而有效降低了NoC整個系統(tǒng)的能耗和延時,。通過NIRGAM平臺的實驗結(jié)果表明,，在實際應(yīng)用任務(wù)DVOPD中，本文提出的算法相較于傳統(tǒng)多目標(biāo)遺傳算法的映射優(yōu)化結(jié)果而言,，能耗降低了49.76%,，通信延時降低了53.23%。而對于通信鏈路較為簡單的VOPD應(yīng)用,，能耗僅有29.54%的降低,，通信延時降低了32.45%。在MWD應(yīng)用中,，系統(tǒng)通信能耗和延時則分別減少了25.93%和28.38%,。對于應(yīng)用MPEG-4來說，系統(tǒng)通信能耗和延時分別降低了45.72%和49.40%,。與SA相比,，IMACL算法在實際應(yīng)用程序中，能耗與延時性能也具有不同程度的提高,。另一方面,，IMACL算法降低算法復(fù)雜度的同時還具有良好的收斂性?？梢姳疚乃崴惴▽Ω纳芅oC映射算法整體性能有著積極意義,。

　　參考文獻(xiàn)

　　[1] MARCULESCU R，OGRAS U Y,，PEH L S,，et al.Outstanding research problems in NoC design：system，micro-architecture,，and circuit perspectives[J].IEEE Transactions on Computeraided Design of Integrated and Systems,，2009，28(1)：3-21.

　　[2] SALEHI M E,，MOHAMMADI S,，F(xiàn)AKHRAIE S M，et al.Energy/throughput trade-off in a fully asynchronous NoC for GALS-based MPSoC architectures[C].In Proc.5th International Conference on Design and Technology of Integrated Systems in Nanoscale Era(DTIS),，Hammamet,，Tunisia，2010：1-6.

　　[3] BOGDAN P,，MARCULESCU R.Non-stationary traffic analysis and its implications on multicore platform design[J].IEEETransactions on Computer-Aided Design of Integrated Circuits and Systems,，2011,，30(4)：508-519.

　　[4] TOSUN S.New heuristic algorithms for energy aware application mapping and routing on mesh-based NoCs[J].Journal of Systems Architecture,，2011，57(1)：69-78.

　　[5] 陳亦鷗.面向?qū)崟r復(fù)雜系統(tǒng)的片上網(wǎng)絡(luò)架構(gòu)及映射技術(shù)研究[D].成都：電子科技大學(xué),，2013.

　　[6] Zhou Liyang,，Jing Ming’e,，Zhong Liulin，et al.Taskbinding based branch-and-bound algorithm for NoCmapping[J].Circuits and Systems,，2012,，3(3)：648-651.

　　[7] 易宏波，羅興國.Boltzmann-NSGAⅡ算法的NoC映射研究[J].計算機工程,，2012,，38(22)：283-286.

　　[8] SEPU′LVEDA M J，WANG J C,，GOGNIAT G,，et al.A multi-objective adaptive immune algorithm for multiapplication NoC mapping[J].Analog Integr.Circ.& Sig.Process，2012,，73(3)：851-860.

　　[9] 呂興勝,，李光順，吳俊華.基于多目標(biāo)免疫算法的NoC映射優(yōu)化[J].計算機工程,，2015,，41(4)：316-321.

　　[10] SAHU P K，MANNA K,，SHAN T,，et al.A constructiveheuristic for application mapping onto mesh based Network-on-Chip[J].Journal of Circuits，Systems,，and Computers,，2015，24(8)：126-155.

　　[11] TERRY T Y,，LUCA B,，GIOVANNI D M.Analysis of power consumption on switch fabrics in network routers[C].In Proc.39th annual Design Automation Conference，New Orleans,，USA,，2002：524-529.

　　[12] Nirgam(V2.0)[EB/OL].(2013-12-20)[2016-03-08].http：//nirgam.ecs.soton.ac.uk.