萬(wàn)逸君，張大坤，鄭亞振

天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387

三維片上網(wǎng)絡(luò)離散量子粒子群布圖算法研究*

萬(wàn)逸君，張大坤+，鄭亞振

天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387

三維片上網(wǎng)絡(luò)在多種性能上均優(yōu)于二維片上網(wǎng)絡(luò)，已成為研究熱點(diǎn)。布圖算法直接影響芯片的面積和布線長(zhǎng)度，成為三維片上網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的重要方向。提出一種基于離散粒子群算法的三維片上網(wǎng)絡(luò)布圖優(yōu)化算法，與之前常使用的模擬退火算法相比，不再使用單一解局部擾動(dòng)的方式得到整個(gè)解空間，該算法采用初始化隨機(jī)種群并不斷迭代的進(jìn)化方式，具有更優(yōu)的搜索能力和更快的收斂速度。仿真結(jié)果表明，采用該算法選擇布圖方案可以顯著降低微片延遲，節(jié)省CPU計(jì)算時(shí)間，尤其是在IP核數(shù)量眾多的測(cè)試用例和高注入率情況下效果更為明顯，如對(duì)于ami49測(cè)試用例當(dāng)注入率為100%時(shí)，基于離散量子粒子群算法的結(jié)果和基于模擬退火算法的結(jié)果相比，平均微片延遲減少了20.63%，CPU平均時(shí)間減少了69.40%。

三維片上網(wǎng)絡(luò)；布圖算法；B*-tree；離散量子粒子群算法；模擬退火算法；粒子群算法

1 引言

隨著大規(guī)模集成電路技術(shù)的發(fā)展，片上系統(tǒng)（system-on-chip，SoC）、二維片上網(wǎng)絡(luò)（two dimensional network-on-chip，2D NoC）相繼產(chǎn)生。隨著2D NoC規(guī)模的增大，2D NoC在面積、功耗、布局布線以及封裝密度等方面都已達(dá)到了瓶頸[1]。因而三維片上網(wǎng)絡(luò)（three dimensional network-on-chip，3D NoC）應(yīng)運(yùn)而生，并成為研究熱點(diǎn)[2-4]。3D NoC通過(guò)三維集成電路堆疊技術(shù)（die stacking）將多層硅晶互相堆疊，然后通過(guò)矽晶穿孔（through silicon via，TSV）技術(shù)實(shí)現(xiàn)了層次芯片設(shè)計(jì)，它擁有更好的適應(yīng)性和擴(kuò)展性，同時(shí)減小了芯片面積。

衡量3D NoC性能的指標(biāo)有很多，如微片延遲、功耗和發(fā)熱等，這些性能指標(biāo)均與三維芯片中IP核的布圖方式密切相關(guān)。3D NoC布圖方式可分為兩大類，即二分結(jié)構(gòu)（slicing structure）[5]和非二分結(jié)構(gòu)（none slicing structure）[6]。二分結(jié)構(gòu)是指通過(guò)橫向或縱向迭代切割布圖區(qū)域，從而得到布圖方案，如圖1所示。其中（a）是二分結(jié)構(gòu)布圖方案，（b）是相應(yīng)的切割樹(shù)，這種結(jié)構(gòu)在實(shí)際中有許多應(yīng)用[7-8]。非二分結(jié)構(gòu)不能通過(guò)迭代切割獲得，而只能通過(guò)總體布局設(shè)計(jì)而獲得，如圖2所示，有許多二分結(jié)構(gòu)的應(yīng)用實(shí)例[9-10]。一般來(lái)說(shuō)，二分結(jié)構(gòu)實(shí)現(xiàn)起來(lái)更加簡(jiǎn)單，但對(duì)布圖圖形以及布圖方式要求較高；而非二分結(jié)構(gòu)更具普遍性，應(yīng)用更為廣泛，針對(duì)非二分結(jié)構(gòu)研究三維片上網(wǎng)絡(luò)布圖優(yōu)化算法更具有普遍意義。

Fig.1 Slicing structure and its cutting tree圖1 二分結(jié)構(gòu)及其對(duì)應(yīng)的切割樹(shù)

Fig.2 None slicing structure圖2 非二分結(jié)構(gòu)

在計(jì)算機(jī)中，需要使用表示布圖的編碼方法，即使用一個(gè)數(shù)字或者字母的序列來(lái)表示一種布圖方案。二分結(jié)構(gòu)常使用的表示法有二叉樹(shù)[11]及正則波蘭表達(dá)式[12]；非二分常使用的表示法有SP（sequence pair）[13]、BSG（bounded-sliceline grid）[14]、TCG（transitive closure graph）[15]、ACG（adjacent constraint graph）[16]、O-tree[17]和 B*-tree[18]。

目前，3D NoC布圖優(yōu)化算法主要有基于模擬退火算法（simulated annealing，SA）的布圖優(yōu)化算法[19]、基于粒子群算法的布圖優(yōu)化算法（particle swarm optimization，PSO）[20]以及基于模擬退火改進(jìn)的粒子群算法的布圖算法。分析現(xiàn)有的這些算法可知，它們都通過(guò)單一解擾動(dòng)方式獲得下一個(gè)可行解，收斂速度較慢。當(dāng)三維片上網(wǎng)絡(luò)規(guī)模增大、結(jié)構(gòu)復(fù)雜度增加時(shí)，布圖可行方案數(shù)會(huì)急劇增加，解的擾動(dòng)次數(shù)也隨之增加，求解時(shí)間將大幅度增加，因而導(dǎo)致求解效率顯著下降。為了提高求解效率等，本文提出一種基于離散粒子群算法的三維片上網(wǎng)絡(luò)布圖優(yōu)化算法，該算法采用初始化隨機(jī)種群并不斷迭代的進(jìn)化方式，具有更優(yōu)的搜索能力和更快的收斂速度。

2 基本設(shè)計(jì)

2.1 3D NoC架構(gòu)和設(shè)計(jì)流程

本文采用3層的片上網(wǎng)絡(luò)，如圖3所示。該結(jié)構(gòu)是美國(guó)North Dakota State大學(xué)Cristinel Ababei教授等提出的[21]，并開(kāi)發(fā)了基于該結(jié)構(gòu)的仿真平臺(tái)vnoc3。其中，第1層、第3層片上放置任意尺寸大小的異構(gòu)IP核；第2層是標(biāo)準(zhǔn)mesh結(jié)構(gòu)，放置路由器。

Fig.3 Atask graph mapping 3 layer structure圖3 一個(gè)任務(wù)圖映射3層結(jié)構(gòu)

這種3層結(jié)構(gòu)保持了網(wǎng)絡(luò)層的規(guī)則性，使3D NoC的整體設(shè)計(jì)更加簡(jiǎn)單，設(shè)計(jì)流程如圖4所示。

Fig.4 3D NoC design process圖4 3D NoC設(shè)計(jì)流程

（1）將不同的任務(wù)映射到IP核上，并根據(jù)任務(wù)圖，使用hMetis圖劃分器，按照最小割邊的標(biāo)準(zhǔn)，將IP核分為兩層。

（2）分層使用布圖算法，先用布圖算法將一部分IP核分配到第1層中，再分配剩下的IP核到第3層；使用布圖算法時(shí)加上了垂直方向的約束條件，以減少鏈路的長(zhǎng)度。將布圖算法在每一層應(yīng)用10次，保存其中最優(yōu)的3個(gè)布圖方案。

（3）在3個(gè)布圖方案中，為每層IP核分配路由器。首先將第2層設(shè)置為R×R標(biāo)準(zhǔn)mesh結(jié)構(gòu)，保證至少每一個(gè)IP核都能分配到一個(gè)路由器（稱之為直接拓?fù)洌?，并不是每一個(gè)IP核都能連接上垂直方向的路由器，因此有的IP核需要使用額外的鏈路來(lái)連接路由器，這些額外鏈路也會(huì)影響微片的延遲，vnoc3中將此問(wèn)題看作一個(gè)線性分配問(wèn)題，應(yīng)用Kuhn-Munkres算法來(lái)解決。

（4）實(shí)現(xiàn)周期內(nèi)的精準(zhǔn)模擬，模擬出微片的平均延遲和運(yùn)行時(shí)間等。

對(duì)ami33測(cè)試用例使用這種設(shè)計(jì)結(jié)構(gòu)，其中的一種布圖方案如圖5所示，mesh中的紅色路由器表示沒(méi)有連接IP核，路由器上的斜線表示額外鏈路。

2.2 B*-tree編碼表示及更新算法

2.2.1 B*-tree編碼表示法

B*-tree布圖表示法由Chang等人首次提出[22]，它用有序二叉樹(shù)B*-tree表示布圖方案，是一種自左下角向右上角直至全局的緊湊布圖表示法，即在布圖方案中沒(méi)有任何一個(gè)模塊可以向其左下方移動(dòng)，優(yōu)點(diǎn)是每一個(gè)可行的布圖方案只對(duì)應(yīng)唯一的一個(gè)B*-tree，反之亦然。

布圖中模塊Mi與B*-tree中的節(jié)點(diǎn)Ni一一對(duì)應(yīng)，定義B*-tree的節(jié)點(diǎn)和B*-tree結(jié)構(gòu)為：

節(jié)點(diǎn)中的id、parent、left、right分別記錄此節(jié)點(diǎn)、父節(jié)點(diǎn)、左孩子、右孩子的id號(hào)；rotate是模塊能否旋轉(zhuǎn)角度的標(biāo)志；B*-tree中nodes_list記錄所有Node節(jié)點(diǎn)的集合；nodes_root記錄根節(jié)點(diǎn)的id號(hào)，可以構(gòu)造一棵B*-tree。

Fig.5 Layout and topology scheme of ami33 using 3 layer structure圖5 使用3層結(jié)構(gòu)的ami33的一種布圖和拓?fù)浞桨?/p>

設(shè)(x,y)為模塊M的左下點(diǎn)坐標(biāo)，w、h分別為模塊M寬和高，如果B*-tree有Ni、Nj兩節(jié)點(diǎn)，對(duì)應(yīng)的模塊Mi、Mj幾何關(guān)系如圖6所示，規(guī)則如下。

Fig.6 Feasible floorplanning and its corresponding B*-tree圖6 可行布圖方案及其對(duì)應(yīng)的B*-tree

（1）根節(jié)點(diǎn)對(duì)應(yīng)整個(gè)布圖最左下角模塊，其坐標(biāo)(xroot,yroot)=(0,0)。

（2）如果節(jié)點(diǎn)Nj是節(jié)點(diǎn)Ni的左孩子，那么在布圖方案中Mj緊鄰著Mi，并且是Mi右側(cè)最下方尚未在布局方案中的模塊，且xj=xi+wi。

（3）如果Nj是Ni的右孩子，那么模塊Mj緊挨著模塊Mi在其上側(cè)，而且兩個(gè)模塊在X軸的坐標(biāo)相等，即xi=xj。

2.2.2 基于B＊-tree的布圖位置更新算法

對(duì)于已有的一棵B*-tree，將其轉(zhuǎn)換成一個(gè)布圖方案就需要按照樹(shù)深度優(yōu)先遍歷的順序，將每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的模塊加入布圖方案中，更新其坐標(biāo)以及布圖方案的輪廓邊界。在放置一個(gè)模塊且更新邊界的算法中，定義輪廓界限的結(jié)構(gòu)為：

其中，front記錄本輪廓界限的前一段輪廓對(duì)應(yīng)的模塊序號(hào)；back記錄本輪廓界限的后一段輪廓對(duì)應(yīng)的模塊序號(hào)。如圖7（a）所示，每一個(gè)模塊都用(x,y)以及(rx,ry)兩組坐標(biāo)來(lái)表示它的位置以及范圍，IP0對(duì)應(yīng)的輪廓Contour0是最小的點(diǎn)組成的虛線，Contour0.front=1,Contour0.back=2，最開(kāi)始已知IP0的坐標(biāo)(x0,y0)=(xroot,yroot)=(0,0)。

Fig.7 B*-tree and update coordinates and contours圖7 B＊-tree及更新坐標(biāo)和輪廓界限

當(dāng)前布圖方案中已有IP0、IP1以及IP2這3個(gè)模塊，并已知它們的左下角坐標(biāo)分別為(x0,y0)、(x1,y1)以及 (x2,y2)，右上角坐標(biāo)分別為 (rx0，ry0)、(rx1，ry1)以及(rx2,ry2)，此時(shí)布圖的輪廓界限由Contour0、Contour1、Contour2組成，將要加入的模塊為IP3，根據(jù)布圖方案對(duì)應(yīng)的B*-tree來(lái)更新布圖方案。

（1）判斷要插入的節(jié)點(diǎn)，節(jié)點(diǎn)3在B*-tree中是節(jié)點(diǎn)1的右孩子，如圖7（b）所示。

（2）IP3應(yīng)該放置在IP1的上方，且IP3的x3與其父節(jié)點(diǎn)對(duì)應(yīng)的模塊IP1的x1相等，更新x3=x1,y3與父節(jié)點(diǎn)模塊的ry1相等，更新y3=ry1，而且IP3的rx3=x3+w（w為IP3模塊的寬度），ry3=y3+h（h為IP3模塊的高度）。

（3）由于加入了新的節(jié)點(diǎn)要更新布圖輪廓，更新IP0對(duì)應(yīng)的輪廓Contour0以及IP3對(duì)應(yīng)的輪廓Contour3，Contour0.front=3,Contour3.back=0。

（4）比較rx3與rx1，如果rx3＜rx1，則更新IP3所對(duì)應(yīng)的輪廓Contour3以及IP1所對(duì)應(yīng)的輪廓Contour1，Contour3.front=1,Contour1.back=3；否則IP3所對(duì)應(yīng)的輪廓Contour3將代替IP1所對(duì)應(yīng)的輪廓Contour1，Contour3.front=Contour1.front，如果IP1輪廓的front不為空的話，(Contour1.front).back=3，如此迭代更新，直至形成整個(gè)布圖方案。

3 3D NoC離散量子粒子群布圖優(yōu)化算法研究

3.1 目標(biāo)函數(shù)選取

3D NoC布圖優(yōu)化，就是對(duì)于給定的測(cè)試用例（由N個(gè)面積、寬高方向數(shù)值不等的IP核組成）使用B*-Tree表示方法編碼，按照優(yōu)化布圖算法，把N個(gè)模塊分配到3D NoC結(jié)構(gòu)的不同層上，即依據(jù)目標(biāo)函數(shù)求出布圖方案的編碼序列，并且按照布圖規(guī)則分配模塊的擺放位置，并且它們互不重疊。它實(shí)際上是一個(gè) NP（non-deterministic polynomial）問(wèn)題[23]，由于布圖方案直接影響芯片的面積、布線的長(zhǎng)度，微片延遲、CPU時(shí)間等衡量3D NoC芯片性能的指標(biāo)會(huì)隨著芯片面積、布線長(zhǎng)度的增加而增加，因此它的目標(biāo)函數(shù)可以定義如下：

其中，A、W分別表示芯片的面積和布線長(zhǎng)度。A、W都由布圖方案得到的模塊信息計(jì)算，使用最外層輪廓對(duì)應(yīng)的模塊坐標(biāo)計(jì)算整個(gè)芯片的面積，使用模塊的坐標(biāo)計(jì)算曼哈頓長(zhǎng)度表示布線長(zhǎng)度。α是由用戶設(shè)置的權(quán)值系數(shù)，在0,1之間隨機(jī)取值，用來(lái)調(diào)整面積和線長(zhǎng)的比重，本算法選取α=0.25（多次實(shí)驗(yàn)表明α=0.25效果最好）。

3.2 標(biāo)準(zhǔn)量子粒子群優(yōu)化算法

量子粒子群優(yōu)化（quantum-behaved particle swarm optimization，QPSO）算法是Sun等人提出的[24]，他們對(duì)人類學(xué)習(xí)模式和群體智能的基本特征進(jìn)行了深入研究[25]，建立了基于量子勢(shì)阱的粒子群模型，并且提出了量子行為的粒子群優(yōu)化算法。本文選用QPSO算法是因?yàn)樗琍SO一樣，具有總結(jié)自身和向群體或領(lǐng)域內(nèi)優(yōu)秀粒子學(xué)習(xí)的能力，整個(gè)種群不斷進(jìn)化迭代，其收斂速度快，能更好地適用于解空間較大的問(wèn)題，如大型架構(gòu)的優(yōu)化布局問(wèn)題；粒子群算法（particle swarm optimization，PSO）存在著參數(shù)較多且要調(diào)整相應(yīng)的取值范圍等缺點(diǎn)，而在QPSO算法中，控制參數(shù)較少，除基本參數(shù)如種群規(guī)模和迭代次數(shù)之外，唯一需要設(shè)定的參數(shù)就是算法的收縮-擴(kuò)張因子（contraction-expansion coefficient，CE因子）[26]。

一般量子粒子群算法的進(jìn)化方程如式（2）～（4）所示：

其中，N表示粒子種群的規(guī)模，即解方案的數(shù)量；M表示解的維度；mbest(t)表示第t次迭代平均最好的位置；pbesti,j(t)表示粒子i在第t次迭代的歷史最佳位置在j維的坐標(biāo)值；gbestj(t)表示第t次迭代的全局最佳粒子位置在第j維的坐標(biāo)值；φ是0,1之間的隨機(jī)分布數(shù)；Xi,j(t)表示粒子i第t次迭代在j維的坐標(biāo)值；u是0,1之間的隨機(jī)分布數(shù)；α是收縮-擴(kuò)張系數(shù)，一般處于1.0到0.5之間，并且呈線性遞減，如式（5）所示：

其中，T為總迭代次數(shù)；count為當(dāng)前迭代次數(shù)；αmax=1.0,αmin=0.5。

3.3 基于離散量子粒子群算法的布圖優(yōu)化算法設(shè)計(jì)

一般的QPSO算法大多都是針對(duì)連續(xù)的解空間，而對(duì)于3D NoC的布局問(wèn)題，它的解空間是離散的，且需要與B*-tree編碼相對(duì)應(yīng)，因此需要重新定義離散量子粒子群優(yōu)化算法（discrete quantum-behaved particle swarm optimization，DQPSO）、粒子所代表的意義和DQPSO算法中的一些操作。

3.3.1 粒子結(jié)構(gòu)的定義

為了結(jié)合量子粒子群算法的特點(diǎn)，方便粒子進(jìn)化操作，本文定義的粒子結(jié)構(gòu)為：

Quantum與B*-tree中的節(jié)點(diǎn)相對(duì)，id代表它的序號(hào)，left、right取值為1或0，1代表有左孩子或右孩子，0代表沒(méi)有。每一個(gè)Quantum序列設(shè)為{Q1,Q2,…,QM}，如果它可以生成一棵B*-tree，其中Quantum的id出現(xiàn)順序代表一棵樹(shù)的廣度優(yōu)先遍歷順序，Quantum的left、right代表節(jié)點(diǎn)排列的疏密程度，left、right中1越多代表生成的B*-tree節(jié)點(diǎn)排列越稠密，同時(shí)序列也對(duì)應(yīng)一種布圖方案；如果Quantum序列不能生成一棵B*-tree就需要對(duì)解進(jìn)行修正，重新隨機(jī)選擇Quantum序列中l(wèi)eft、right的0、1值直到能構(gòu)成B*-tree為止。

3.3.2 初始種群的生成

應(yīng)用DQPSO算法實(shí)現(xiàn)布圖，首先可以通過(guò)對(duì)B*-tree的局部擾動(dòng)方法生成初始種群。局部擾動(dòng)同時(shí)可以完成局部搜索，以及增加解空間的多樣性，擾動(dòng)方法有：

（1）旋轉(zhuǎn)節(jié)點(diǎn)。隨機(jī)選取節(jié)點(diǎn)，如果節(jié)點(diǎn)有可旋轉(zhuǎn)標(biāo)志，此時(shí)交換模塊的寬和高。

（2）交換節(jié)點(diǎn)。隨機(jī)選取兩個(gè)節(jié)點(diǎn)，并交換它們的位置，對(duì)應(yīng)的模塊布圖位置也相應(yīng)交換。

（3）刪除和插入節(jié)點(diǎn)。隨機(jī)選取一個(gè)節(jié)點(diǎn)刪除它，將它的左、右子樹(shù)，添加到其父節(jié)點(diǎn)之下，同時(shí)隨機(jī)選取另一個(gè)節(jié)點(diǎn)并把它作為父節(jié)點(diǎn)，在它下面插入已經(jīng)刪除的節(jié)點(diǎn)。

同時(shí)為了增大局部搜索，以及保存部分模塊已有的位置優(yōu)勢(shì)，本文增加了兩種擾動(dòng)方式。

（4）交換子樹(shù)。任意選擇兩個(gè)節(jié)點(diǎn)，其中一個(gè)節(jié)點(diǎn)不能是另一個(gè)節(jié)點(diǎn)的祖先，找到兩棵以這兩個(gè)節(jié)點(diǎn)為根的子樹(shù)，并交換這兩個(gè)子樹(shù)。

（5）刪除和插入樹(shù)。任意選擇兩個(gè)節(jié)點(diǎn)a和b,a代表要?jiǎng)h除的子樹(shù)的根節(jié)點(diǎn)，b代表要插入位置的父節(jié)點(diǎn)，其中a不能是b的祖先，將子樹(shù)從a刪除，插入b位置。

3.3.3 粒子進(jìn)化操作說(shuō)明

已有QPSO算法的進(jìn)化公式不適用于本文定義的與B*-tree相對(duì)應(yīng)的離散解的結(jié)構(gòu)，需要對(duì)一系列的進(jìn)化操作重新解釋說(shuō)明，說(shuō)明如下。

說(shuō)明1式（2）中，初始有N個(gè)Quantum序列，每個(gè)序列M維，把它們?cè)O(shè)為初始的pbesti，0≤i≤N-1。在第t次迭代中，求解種群平均最優(yōu)位置mbest={mbest1,mbest2,…,mbestM}，N個(gè)pbest，也就是N個(gè)Quantum序列 {Q1,Q2,…,QM}，pbesti={Q1,Q2,…,QM}，Qj中的id可能為M個(gè)模塊中的任意一個(gè)，即0≤Qj.id≤M-1。對(duì)于mbest第j個(gè)維度的值mbestj，求解N個(gè)pbest在維度j中的不同id號(hào)出現(xiàn)的次數(shù)，即如果Qj.id=k,0≤k≤M-1，計(jì)算N個(gè)pbest第j維Qj.id中k出現(xiàn)的次數(shù)，記錄下出現(xiàn)最多的id號(hào)k以及k出現(xiàn)的次數(shù)n，計(jì)算n/N，如果大于1/N，證明k出現(xiàn)的幾率大于隨機(jī)選擇，則mbestj.id=k，否則隨機(jī)生成0到M-1的任意數(shù)L，則mbestj.id=L。同樣記錄下N個(gè)pbest第j維Qj.left和n，計(jì)算n/N，如果大于1/2，表明1出現(xiàn)的次數(shù)大于0出現(xiàn)的次數(shù)，則mbestj.left=1，如果小于1/2，mbestj.left=0，如果等于1/2，則隨機(jī)生成0或1。同理right也是如此。

說(shuō)明2式（3）中，在第t次迭代中，求解第i個(gè)粒子的Pi,j,0≤i≤N-1,1≤j≤M。φ×pbest可以理解為以φ的概率收斂到自身歷史最佳位置pbest，同時(shí)以1-φ的概率收斂到全局最佳位置gbest，需要隨機(jī)產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)r，如果r＜φ,Pi,j=pbesti,j，否則Pi,j=gbestj，并且為了增加收斂速度，取φ=fpbest/(fpbest+fgbest),fpbest、fgbest分別代表每個(gè)粒子歷史最優(yōu)解以及全局最優(yōu)解的適應(yīng)值。

說(shuō)明3式（4）中，表示迭代次數(shù)從第t次到t+1次粒子位置的更新。先定義mbest-Xi可以理解為平均最優(yōu)位置與第i個(gè)解的位置之差，{mbest1,mbest2,…,mbestM}與{Xi,1,Xi,2,…,Xi,M}之差Vi，如果mbestj=Xi,j，則Vi,j取0，表示位置不變，否則取1，表示位置變化，如果Vi,j=0，說(shuō)明在第t+1次位置不更新，保持Pi,j的值不變，如果Vij=1，生成0到1的隨機(jī)數(shù)k。從概率角度，當(dāng)k≥α?xí)r，產(chǎn)生隨機(jī)數(shù)u，如果u≤0.5,Xi,j(t+1)的結(jié)果取值為(Pi,j(t)+10×k)mod(M)，否則結(jié)果取值為|Pi,j(t)-10×k|mod(M)，當(dāng)k＜α?xí)r，保持Pi,j的值不變。

3.3.4 離散量子粒子群布圖優(yōu)化算法的實(shí)現(xiàn)過(guò)程

DQPSO布圖優(yōu)化算法的流程圖如圖8所示。

（1）初始化一棵二叉樹(shù)，并通過(guò)擾動(dòng)方式生成初始種群，種群規(guī)模為N；然后求出這N個(gè)個(gè)體的適應(yīng)值，記錄每一個(gè)適應(yīng)值fpbesti,i取值在0到N-1之間，也就是初始化這N個(gè)個(gè)體的歷史最優(yōu)值；同時(shí)記錄它們的歷史最優(yōu)位置pbesti，選取fpbesti中最優(yōu)的值記為全局最優(yōu)值fgbest，全局最優(yōu)位置為gbest，設(shè)置初始迭代次數(shù)記錄值count為1。

（2）由這N個(gè)個(gè)體的歷史最優(yōu)位置，計(jì)算出平均最佳位置mbest。

（3）根據(jù)fpbesti和fgbest計(jì)算出φ和相應(yīng)的位置Pij。

（4）計(jì)算收縮-擴(kuò)張系數(shù)α，開(kāi)啟每一個(gè)粒子的進(jìn)化過(guò)程，隨機(jī)生成0到1之間的隨機(jī)數(shù)u，更新每一個(gè)粒子位置，驗(yàn)證每一個(gè)位置是否合法，即能否生成一個(gè)新的B*-tree，如果不能，就要修正這個(gè)新位置，使之能構(gòu)成B*-tree。

（5）根據(jù)N個(gè)新解生成的二叉樹(shù)布圖方案，計(jì)算出適應(yīng)值，如果小于這個(gè)解的歷史最優(yōu)值，隨即更新歷史最優(yōu)值和其相應(yīng)位置，如果這個(gè)新值同時(shí)小于已有的全局最優(yōu)值，那么全局最優(yōu)值和其位置也相應(yīng)更新，否則保持原值不變。

（6）查看是否達(dá)到最大的迭代次數(shù)，以及是否達(dá)到設(shè)定的收斂條件，如果達(dá)到則執(zhí)行（8），否則執(zhí)行（7）。

（7）迭代次數(shù)記錄值count加1，執(zhí)行（2）。

Fig.8 DQPSO floorplanning process圖8 離散量子粒子群布圖優(yōu)化流程

（8）迭代結(jié)束，輸出保存的全局最優(yōu)值以及全局最優(yōu)位置也就是最優(yōu)解序列。

4 仿真實(shí)驗(yàn)及分析

4.1 仿真器與仿真環(huán)境

為了驗(yàn)證本文提出的3D NoC離散量子粒子群布圖優(yōu)化算法，采用VNOC3仿真器進(jìn)行仿真。它是在Linux系統(tǒng)下，使用C++語(yǔ)言開(kāi)發(fā)的。仿真實(shí)驗(yàn)的硬件環(huán)境：CPU為Intel?CoreTMi5-4590，主頻為3.30 GHz，內(nèi)存為8 GB的微型計(jì)算機(jī)；采用了VMware虛擬機(jī)以及Centos操作系統(tǒng)。

4.2 實(shí)驗(yàn)用例與仿真過(guò)程

實(shí)驗(yàn)中使用了常用的MCNC（Microelectronics Centre of North-Carolina）典型測(cè)試用例，其屬性值如表1所示。

Table 1 Attribute value of experimental use case表1 實(shí)驗(yàn)用例的屬性值

vnoc3采用Elmore[27]延遲公式來(lái)估算物理鏈路以及IP核與路由間額外鏈路的延遲。為了測(cè)試本文算法的優(yōu)勢(shì)，將基于離散量子粒子群算法的實(shí)驗(yàn)數(shù)據(jù)與基于傳統(tǒng)的模擬退火算法[21,28]、改進(jìn)的基于模擬退火的粒子群算法[29]的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對(duì)比，SA算法初始溫度為1，停止溫度為0.1；PSO與本文使用的DQPSO算法初始種群為100，迭代總次數(shù)為500。

4.3 仿真結(jié)果與分析

4.3.1 微片延遲對(duì)比

3種算法在6種不同的測(cè)試用例中，隨著注入率從20%到100%的變化，平均微片延遲的變化如圖9所示。

由圖9的6張圖可以看出，微片延遲整體隨著注入率增加而增加。6個(gè)測(cè)試用例可以分成3組：（1）IP核數(shù)量較少，如圖（a）、（b）所示的apte、xerox；（2）IP核橫縱相差較大，如圖（c）所示的hp；（3）IP核數(shù)量較多，如圖（d）、（e）、（f）所示的ami25、ami33、ami49。由圖9可見(jiàn)在組（1）中，采用3種算法的微片延遲相差不大，算法優(yōu)勢(shì)不明顯。在組（2）的hp中，在注入率小時(shí)，3種算法的微片延遲基本相同，當(dāng)注入率增大到80%時(shí)，雖然延遲仍然上升，但是DQPSO算法的微片延遲明顯小于其他兩種算法的延遲，在注入率為100%時(shí)，DQPSO算法的微片延遲比傳統(tǒng)SA算法減少了21.85%，比PSO算法減少了53.17%。在組（3）中，都是IP核較多的用例，其中IP核之間通訊較為復(fù)雜，選擇ami49進(jìn)行比較，當(dāng)注入率小于60%時(shí)，3種算法的微片延遲基本相同，當(dāng)注入率大于60%時(shí)，微片延遲明顯上升，但是DQPSO算法的上升速度低于其他兩種算法的上升速度，SA算法與PSO算法的微片延遲基本相同；當(dāng)注入率達(dá)到100%時(shí)，DQPSO算法的微片延遲比SA算法減少了20.63%，比PSO算法減少了23.69%。由以上數(shù)據(jù)分析，組（2）用例和組（3）用例這種網(wǎng)絡(luò)規(guī)模大的情況下，解空間急劇增加，DQPSO算法不是依靠隨機(jī)擾動(dòng)的方法，能快速尋找到較優(yōu)解，減少陷入局部極值，使鏈路長(zhǎng)度和面積更小，使鏈路延遲更短，路由分配更合理。

4.3.2 平均CPU時(shí)間的對(duì)比

3種算法所消耗的CPU平均計(jì)算時(shí)間對(duì)比如圖10所示?？梢钥闯鯯A、PSO和DQPSO算法所消耗的CPU平均計(jì)算時(shí)間在apte、xerox兩個(gè)測(cè)試用例中相差不大，從hp開(kāi)始DQPSO算法的優(yōu)勢(shì)比較明顯，尤其在ami49中，DQPSO算法所消耗的CPU平均計(jì)算時(shí)間比SA算法減少了69.40%，比PSO算法減少了46.55%，是因?yàn)閔p用例中核縱橫比平均值和標(biāo)準(zhǔn)差大。后面3個(gè)用例中，IP核較多，都導(dǎo)致解空間較大，因?yàn)镈QPSO采用種群迭代、粒子聚集的方式，所以收斂速度更快。

4.3.3 算法的穩(wěn)定性分析

同時(shí)隨機(jī)對(duì)3種算法選取了10次實(shí)驗(yàn)結(jié)果，通過(guò)每次實(shí)驗(yàn)結(jié)果的變化趨勢(shì)分析算法的穩(wěn)定性。由于組（1）用例IP核較少，微片延遲較低，每次實(shí)驗(yàn)結(jié)果相差不大，效果不明顯。因此，實(shí)驗(yàn)中選用布圖方案多，結(jié)果性能相差大的用例，如組（2）的hp與組（3）的ami49用例來(lái)分析。

為了更直觀地觀察實(shí)驗(yàn)結(jié)果，本文計(jì)算出每種算法在固定注入率下10次實(shí)驗(yàn)結(jié)果的標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差越接近0，證明結(jié)果的一致性越高。

Fig.9 Latency changes with injection of 3 algorithms in 6 testcases圖9 6種測(cè)試用例中3種算法隨注入率變化的延遲變化

Fig.10 CPU time changes with injection of 3 algorithms in 6 testcases圖10 6種測(cè)試用例中3種算法隨注入率變化的CPU平均時(shí)間變化

hp用例標(biāo)準(zhǔn)差如圖11所示，在開(kāi)始注入率由20%增加到70%的過(guò)程中，10次實(shí)驗(yàn)的結(jié)果一致性較強(qiáng)；但在注入率到達(dá)80%之后，DQPSO算法的標(biāo)準(zhǔn)差明顯低于另外兩種算法；在到達(dá)100%時(shí)，DQPSO算法的標(biāo)準(zhǔn)差比SA算法減少了約95.32%，比PSO算法減少了約74.50%。說(shuō)明當(dāng)測(cè)試用例中IP核長(zhǎng)寬相差較大時(shí)，提高注入率，SA及PSO算法得到的結(jié)果差距大，算法不穩(wěn)定；DQPSO算法更加穩(wěn)定，能得到更準(zhǔn)確的解。

ami49用例標(biāo)準(zhǔn)差如圖12所示，在開(kāi)始注入率由20%增加到50%的過(guò)程中，10次實(shí)驗(yàn)的結(jié)果一致性較強(qiáng)；但在注入率到達(dá)60%之后，DQPSO算法的標(biāo)準(zhǔn)差明顯低于另外兩種算法；在到達(dá)100%時(shí)，DQPSO算法的標(biāo)準(zhǔn)差比SA算法減少了約50.94%，比PSO算法減少了約29.63%。說(shuō)明當(dāng)測(cè)試用例中IP核數(shù)量較多時(shí)，提高注入率DQPSO布圖算法得到的結(jié)果更準(zhǔn)確，更具一般性。

Fig.11 Standard deviation of 3 kinds of algorithms in hp圖11 hp用例中3種算法微片延遲的標(biāo)準(zhǔn)差

Fig.12 Standard deviation of 3 kinds of algorithms in ami49圖12 ami49用例中3種算法微片延遲的標(biāo)準(zhǔn)差

4.3.4 芯片面積對(duì)比

3種算法在MCNC的6種測(cè)試用例下的芯片面積對(duì)比如圖13所示。

如圖13所示，使用DQPSO算法，面積略有下降，但是效果不明顯，apte中DQPSO選擇的芯片面積是SA的89.21%；ami49中DQPSO選擇的芯片面積是SA的94.63%。DQPSO算法對(duì)芯片面積優(yōu)化方面的優(yōu)勢(shì)不大。

5 結(jié)束語(yǔ)

本文提出了一種基于離散量子粒子群算法并與B*-tree編碼方式相結(jié)合的布圖優(yōu)化算法，用以解決異構(gòu)3D NoC芯片的布圖問(wèn)題；根據(jù)布圖問(wèn)題解空間離散化的特點(diǎn)，重新定義了量子粒子群算法的實(shí)現(xiàn)過(guò)程；初始化一個(gè)隨機(jī)可行解的種群，通過(guò)進(jìn)化迭代來(lái)慢慢收斂于全局最優(yōu)解，避免容易陷入局部極值，這樣大大地提高了解的收斂速度，減少了計(jì)算時(shí)間，更快地得到了更優(yōu)的布圖方案。

仿真實(shí)驗(yàn)結(jié)果表明，本文提出的基于DQPSO的布圖算法在IP核較多，IP核形狀長(zhǎng)寬比較大的情況下，微片延遲明顯減少，CPU平均運(yùn)行時(shí)間也大幅減少，同時(shí)算法標(biāo)準(zhǔn)差最小，說(shuō)明DQPSO算法更穩(wěn)定。

在未來(lái)的研究中，可以適當(dāng)增加DQPSO算法中解的多樣性，以便更好地尋找更優(yōu)解；同時(shí)可以把布圖算法引入到3D NoC的功耗、發(fā)熱等性能指標(biāo)驗(yàn)證中，進(jìn)一步提高3D NoC的性能。

[1]Zhang Dakun,Song Guozhi,Lin Huazhou,et al.Double improved genetic algorithm and low power task mapping in 3D networks-on-chip[J].Journal of Computer Research and Development,2016,53(4):921-931.

[2]Yadav S,Laxmi V,Gaur M S.A power efficient dual link mesh NoC architecture to support nonuniform traffic arbitration at routing logic[C]//Proceedings of the 29th International Conference on VLSI Design and 15th International Conference on Embedded Systems,Kolkata,India,Jan 4-8,2016.Washington:IEEE Computer Society,2016:69-74.

[3]Jafri A,Baghdadi A,Najam-Ul-Islam M,et al.Heterogeneous multi-ASIP and NoC-based architecture for adaptive parallel TBICM-ID-SSD[J].IEEE Transactions on Circuits&Systems II Express Briefs,2017,64(3):259-263.

[4]Rezaei S H S,Modarressi M,Daneshtalab M,et al.A threedimensional networks-on-chip architecture with dynamic buffer sharing[C]//Proceedings of the 24th Euromicro Inter-national Conference on Parallel,Distributed,and Network-Based Processing,Heraklion,Greece,Feb 17-19,2016.Washington:IEEE Computer Society,2016:771-776.

[5]Zhou Hongxia,Sham C W,Yao Hailong.Slicing floorplans with handling symmetry and general placement constraints[C]//Proceedings of the 2016 IEEE Computer Society Annual Symposium on VLSI,Tampa,USA,Jul 9-11,2016.Washington:IEEE Computer Society,2014:112-117.

[6]Alpert C J,Mehta D P,Sapatnekar S S.Handbook of algorithms for physical design automation[M].Boston,USA:Auerbach Publications,2008:139-142.

[7]Young F Y,Wong D F,Yang H H.Slicing floorplans with range constraint[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2000,19(2):272-278.

[8]Yuen W S,Young F Y.Slicing floorplan with clustering constraints[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2003,22(5):652-658.

[9]Ma Qiang,Xiao Linfu,Tam Y C,et al.Simultaneous handling of symmetry,common centroid,and general placement constraints[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2011,30(1):85-95.

[10]Chou P Y,Ou H C,Chang Yaowen.Heterogeneous B*-trees for analog placement with symmetry and regularity considerations[C]//Proceedings of the 2011 International Conference on Computer-Aided Design,San Jose,USA,Nov 7-11,2011.Washington:IEEE Computer Society,2011:512-516.

[11]Otten R H J M.Automatic floorplan design[C]//Proceedings of the 19th Design Automation Conference,Las Vegas,USA,Jun 14-16,1982.Piscataway,USA:IEEE,1982:261-267.

[12]Wong D F,Liu C L.A new algorithm for floorplan design[C]//Proceedings of the 23rd ACM/IEEE Design Automation Conference,Las Vegas,USA,Jun 29-Jul 2,1986.Piscataway,USA:IEEE,1986:101-107.

[13]Murata H,Fujiyoshi K,Nakatake S,et al.Rectangle-packingbased module placement[C]//Proceedings of the 1995 International Conference on Computer-Aided Design,San Jose,USA,Nov 5-9,1995.Washington:IEEE Computer Society,1995:535-548.

[14]Nakatake S,Fujiyoshi K,Murata H,et al.Module placement on BSG-structure and IC layout applications[C]//Proceedings of the 1996 International Conference on Computer-Aided Design,San Jose,USA,Nov 10-14,1996.Washington:IEEE Computer Society,1996:484-491.

[15]Lin Jaiming,Chang Yaowen.TCG:a transitive closure graphbased representation for non-slicing floorplans[C]//Proceedings of the 38th Annual Design Automation Conference,Las Vegas,USA,Jun 18-22,2001.New York:ACM,2001:764-769.

[16]Zhou Hai,Wang Jia.ACG-adjacent constraint graph for general floorplans[C]//Proceedings of the 30th International Conference on Computer Design,San Jose,USA,Oct 11-13,2004.Washington:IEEE Computer Society,2004:572-575.

[17]Guo Peining,Takahashi T,Cheng C K,et al.Floorplanning using a tree representation[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2001,20(2):281-289.

[18]Chen T C,Chang Yaowen.Modern floorplanning based on B*-tree and fast simulated annealing[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2006,25(4):637-650.

[19]Vorwerk K,Kennings A,Greene J W.Improving simulated annealing-based FPGA placement with directed moves[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2009,28(2):179-192.

[20]Chen Guolong,Guo Wenzhong,Cheng Hongju,et al.VLSI floorplanning based on particle swarm optimization[C]//Proceedings of the 3rd International Conference on Intelligent System and Knowledge Engineering,Xiamen,China,Nov 17-19,2008.Piscataway,USA:IEEE,2008:1020-1025.

[21]Paulo V D,Cristinel A.3D network-on-chip architectures using homogeneous meshes and heterogeneous floorplans[J].International Journal of Reconfigurable Computing,2010:603059.

[22]Chang Y C,Chang YW,Wu G M,et al.B*-trees:a new representation for non-slicing floorplans[C]//Proceedings of the 37th Annual Design Automation Conference,Los Angeles,USA,Jun 5-9,2000.New York:ACM,2000:458-463.

[23]Garey M R,Johnson D S.Computers and intractability:a guide to the theory of NP-completeness[M].New York:W H Freeman&Company,1979:8-10.

[24]Sun Jun,Feng Bin,Xu Wenbo.Particle swarm optimization with particles having quantum behavior[C]//Proceedings of the Congress on Evolutionary Computation,Portland,USA,Jun 19-23,2004.Piscataway,USA:IEEE,2004:1571-1580.

[25]Sun Jun.Research on quantum behaved particle swarm optimization algorithm[D].Wuxi:Jiangnan University,2009.

[26]Yang Chuanjiang,Liu Qing,Huang Zhen.One method of improving quantum-behaved particle swarm optimization[J].Computing Technology andAutomation,2009,28(1):100-103.

[27]Rabaey J M.Digital integrated circuits:a design perspective[M].Upper Saddle River,USA:Prentice Hall,1996:274-278.

[28]Wang Lianlian.Research on the routing algorithm of the network routing algorithm based on the heterogeneous layout[D].Tianjin:Tianjin Polytechnic University,2013.

[29]Song Guozhi,Zhang Dakun,Tu Yao,et al.Improved algorithm for 3D NoC floorplan based on particle swarm optimization[J].Computer Science,2015,42(7):114-117.

附中文參考文獻(xiàn)：

[1]張大坤,宋國(guó)治,林華洲,等.二次改進(jìn)遺傳算法與3D NoC低功耗映射[J].計(jì)算機(jī)研究與發(fā)展,2016,53(4):921-931.

[25]孫俊.量子行為粒子群優(yōu)化算法研究[D].無(wú)錫:江南大學(xué),2009.

[26]楊傳將,劉清,黃珍.一種量子粒子群算法的改進(jìn)方法[J].計(jì)算技術(shù)與自動(dòng)化,2009,28(1):100-103.

[28]王蓮蓮.基于異構(gòu)布局的三維片上網(wǎng)絡(luò)路由算法的研究[D].天津:天津工業(yè)大學(xué),2013.

[29]宋國(guó)治,張大坤,涂遙,等.一種改進(jìn)的基于粒子群的三維片上網(wǎng)絡(luò)優(yōu)化布局算法[J].計(jì)算機(jī)科學(xué),2015,42(7):114-117.

Research on Floorplanning Algorithm Based on Discrete Quantum Particle Swarm Optimization in Three Dimensional Network-on-Chip*

WAN Yijun,ZHANG Dakun+,ZHENG Yazhen

School of Computer Science&Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China

2016-10,Accepted 2016-12.

The performance of three dimensional network-on-chip is much better than that of two dimensional networkon-chip in many aspects,so that it has become a hot research topic.The floorplanning algorithm directly affects the chip size,wiring length,and becomes the significant direction of the optimization design in three dimensional networkon-chip.This paper proposes a floorplanning optimization algorithm based on discrete quantum-behaved particle swarm algorithm.Compared with the simulated annealing algorithm commonly used in the previous research,this algorithm initializes the random population and uses the evolutionary way,instead of using a local single solution perturbation method to get solution space,so it has better search ability and faster convergence speed.Simulation results show that using this algorithm can select floorplanning scheme which can reduce flit latency and save CPU computing time.It has significant effect especially in test cases which has more IP cores and high injection rate.In ami49 experiment with 100%of the injection rate,compared with the simulated annealing algorithm,the average flit latency of this algorithm reduces 20.63%;while the average CPU time of this algorithm reduces 69.40%.

three dimensional network-on-chip;floorplanning algorithm;B*-tree;discrete quantum-behaved particle swarm optimization;simulated annealing;particle swarm optimization

+Corresponding author:E-mail:zhangdakun2002@163.com

10.3778/j.issn.1673-9418.1610016

*The National Natural Science Foundation of China under Grant No.61272006(國(guó)家自然科學(xué)基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-12-07,http://www.cnki.net/kcms/detail/11.5602.TP.20161207.0922.012.html

WAN Yijun,ZHANG Dakun,ZHENG Yazhen.Research on floorplanning algorithm based on discrete quantum particle swarm optimization in three dimensional network-on-chip.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1953-1964.

A

TP393

WAN Yijun was born in 1988.She is an M.S.candidate at Tianjin Polytechnic University.Her research interests include 3D network on chip and its floorplanning algorithm.

萬(wàn)逸君（1988—），女，天津工業(yè)大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)槿S片上網(wǎng)絡(luò)和片上網(wǎng)絡(luò)布圖算法。

ZHANG Dakun was born in 1960.She received the Ph.D.degree in computer application technology from Northeastern University in 2004.Now she is a professor and Ph.D.supervisor at Tianjin Polytechnic University.Her research interests include network on chip,combinational algorithm and virtual reality technology.

張大坤（1960—），女，遼寧阜新人，2004年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為天津工業(yè)大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)槠暇W(wǎng)絡(luò)，組合算法，虛擬現(xiàn)實(shí)技術(shù)。

ZHENG Yazhen was born in 1989.He is an M.S.candidate at Tianjin Polytechnic University.His research interests include 3D network on chip and topology.

鄭亞振（1989—），男，天津工業(yè)大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)槿S片上網(wǎng)絡(luò)和片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。