The Research And Design Of FPGA Placement Algorithm

Since FPGA (Field Programmable Gate Array) has the characteristics of high integration, rich logical resource, flexible design and a widely usage, it has been widely used in the design of digital systems. FPGA design flow includes design entry, logic synthesis, logic optimization, technology mapping, packing, placement and routing. In the flow of FPGA design, the placement is extremely important because it directly affects the quality of routing and the performance of whole circuit. Routing resources account for over 60% of overall resources in FPGA chips, so how to do a reasonable estimation for the routing resource and effectively reduce the routing congestion becomes an important research direction for placement algorithm.The research of placement algorithm based on routing congestion is divided into two aspects. The first aspects is how to adapt the existing optimization algorithm to FPGA architecture and merge routing congestion function into the algorithm structure, so as to achieve the reduction of routing congestion in the placement.Secondly, the research has been focusing on the routing congestion estimation model. In these algorithms, the routing congestion estimation model can accurately estimate the routing resource utilization.Then the cost of routing congestion as a part of the cost function can guide the placement algorithm for reducing the use of routing resources.This thesis carried out a detailed analysis on the main placement algorithm based on routing congestion, including partition-based algorithm, simulated annealing algorithm, genetic algorithm and ant colony algorithm. With the comparison of these optimization algorithms, ACO(Ant Colony Optimization) is applied to FPGA placement considering routing congestion. Experiments show that ACO-based placement algorithm can obtain better results than that of VPR.Routing congestion estimation model is very important for placement algorithm. We proposed a equiprobable-estimation model based on bounding box structure. Experimental results demonstrate that the accuracy of this model is comparable with Xilinx ISE. This model which was integrated into placement algorithm can improve the circuit performance without a significant increasing of run time of placement.