VLSI积木块布图设计的通道定序与布线

本文研究了VLSI积木块布图设计中的通道定序与布线问题。首先提出了T形约束图的概念和通道分级的思想,针对布局中出现的循环通道约束,基于三边通道的布线,通过引入一类通道——预定通道来破坏约束环。在此基础上,给出了一个在给定积木块的布局和总体布线条件下通道定序与布线的有效算法。算法已在UNIVAC1100/10上用FORTRAN77实现,结果令人满意。     

基于线网路径总体分配的LSI环形通道全局布线方法

大规模集成电路(LSI)中,在芯片周界的环形区域内,环形通道布线完成线网与压焊块的自动连接与压焊块的最终定位.基于环形通道区的特征与线网路径约束关系的分析,本文提出一个新的环形通道自动全局布线方法.文中详细地讨论了线网拓扑路径总体分配的图模型和轨道优化分配公式,并介绍实现的算法.实例结果十分令人满意,优于国外同类问题的最新算法的结果.     

VLSI版图综合中的P／G网实体优化布线

本文提出了一种在通道内将Ｐ／Ｇ网与信号网的实体布线一体化考虑的优化布线策略，目的是在保证１００％布通的前提下，完成Ｐ／Ｇ网的平面化实体嵌入和信号网的实体布线，并使Ｐ／Ｇ走线对信号网走线的影响尽可能小。算法以提高布线区利用率、减小通道高度和减少通孔数为目标，实现总体性能的优化。系统实现的结果表明，本文算法所采用的策略是可行的、有效的。     

LSI版图设计中的一种P／G网布线法

本文提出了一种有效的P/G网布线算法和在积木块式布图系统中实现的策略。与以往算法比较,此算法允许每条电源网具有多个馈电脚存在。其策略包括四个部分:(1)一种有效的层次式自上而下的P/G网平面性分析和拓扑路径分配算法;(2)P/G网线宽的确定;(3)总体压缩和再布线后P/G网布线信息的动态修改;(4)与信号网一起的平面性无网格电源网通道详细嵌入。实验结果表明我们的P/G网布线方法可获得令人满意的布线结果。     

CMOS门阵列的一种布线方法

本文提出了一种适合于单层铝在线CMOS门阵列的布线方法.对于不同的电路只要求改变铝布线设计就可完成.由于布线区域是固定的,通道中的走线密度不能超过系统预先给定的容量,同时,所有的信号连接端一般都须经多晶硅条方能引出,因而不允许存在两个或两个以上的不同信号网的连接端分配到同一条多晶硅上.为此,在本文中提出了一个信号连接点的线性规划算法和通道调整的子树连接算法,较好地解决了信号连接点在多晶硅条上的分配问题以及固定布线区域问题.     

超平面布线

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

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

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

用于宏单元阵列的自动布局算法

本文针对宏单元阵列的特点,提出了构造布局和布局改善同时进行的布局算法和以布局均匀和信号网分布均匀为主要目标的多目标布局评价函数.它在布局过程中就考虑到布局对布线的影响,并自始至终地把总体布线的思想恰如其份地和布局问题结合起来.另外,比以在的算法增加了以局部区域通道布线密度下降为目标的通道布线密度均匀化处理,从而极大地减少了由于局部区域拥挤而造成整个布图失败的可能性.实用结果表明该算法的布局效果是良好的.     

MAP-NSF算法的收敛条件和适用范围扩展

为了拓宽最大后验概率-噪声子空间拟合（MAP-NSF）算法在信号到达角估计上的适用范围,针对通道特性失配和非结构误差两种阵列扰动模型,对MAP-NSF算法的信号到达角估计问题进行了讨论。给出了两种误差模型参数化之间的关系,通过分析,得到了在非结构误差模型下MAP-NSF算法的收敛条件,同时证明了在通道特性失配模型下,MPA-NSF算法可适用于有限样本误差与非结构误差与非结构误差不同量级时的情况。数值仿真结果证实了所得到结论的正确性。     

双基星载HRWS鄄SAR系统方位向信号重构的最小二乘算法

双基星载高分辨率宽测绘带合成孔径雷达系统(HRWS-SAR)的方位向信号普遍为非均匀采样,重构其均匀采样信号或多普勒频谱是成像处理的关键步骤。文中将方位照射时间内时变的发射接收距离比近似为常数,利用双基系统与单基系统方位向通道间传递函数的等效关系,建立了一般双基构型星载HRWS-SAR 系统的方位向信号模型,构建了方位向信号重构的最小二乘算法,利用传递函数矩阵的Vandermonde矩阵表示有效降低算法复杂度,并给出了重构性能指标信噪比缩放因子及方位模糊比的计算公式。文中对几种典型双基构型的星载HRWS鄄SAR 系统进行方位向信号重构仿真,结果表明最小二乘算法能较高性能的重构出方位向信号的多普勒频谱。     

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

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

二向不等距网格上的通道区布线及其实体化

本文讨论了在硅栅或铝栅MOS 电路工艺中,利用单层金属布线完成自动布线时所存在的二向不等距网格上的布线问题,提出了解决的方法并给出了实际应用的结果,结果表明,在绝大部分情况中,可在不影响布线精度的前提下令人满意地解决上述问题.     

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

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

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

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

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

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

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

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

一种新的无网格拆线重布算法

结合无网格布线的特点,提出一种新的无网格拆线重布算法.该算法显式地表示并动态更新线网所属区域的拥挤程度.在拆线重布进行待布线网的路径搜索时,每个扩展节点中增加拆除线网周边的拥挤权重,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来,有效地提高了被拆除线网重新布通的可能性.该算法利用改进的二叉区间树有效组织中间数据,降低计算的复杂度.实验结果表明,该算法能有效消除布线顺序对布线结果的影响,提高布通率,且算法运行速度较快.     

一种新的无网格拆线重布算法

结合无网格布线的特点,提出一种新的无网格拆线重布算法.该算法显式地表示并动态更新线网所属区域的拥挤程度.在拆线重布进行待布线网的路径搜索时,每个扩展节点中增加拆除线网周边的拥挤权重,从而将待布线网的路径搜索过程和拆除线网的选择过程统一起来,有效地提高了被拆除线网重新布通的可能性.该算法利用改进的二叉区间树有效组织中间数据,降低计算的复杂度.实验结果表明,该算法能有效消除布线顺序对布线结果的影响,提高布通率,且算法运行速度较快.     

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

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

针对一种岛式FPGA布局布线方法的研究与改进

针对一种岛式FPGA(Field Programmable Gate Array)芯片VS1000的架构,开发了一种布局布线工具VA,该工具在VPR的基础上做了两方面改进.第一,在传统布线算法的布线资源图基础上建立了全局信号布线资源图,完成了对全局信号的布线,使全局信号布线与其他信号布线独立起来,以达到减少全局信号相对延时和节省通用布线资源的目的.第二,提出了两种新的布线顺序:高扇出线网优先和高关键度线网优先.实验结果表明,对于标准测试电路,高扇出优先的布线顺序平均可减少21.8%的迭代次数,高关键度优先的布线顺序平均可减少22.3%的关键路径延时.