基于VPR的FPGA布局算法研究与改进

作     者：祁火林 

作者单位：武汉理工大学 

学位级别：硕士

导师姓名：徐宁

授予年度：2009年

学科分类：080902[工学-电路与系统] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

主      题：布局 现场可编程门阵列 电子设计自动化 VPR 

摘      要：FPGA是八十年代中期出现的新型可编程逻辑器件,在FPGA芯片设计研究上,现有的布局算法日渐成熟,但仍然存在很多问题。布局布线是FPGA芯片设计中最耗时的阶段,能够设计出更加快速、更小面积、时延少、低功耗的算法是学术界研究的热点和趋势。广泛应用于学术界研究的VPR软件是一款FPGA布局布线的通用软件,它提出了相对较完整的布局布线方法的解决方案。VPR布局算法使用的是模拟退火法,模拟退火法的优点是能跳出迭代过程中的局部最优解而得到接近于全局的最优解,但缺点是需花费较长的时间。 为解决FPGA的布局问题,本文以VPR为基础,提出和实践了快速模拟退火算法布局法,推广型模拟退火算法布局法,力矢量退火算法布局法,渐升温回火退火算法布局法。与经典模拟退火算法相比,快速模拟退火算法模型的接收概率是按广义Gibbs分布给出的,其扰动模型类似Cauchy分布,降温方式为T(K)=TaK),采用新的模型收敛速度更快。推广型模拟退火算法也是以广义Gibbs分布为基础,扰动模型为Tsallis-Stariolo跃迁分布形式,它在目标函数多,局域极小值也较多时比经典模拟退火算法更为有效。经典模拟退火算法和快速模拟退火算法都是推广型模拟退火算法的特例。力矢量混合退火算法布局是把力矢量松弛法和模拟退火法结合起来的布局方法,力矢量松弛法的核心是每次交换时与当前单元受力最小的理想位置交换,结合模拟退火法就是用模拟退火法的接受策略来判断是否接受交换后的解。渐升温回火退火算法改变退火的降温策略,先用较低的温度退火,把优化后的解作为下一次退火的初始解,初始温度逐渐上升,反复执行退火策略得到最后结果。 实验结果表明,与VPR相比,在大规模电路布局中:快速模拟退火算法可以提高速度为原来的1.9倍,但是布局质量下降4%;推广型模拟退火算法可以提高速度为原来的6.3倍,但是布局质量下降15%左右;力矢量混合退火算法基本没有改变效果;渐升温回火退火算法可以提高速度为原来的3倍,而且布局质量不下降。上述算法在FPGA的布局速度方面做出了一定的改进。