-
题名结合改进A^(*)算法与拆线重布的有序逃逸布线
被引量:1
- 1
-
-
作者
邓新国
叶似锦
陈家瑞
陈传东
-
机构
福州大学数学与计算机科学学院
福州大学物理与信息工程学院
-
出处
《电子与信息学报》
EI
CSCD
北大核心
2021年第6期1609-1616,共8页
-
基金
国家自然科学基金(61977017)
国家科技部重点研发计划课题(2018YFB2202704)
中国福建光电信息科学与技术创新实验室(闽都创新实验室)基金(2021ZR142)。
-
文摘
逃逸布线是印刷电路板设计的一个重要组成部分。针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A^(*)算法与拆线重布的有序逃逸布线方法。首先,通过代价预估函数确定引脚的布线顺序,使用改进A^(*)算法初始化有序逃逸布线。接着,优化同长度布线路径,调整拥挤区域布线路径。最后,使用A^(*)算法和广度优先搜索进行拆线重布。实验结果表明,该方法对给出的所有测试用例都实现了100%的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6%,97.8%,总体线长也接近最优。提出的方法能够明显减少寻找可行解的时间,提高布线质量。
-
关键词
A^(*)算法
拆线重布
有序逃逸布线
最短路径
-
Keywords
A^(*)algorithm
Rip-up and reroute
Ordered escape routing
Shortest path
-
分类号
TN43
[电子电信—微电子学与固体电子学]
TP302.1
[自动化与计算机技术—计算机系统结构]
-