有环形约束的两层通道布线的一种算法

两层通道布线问题在超大规模集成电路自动布图设计中是关键步骤之一。虽然现在已经有一些通道布线的有效算法,但通常的这些算法不适用于垂直约束图存在闭环的情况。本文提出的算法以垂直约束图的合并算法为基础,但进一步可以处理有环形约束的问题。此算法包括五个子算法,按次序试用这些子算法去解决闭环,直至将其解决。由于第五个子算法利用通道左端或右端的附加垂直走线道,故可以保证一定能使闭环得以解决。本算法已经用PASCAL语言编出程序并在美国伯克利加州大学电气工程与计算机科学系的VAX11/780计算机上运行,得到相当好的结果。     

基于结点的度性质的几何约束求解的研究

针对参数化设计中的几何约束求解问题,提出一个新的分解算法.通过在约束图中引入结点的度的概念,根据在完备约束图中度为2的结点所特有的性质借鉴Joan-Arinyo经典算法,提出新的几何约束分解算法.为使新算法解决与Joan-Arinyo的算法所能解决的同类问题,基于Joan-Arinyo的算法与新算法的共同点进而提出新的合并算法.合并后的算法与Joan-Arinyo的算法在使用范围上相同,但在概念上更简单且更容易实现.     

一种建立在两个新的约束条件之上的四边通道区布线算法

提出 2个针对四边通道区布线问题的新的约束—行约束和列约束 .并在此基础上建立了布线算法 ,它包括线网分类 ,线网修改 ,顺序布线和改进线探索法 4个主要组成部分     

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

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

不等间距不等宽度端口的通道布线算法

本文提出了一种适用于标准单元具有不等间距和不等宽度端口时的通道布线算法。该算法在垂直约束图和重迭区表示图的基础上，对线网进行分析和权重计算，优选线网加以布线。通过若干实例运算表明，该算法通过若干实例运算表明，该算法是一种有效和实用的算法。     

一种L型通道布线算法

近年来,通道布线问题引起了人们广泛的重视。但至今研究L型通道布线的文章很少。本文提出了一种以减少信号网冲突数为主要目标的L型通道布线算法。该算法从一种总体的考虑出发,把L型通道分解为两个相关的四边通道进行布线,提高了布线成功率。     

一个带串扰限制的L-型通道集成电路布线优化算法

针对 L -型通道集成电路布线问题 ,给出一个带有串扰限制的优化布线算法 .此算法思想也适用于解决矩形通道、十字型通道等各种不同类型单层通道的布线问题 .文章的最后对算法的时间复杂性进行了简要的分析     

实用的应用图论算法的单元及通道布线

如何高效节省的进行电路板及芯片的布线,对于提高设计速度减少工作强度具有十分重要的意义。本文给出了一种实用的应用图论算法的单元及通道布线的算法,并采用一种绕线方法成功解决了两层通道布线问题。     

楼宇三维路径模型的自动生成算法

提出了一种楼宇三维路径的自动生成算法.该算法首先使用图像细化算法及特征点提取算法建立单层楼的通道路径,并将房间等楼层实体作为结点连接到通道路径上,从而建立好单层楼的路径图;然后利用楼梯结点和电梯结点将相邻的楼层路径图相互连接起来,生成完整的楼宇三维路径模型.该路径模型是由弧和结点结构组成的带权图结构,可以应用于智能导航、楼宇自动控制、紧急情况的人员疏散及楼宇安全等领域.     

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

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

解决布线过程中通道消失分解、合并问题的一种方法

在 VLSI 积木块布图设计模式中,模块的移动会引起通道图发生变化,影响布线的进行。本文给出了一种布线方法,用此方法可保证:任给一个通道图,只要其 T 形约束图中无约束环,无论模块在布线过程中怎样平行移动,均可按照通道图正常布线。此方法已成功地应用在我们研制的 VLSI 版图 CAD 系统中。本文从理论上给予证明,并给出应用实例。     

超大规模集成电路成功布线的策略

该文对超大规模集成电路 (VLSI)的成功布线给出一些策略。运用这些策略可以确定通道区最优布线 ,避免出现“开关盒”问题 ,还可以预知成功布线的可实现性 ,保证在通道区扩张阶段需要重新布线的通道区数目最少。这些策略均以图论为基础 ,对VLSI布图设计具有一定的理论和实用意义。     

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

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

基于D-tree分解的欠约束与完备约束的几何约束求解

提出了解决欠约束、完备约束的几何约束问题的D-tree分解算法.首先,提出了一种适用范围更广的处理特殊约束策略,可以将这种特殊约束与普通约束统一化,采用转化策略将欠约束的几何约束问题转化为完备约束的几何约束问题.然后,根据几何约束图中结点的度的性质给出了D-tree分解算法,相比经典算法,D-tree分解算法拥有更低算法复杂度和相同的求解域.最后,根据D-tree分解算法结果的规律性,给出了一个为基于数值的求解方法导出求解序列的策略.D-tree分解算法通过导出的求解序列将提高几何约束求解中基于数值的求解方法的求解效率.     

基于自由分层的通道区布线算法

本文在分析线网之间关系的基础上提出了自由分层条件下的通道区布线模型:同层限制图 Gs,相交图 Gi。基于这一模型,分析了二层布线条件下对线网分层和布线序的基本限制,导出了分层的基本原则。在此基础上,分析了线网可 overlap 的性质和条件,从总体分析的思想出发,提出了直接以完成布线通道区所需面积最小化为目标的分层布线算法。实验结果表明,通道区布线面积和通孔的数目比基于横竖分层的布线算法有较大减少,对于Deutsch's difficult example,该算法获得18个 track 解。     

基于半定规划的多约束图划分问题

提出一种递归的二分算法,用于求解带顶点权重约束的图划分问题.首先利用内点法求解不加顶点权重约束的半定规划松弛模型,然后利用超平面舍入算法得到满足顶点权重约束的初始可行解,再进一步设计启发式算法对初始可行划分进行局部改进,以得到更优的划分结果.实验结果表明,所设计的算法可在较短时间内得到多约束图划分问题的高质量解.     

任意元胞式LSI版图设计中的一种自动化布线方法

早在六十年代初就有人对布线自动化进行研究了.当初主要用于印刷电路版,后来才用于大规模集成电路的版图设计.布线算法主要可分为两类.一类是迷宫型算法,典型的有“李氏算法”和“行布线算法”.这类算法是以搜索来寻找布线路径,具有较大灵活性和普遍性,但要进一步提高布线成功率则较难,且太费时间和内存,在这以后,出现     

大规模网络最大流对偶图算法模型及实现

在网络最大流算法的研究中,为了减少计算量,提出了许多改进的方法.基于图论中的最大流最小割定理,利用网络流图的对偶图的最短路径求网络最大流,对求最短路径的Dijkstra算法进行了研究,给出了一种改进的Dijkstra算法模型,该算法采用了堆排序中的小根堆来选择最短路径结点,使用集合运算对堆中的结点进行处理,使得参加运算的结点数减少,提高了算法的效率.     

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

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

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.