性能驱动总体布线的关键技术及研究进展

在计算机软件领域,超大规模集成电路技术的迅猛发展迫切需要高性能CAD工具——电子设计自动化(EDA)软件工具的支持.与物理设计相关的CAD技术称为布图设计,总体布线是布图设计中一个极为重要的环节.目前,在深亚微米、超深亚微米工艺下的超大规模、甚大规模集成电路设计中,性能驱动总体布线算法已成为布图设计中的一个国际研究热点.针对这一热点,分析了性能驱动总体布线算法研究中亟待解决的关键技术,并详细阐述了国内外的重要相关研究工作进展情况.  

一种新的与线网顺序无关的随机优化总体布线算法

针对目前总体布线中仍然存在的3个关键问题；布线结果受布线顺序的影响、总体布线图中拥挤区域的不可预见性、线网连接式样受到算法的限制等，该文提出了一种新的不受线网顺序影响的总体布线算法，并实现了相应的总体布线器RINO－Router。该算法采用随机优化方法来保 证先后被拆线重布的线网有相同的通过拥挤区域的机会，并能得到GRG边的拥挤度估计值；采用高效的Steiner树改造算法构造避开拥挤区域的布线树，采用典型电路实例进行了测试，并将布线结果与基于多商品流算法的总体布线器Matula-Router进行了对比。结果表明，RINO－Router能够在短得多的运行时间内求得质量与Matula-Router相近的总体布线解。  

FaSa: A Fast and Stable Quadratic Placement Algorithm

Placement is a critical step in VLSI design because it dominates overall speed and quality of design flow.In this paper,a new fast and stable placement algorithm called FaSa is proposed.It uses quadratic programming model and Lagrange multiplier method to solve placement problems.And an incremental LU factorization method is used to solve equations for speeding up.The experimental results show that FaSa is very stable,much faster than previous algorithms and its total wire length is comparable with other algorithms.  

基于部分随机行走的电源线/地线(P/G)网络快速求解方法

介绍一种基于随机行走方法与松弛迭代(SOR)算法相结合的快速电源网络求解方法，它先将P／G网分为若干块，然后用简化的随机行走方法求取电路块边界结点的电压，最后采用松弛迭代算法求出电路块内部结点的电压．同时还给出了一种电路块从对角顶点向中央求解的策略，并将此方法推广到采用RLC瞬态网络的求解．大量的实验数据表明，受限于P／G网供电PAD的数目较少这一现实，随机行走方法的效率比较低，在此情形下，该方法比随机行走方法快20倍．  

An Optimum Placement Search Algorithm Based on Extended Corner Block List

A non-slicing approach,Corner Block List(CBL),has been presented recently.Since CBL only can represent floorplans without empty rooms,the algorithm based on CBL cannot get the optimum placement.In this paper,an extended corner block list,ECBLλ,is proposed.It can represent non-slicing floorplan including empty rooms.Based on the optimum solution theorem of BSG(bounded-sliceline grid),it is proved that the solution space of ECBLn,where n is the number of blocks,contains the optimum block placement with the minimum area.A placement algorithm based on ECBLλ,whose solution space can be controlled by setting λ,the extending ratio,is completed.Whenλ is set as n,the algorithm based on ECBLn is the optimum placement search algorithm.Experiments show that λ has a reasonable constant range for building block layout problem,so the algorithm can translate an ECBLλ representation to its corresponding placement in O(n) time,Experimental results on MCNC benchmarks show promising performance with 7% improvement in wire length and 2% decrease in dead space over algorthms based on CBL.Meanwhile,compared with other algorithms,the proposed algorithm can get better results with less runtime.  

PhyD-XML:VLSI物理设计数据标记语言设计与实现

深亚微米时代芯片互连对芯片性能的影响加剧，对物理设计方法、工具与算法的集成提出了新的要求，在对XML技术进行分析的基础上，提出基于可扩展物理设计数据标记语言的集成方法．借助结构化和面向对象分析技术，对物理设计阶段的信息进行整理分析，设计了一种易于扩展的基于对象的结构化数据模型和物理设计数据可扩展标记语言PhyD—XML，并给出语言的实现结构和集成构架．  

一种基于结群的零偏差时钟布线算法

介绍了一种基于结群的零偏差时钟布线算法，该算法采用新的单元匹配策略，递归地把时钟节点划分成2个负载和半径比较均衡的子集，结合缓冲器的适当插入，产生一棵零偏差的时钟布线树。实验表明，结群处理对处理规模较大的电路快速有效，时钟延迟得到了明显减少。  

直角多边形布图区域内的二次布局算法

提出了一种直角多边形布图区域内的基于动态划分的二次布局算法——DPRR．通过在传统的二次布局算法中引入一种新的圆盘划分和分布约束生成策略，解决了直角多边形布图区域里的单元布局问题，并且由于该算法在迭代优化过程中动态地划分电路并生成分布约束，且不限制单元在布图区域的不同部分间自由移动，所以它可以在一定程度上避免优化过程中出现的“局部最优”，从而达到更高的布局质量．对一些电路实例的测试和比较结果也证明DPRR是一种高效优良的布局算法，并且它十分适用于解决非矩形的直角多边形布图区域内的标准单元布局问题．  

基于几何多网格的RLC电源网络的瞬态模拟

提出了一种高效的、针对VLSI中Mesh拓扑结构的RLC电源线／地线网络的时域分析算法，该算法首次利用一种基于启发式原则的电路模型的简化方法来缩小电路网络的规模，扩展了原有的几何多网格方法来模拟求解以RLC元件建模的电源线网络．实验数据表明，对于一些规模较大的电路实例，在一个较小的误差损失下，该算法能大幅缩小电路的求解规模，求解速度比SPICE快两个数量级以上，比原有的几何多网格方法也有大幅的提高．如在Sun工作站上，当误差控制在1．5％时，模拟求解一个百万节点的电路网络仅仅需要半个小时．  

混合模式自动布局系统EMMP的设计与实现

混合模式电路的特征是在大量的标准单元电路中混入一些电路宏模块，这些宏模块的大小和数量在不同的电路中存在着巨大的差异，给现有的布局技术带来了巨大的挑战,使得一些商业的布局软件无能为力。文章介绍了一种混合模式自动布局系统EMMP，该系统采用划分、模块级规划、单元级总体布局和详细布局等技术相结合的方式，在统一的数据环境基础之上，自动完成电路所有单元的布局定位任务。实验数据表明，该系统能够适应不同类型的混合模式电路的布局，并能够在合理的运行时间里获得线长指标优良的布局质量。