Research Of Hybrid Optimization Algorithm For FPGA Placement

With the rapid development of integrated circuits,FPGA scale continues to expand,the complexity of FPGA chip is also increasing.However the Electronic Design Automation(EDA)Tool also meets greater challenges.The main function of FPGA placement is to determine the physical location of the logical components in the chip to map the logical unit in the netlist file that we get in the synthesis phase under the optimize target with the actual physical coordinates of the FPGA chip.The wire length of the chip is closely related to the power consumption,delay,performance as well as other aspects of the chip.How to reduce the total length of the interconnection wires with less time and ensure the placement quality is the critical problem to be considered in the placement algorithm.This thesis takes into account the running time and placement quality of the placement algorithm.Through the research and analysis of the current mainstream FPGA placement algorithm,the following main work is done:(1)The advantages and disadvantages of several algorithms are compared,according to the complex structural characteristics of modern FPGA with a variety of logic resources.The placement of the logic unit is established based on the local box netlist.Compared with the traditional netlist,it guarantees a fixed combination of specific logic,and not to reduce the number of feasible solutions of placement.In contrast to the concept of physical coordinate system,a logical coordinate system is established to classify different types of logical units on different level.(2)Based on the chip architecture of XILINX Virtex-5 series,a fast placement algorithm is proposed in this thesis.Combining the quadratic analytic algorithm with the simulated annealing algorithm,we utilize the advantages of both algorithms and apply them in global layout and local optimization separately.We optimize the traditional quadratic analytic algorithm to reduce the total length of the bus.By adding a pseudo-fixed point as a force vector,we get a pseudo-network,which produces a tension for the logic unit that needs to move.According to the virtual boundary smoothing movement module to achieve the expansion and contraction of the second analytic algorithm,we complete the global layout.Logical units in the chip can quickly expand which allow a small amount of overlap between them,and then through the breadth search for the global placement results,and legalized those illegal logic units with small overlap or signal mismatch.(3)Based on the low temperature simulated annealing algorithm,the algorithm is locally optimized by BLE level.Compared with the traditional simulated annealing algorithm,the algorithm starts directly from low temperature and shortens the exchange radius of neighborhood solution,which greatly accelerates the annealing speed.Moreover,the process of simulated tempering is introduced,it increase the temperature and the range and frequency of the low temperature search,so that the algorithm is closer to the global optimal solution.The results show that the algorithm is of higher quality than simulated annealing and quadratic analytic algorithms,and the speed is faster than simulated annealing,and it can get a good trade-off between time and performance which can hopefully be applied to reality Industry successfully.