• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2021, Vol. 43 ›› Issue (07): 1185-1191.

• 高性能计算 • 上一篇    下一篇

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

袁也,王刚,刘晓光,李雨森   

  1. (1.南开大学计算机学院,天津 300350;

    2.天津市网络与数据安全重点实验室(南开大学),天津 300350)

  • 收稿日期:2020-06-30 修回日期:2020-11-09 接受日期:2021-07-25 出版日期:2021-07-25 发布日期:2021-08-16
  • 基金资助:
    国家自然科学基金(U1833114,61872201,61702521);天津市人工智能重大专项(18ZXZNGX00140,18ZXZNGX00200)

A novel circuit layout and routing algorithm

YUAN Ye,WANG Gang,LIU Xiao-guang,LI Yu-sen   

  1. (College of Computer Science,Nankai University,Tianjin 300350;

    Tianjin Key Laboratory of Network and Data Security Technology(Nankai University),Tianjin 300350,China)

  • Received:2020-06-30 Revised:2020-11-09 Accepted:2021-07-25 Online:2021-07-25 Published:2021-08-16

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


关键词: 电路设计自动化(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