一种新的基于知识的四边通道布线算法

本文提出了一种新的基于知识的双层四边通道布线算法,该算法对四边通道的布线是通过以下四步完成的。首先,对四边通道的四个角布线,其次,对关键线网优先布线,接下来,利用线网间相互制约关系进行同步增长布线;最后,对仍然没有完成连接的线网,用李氏算法布线。由于使用了启发式规则,使得该算法具有较高的布通率和布线效率。     

通道区布线的线网分布优化问题及其算法

在ＶＬＳＩ布线设计中，线网的分布情况直接影响到ＶＬＳＩ芯片的电学性能、可靠性和制造成本。但是，由于通道区布线问题的计算复杂性很高＾［１］，布线过程中往往没有考虑到线网的分布问题，因此，布线完成后有必要对布线结果进行一次线网分布优化。本文中提出了两种工艺的双层通道区布线线网分布优化问题，并给出了相应的算法。     

重叠端口通道dogleg的优化算法

针对重叠端口通道的多层布线模型，提出了一个优化通道内ｄｏｇｌｅｇ数目的算法。该算法避免了一般优化算法中难以确定合理的优化顺序的不足，用它来对重叠端口通道布线结果进行优化，能快速减少ｄｏｇｌｅｇ数目，提高电路的电学性能。最后分析了算法的时间复杂性。     

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

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

一个基于整体优化分析的区域布线算法——DRAFT

本文提出一种新的基于整体优化分析的区域布线算法──DRAFT,它可以解决通道布线和四边布线问题。该算法分二个阶段完成区域详细布线:定向布线和最终布线。定向布线阶段给出各线网可行走线区间和最佳走线位置,其结果在最终布线阶段引导各线网的实际走线。布线在两层上进行,但不限制不同方向的走线必须走在不同层上。实验结果令人满意,对于大多数发表在文献中的通道布线和四边布线例子,DRAFT都得到了相当满意的解。     

一个新的Over-The-Cell布线算法

本文提出了一个新的Over-The-Cell通道布线算法.我们将有线问题分为两个阶段:1)单元区布线,2)通道区布线.单元区布线的目标是最大可能地减小通道密度,而不同于以在算法总企图在单元区嵌入最多的线网.文中提出了最大密度段的概念,单元区布线优先选取覆盖最大密度段的线网,这更有利于降低通道密度.布线结果只需利用较少的单元区走线道,便可有效地降低通道密度,因而增强了算法的实用性.本文提出的算法已在SUN4/110工作站上用C语言编程实现,运行结果优于国内外已发表算法的结果.     

通道区布线的线网分在优化问题及其算法

在ＶＬＳＩ布线设计中，线网的分布情况直接影响到ＶＬＳＩ芯片的电学性能、可靠性和制造成本。但是，由于通道区布线问题的计算复杂性很高￣［１］，布线过程中往往没有考虑到线网的分布问题，因此，布线完成后有必要对布线结果进行一次线网分布优化。本文中提出了两种工艺的双层通道区布线线网分布优化问题，并给出了相应的算法。     

优化层分配的无网格详细布线算法

H—V布线模式下产生通孔的根本原因是由于不同线网间存在几何重叠或交叉；标准单元内布线主要应用多晶硅层与单金属层的布线层资源，考虑到不同层间相异的导电特性，文章提出了一种算法，基于网段拓扑交叉分析实现最大化金属层及最小化多晶层分配，优化线网通道分配与线长，同时满足通孔最小化。     

一种基于整体化策略的通道区布线方法

本文提出一个基于整体化策略的通道区布线方法,打破了把通道区看成彼此独立、互不重叠的传统做法,克服了只孤立考虑通道内部的优化布线却造成整体布线效果差的缺点。本方法简单有效,以很小的存贮空间、运行时间开销,获取了从整体上显著提高布线质量的效果。     

超平面布线

本文大胆打破了传统通道模型的束缚,建立了一个能更好体现多层布线内在本质约束的新模型：超平面布图模型,在该模型下提出了超平面布线算法。该算法以全新的逆向删冗策略成功地解决了布线线序的问题,使线网布线真正达到了并行处理。算法遵循了王守觉先生关于总体分析的方法作为解决超平面布线问题的指导思想,以布线层数最少化和通孔最少化为目标,通过动态地分析线网间的相互位置关系,全局考虑去释放各线网占据的不合理布线资源     

考虑拥挤度和性能的全芯片可控布线系统框架

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

设计规则驱动的多层布线算法

迷宫算法是集成电路两端线网优化布线问题的经典算法。多层布线受复杂版图设计规则约束．简单直接应用迷宫布线算法，或者无法获得优化的结果，或者无法满足设计规则。文章分析了迷宫算法特性与局限．提出基于群组图的多层迷宫算法，圆满地解决了上述问题。     

时延驱动的整平面整体布线算法

本文结出了一个新的时延驱动的整体布线算法．算法采用了整平面布线技术，从而具有快速求解的特点且无网序问题的困扰．算法优化的目标是使所有线网的最大时延之和最小，尤其是在关键路径上的线网实际电路的布线结果表明该算法可有效地改善关键路径上线网的时延．     

基于线网类型分析的过点分配算法

过点分配是布线过程中位于总体布线和详细布线之间的一个步骤，它用于在详细布线之前确定线网在总体布线单元边界上的物理位置．本文提出一种新的过点分配的启发式算法，它基于总体布线后的线网类型的分析，考虑了总体布线单元中障碍对过点分配的影响，把整个布线区域的过点分配问题转化成一系列的单列（行）总体布线单元边界的过点分配问题，然后利用经典的线性分配方法进行过点的分配．     

MARS：一个通用多层区域布线算法

提出一个VLSI多层区域详细布线算法,算法使用模拟进化技术进行拆线重布线,对单个线网则使用改进型多层迷宫算法进行布线。     

MARS:一个通用多层区域布线算法

提出一个 VL SI多层区域详细布线算法 ,算法使用模拟进化技术进行拆线重布线 ,对单个线网则使用改进型多层迷宫算法进行布线。     

Full-Chip Scalable Routing Framework Considering Congestion and Performance

提出一个全新的全芯片可控布线系统框架,同时考虑布线拥挤度和芯片性能.为了在总体布线和详细布线之间架起桥梁,该框架把总体布线和详细布线集成起来,交互进行,每完成一个线网的布线,都及时对布线资源进行更新,由此可以得到精确的资源估计结果,有利于指导后续总体布线决策.该系统框架的主要特征包括快速的基于模式的和基于外框约束下最短路算法的总体布线器、基于迷宫算法的拥挤度驱动的详细布线器以及在两个布线器之间很好的交互性.在该布线系统框架中,为了优化电路性能,在布线中关键线网被赋予更高的优先级.同时,为了优化不同的布线目标,可以采用不同的线网排序策略.该布线系统框架在一套公用的测试电路上完成测试,并与之前提出的多级布线系统框架进行比较,实验结果表明,文中提出的布线系统框架在电路性能、布通率和运行时间方面都取得了很大改进.     

一种基于知识的双层四边通道区布线系统KBSRS

KBSRS是以我们提出的一种新的基于知识的四边通道区布线算法为基础，在SUN3／60工程工作站上用PASCAL及C道区布线系统．文中重点讨论了布线算法及KBSRS的实现．理论分析及实验结果表明．该系统具有较好的性能。     

一种VLSI零偏差时钟线网布线算法

本文给出了一种时钟线网布线的新算法。算法基本上消化了时钟偏差，并使线网总线长得到了最小化。其关键在于：１在旋转定位的基础上，采用平衡合并的原则构造时钟树拓扑结构，并在合并过程中，保证点与弧之间的连续优化。２根据拓扑表，确定详细布线时的连线走向，从而对总线长作出了进一步的优化。实验结果表明，我们的算法是有效的，能够较好地用一大规模集成电路的时钟线网的布线。     

一种减小关键路径延迟的回路布线法

传统的性能驱动布线算法受限于树形或固定的布线拓扑结构．本文提出一种回路性能优化布线算法，针对树形线网布线，通过在已存在的布线树上加入回路来减小所选择关键路径的延迟时间或线网的最大延迟．我们将互连线树归结为分布传输线网络并采用Ｅｌｍｏｒｅ延迟计算方法．本文证明，通过选择适当的ＲＣ，在连接节点与关键节点之间加入连线可达到减小所选择线网中关键路径延迟或线网最大延迟的目的．实验结果表明，我们的方法有效且可以集成在现有ＣＡＤ性能优化布线系统中．本文同时给出了所加入线段长度的计算方法．