关键词: 电路设计自动化(EDA), Stoer-Wagner算法, 超图, 模拟退火算法, A*算法

Abstract: This paper investigates the research status of automatic circuit layout and routing technology at home and abroad, and designs a layout and routing algorithm for medium-sized circuits. It is mainly used in the module test of large-scale layout design software, and provides users with preliminary wiring and layout results of each module, which is convenient for users to find and correct error points efficiently, and fills the gap in related fields in China. In this paper, a hypergraph model is established and transformed into a graph model. The Stoer-Wagner algorithm is improved, and the algorithm and the Fiduccia-Mattheyses algorithm are used to divide the graph based on the minimum cut theory, and construct a partition tree. Based on this tree, this paper designs a binary relative moving algorithm to determine the location of each circuit component, which greatly reduces the layout congestion and improves the aesthetics. For a circuit with hundreds of components, its layout can be obtained within 0.5 seconds. Based on the A* algorithm, the routing is improved in many aspects, and the routing speed is improved. For a circuit with <1000 wires, the routing results can be obtained within 0.1 s to 60 s, achieving 100% routing rate and uniform layout and routing effect.

Key words: electroic design automation (EDA), Stoer-Wagner algorithm, hypergraph, simulated- annealing algorithm, A* algorithm