基于改進(jìn)量子遺傳算法的片上網(wǎng)絡(luò)多目標(biāo)映射技術(shù)

張保崗 韓國棟 湯先拓

(信息工程大學(xué) 河南 鄭州 450002)

0 引 言

片上系統(tǒng)(System on Chip，SoC)隨著超大規(guī)模集成電路的快速發(fā)展也在不斷改進(jìn)，內(nèi)部總線結(jié)構(gòu)的通信系統(tǒng)早已經(jīng)不能滿足需要，片上網(wǎng)絡(luò)[2](Network on Chip，NoC)逐漸成為SoC內(nèi)部通信系統(tǒng)的主流設(shè)計(jì)[1]。隨著單位芯片上處理單元(Processing elements，PE)集成數(shù)量越來越多，在快速高效低時(shí)延和穩(wěn)定性上對NoC的要求也越來越高，能耗、低時(shí)延和穩(wěn)定性也逐漸成為限制芯片發(fā)展的重要因素。NoC發(fā)展迅速，極大地推進(jìn)了芯片的發(fā)展，其能耗和時(shí)延是SoC研究設(shè)計(jì)最重要的指標(biāo)。片上網(wǎng)絡(luò)映射作為NoC設(shè)計(jì)的重要一維，其低功耗和低時(shí)延的優(yōu)化設(shè)計(jì)實(shí)現(xiàn)影響著整個(gè)片上網(wǎng)絡(luò)性能表現(xiàn)[3]。

如何在系統(tǒng)條件約束下，在現(xiàn)有NoC拓?fù)浣Y(jié)構(gòu)和路由的基礎(chǔ)上，將任務(wù)節(jié)點(diǎn)按照一定規(guī)則有效地映射到片上網(wǎng)絡(luò)各個(gè)處理單元上，盡可能減少總的信息交互功耗并在較低的時(shí)延內(nèi)實(shí)現(xiàn)是NoC技術(shù)研究的一個(gè)熱點(diǎn)。隨著芯片PE數(shù)量的增加，需要處理的應(yīng)用越來越多也越復(fù)雜，傳統(tǒng)的遍歷比較窮舉求最優(yōu)解的方法早已經(jīng)不適合，目前智能啟發(fā)式算法在該領(lǐng)域逐步展現(xiàn)其優(yōu)越性和實(shí)用性，也是近年來NoC映射技術(shù)研究的熱點(diǎn)。

1 相關(guān)工作

基于啟發(fā)式算法的NoC映射技術(shù)有很多，在低功耗和多目標(biāo)方面的相關(guān)研究成果也有很多，如文獻(xiàn)[4]提出一種基于混合量子遺傳算法的新型片上低功耗映射方法，結(jié)合自適應(yīng)旋轉(zhuǎn)角度調(diào)整策略，量子比特交叉變異操作和群體突變思想，并在每次迭代中選擇具有一定概率的初始解，以防止算法停滯。文獻(xiàn)[5]利用任務(wù)節(jié)點(diǎn)通信量大小劃分優(yōu)先級，得到若干較優(yōu)初始解集；利用離散粒子群算法的快速搜索能力迅速靠近最優(yōu)解；利用遺傳操作中的選擇和變異防止算法掉入局部較優(yōu)解陷阱，以較少的迭代次數(shù)完成最優(yōu)解的尋找。文獻(xiàn)[6]結(jié)合了禁忌搜索，主要優(yōu)化離散粒子群，用禁忌列表防止群粒子重復(fù)搜索，使得NoC的總體通信延遲和能耗最小化。文獻(xiàn)[7]提出一種優(yōu)化快速最近鄰啟發(fā)算法ONMAP，最小化NoC通信消耗并可以映射實(shí)時(shí)嵌入式應(yīng)用程序，某種程度上實(shí)現(xiàn)了動態(tài)映射效果。文獻(xiàn)[8]提出了一種新的基于遺傳的超啟發(fā)式算法作為核心算法，由于該算法可以在映射過程中自動選擇合適的算子，因此可以顯著提高收斂速度并表現(xiàn)出優(yōu)異的穩(wěn)定性，用于共同優(yōu)化片上網(wǎng)絡(luò)的能耗和通信延遲。

上述有關(guān)研究成果對NoC低功耗低時(shí)延等多目標(biāo)映射方面有很大的推進(jìn)作用，但依然有可優(yōu)化的空間，大多算法都是在通信帶寬滿足需要不會出現(xiàn)擁堵現(xiàn)象的情況下實(shí)現(xiàn)的。隨著人們對任務(wù)功能需求的提高，NoC部分節(jié)點(diǎn)鏈路很可能會出現(xiàn)擁堵。本文在考慮擁堵的情況下設(shè)計(jì)多目標(biāo)評估模型，在充分理解量子遺傳算法(Quantum Genetic Algorithm，QGA)優(yōu)缺點(diǎn)的基礎(chǔ)上[9]，結(jié)合應(yīng)用任務(wù)和2D Mesh拓?fù)浣Y(jié)構(gòu)NoC的特點(diǎn)，設(shè)計(jì)一種改進(jìn)的量子遺傳算法(Modified Quantum Genetic Algorithm，MQGA)來實(shí)現(xiàn)NoC低功耗低時(shí)延等多目標(biāo)映射。

2 問題定義和模型描述

2.1 問題定義

定義1應(yīng)用任務(wù)圖(Application Task Graph，ATG)如圖1(a)所示，它是一個(gè)帶通信權(quán)重的有向圖。該應(yīng)用有8個(gè)任務(wù)節(jié)點(diǎn)，有10條相關(guān)鏈路，含有數(shù)字的圓圈代表相應(yīng)的任務(wù)節(jié)點(diǎn)ti，從任務(wù)節(jié)點(diǎn)ti到tj的通信量記為Vti,t2，圖中Vt1,t2=40，方向從t1到t2。

定義2結(jié)構(gòu)特征圖(Architecture Characteristic Graph，ARCG)如圖1(b)所示，是由各個(gè)帶處理單元的交換節(jié)點(diǎn)相互連接，可以實(shí)現(xiàn)雙向通信的有向圖。圖1(b)為典型的3×3的Mesh拓?fù)浣Y(jié)構(gòu)，含有數(shù)字的圓圈代表相關(guān)交換節(jié)點(diǎn)si，每個(gè)交換節(jié)點(diǎn)都有一個(gè)處理單元pi與之對應(yīng)。兩個(gè)處理單元pi、pj之間的曼哈頓距離為Mpi,pj，對于Mesh結(jié)構(gòu)一般為兩個(gè)資源節(jié)點(diǎn)所經(jīng)歷最少交換節(jié)點(diǎn)數(shù)減1。

(a) 應(yīng)用任務(wù)圖ATG (b) 結(jié)構(gòu)特征圖ARCG圖1 映射流程圖

2.2 NoC映射

片上網(wǎng)絡(luò)映射就是將給定的ATG，按一定的順序分配到ARCG中，任務(wù)節(jié)點(diǎn)與處理單元一一對應(yīng)，為處理單元通過NoC完成相應(yīng)的處理任務(wù)做準(zhǔn)備。映射結(jié)果要正確執(zhí)行，需要保證結(jié)構(gòu)特征圖的處理節(jié)點(diǎn)數(shù)量大于任務(wù)圖中的任務(wù)節(jié)點(diǎn)數(shù)，即：

Size(ATG)≤Size(ARCG)

(1)

任務(wù)節(jié)點(diǎn)數(shù)量為m的ATG要映射到n×n的2D Mesh上，需要滿足m≤n2。m個(gè)任務(wù)節(jié)點(diǎn)參與映射就有n2！/(n2-m)！個(gè)映射結(jié)果，合理的映射結(jié)果可以更好地利用現(xiàn)有處理資源來完成相應(yīng)的應(yīng)用任務(wù)，比如快速、低功耗等。如何找到一個(gè)較好的低功耗低時(shí)延映射結(jié)果是本文所要解決的主要問題。

2.3 功耗模型

片上網(wǎng)絡(luò)功耗模型中單位比特?cái)?shù)據(jù)在兩個(gè)相鄰處理單元之間傳遞消耗的能量Ebit為：

Ebit=ESbit+EBbit+EWbit+ELbit

(2)

式中：ESbit為單位比特在交換節(jié)點(diǎn)的能量消耗；EBbit、EWbit為單位比特在緩存區(qū)和處理單元與相應(yīng)交換節(jié)點(diǎn)之間鏈路消耗的能量；ELbit是單位比特在兩個(gè)處理單元之間鏈路傳輸消耗的能量。由于EBbit、EWbit遠(yuǎn)遠(yuǎn)小于ESbit和ELbit，所以公式可以簡化為：

Ebit=ESbit+ELbit

(3)

因此，單位比特從處理單元pi到pj所消耗的能量為：

(4)

對于n×n規(guī)則2D Mesh拓?fù)浣Y(jié)構(gòu)的NoC來說，令N=n×n，則任務(wù)節(jié)點(diǎn)數(shù)為m的任務(wù)圖映射到結(jié)構(gòu)特征圖后所消耗的總能耗ENoC為：

(5)

由功耗模型可知，任務(wù)節(jié)點(diǎn)映射到的處理節(jié)點(diǎn)不同，最終完成任務(wù)需要消耗的能耗也不盡相同。由式(4)-式(5)可知，要減少片上網(wǎng)絡(luò)的總功耗，關(guān)鍵在于降低映射結(jié)果的總通信權(quán)重的曼哈頓距離。

2.4 時(shí)延模型

映射后處理應(yīng)用程序所需時(shí)間如下[5]：

(6)

式中：TL、TS分別為單位比特?cái)?shù)據(jù)在無阻塞情況下，流經(jīng)單位鏈路和單個(gè)交換節(jié)點(diǎn)所需要的時(shí)間；TW為鏈路有阻塞時(shí)的總時(shí)間延遲。從式(6)可看出，映射完成后NoC的時(shí)間消耗一方面與總的通信曼哈頓距離有關(guān)，另一方面受傳遞路徑阻塞延遲TW的影響。阻塞出現(xiàn)一般為某些鏈路和交換節(jié)點(diǎn)可以提供的帶寬不能滿足需要。為減少阻塞，需要通信鏈路負(fù)載均衡，故TW可以用鏈路平均負(fù)載方差來衡量：

(7)

式中：Fi,Fj為鏈路i、j的負(fù)載量；L為NoC總鏈路數(shù)(兩個(gè)相鄰交換節(jié)點(diǎn)之間的鏈路為一個(gè)單位鏈路)，且FNoC越大TW亦越大。NoC的總延時(shí)和負(fù)載方差之間的關(guān)系為：

TW=FNoC×b

(8)

式中：b視為某一常數(shù)。

2.5 多目標(biāo)優(yōu)化模型

由線性加權(quán)和法得多目標(biāo)優(yōu)化函數(shù)為:

min{a×TNoC×c+(1-a)×ENoC}

(9)

式中：a為線性加權(quán)系數(shù)，取0～1之間任一實(shí)數(shù)，為1時(shí)只考慮時(shí)延；為0時(shí)只考慮能耗。c為某個(gè)常數(shù)，為了更好地與ENoC融合便于進(jìn)行量化比較，c值可以設(shè)為通信帶寬。通過NoC映射的功耗和時(shí)耗公式可以看到，TNoC在無阻塞時(shí)的時(shí)間消耗和能耗成正比，執(zhí)行一個(gè)應(yīng)用能耗越低則耗時(shí)也較短；有阻塞時(shí)時(shí)間消耗就和能耗成反比。所以，要想獲得時(shí)間能耗等的多目標(biāo)優(yōu)化，就需要負(fù)載均衡防止擁塞的情況下盡可能降低功耗，通過負(fù)載均衡也可以減少NoC通信熱點(diǎn)的出現(xiàn)，提高通信可靠性穩(wěn)定性。

3 基于改進(jìn)量子遺傳算法的映射技術(shù)

量子遺傳算法具有適應(yīng)性強(qiáng)、種群規(guī)模小、種群多樣性、強(qiáng)大的全局搜索能力以及具備較強(qiáng)的勘探能力等特點(diǎn)，在很多領(lǐng)域得到廣泛的應(yīng)用。

3.1 解結(jié)構(gòu)

如圖1中ARCG結(jié)構(gòu)是一個(gè)典型的3×3 Mesh的NoC，本文只考慮2D Mesh結(jié)構(gòu)的NoC，n×n的Mesh結(jié)構(gòu)有n2個(gè)處理單元，每個(gè)處理單元在NoC中位置不同，分別有2、3、4條物理鏈路將各個(gè)處理單元連接起來，實(shí)現(xiàn)相互之間的通信。對于量子遺傳算法，每個(gè)種群個(gè)體都代表一個(gè)映射結(jié)果。

將2D Mesh中的處理單元從左到右、從上至下進(jìn)行升序排序，如圖2所示，從P1到P9，每個(gè)處理單元都有一個(gè)唯一的數(shù)字編號，對于圖中3×3 Mesh結(jié)構(gòu)的，最大編號為9。將圖1中的任務(wù)節(jié)點(diǎn)映射到該NoC中，由于任務(wù)節(jié)點(diǎn)數(shù)量為6，則有9!/(9-8)!=362 880個(gè)映射結(jié)果，其中映射結(jié)果a、b對應(yīng)映射位置信息Pa={1,4,5,2,3,7,8,9}、Pb={1,5,9,2,3,7,4,6}為兩個(gè)有效的映射結(jié)果即有效解，只要對應(yīng)位置信息為8個(gè)不大于9的不相同整數(shù)，都是一個(gè)有效解。

(a) 映射a (b) 映射b (c) 映射結(jié)果圖2 映射結(jié)果圖

3.2 初始解構(gòu)造

遺傳算法和量子遺傳算法的初始解集大多是隨機(jī)產(chǎn)生的，當(dāng)種群規(guī)模比較大時(shí)進(jìn)化效率很低，為了提高收斂速度，結(jié)合NoC的結(jié)構(gòu)特點(diǎn)，按照相關(guān)鏈路數(shù)量和通信量大小雙重標(biāo)準(zhǔn)對任務(wù)節(jié)點(diǎn)優(yōu)先排序，優(yōu)先級高的優(yōu)先選擇映射位置，構(gòu)建一個(gè)較優(yōu)初始解集，將大大提升種群進(jìn)化效率。

構(gòu)建較優(yōu)初始解集步驟如下：

1) 統(tǒng)計(jì)各個(gè)任務(wù)節(jié)點(diǎn)相關(guān)鏈路數(shù)量RLnum和相關(guān)通信總量:

(10)

以圖1中ATG為例，優(yōu)先級定級如表1所示。

表1 任務(wù)節(jié)點(diǎn)優(yōu)先級定級

2) 優(yōu)先考慮任務(wù)節(jié)點(diǎn)相關(guān)鏈路數(shù)量，數(shù)量越多，優(yōu)先級越高；數(shù)量相同時(shí)，考慮任務(wù)節(jié)點(diǎn)相關(guān)通信總量，通信總量越高的優(yōu)先級越高。

3) 優(yōu)先級高的優(yōu)先在對應(yīng)的ARCG中選擇合適的位置放置，再放置與它相關(guān)的任務(wù)節(jié)點(diǎn)，相關(guān)任務(wù)節(jié)點(diǎn)有多個(gè)時(shí)優(yōu)先級越高的優(yōu)先放置。

4) 剩余少量節(jié)點(diǎn)可以隨機(jī)放置，產(chǎn)生初始解集。

如圖3所示，以圖1中的ATG和ARCG為例，任務(wù)節(jié)點(diǎn)3有4個(gè)相關(guān)鏈路，則最先映射，對應(yīng)ARCG中位置5剛好有4個(gè)相關(guān)物理鏈路，則任務(wù)節(jié)點(diǎn)3放置在位置5；與任務(wù)節(jié)點(diǎn)3有關(guān)系的任務(wù)節(jié)點(diǎn)2、4、5、7按照表1中的優(yōu)先級放置，則依次放置節(jié)點(diǎn)4、7、2、5；最后考慮第三梯隊(duì)的放置，優(yōu)先放置與任務(wù)節(jié)點(diǎn)4相關(guān)的鏈路，其中3、5已經(jīng)確定位置，則就近放置1即可，其他同理放置，直至所有任務(wù)節(jié)點(diǎn)全部放置在ARCG中。由于放置任務(wù)節(jié)點(diǎn)4時(shí)有4個(gè)位置可以選擇，任務(wù)節(jié)點(diǎn)4確定后任務(wù)節(jié)點(diǎn)3有3個(gè)位置可以選擇，進(jìn)而產(chǎn)生很多可能的較優(yōu)解。

圖3 較優(yōu)初始解集構(gòu)造

以上是對于3×3 Mesh的NoC，如果是4×4 Mesh，第一個(gè)任務(wù)節(jié)點(diǎn)就有4個(gè)映射位置可供選擇，8個(gè)任務(wù)節(jié)點(diǎn)放置到16個(gè)映射位置中，結(jié)構(gòu)冗余很大，一般隨機(jī)確定第一個(gè)任務(wù)節(jié)點(diǎn)的位置，然后按照上述方法構(gòu)造較優(yōu)初始解集。如果初始解集需求較大時(shí)可以通過變更第一個(gè)任務(wù)節(jié)點(diǎn)位置來獲取更多的較優(yōu)初始解。

3.3 量子遺傳算法原理

量子遺傳算法利用量子多態(tài)特性，用概率幅對染色體進(jìn)行編碼，然后通過量子旋轉(zhuǎn)門調(diào)整概率幅進(jìn)化種群來尋找最優(yōu)解，具體可在文獻(xiàn)[9]中了解相關(guān)原理。

QGA引入量子比特，一個(gè)量子比特是兩個(gè)基態(tài)的任一線性組合如下：

|φ〉=α|0〉+β|1〉

(11)

式中:α、β為兩個(gè)基態(tài)|0〉、|1〉對應(yīng)的概率幅，表示量子態(tài)|φ〉被觀察為基態(tài)的相應(yīng)概率，且滿足：

(12)

一對復(fù)數(shù)定義一個(gè)量子位，用概率幅對染色體進(jìn)行編碼，則長度為m的量子染色體可表示為：

(13)

QGA通過量子旋轉(zhuǎn)門實(shí)現(xiàn)種群的進(jìn)化，即替代原遺傳算法的選擇、交叉、變異操作，使得遺傳算法的進(jìn)化實(shí)現(xiàn)更簡單。量子旋轉(zhuǎn)門更新方式為：

(14)

3.4 改進(jìn)量子遺傳算法的實(shí)現(xiàn)

QGA具有全局搜索能力強(qiáng)、收斂速度快、個(gè)體數(shù)目少易于進(jìn)化計(jì)算且不容易陷入“早熟”陷阱等優(yōu)點(diǎn)。不同于變異操作，量子變異操作通過選擇改變變異位的概率幅，利用量子糾纏特性，只需要采用單點(diǎn)變異就能防止遺傳早熟現(xiàn)象出現(xiàn)。QGA改進(jìn)策略(MQGA)如圖4所示。

圖4 MQGA策略圖

MQGA流程如下：

1) 初始化總?cè)篞(t)，結(jié)合Mesh拓?fù)浣Y(jié)構(gòu)特點(diǎn)采用前面講到的新方法生成初始種群Q(t0)，含有N個(gè)量子編碼的染色體。

2) 對Q(t0)進(jìn)行一次測量并進(jìn)行適應(yīng)度評估，得到該種群的最優(yōu)個(gè)體解Bgtj(t0)，并做好相應(yīng)記錄。

3) 判斷計(jì)算過程是否滿足結(jié)束條件，滿足則退出，否則繼續(xù)計(jì)算。

4) 量子旋轉(zhuǎn)門操作得到下一代種群Q(t1)。

5) 對Q(t1)種群進(jìn)行一次適應(yīng)度計(jì)算，得到最優(yōu)個(gè)體解Bgtj(t1)，并做好相應(yīng)記錄。

6) 返回步驟3)進(jìn)行下一次迭代。

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

1) 仿真平臺。實(shí)驗(yàn)在Linux環(huán)境下用C++完成映射算法程序等相關(guān)源代碼的編寫，采用2D NoC仿真軟件Noxim作為仿真軟件，在Ubuntu 16.04操作系統(tǒng)下實(shí)現(xiàn)。硬件環(huán)境采用CPU為第八代Intel Core i7-8550U，最高睿頻4.0 GHz，內(nèi)存16 GB DDR4雙通道的微型計(jì)算機(jī)。

2) ARCG拓?fù)浣Y(jié)構(gòu)和路由選擇。2D Mesh拓?fù)浣Y(jié)構(gòu)結(jié)構(gòu)規(guī)則、實(shí)現(xiàn)容易、布線簡單、便于拓展，是常用的NoC拓?fù)浣Y(jié)構(gòu)，對于映射算法研究非常合適。該實(shí)驗(yàn)選用2D Mesh拓?fù)浣Y(jié)構(gòu)，根據(jù)實(shí)驗(yàn)需要有4×4、5×5、6×6三種規(guī)模的Mesh拓?fù)洹Ｂ酚伤惴ú捎萌菀桌斫夂蛯?shí)現(xiàn)的XY路由算法，也是NoC主流路由算法。

3) 應(yīng)用任務(wù)圖的選擇。為了體現(xiàn)QGA算法對各種實(shí)際應(yīng)用的有效性，并便于與同類算法作對比分析，實(shí)驗(yàn)采用典型的實(shí)際應(yīng)用任務(wù)圖VOPD、MPEG-4、263Enc、263Dec[13]。4種應(yīng)用任務(wù)圖結(jié)構(gòu)不同，任務(wù)節(jié)點(diǎn)數(shù)和通信總量也不盡相同，詳細(xì)特征屬性見表2。

表2 應(yīng)用任務(wù)屬性

4) 實(shí)驗(yàn)結(jié)果計(jì)算方式。由于芯片生產(chǎn)工藝的不同，不同芯片的Mesh結(jié)構(gòu)相鄰處理單元之間傳遞信息的能耗和時(shí)延也不相同。為了便于評估映射結(jié)果的功耗和時(shí)延，考慮到Mesh結(jié)構(gòu)的規(guī)則對稱性，實(shí)驗(yàn)計(jì)算時(shí)將相鄰兩個(gè)處理單元之間的距離視為一個(gè)曼哈頓距離M，每M通信傳遞消耗1個(gè)能量單元，時(shí)延時(shí)間按式(9)進(jìn)行同一量化。由于智能算法有一定的隨機(jī)性，為確保實(shí)驗(yàn)結(jié)果準(zhǔn)確性，每種應(yīng)用任務(wù)圖在同一規(guī)模的Mesh結(jié)構(gòu)特征圖下分別運(yùn)行10次，然后取10次結(jié)果的平均值。

4.2 多目標(biāo)線性加權(quán)系數(shù)a的選取

a的選擇主要由鏈路帶寬的高低和處理任務(wù)通信量的大小等決定。以4×4規(guī)模的NoC為例，由于VOPD、MPEG-4通信量比263Enc尤其是263Dec大很多倍，對前兩個(gè)可能會出現(xiàn)擁堵的帶寬在運(yùn)行263Enc、263Dec時(shí)不會發(fā)生擁堵。所以實(shí)驗(yàn)時(shí)鏈路帶寬根據(jù)處理任務(wù)通信量的多少進(jìn)行變化，保證存在一定擁堵的可能性，該實(shí)驗(yàn)取平均鏈路負(fù)載的5倍。VOPD、MPEG-4鏈路帶寬相近，可放在同一圖中對比，在不同a取值下的實(shí)驗(yàn)結(jié)果如圖5所示。

(a) VOPD與MPEG-4

(b) 263Dec

(c) 263Enc圖5 4×4不同應(yīng)用MQGA能耗隨a值變化圖

通過4種應(yīng)用能耗曲線可以看出，在不考慮時(shí)延時(shí)能耗都會偏高，在過于考慮時(shí)延時(shí)反而造成能耗的大量提升，在實(shí)驗(yàn)設(shè)定的帶寬下，a值取0.3附近時(shí)效果比較好，能耗相對較低。

VOPD在不同規(guī)模的Mesh結(jié)構(gòu)隨a值變化對比圖如圖6所示。隨著NoC結(jié)構(gòu)規(guī)模的擴(kuò)大，處理應(yīng)用能耗整體會有不少提升，因?yàn)橐?guī)模變大后，鏈路帶寬降低，擁堵更嚴(yán)重；a值的調(diào)節(jié)在前期比較顯著，最低能耗的a值會減小，說明NoC規(guī)模越大，a值的合理取值應(yīng)該越小。

圖6 VOPD不同規(guī)模MQGA能耗隨a值變化圖

4.3 能耗對比

對比不同算法時(shí)設(shè)置a值為0.3，在4×4規(guī)模的Mesh結(jié)構(gòu)下，與GA[10]、AGA[11]、DPSOGA[5]、HQGA[4]4種算法作對比。為了同框便于直觀顯示，以4種應(yīng)用任務(wù)映射結(jié)果能耗對另外4種算法的能耗降低百分比如圖7所示。

圖7 能耗降低條形圖

可以看出，MQGA在相同運(yùn)行環(huán)境下比GA、AGA有更大的提升,相比較新的DPSOGA和HQGA也有不少提升，說明MQGA搜索精度更精確。例如對VOPD應(yīng)用來說，MQGA比早期的GA提升25.4%，比AGA提升10.4%，比近兩年的DPSOGA也提升4.1%，即使同樣采用量子編碼的HQGA也有提升了1.6%；對263Dec應(yīng)用時(shí)候提升更多，即使對比較新的DPSOGA也提升了13.2%，比HQGA提升了5.8%。

4.4 收斂速度對比

MQGA在具有較快收斂特性的QGA基礎(chǔ)上，結(jié)合NoC應(yīng)用映射特點(diǎn)，進(jìn)一步優(yōu)化初始解集，使得MQGA收斂速度更快。在同一環(huán)境平臺下5種算法處理VOPD應(yīng)用任務(wù)能耗隨遺傳迭代次數(shù)收斂情況如圖8所示。MQGA的收斂速度是最快的，最早的GA迭代到收斂需要150次左右，同樣情況下MQGA 30次迭代就可以達(dá)到收斂，而且收斂精度遠(yuǎn)遠(yuǎn)高于GA。對于同樣適用較優(yōu)初始解集的DPSOGA，MQGA的初始解集質(zhì)量更高，收斂速度也更快。對于同樣改進(jìn)QGA的HQGA，由于初始解集更優(yōu)秀，收斂速度大大提升，收斂精度也有提高。可以看出，GA結(jié)合量子編碼會很大程度地提升收斂速度。

圖8 5種算法收斂走勢圖

5 結(jié) 語

本文在考慮擁堵的情況下利用線性加權(quán)和負(fù)載均衡的辦法設(shè)計(jì)了NoC多目標(biāo)映射評估模型，不僅可以實(shí)現(xiàn)低功耗低時(shí)延，也同時(shí)提高了系統(tǒng)穩(wěn)定性和可靠性，結(jié)合NoC映射特點(diǎn)改進(jìn)了量子遺傳算法。實(shí)驗(yàn)結(jié)果表明，MQGA在相關(guān)算法比較中效果顯著，大大提升了NoC映射算法的收斂速度，并進(jìn)一步提升了搜索精度。算法實(shí)現(xiàn)時(shí)量子遺傳編碼比較復(fù)雜，編碼解碼速度慢，后續(xù)研究可以圍繞編碼問題進(jìn)一步優(yōu)化。隨著應(yīng)用任務(wù)越來越復(fù)雜，片上網(wǎng)絡(luò)規(guī)模的擴(kuò)大，較優(yōu)初始解集的產(chǎn)生也需要合適的算法方可更好實(shí)現(xiàn)。