A Fast FPGA Placement Algorithm Based On Quantum Evolutionary Algorithm

With the rapid development of integrated circuit technology and ever-changing demand of applications, reconfigurable computing has become a hot research topic of microelectronics and computer science research field. FPGA (Field Programmable Gate Array), a fine-grained reconfigurable architecture for general purpose computing, is a widely used programmable device. With the continuous development of integrated circuit technology, the scale of FPGA chip becomes larger and larger. This trend brings great challenges to FPGA CAD software. Placement, which is an important part of FPGA CAD tool, determines the locations for blocks mapped on FPGA and therefore makes great impact on the performance of the final result. Meanwhile, placement is one of the most time-consuming procedures in FPGA CAD tool. Therefore, faster placement will contribute to the improvement of efficiency in FPGA physical design.In this paper, a survey on the recent development of FPGA placement is conducted at first. Then a fast placement algorithm which is based on quantum evolutionary algorithm is proposed. This algorithm supports both timing and wire length optimization for island style FPGAs. The innovative work of this algorithm is as follows. First, divide blocks into groups using the connections information of input circuit. Then quantum probabilistic model is set up for groups. After that, improvements for quantum evolutionary algorithm have been made to generate a fast global placement. Finally, quality of placement result will be further improved with a low-temperature simulated annealing algorithm.This proposed algorithm has been implemented and embedded in VPR, which is academic open-source FPGA back-end software. Experimental results demonstrate that compared with simulated annealing algorithm in VPR, the proposed algorithm achieves similar high quality of placement result while speed has been improved by 83%. Besides, the proposed algorithm supports open objective function which is of practical value in real FPGA physical design.