自动布线方法(上)

本文介绍主要的布线方法及其优缺点,并进行一些分析比较。主要布线方法有:李氏算法、线探索法、单元布线法、迭代法、单层单行布线法、组合布线法、最优通道法、通道布线法、分级布线法、快速迷路法、分支限界布线法等。最后介绍在小型计算机上实现改进的李氏算法的一种方案。用线符代替线号,朝向终点迷路找线。这样可以用较少的内存,缩短布线时间。     

最小费用布线

本文提出最小费用布线,此是李氏算法的一种改进算法.定义了费用函数,在格同图G上已给两点s和t,按照最小费用,找s和t之间的最小费用连线.此比用李氏算法找线快,便于控制走线.最小费用布线法已经用FORTRAN语言编写程序,在M68000计算机上进行了试算.     

新型实用布线算法──L─M算法

本文提出新型布线算法，集李氏迷宫法与线搜索法的长处为一体，以饱和带法进行动态排序，以线搜索法确定借孔位置，然后用李氏法进行单层布线，获得最佳路径，从而达到线型好，布通率高的效果。     

多层印制板最佳分布算法

针对李氏算法的某些不足,本文探索一种整体布线方法。对已给的多层印制板网络{N_i},根据代价函数给出其最佳路径分布算法。此算法不仅布线速度很快,而且使走线更加均匀,合理,有利于提高布通率。     

朝向目标的线探索法——用小型计算机实现自动布线

本文提出了一种适合于小型计算机实现的自动布线方法——朝向目标的线探索法。该方法既适用于印制板布线,也可用于集成电路布线,其基本要素是带有预定终点的探索线。方法的特点是线探索针对目标,数据结构合理,所需存储量小,布线速度快。     

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

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

多层印制电路板的线探索布线

本文介绍适合于多层印制板的一种高效快速的线探索布线方法,并讨论了改善全局布线效果和布线合理性的一些途径:通过扩充探索线的概念,将朝向目标线探索的思想推广至多层板布线;采用分级探索和多层同时探索的策略,改善全局布线效果;采用多级优化措施,保证布线的合理性。     

一种基于非严格预留层的双层通道布线算法

本文提出一种基于非严格预留层的双层通道布线算法，算法通过确定较好的布线顺序，在基本上不增加空间的情况下，有效地减少GP线与通孔。实验结果证明，该算法能得到较好的布线结果。     

逻辑图自动绘制算法

研究讨论了逻辑图的自动布局、布线问题。在布局方面，以减少线交叉为优化目标，对重心布局算法＾⑴进行了几点改进；在布线方面，引入了垂直通道的概念，以减少线交叉和连线总长为优化目标，提出了一种新的布线算法，即求解线交叉最少和连接总长最短的布线算法。     

启发式布线方法

Lee’s迷路法实质上就是广度优先搜索法,线探索法实质上就是深度优先搜索法,它们是图搜索的两种极端情况。本文按照Rubin策略提出一种新的布线方法——启发式布线方法,它在布线过程中的每一步给出一个启发值,由此来确定向什么方向走线,其效率比DFS和BFS要好得多。     

布局问题的模拟退火算法

布局问题属于ＮＰ－完全问题已被研究多年，模拟退火法是一种新的通用启发式优化算法，现已广泛用于解决大规模集成电路逻辑布线设计、图象处理等组成优化问题，本语文通过对布局问题及模拟退火算法的分析，将它们综合起来构成了求解布局问题的模拟退火算法，计算结果表明，本文算法得到的解优于传统优化方法所得到的解；本文还通过实验对算法中各参数所起作用进行了论述。     

一种在VLSI电路物理设计中减小串扰的优化算法

通过研究调整线段和线间距对串扰的影响,提出了一种在布线时通过采线段摄动和压缩线间距的措施来减小串扰的优化算法,计算机仿真结果表明,该算法能有效地减少芯片中的串扰,此外,可预期算法应用于布线区域不规则的情形。     

PCB的指定距离布线

控制时钟偏差是提高巨型机主频的关键技术之一，在ＰＣＢ上利用指定距离布线算法调整时钟到各寄存器的连线延时是实现这一技术的有效途径。本文提出“两段布线”和“挤压延长”两种新的指定距离布线算法，实际应用表明，它比传统算法布线速度快，布线成功率高。     

李氏算法加速技术的探讨与应用

本文讨论了李氏算法在实用布线软件中的实现问题,着重说明了针对多层高密度PCB布线软件中应用李氏算法采用的加速技术,提出了网格尺度最小化原则,引出了动态网格和静态网格概念,运用了非均匀网格划分思想、不透明的存储管理、合理使用网格资源、模糊理想走线模式等加速技术,在实践中取得了满意的结果。     

优选找线方向布线

本文介绍优选找线方向布线法。此法是在修正的最小迂路法基础上的一种改进布线法。 在格网图G上,已给始点S和终点t,求S和t之间的最短连线。设立S_1、S_2、S_3三个后进先出栈,分别存本点的S_1、S_2、S_3方向的邻点。每次从本点出发,找本点未用的邻点,按照S_1、S_2、S_3方向,分别将本点未用的邻点存入S_1、S_2、S_3栈中,再按照后进先出的顺序,逐次发展S_1、S_2、S_3中点,直到找到终点t;或者,S_1、S_2、S_3中已空,未找到点t,即S和t之间不存在连线。 本文介绍了优选找线方向布线法的思想和步骤,并且与李氏迷路法、修正的最小迂路法进行了比较。 优选找线方向布线法已经用FORTRAN语言编程序,在DUAL计算机上进行了试算。     

基于边界扩张的点对点布线新算法

在超大规模集成电路设计中,全局布线是非常重要的步骤。工业界普遍采用经典的迷宫算法及其改进算法解决全局布线问题。随着工艺节点的减小,传统迷宫算法复杂度高的缺点越来越明显。针对传统迷宫算法的复杂度会随着布线规模的扩大而迅速增加的问题,借助于边界扩张的概念,提出一种新的点对点布线路径的搜索算法。摒弃了迷宫算法低效率的逐个节点扩张的思想,通过自由节点的定义对节点边界进行迅速扩张并不断地找到新的自由节点,直到找出路径或确定无解时结束。将该算法与经典的布线算法进行理论和实验比较,结果表明在大多数情况下该算法使用经典算法7%~14%的运行时间即可完成路径搜索。     

多层印制底板自动布线系统DBX 2

此文介绍多层印制底板自动布线系统DBX2,此系统有人工布局和自动布局,布线算法有改进的李氏迷路法和最小费用布线法.布线后加工形成生产印制板需要的数据.DBX2系统用FORTRAN语言编写程序,运行在M68000机、VAX11/785机和IBM4341机上,已经为KJ8920计算机自动布线底板122块,平均布通率为96%以上,可以满足设计要求,已经在实际中使用.     

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

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

一种基于迷宫算法的有效FPGA布线方法

在本篇论文中,我们介绍了在标准对称阵列（隔离岛状）现场可编程逻辑阵列结构下的一种基于迷宫布线算法的新型有效布线方法,Pathfinder.实验结果显示,相比普通的迷宫布线法,Pathfinder算法在布线时间上减少了90%.     

基于UG的三维电气自动布线技术研究

对三维电气布线的方法和技术进行了深入的研究。针对传统布线过程存在的预处理成本高、操作繁琐、干涉检测维护难等问题,通过综合"迷宫法"、线搜索法"等搜索算法和路径干涉理论,提出了"按面自动布线"和"贴壁干涉自动调整"的方法。以UG为开发平台,实现了包括三维布线路径自动生成和路径干涉检查及自动调整在内的三维自动布线。并以UG布线实例验证了所提出的三维布线方法的有效性和实用性。