Fine-grain FPGA Placement And Routing Optimization And Software Implementation

Placement and routing are critical part in the FPGA(shortened from Field Programmable Gate Array) computer-aided design(CAD), its function will greatly impact how to route the logic circuit into the physical chips smoothly. As long as the gates quantity increasing and more and more complex structures developed, which greatly stimulate the placement and routing algorithm improvement to improve the CAD system routability and timing, and finally improve the chips performance.This pape deeply research current FPGA architecture in academic environment, and how the mainstream CAD system works, designs and optimizes the fine-grain FPGA placement and routing algorithm in CAD system. Main contribution as below:1. Study and compare the FPGA development history and main achitecture, and briefly introduce the CAD system. And also introduce the combination logic element and sequential logic element.2. Thoroughly studied the VPR(Versatile Place and Route) agorithem and elaborated the placement algorithm based on SA(Simulated Annealing), and introduced parametric structure description on the routing resource, as well as routing resource graph and globle routing and globle and detailed routing method.3. Analyze the word-wide academic study achievement regarding the placement and routing, partitularly focus on comparing the advantages and disadvantages among fast simulated annealing(SA) algorithm, generalized simulated annealing algorithm and adaptive simulated annealing. Futhermore, considering the specific features in the row-based, multiple CLB(configuble logic block) fine grain FPGA, concluded adaptive SA as the optimized placement agorithem and path-finding as dual CLB routing algorithm.4. At last, code the architecture file in XML and placement and routing program in C language, realized the fine-grain FPGA new placement and routing algorithm, and validate the results.