基于量子粒子群的三維片上網(wǎng)絡(luò)布圖優(yōu)化算法研究.pdf

1、隨著片上網(wǎng)絡(luò)的發(fā)展和芯片規(guī)模的擴大，二維片上網(wǎng)絡(luò)(Two-dimensional Network-on-Chip，2D NoC)在布圖面積、布線長度、封裝密度以及功耗等方面都已達(dá)到了瓶頸，三維片上網(wǎng)絡(luò)(Three-dimensional Network-on-Chip，3D NoC)應(yīng)運而生，并在多種性能上均優(yōu)于二維片上網(wǎng)絡(luò)。其中，為了充分發(fā)揮3D NoC的空間優(yōu)勢，如何放置電子元件和模塊的布圖算法成為3D NoC設(shè)計過程的重要環(huán)節(jié)，布

2、圖算法直接影響芯片的面積和布線長度，同時對通信微片延遲、CPU計算時間等均有較大影響。因此，三維片上網(wǎng)絡(luò)布圖算法逐漸成為一個重要的研究方向。
　　模擬退火算法是三維片上網(wǎng)絡(luò)布圖問題中最常使用方法，另外基于模擬退火改進(jìn)的粒子群算法也常被應(yīng)用于三維片上網(wǎng)絡(luò)布圖中，以上兩類算法都是采用單一解擾動方式得到下一個可行解，故其收斂速度較慢。當(dāng)三維片上網(wǎng)絡(luò)規(guī)模增大、結(jié)構(gòu)復(fù)雜度增加時，布圖可行方案數(shù)急劇增加，解的擾動次數(shù)也隨之增加，求解時間將大幅

3、度增加。本文提出一種基于離散量子粒子群算法的三維片上網(wǎng)絡(luò)布圖優(yōu)化算法，該算法采用初始化種群并不斷迭代的進(jìn)化方式，具有更優(yōu)的搜索能力和更快的收斂速度;為了適當(dāng)增加解的多樣性本文又進(jìn)一步改進(jìn)。仿真結(jié)果表明，采用離散量子粒子群算法選擇布圖方案可以顯著降低微片延遲、節(jié)省CPU計算時間，尤其是在IP核數(shù)量眾多的測試用例和高注入率情況下效果更為明顯，如對于ami49測試用例當(dāng)注入率為100％時，基于離散量子粒子群算法的平均微片延遲比基于模擬退火算法