Extended Abstract
Field Programmable Gate Array (FPGA) is also known as the “Transformer” in the field of integrated circuits. As a semi-custom circuit, it has been widely used in the design of modern digital systems as soon as it comes out. After more than 30 years of development, FPGA has embedded a variety of IP cores, integrated millions of logic cells, and contains billions of transistors. The advantages of FPGA are high degree of concurrency, short development cycle, and the ability to reconfigure and implement different functions at any time, eliminating the long waiting cycle of user-customized Application Specific Integrated Circuit (ASIC) and the huge cost risk that needs to be borne. FPGAs are widely used in modern digital systems, such as mobile phones, aerospace, communication equipment, automotive electronics, home applications, satellites and other fields, and the scope of FPGA applications continues to expand. With the development of various emerging technologies, the application scope of FPGA has expanded from ordinary consumer electronics to smart grids, high-performance computing, Internet of Things (IoTs), Artificial Intelligence (AI) and other fields. Among the many factors that restrict the development of FPGA, the most critical is Electronic Design Automation (EDA) technology, such as the pen of a graphic artist and the boat of crossing the river. Without EDA, the development of FPGA will be impossible. When using FPGA to design a system, the user first uses a Hardware Description Language (HDL) to describe the circuit or system function to be implemented in next. Then, the FPGA EDA software tool is used to compile the circuit step by step, and finally convert the circuit into the form of binary code stream. Finally, the binary code stream is used to configure the state of devices such as switches and Look-Up Tables (LUT) inside the FPGA, so as to realize the target circuit or system function on the FPGA chip. Due to the improvement of FPGA integration and increase in the scale of modern FPGA circuits, it takes longer and longer for FPGA EDA software to compile the circuit into binary code stream. FPGA EDA software has fallen behind the rapid development of FPGA hardware. The design process of FPGA EDA tools mainly includes design input, behavior synthesis, logic mapping, packing, placement, routing and binary code stream generation. Among them, placement and routing are the most import steps in the design process, and they are also the most time-consuming steps. The final result of placement and routing directly determines the performance of the design circuit after it is implemented on the FPGA. Therefore, the research of placement and routing technology is of great significance to the healthy and sustainable development of FPGA. In this article, we categorize all methods of placement and routing for the FPGA by different grouping criteria and evaluate their performance from the methodological point of view. For the technology of placement for the FPGA, the first category of methods is the partition-based placement method, which refers to the partition of placement instances through continuous recursive iterations on the basis of the most original placement instances based on the known placement constraints, until all the placement instances are less than the preset threshold. The second uses some natural phenomena in the existing scientific fields as design principles to model the placement process of FPGA heterogeneous logic cells. The last category of methods is the analytical-based placement approach, which formulate the placement as a more sophisticated continuous optimization problem and solve it using various principled gradient descent methods. For the technology of routing for the FPGA, there are two categories, serial and parallel routing methods. The advantages and disadvantages of different technologies are analyzed and compared. On this basis, the future development trend is prospected from three aspects: optimization of FPGA placement and routing process by artificial intelligence technology, exploration of multi-driver placement and routing strategies, and research on more simple and feasible parallel acceleration methods, with a view to providing reference for experts and scholars in this field and related fields.