没有合适的资源?快使用搜索试试~ 我知道了~
结合改进A算法与拆线重布的有序逃逸布线.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 58 浏览量
2023-02-23
20:12:35
上传
评论
收藏 852KB DOCX 举报
温馨提示
试读
14页
结合改进A算法与拆线重布的有序逃逸布线.docx
资源推荐
资源详情
资源评论
1. 引言
有序逃逸布线问题,作为印刷电路板(Printed Circuit Board, PCB)设计中的关键问题。
目前,电路板的布线在很大程度上还是由专业人员手工完成。随着电路板器件集成度不断
提高,器件引脚数量大规模增加,现有自动逃逸布线算法已经无法为专业人员提供有效的
帮助。因此,如何能够快速得到一个可行的布线方案已成为急需解决的问题。
逃逸布线是将引脚网格内的某些引脚连接到网格的边界上,最主要的考虑因素是可布
线性,在可布线性得到满足的情况下优化线长,逃逸布线问题主要分为无序逃逸布线和有
序逃逸布线两类
[1,2]
。目前,对于无序逃逸布线的研究已经取得了很好的成果,由于无序逃
逸布线没有终点顺序要求,所以对于该问题的研究
[3-5]
都使用网络流方法进行求解并可以在
短时间内得到最优解,且文献[6,7]研究并解决多层逃逸问题。
而有序逃逸布线由于逃逸目标线路顺序的限制,使用网络流方法无法解决,现有的研
究提出的方法又可以分为并行布线方法和串行布线方法
[8]
。并行布线就是一次性对所有引
脚进行线路规划,文献[9,10]用整数线性规划(Integer Linear Programming, ILP)解决了一个
相关但不同的逃逸问题,该问题中引脚具有固定的逃逸终点,文献[11]使用分组等策略改
进 ILP,降低约束项数量。Tomioka 等人
[12]
只采用无绕行单调模式,这意味着即使存在解
决方案,也不一定能保证找到解决方案。尽管他们使用的方法在图有环时考虑非单调布
线,但是在资源冲突需要绕行时,非单调布线就会失败。文献[13,14]将有序的逃逸布线转
换为一个布尔可满足性问题(Boolean Satisfiability Problem, SAT),并通过 SAT 求解器解
决。该方法无需对路线始末进行任何假设,即可准确完成布线。但是,该方法很难解决逃
逸布线容量不为 1 的情况。在最新的研究中,Jiao 等人
[15]
使用最小费用多商品流(Min-cost
Multi-Commodity Flow, MMCF)方法来解决这个问题,主要是通过使用虚拟节点,构建具有
始末节点且符合求解约束的图,进而使用 MMCF 求解器来求解,在大规模引脚阵列中构建
图,虚拟点的数量过多会使得运算量大幅度增加。
串行布线则是按照每条线的顺序依次进行布线,每条线布线完成后更新占用的资源,
下一条线在空余资源上进行规划。串行布线对布线的先后顺序有很强的依赖性,因为先行
的线占用了资源后,之后的引脚可能无法逃逸,因此,使用拆线重布
[16]
的方法来对已有的
线进行调整。
并行布线的方法随着电路板引脚数量变多,时间复杂度会迅速增加,耗费的 CPU 时
间会成倍增长,甚至会无法求解。因此,当遇到的引脚阵列规模较大时,并行布线的方法
会允许程序寻找可行解而不是最优解。
在逃逸布线中兼顾可布线性与线长,提出了一种 3 阶段串行布线的逃逸布线方法。主
要步骤为:首先构造预估函数估算引脚逃逸所需的资源,确定可行的布线顺序,以此构造初
始解,接着对拥挤区域与同长度布线路径进行优化,最后使用拆线重布的方法对无法逃逸
的引脚进行重新布线。
2. 问题描述
逃逸布线是将引脚阵列内的某些引脚连接到组件边界上。
目前市面上器件的封装形式主要分为交错引脚阵列(Staggered Pin Arrays, SPA)
[17]
和网
格引脚阵列(Grid Pin Array, GPA),本文主要研究 GPA 下的逃逸布线,如图 1。定义一个多
行多列的规则排布引脚阵列,假设在每 4 个引脚中间有一个中心节点,使得需要逃逸的引
脚通过中心节点连接到边界上。
图 1 GPA 单边逃逸布线示意图
下载: 全尺寸图片 幻灯片
算法输入为给定引脚阵列构建的有向图$G(V,E)$,其中$V =
\left\{ {{v_0},{v_1},{v_2}, ··· ,{v_m}} \right\}$是引脚与中心点标号集合,$E$是边集合,
$S$, $T$分别表示起点集合(引脚集合)和终点集合,${x_{uw}} = 1$表示由节点 u 前往节点
w 的有向边被选中,${x_{uw}} = 0$则表示没被选中,${c_{uw}}$表示由节点 u 前往节点
w 的有向边的代价,将问题描述为一个整数线性规划问题,即
$$\begin{split} &{\min }\quad{\sum\limits_{(u,w) \in E} {{c_{uw}}{x_{uw}}} } \\ &
{{\rm{s}}{\rm{.t}}{\rm{.}}}\quad\;\;{\sum\limits_{w \in V} {{x_{uw}} \le 1,} }{u \in V} \\
&\quad\quad\quad{\sum\limits_{w \in V} {{x_{uw}}{\rm{ - }}\sum\limits_{w \in V} {{x_{wu}}{\rm{ = 0,}}} } }\;{u
(1)
剩余13页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3578
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功