FPGA布局算法研究和优化

发布时间：2018-05-25 03:10

本文选题：现场可编程门阵列 + 布局　；参考：《西安电子科技大学》2015年硕士论文

【摘要】：FPGA因为其开发周期短、灵活性强等诸多优点,已成为当今世界应用最为广泛的半导体器件之一。在FPGA EDA流程中,布局是非常重要的一个环节,通常使用模拟退火算法来求取一个近似最优解。但在集成电路规模日益增大的当下,传统的模拟退火算法在布局效率上越来越不能让人满意,而一些试图提高布局效率的算法往往又导致布局质量降低。本文以传统的模拟退火算法为基础,提出一种改进型的布局算法,称为超快速退火回火算法。该算法将超快速模拟重复退火和模拟回火相结合,首先在高温时利用超快速模拟重复退火温度指数下降的特点,在进行短暂的高温随机过程后,立刻使算法进入到适合搜索全局最优解的温度,这样就节省了大量时间,加速了算法的运行。随后在低温的过程中又引入模拟回火过程,这时候温度被当作一个变量,在每一次温度更新时,不仅可以下降,还可以保持不变,甚至可以上升到温度序列的上一个温度,这样整个温度序列就会被拉长,从而增加低温阶段的搜索,使得算法可以以更高的概率向全局最优解收敛。这样一个在高温时加速,低温时增加搜索次数的方式在总体上使得算法在提升布局效率的同时提高了布局的质量。仿真实验表明,超快速回火退火算法与传统的模拟退火算法相比在布局效率方面提升11.22%,在关键路径延时方面优化1.91%,在总线长方面优化0.16%。
[Abstract]:FPGA has become one of the most widely used semiconductor devices in the world because of its advantages of short development period and strong flexibility. Layout is a very important part of FPGA EDA process. Simulated annealing algorithm is usually used to find an approximate optimal solution. However, with the increasing scale of integrated circuits, the traditional simulated annealing algorithm is more and more unsatisfactory in layout efficiency, and some algorithms that try to improve layout efficiency often lead to poor layout quality. Based on the traditional simulated annealing algorithm, an improved layout algorithm is proposed in this paper, which is called super-fast annealing tempering algorithm. The algorithm combines ultra-fast simulated repeated annealing with simulated tempering. Firstly, at high temperature, the characteristic of decreasing temperature exponent of ultra-fast simulated repeated annealing is used, after a short period of high temperature random process, The algorithm is immediately entered into the temperature suitable for searching the global optimal solution, which saves a lot of time and speeds up the operation of the algorithm. Then a simulated tempering process is introduced in the process of low temperature, where the temperature is treated as a variable, which can not only decrease, but also remain unchanged, or even rise to the last temperature in the temperature series, each time the temperature is renewed. In this way, the whole temperature sequence will be elongated, thus increasing the search at the low temperature stage, so that the algorithm can converge to the global optimal solution with a higher probability. Such a way of accelerating at high temperature and increasing search times at low temperature makes the algorithm improve the layout efficiency while improving the quality of the layout. The simulation results show that compared with the traditional simulated annealing algorithm, the ultra-fast tempering annealing algorithm improves the layout efficiency by 11.22 points, optimizes the critical path delay by 1.91, and optimizes the bus length by 0.16.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN791;TP18

【参考文献】