计算机工程与科学

作者：闻豪, 李振松

单位：北京信息科技大学信息与通信工程学院,北京 102206

关键词：最小斯坦纳树,避障,布线,超大规模集成电路,

基金：国家自然科学基金(62074017)；国家自然科学基金联合基金叶企孙基金(U2341223)

在超大规模集成（VLSI）电路的布线阶段，迅速有效地创建直角避障最小斯坦纳树(ROASMT)是成功布线的重点。为此，提出了一种结合划分法和合法化的基于线网划分的单层直角避障最小斯坦纳树生成SL-ROASMT算法。通过划分扫描点区域，生成避障生成图(OASG)，在避障生成图中筛选避障生成树并转变成引脚生成树(PST)，从而将原始线网划分成多个子线网；再利用直角最小斯坦纳树(RSMT)算法对无障碍的各子线网创建直角最小斯坦纳树并合法化获得合法初始解。同时提出了基于“多段边”的全局优化和基于“类V结构”的局部优化方式。算法验证结果显示，SL-ROASMT算法较基于生成图的算法和基于边的算法平均缩短约3.6%的总线长度，且算法都在1 s内完成全部测试样例的布线。

来源：2026年第3期

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

查看计算机工程与科学杂志2026年第3期