基于量子粒子群的三维片上网络布图优化算法研究

发布时间：2018-03-07 00:13

本文选题：三维片上网络　切入点：布图算法　出处：《天津工业大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着片上网络的发展和芯片规模的扩大,二维片上网络(Two-dimensional Network-on-Chip,2DNoC)在布图面积、布线长度、封装密度以及功耗等方面都已达到了瓶颈,三维片上网络(Three-dimensional Network-on-Chip,3D NoC)应运而生,并在多种性能上均优于二维片上网络。其中,为了充分发挥3D NoC的空间优势,如何放置电子元件和模块的布图算法成为3D NoC设计过程的重要环节,布图算法直接影响芯片的面积和布线长度,同时对通信微片延迟、CPU计算时间等均有较大影响。因此,三维片上网络布图算法逐渐成为一个重要的研究方向。模拟退火算法是三维片上网络布图问题中最常使用方法,另外基于模拟退火改进的粒子群算法也常被应用于三维片上网络布图中,以上两类算法都是采用单一解扰动方式得到下一个可行解,故其收敛速度较慢。当三维片上网络规模增大、结构复杂度增加时,布图可行方案数急剧增加,解的扰动次数也随之增加,求解时间将大幅度增加。本文提出一种基于离散量子粒子群算法的三维片上网络布图优化算法,该算法采用初始化种群并不断迭代的进化方式,具有更优的搜索能力和更快的收敛速度;为了适当增加解的多样性本文又进一步改进。仿真结果表明,采用离散量子粒子群算法选择布图方案可以显著降低微片延迟、节省CPU计算时间,尤其是在IP核数量众多的测试用例和高注入率情况下效果更为明显,如对于ami49测试用例当注入率为100%时,基于离散量子粒子群算法的平均微片延迟比基于模拟退火算法的平均微片延迟减少了 20.63%;基于离散量子粒子群算法所消耗的CPU平均时间比基于模拟退火算法的CPU平均时间减少了69.40%;改进后的离散量子粒子群算法适当减缓了进化速度,进一步提高了最优解的质量,在ami49中最优解的适应值比原离散量子粒子群算法减少12.55%。
[Abstract]:With the development of the on-chip network and the expansion of the chip scale, Two-dimensional Network-on-ChipH2DNoC has reached a bottleneck in layout area, wiring length, package density and power consumption. Three-dimensional Network-on-Chipfen 3D NoC (3D NoC) has emerged as the times require. In order to give full play to the spatial advantages of 3D NoC, how to place the layout algorithm of electronic components and modules becomes an important part of 3D NoC design process. The layout algorithm directly affects the chip area and wiring length, and also has a great impact on the CPU computing time of the communication microchip delay. The algorithm of 3D on-chip network layout is becoming an important research direction. Simulated annealing algorithm is the most commonly used method in the problem of 3D on-chip network layout. In addition, the improved particle swarm optimization algorithm based on simulated annealing is also often used in 3D on-chip network layout. Both of the above two kinds of algorithms are used to obtain the next feasible solution by using a single unperturbed method. Therefore, the convergence rate is slow. When the scale of the 3D on-chip network increases and the structural complexity increases, the number of feasible solutions increases sharply, and the number of perturbations of the solution increases. In this paper, we propose a new algorithm based on discrete Quantum Particle Swarm Optimization (DQPSO), which is based on discrete Quantum Particle Swarm Optimization (DQPSO). It has better searching ability and faster convergence speed. In order to increase the diversity of solution properly, the simulation results show that using discrete quantum particle swarm optimization algorithm to select layout scheme can significantly reduce the delay of microchip. Save CPU computing time, especially in the case of large number of test cases with IP cores and high injection rate, for example, for ami49 test cases, when the injection rate is 100, The average microchip delay based on discrete Quantum Particle Swarm Optimization (DQPSO) is 20.63 lower than that based on simulated annealing (SA), and the average CPU time consumed by DQPSO is higher than that of CPU based on simulated annealing (SA). The average time is reduced by 69.40; the improved discrete quantum particle swarm optimization algorithm slows down the evolution. The quality of the optimal solution is further improved. The fitness of the optimal solution in ami49 is 12.55 less than that of the original discrete quantum particle swarm optimization algorithm.
【学位授予单位】：天津工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN47

【相似文献】