Research And Optimization Of FPGA Placement Algorithm

FPGA because of its short development cycle, flexibility and many other advantages, has become one of the world's most widely used semiconductor devices. In the FPGA EDA flow, the placement is a very important aspect, often used to strike an approximate optimal solution with simulated annealing algorithm. But with the increasing scale of integrated circuit, the drawback of traditional simulated annealing algorithm has became more and more obvious, and some attempt to improve placement efficiency often lead to low quality.Based on the traditional simulated annealing algorithm, we propose a modified algorithm called very fast simulated annealing tempering algorithm. Our algorithm combines very fast simulated re-annealing algorithm and simulation tempering algorithm. First, our algorithm introduce very fast simulated re-annealing algorithm, the algorithm drops its temperature in an exponential way, after a short random process in the high temperature, the algorithm quickly falls into the temperature range where to search the globally optimal solution well, thus saving a lot of time and speed up the annealing process. Then, we introduce simulation tempering algorithm in the low temperature, this algorithm regards temperature as a variable, when the temperature changes, it could drop, may remain unchanged, or even increased, so to stretch the temperature sequences, thereby increasing the search times in low temperature phase, so that the algorithm can achieve a higher probability of convergence to the global optimal solution. Our algorithm finally improves the placement efficiency while improving the quality. Simulation results show that, compare with the traditional simulated annealing algorithm, very fast annealing tempering algorithm got 11.22% improving in placement efficiency, 1.91% improving in critical path delay, and 0.16% improving in total wire length.