A Hierarchical FPGA Placement and Routing Method Based on Multilevel Method and Weighted Hypergraph

Abstract

The invention relates to a hierarchical FPGA layout and wiring method based on a multi-level method and empowerment hypergraph. A mathematical model of a logical netlist in a hierarchical FPGA layout and wiring process is constructed by using empowerment hypergraph; circuit logic units are represented as nodes in the empowerment hypergraph; wiring among the circuit units is expressed as overrides in the empowerment hypergraph. The multi-level method is adopted as a hierarchical FPGA layout and wiring method to effectively meet the higher requirements of VLSI on the operating efficiency and processing capacity. The method can gradually reduce the scale of problems and the time complexity of methods by bottom up cluster stage and also can process details of problems level by level, increasing solution accuracy of methods by means of top-down projection optimization so as to be naturally combined with hierarchical features of researched objects. By means of the hierarchical FPGA layout and wiring method based on the multi-level method and empowerment hypergraph, the time complexity of FPGA physical design can be effectively reduced and the design capability and performance of FPGA are increased.

Description

technical field [0001] The invention relates to an FPGA layout and wiring method, in particular to a hierarchical FPGA layout and wiring method based on a multi-level method and a weighted hypergraph. Background technique [0002] With the development of very large-scale integration (VLSI) technology, the manufacturing process of VLSI has entered the era of nanotechnology from the era of deep submicron technology. The International Semiconductor Technology Roadmap report predicts that the feature size of VLSI will be reduced to 5nm in 2020, and the expansion of Field Programmable Gate Array (FPGA) and the complexity of its structure will bring new challenges to FPGA physical design. As a key link in FPGA physical design, layout and routing determine the mapping relationship between logical netlist and physical devices and the topological connection relationship. The quality of layout and routing directly affects the final performance, power consumption and reliability of FPG...

AI Technical Summary

Problems solved by technology

[0010] In 2008, the Chinese Patent Office announced the invention patent of Leng Ming, Yu Songnian and Sun Lingyu, whose Chinese patent number is No. 200710043765.3 "Large-scale integrated circuit division method based on multi-level method". The strategy is matched and the greedy principle is used for migration optimization, which leads to the partition that cannot escape the local optimum, and provides an improved large-scale integrated circuit partition method based on the multi-level method, which effectively improves the efficiency and performance of large-scale integrated circuit partition

Images