Research And Improvement Of Placement Algorithm For Dynamically Reconfigurable FPGA

With the increase of the complexity of embedded systems, Field Programmable Gate Arrays (FPGAs) are gaining popularity in embedded system design. FPGA presents a convenient way for the design of hardware circuits, and the whole design flow of hardware circuit can be accelerated through computer aided design software. In the design flow of the FPGA circuits, placement is the most time-consuming step, and also has a strong impact on the quality of the final FPGA circuit. Improving the efficiency of placement can reduce the design cycle significantly, thus FPGA placement becomes the research hotpot in recent years.There are two major research issues on FPGA placement:placement evaluation method and placement algorithm. Placement evaluation methods determine the direction of placement optimization. Current placement tools usually employ wiring length to evaluate the quality of placement. However, as the development of dynamically reconfigurable FPGA, the old evaluation method can't accommodate with new situations well. In this paper we perform research on the traditional method, and based on the analyzing of its deficiency present a new placement evaluation method, which considers both wiring and area cost of placement. Experiment results show the new placement evaluation method has good performance.Placement algorithm has a strong impact on the efficiency of finding the best solution and the quality of the final FPGA circuit. FPGA placement is an NP-complete problem, thus heuristic algorithms are usually applied, for example, Versatile Place and Route (VPR) employs Simulated Annealing (SA) to treat placement problems. In this paper we consider placement algorithms based on SA. We also present a method that using Genetic Algorithm (GA) on the placement problem, and give an improved algorithm based on SA, and then compare their efficiency and expansibility. Finally, the new algorithm is implemented in the VPR tool and experiment results show this solution has a higher efficiency than the initial one, and its annealing schedule can adjust itself automatically according to optimization rate. As a result, the new algorithm simplifies the hard task of parameter adjustment and enhances the efficiency of placement and has good expansibility.