结合改进A*算法与拆线重布的有序逃逸布线

• 作者: 邓新国 叶似锦 陈家瑞 陈传东
• 来源期刊: 电子与信息学报
• 关键词: A*算法 拆线重布 有序逃逸布线 最短路径
• 年，卷（期）: 2021,（6）
• 所属期刊栏目: 先进芯片与系统前沿技术专题|Special Issue on Advanced Chip and System Frontier Technology
• 页码范围: 1609-1616
• 页数: 8页
• 分类号: TN43|TP302.1
• 语种: 中文
• DOI: 10.11999/JEIT201033

摘要

逃逸布线是印刷电路板设计的一个重要组成部分.针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法.首先,通过代价预估函数确定引脚的布线顺序,使用改进A*算法初始化有序逃逸布线.接着,优化同长度布线路径,调整拥挤区域布线路径.最后,使用A*算法和广度优先搜索进行拆线重布.实验结果表明,该方法对给出的所有测试用例都实现了100％的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6％,?97.8％,总体线长也接近最优.提出的方法能够明显减少寻找可行解的时间,提高布线质量.