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

萬逸君，張大坤，鄭亞振

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

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

萬逸君，張大坤+，鄭亞振

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

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

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

1 引言

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

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

Fig.1 Slicing structure and its cutting tree圖1 二分結構及其對應的切割樹

Fig.2 None slicing structure圖2 非二分結構

在計算機中，需要使用表示布圖的編碼方法，即使用一個數(shù)字或者字母的序列來表示一種布圖方案。二分結構常使用的表示法有二叉樹[11]及正則波蘭表達式[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]以及基于模擬退火改進的粒子群算法的布圖算法。分析現(xiàn)有的這些算法可知，它們都通過單一解擾動方式獲得下一個可行解，收斂速度較慢。當三維片上網(wǎng)絡規(guī)模增大、結構復雜度增加時，布圖可行方案數(shù)會急劇增加，解的擾動次數(shù)也隨之增加，求解時間將大幅度增加，因而導致求解效率顯著下降。為了提高求解效率等，本文提出一種基于離散粒子群算法的三維片上網(wǎng)絡布圖優(yōu)化算法，該算法采用初始化隨機種群并不斷迭代的進化方式，具有更優(yōu)的搜索能力和更快的收斂速度。

2 基本設計

2.1 3D NoC架構和設計流程

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

Fig.3 Atask graph mapping 3 layer structure圖3 一個任務圖映射3層結構

這種3層結構保持了網(wǎng)絡層的規(guī)則性，使3D NoC的整體設計更加簡單，設計流程如圖4所示。

Fig.4 3D NoC design process圖4 3D NoC設計流程

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

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

（3）在3個布圖方案中，為每層IP核分配路由器。首先將第2層設置為R×R標準mesh結構，保證至少每一個IP核都能分配到一個路由器（稱之為直接拓撲），并不是每一個IP核都能連接上垂直方向的路由器，因此有的IP核需要使用額外的鏈路來連接路由器，這些額外鏈路也會影響微片的延遲，vnoc3中將此問題看作一個線性分配問題，應用Kuhn-Munkres算法來解決。

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

對ami33測試用例使用這種設計結構，其中的一種布圖方案如圖5所示，mesh中的紅色路由器表示沒有連接IP核，路由器上的斜線表示額外鏈路。

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

2.2.1 B*-tree編碼表示法

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

布圖中模塊Mi與B*-tree中的節(jié)點Ni一一對應，定義B*-tree的節(jié)點和B*-tree結構為：

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

Fig.5 Layout and topology scheme of ami33 using 3 layer structure圖5 使用3層結構的ami33的一種布圖和拓撲方案

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

Fig.6 Feasible floorplanning and its corresponding B*-tree圖6 可行布圖方案及其對應的B*-tree

（1）根節(jié)點對應整個布圖最左下角模塊，其坐標(xroot,yroot)=(0,0)。

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

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

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

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

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

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

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

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

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

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

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

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

3.1 目標函數(shù)選取

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

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

3.2 標準量子粒子群優(yōu)化算法

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

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

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

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

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

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

3.3.1 粒子結構的定義

為了結合量子粒子群算法的特點，方便粒子進化操作，本文定義的粒子結構為：

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

3.3.2 初始種群的生成

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

（1）旋轉節(jié)點。隨機選取節(jié)點，如果節(jié)點有可旋轉標志，此時交換模塊的寬和高。

（2）交換節(jié)點。隨機選取兩個節(jié)點，并交換它們的位置，對應的模塊布圖位置也相應交換。

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

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

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

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

3.3.3 粒子進化操作說明

已有QPSO算法的進化公式不適用于本文定義的與B*-tree相對應的離散解的結構，需要對一系列的進化操作重新解釋說明，說明如下。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實驗及分析

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

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

4.2 實驗用例與仿真過程

實驗中使用了常用的MCNC（Microelectronics Centre of North-Carolina）典型測試用例，其屬性值如表1所示。

Table 1 Attribute value of experimental use case表1 實驗用例的屬性值

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

4.3 仿真結果與分析

4.3.1 微片延遲對比

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

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

4.3.2 平均CPU時間的對比

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

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

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

為了更直觀地觀察實驗結果，本文計算出每種算法在固定注入率下10次實驗結果的標準差，標準差越接近0，證明結果的一致性越高。

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

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

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

ami49用例標準差如圖12所示，在開始注入率由20%增加到50%的過程中，10次實驗的結果一致性較強；但在注入率到達60%之后，DQPSO算法的標準差明顯低于另外兩種算法；在到達100%時，DQPSO算法的標準差比SA算法減少了約50.94%，比PSO算法減少了約29.63%。說明當測試用例中IP核數(shù)量較多時，提高注入率DQPSO布圖算法得到的結果更準確，更具一般性。

Fig.11 Standard deviation of 3 kinds of algorithms in hp圖11 hp用例中3種算法微片延遲的標準差

Fig.12 Standard deviation of 3 kinds of algorithms in ami49圖12 ami49用例中3種算法微片延遲的標準差

4.3.4 芯片面積對比

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

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

5 結束語

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

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

在未來的研究中，可以適當增加DQPSO算法中解的多樣性，以便更好地尋找更優(yōu)解；同時可以把布圖算法引入到3D NoC的功耗、發(fā)熱等性能指標驗證中，進一步提高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.

附中文參考文獻：

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

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

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

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

[29]宋國治,張大坤,涂遙,等.一種改進的基于粒子群的三維片上網(wǎng)絡優(yōu)化布局算法[J].計算機科學,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(國家自然科學基金).

CNKI網(wǎng)絡優(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.

萬逸君（1988—），女，天津工業(yè)大學碩士研究生，主要研究領域為三維片上網(wǎng)絡和片上網(wǎng)絡布圖算法。

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年于東北大學獲得博士學位，現(xiàn)為天津工業(yè)大學教授、博士生導師，主要研究領域為片上網(wǎng)絡，組合算法，虛擬現(xiàn)實技術。

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è)大學碩士研究生，主要研究領域為三維片上網(wǎng)絡和片上網(wǎng)絡拓撲結構。