新型电路版图布局布线算法设计

A novel circuit layout and routing algorithm

调研了电路自动布局布线技术的国内外研究现状,在此基础上设计了一种面向中等规模电路布局布线算法,主要用于大型版图设计软件的模块测试环节,为用户提供各模块初步的布线布局结果,方便用户高效查找并修正错误点,填补了我国在相关领域的空白。建立了超图模型并转换为图模型,改进了Stoer-Wagner算法并利用该算法和Fiduccia-Mattheyses算法对图进行了基于最小割理论的划分,从而构建出一棵划分树。在这棵树的基础上设计了一种二元相对移动算法来确定各个电路元件的位置,大大降低了布局拥挤度,提高了美观度,对于数百元件的电路均能在0.5 s内得出布局结果。基于A*算法在多个方面做了改进,提高了布线速度,对于线路数1000以下的元件能在0.1 s~60 s内得出结果,实现了100%布通率以及均匀的布局布线效果。

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.