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

作     者：万逸君 

作者单位：天津工业大学 

学位级别：硕士

导师姓名：张大坤

授予年度：2017年

学科分类：080903[工学-微电子学与固体电子学] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

主      题：三维片上网络 布图算法 B*-tree 离散量子粒子群算法 

摘      要：随着片上网络的发展和芯片规模的扩大,二维片上网络(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%。