计算机工程与科学

作者：袁也, 王刚, 刘晓光, 李雨森

单位：1.南开大学计算机学院，天津 300350；2.天津市网络与数据安全重点实验室（南开大学），天津 300350

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

基金：国家自然科学基金（U1833114,61872201,61702521）;天津市人工智能重大专项（18ZXZNGX00140,18ZXZNGX00200）

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

来源：2021年第7期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2021年第7期