摘要: 基于模拟退火的现场可编程门阵列(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
中图分类号:
任小西,吴楚,丁宇. 基于VPR的FPGA布局算法时延改进[J]. 计算机工程, 2014, 40(12): 302-305.
REN Xiaoxi,WU Chu,DING Yu. Time Delay Improvement of FPGA Placement Algorithm Based on VPR[J]. Computer Engineering, 2014, 40(12): 302-305.