作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2014, Vol. 40 ›› Issue (12): 302-305. doi: 10.3969/j.issn.1000-3428.2014.12.057

• 开发研究与工程应用 • 上一篇    下一篇

基于VPR的FPGA布局算法时延改进

任小西1,吴楚1,丁宇2   

  1. 1.湖南大学信息科学与工程学院,长沙 410082; 2.三一汽车起重机械有限公司,长沙 410600
  • 收稿日期:2014-01-02 修回日期:2014-02-20 出版日期:2014-12-15 发布日期:2015-01-16
  • 作者简介:任小西(1978-),女,副教授、博士,主研方向:嵌入式计算;吴 楚、丁 宇,硕士。
  • 基金资助:
    国家自然科学基金资助项目(61173037);湖南大学青年教师成长计划基金资助项目。

Time Delay Improvement of FPGA Placement Algorithm Based on VPR

REN Xiaoxi1,WU Chu1,DING Yu2   

  1. 1.School of Information Science and Engineering,Hunan University,Changsha 410082,China;
    2.Sany Mobile Crane Machinery Co.,Ltd.,Changsha 410600,China
  • Received:2014-01-02 Revised:2014-02-20 Online:2014-12-15 Published:2015-01-16

摘要: 基于模拟退火的现场可编程门阵列(FPGA)布局算法在计算关键度时存在一定的偏差。为此,提出一种FPGA布局时延改进算法。利用不同的模拟退火温度和交换接收率,以及前后2次布局的时延代价差,对FPGA布局的时延代价进行补偿。通过增加时延补偿模块来调整布局的代价函数,达到重新寻找布局过程中被遗弃的较优解的目的。实验结果表明,在MCNC基准电路上使用改进算法,布局的时延代价和线网代价分别比改进前的算法减少19.2%和0.5%。此外,电路的关键路径时延也得到了不同程度的改善,使得布局质量在各个方面都明显优于优化前的通用布局布线算法。

关键词: 现场可编程门阵列, 模拟退火算法, 关键路径时延, 关键度, 布局, 通用布局布线算法

Abstract: There is some degree of error during the calculation of the critical in Field Programmable Gate Array(FPGA) placement algorithm based on simulated annealing.In order to solve this problem,a new FPGA placement algorithm is proposed.The improved algorithm can find a better placement that is discarded previously by adding a delay compensation module which leverages the information such as the different annealing temperature,the every exchange success rate under different temperatures,and the difference of delay cost between two successive placements.The new algorithm is implemented and tested on several MCNC benchmark circuits.Experimental results show that,the delay cost and the wire cost are reduced by 19.2% and 0.5%.Besides,the critical path delay of the circuits is improved at different levels,thus making the quality of placement significantly higher than the original Versatile Place and Route(VPR) placement algorithm.

Key words: Field Programmable Gate Array(FPGA), simulated annealing algorithm, critical path time delay, critical degree, placement, Versatile Place and Route(VPR) algorithm

中图分类号: