A Legalization Method of FPGA Layout Based on Maximum Flow Algorithm

Abstract

The invention discloses a FPGA layout legalization method based on the maximum flow algorithm, and relates to the field of FPGA technology. The method determines the line length of each line network according to the initial layout state of the FPGA, abstracts the initial layout state to establish a remaining graph, and utilizes the line Assign values ​​to the directed edges formed by abstracting the relationship between illegal nodes and vacant positions in the remaining graph as the cost of the edges, solve the remaining graph based on the minimum cost maximum flow algorithm to obtain the legal positions of each illegal node, and The legalization of the layout can be completed by placing each illegal node in the corresponding legal position; this method applies the maximum flow algorithm to the legalization part of the quadratic linear programming algorithm, making the legalization process that was originally not oriented. Orientation, and to a certain extent, improve the quality of the final solution, making the legalized line length shorter and the layout result better.

Description

technical field [0001] The invention relates to the field of FPGA technology, in particular to a method for legalizing FPGA layout based on a maximum flow algorithm. Background technique [0002] Field-Programmable Gate Array (Field-Programmable Gate Array, FPGA) is a chip widely used in household appliances, large machinery and even aerospace. The use of FPGA chips is inseparable from electronic design automation (Electronic Design Automation, EDA) tools. Layout is an important part of the EDA tool, which has a great impact on the running speed of the EDA tool itself and the final quality of the processed circuit. [0003] In recent years, the circuit scale of FPGA chips has grown rapidly, making its functions more powerful, but it has also brought challenges to the corresponding EDA tools. Analytical algorithms have become one of the mainstream directions of today's layout algorithms because they can use mathematical methods to quickly obtain the global optimal solution....

AI Technical Summary

Problems solved by technology

The quadratic linear programming algorithm is a kind of analytical algorithm. When it is specifically applied to solve the layout problem, it shows the characteristics of fast solution. However, after the solution is completed, there are still illegal layouts, such as the common overlapping node, so it needs to be legalized again

Although this method is simple and easy to implement, it does not have any guidance, and there are also the following problems in the selection, for example: if the location distance is marked by the Manhattan distance, can the location with the closest distance be better than the location with a long distance? There are multiple locations with the same Manhattan distance. Do these locations have the same advantages and disadvantages? These problems lead to the fact that although the original legalization process can quickly legalize the illegal layout, it cannot take into account the quality of the legalized layout, which often leads to unsatisfactory final solutions.

Images