三维片上网络离散量子粒子群布图算法研究

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

三维片上网络在多种性能上均优于二维片上网络,已成为研究热点。布图算法直接影响芯片的面积和布线长度,成为三维片上网络优化设计的重要方向。提出一种基于离散粒子群算法的三维片上网络布图优化算法,与之前常使用的模拟退火算法相比,不再使用单一解局部扰动的方式得到整个解空间,该算法采用初始化随机种群并不断迭代的进化方式,具有更优的搜索能力和更快的收敛速度。仿真结果表明,采用该算法选择布图方案可以显著降低微片延迟,节省CPU计算时间,尤其是在IP核数量众多的测试用例和高注入率情况下效果更为明显,如对于ami49测试用例当注入率为100%时,基于离散量子粒子群算法的结果和基于模拟退火算法的结果相比,平均微片延迟减少了20.63%,CPU平均时间减少了69.40%。

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%.