基于最小生成树的动态通道布线算法

针对电子设计自动化中低的通道布线布通率,对影响布通率的因素进行了研究,分析了线网布线次序对通道布线结果的影响,比较了静态排序和动态排序的优缺点,基于最小生成树,提出了一种动态通道布线算法.在布线过程中,根据通道已布线状态,计算剩余线网加权后各自的最小生成树,优先选择受已布线线网影响最大的线网进行连接,避免连接点距离较远的线网对连接点距离较近的线网的约束.实验结果表明,对同一个布局,采用相同的布线规则,算法占有空间资源少,比商用软件在通道布线方面具有更高的布通率.

VLSI标准单元通道布线的研究

在ＶＬＳＩ标准单元通道布线问题中，布线面积大小和过孔多少是衡量布线结果优劣的重要指标．文中从一个全新的角度提出了“线网投影长度”的概念，运用这一概念对通道内的线网设置优先级，按照优先级依次布线，就可实现不仅减小布线面积，同时又减少过孔数的目的，而且为进一步的过孔优化留有余地．

一种基于通孔数最小化的多层通道布线算法

该文提出了一种基于通孔数最小化的多层通道布线算法 .算法采用非预留层模型 ,首先根据线网之间的位置关系利用模拟退火算法将各线网合理地分配到对应的布线层中去 ,然后利用遗传算法得到相关布线层中线网的最佳布线顺序向量 ,最后根据得到的顺序向量利用“沉积法”将各线网布于合理的通道上 .该算法克服了传统通孔优化算法中原始布线对优化结果的不利影响 ,使通孔的优化达到很好的效果 .

基于Hopfield神经网络模型的通道布线算法

本文探讨了用Hopfield神经网络模型解决通道布线问题的一种新算法。算法描述了Hopfield模型与通道布线问题的映射方法和网络能量函数的构造方法,在能量函数中既考虑了合法解约束项,又考虑了优化解约束项,从而提高了布线质量。本文的意义还在于它证明了用Hopfield网络求解通道布线问题是可行的,有效的。

通道布线的神经网络优化算法

介绍通道布线的思想 ,给出相应的形式化描述 ,提出一种神经网络求解算法 .该算法以总线长最短、轨道数最少为优化目标 ,以满足水平、垂直制约为约束条件 ,通过把问题映射为神经网络模型 ,建立了问题的能量函数 ,用均场退火方程迭代求解 .

串扰最小化的网格模式下的双层通道布线

超深亚微米 IC设计中互连线的串扰情况与详细布线方案和信号波形密切相关 .基于这一事实 ,在网格模式下的通道布线算法中建立了最小化串扰的目标函数 ,提出获得最小化串扰布线方案的方法 .与以往算法不同的是 ,本方法将相邻平行线间信号跳变的方式和频度作为目标函数中的影响因子 ,可以更准确地估计出布线区内串扰总和的大小 .并且通过构造布线生成树的方法求得精简的布线方案 。

采用分枝搜索技术的四边通道布线

对二层四边通道布线问题提出一种新算法，其设计基于分枝搜索技术．如果问题的解存在，一定能百分之百地完成布线．

L形通道布线的展开法

本文提出将L形通道展成直通道的布线方法,对展开后的直通道定义了水平约束、垂直约束、拐角约束、走线约束,利用赋权的混合图反映这四种约束、并逐步将图中的无向边转变成有向边,按照有向图的线网上下关系,完成直通道布线,再收缩冗余布线区变成L形通道布线.

通孔最小化的三层不规则边界通道布线

提出了一种以连通孔和布线区域最小化为目标的三层不规则边界通道布线算法。算法将通道边界的凹陷区域看成固定障碍,利用填充和压缩方法,使线网绕过障碍,实现互连。算法已用PASCAL语言编程,并在XT/286机上实现。结果表明,该算法不仅使通孔数减少,而且由于利用了各凹陷区域之间的面积进行布线,通道宽度也相应减小。

基于拓扑分析的多层通道布线算法

本文提出了一种基于拓扑分析的多层通道布线算法。算法把整个布线过程分成拓扑分层和物理布线两个部分。拓扑分层利用线段交叠图及模拟退火算法解决线段分层及通孔最少化问题,物理布线过程引入虚拟走线道解决交叉问题,再利用轮廓线跟踪的方法来决定最终确定各线段的布线位置。算法还解决了多层布线分层的管脚约束问题和相邻约束问题。实验结果表明,这是一种有效的方法。

电路原理图中两边网格通道布线的类贪婪算法

贪婪算法是VLSI设计中通道布线的常用算法,在电路原理图的自动布图中,也会遇到通道布线的问题。但传统的贪婪算法着重于使通道面积最小化,不能满足原理图中对布线结果有序化的要求。提出类贪婪算法,在原贪婪算法的基础上,通过修改处理规则,使得布线结果更加整齐有序,便于阅读,同时也保留了原算法简洁高速的优点。

基于图论模型的两类通道布线算法研究

通道布线问题是VLSI物理设计中的一个关键问题,本文从结点的两类约束图入手来研究布线算法.对垂直约束图中含有有向圈的一类通道布线问题进行研究,设计出包含一对和两对空结点情况下的布线算法,该方法能够得到更好的轨道高度.

一个通道布线问题的图论算法

图论的思想方法在大规模集成电路布线中有广泛的应用。通道布线的线网结构可以用水平约束图和垂直约束图来描述,利用图论的思想可以处理布线轨道高度问题。研究运用图论的方法来解决超大规模集成电路布线中的轨道高度问题。通过寻找并消除临界网的方法给出布线的一个新的算法,该算法能够得到轨道高度的一个下界,并对在含有一个狗腿的情况下如何布线进行了描述,并设计出能运用到实际布线工艺中的两层具有曼哈顿模型的通道布线算法。

一种以改变目标为策略的改进型三层通道布线算法

本文提出了一种改进型的三层通道布线算法——以改变目标为策略的三层通道布线算法.根据不同的布线问题,分别采用不同的布线方法,即首先从分析布线问题的最大垂直限制链长和最大通道密度出发,当以完成布线所需的通道数为最小作为目标时,采用HVH的三层通道布线算法;当以缩短最大垂直限制链长为目标时,采用HVH_m的布线算法.因此,它综合了曲干布线和直干布线两方面的优点,即不仅充分利用了通道区的空间,而且又一定程度地限制了导通孔数的增加.本算法已用FORTRAN语言编程实现,对引文中已发表的若干布线实例,都获得了较满意的结果.

一个具有最小串扰的多层通道集成电路布线算法

提出一种多层通道布线算法.采用动态规划思想逐层进行布线,使当前层面上的串扰达到最小,并将不能在当前层面连接的管脚对"沉积"到下一层,产生多层通道布线解.

随程序规模动态调整的通道优化布线算法

针对常规层次型布图算法在大规模程序中布线混乱的缺点,借鉴Sugiyama层次布局算法,提出了一种随着程序规模动态调整的通道优化布线算法。通过将节点的通道数目与程序规模建立函数关系,以解决现有算法在布图时出现的线路重叠和效率低下的问题;在布图中结合广义张量平衡思想,以减少交叉并实现布图的美观性;并根据调用节点之间的相对位置关系,给出了相应的线路分配和申请策略,实现了布线的有序性。实践证明,该算法能够提高布图效率,有效地减少交叉,实现节点的有序布线和实现简单等优点。

重叠端口通道的四、五层布线算法

本文提出了一个重叠端口通道的四、五层布线算法.算法的目标是占用尽可能少的通道布线行数,为此算法中采用了扩展布线的概念,将部分线网分配到器件区域中进行布线.在通道内部布线时,引入了重叠端口通道的垂直约束矩阵的概念,并用它来指导启发式算法的线网布线顺序.算法在任何情况下都能保证布线的成功,从运行实例上来看,算法速度很快,而且结果都是近似最优的(或者是最优,或者是比最优解多一个布线行).

给定水平约束图的一类集成电路布线算法

针对水平约束图为星图的具有曼哈顿模型的通道布线,提出了一个依据图论模型的最优轨道高度布线算法.该算法根据通道上结点的水平约束图和垂直约束图特点,依次安排好每一个结点的布线轨道,进而通过通孔可以把所有的结点在2层轨道上布线完成.通过计算分析,该算法能够达到最优的布线高度.

基于图论模型的一类集成电路布线算法

针对具有曼哈顿模型的一类通道布线,提出了一个依据图论模型的最优轨道高度布线算法。算法根据通道上结点的水平约束图和垂直约束图,依次安排好每一个结点的布线轨道,进而通过通孔可以把所有的结点在2层轨道上布线完成。通过计算分析,该算法相对以前的算法能够达到更优的布线高度,并且其复杂性保持不变。

RSAB积木块自动布线系统

本文介绍了在SUN工作站UNIX操作系统下实现的一个用于LSI/VLSI积木块布图设计的自动布线系统——RSAB,给出了系统构成,通道定义方法以及全局和通道布线算法。系统除了可对一般信号线网自动布线外,还可处理特殊线网(电源/地线网,临界线网等)的自动布线。目前RSAB已集成在一个交互式版图编辑系统——Magic中,提供设计者一个友好的用户界面和自动/交互式布图环境。实验结果表明RSAB是可行的,布线结果令人满意。