一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.     

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

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

三维互连全耦合电容矩阵的层次式提取算法

基于直接边界元素法,提出一种边界电容矩阵概念,从而实现了三维互连电容的层次式提取算法.该算法将三维求解区域划分为若干小块,对每个小块分别计算其边界电容矩阵,再通过层次式合并算法便可得到全耦合互连电容矩阵.数值实验表明,本方法进行电容提取的速度比商业软件SpiceLink、虚拟多介质快速算法、区域分解法等均快一个数量级以上.     

SOC中Data-Path布图设计面临的挑战

目前所设计的系统级芯片(SOC)包含有多个data-path模块,这使得data-path成为整个G大规模集成电路(GSI)设计中最关键的部分.以往的布图理论及算法在许多方面已不能满足data-path布图设计的需要,这主要是由于传统的布图工具没有考虑data-path所特有的电路结构特点.Data-path具有规整的位片结构,具有很高的性能指标要求,如对于时延、耦合效应和串扰等性能都有严格的要求.此外,data-path中还存在大量成束状结构的BUS线网.文中提出了data-path布图设计所面临的挑战.从介绍data-path布图的基本问题入手,重点分析了data-path布图设计中的关键技术,并在讨论已有研究工作的基础上针对不同的布图阶段提出了可行的技术路线与设想.     

基于最小自由度优先原则的任意多边形模块布局算法

给出了直角多边形模块自由度的定义和公式,扩展了最小自由度优先原则,使算法能够处理任意直角多边形模块以及有相对约束的模块.实验结果说明该方法在布局效果和效率上都有良好的表现.     

Data-Path布图系统的数据管理

Data-Path布图系统需要有效的数据管理作为支撑。该数据管理工作主要包括数据格式转换、数据结构设计和数据接口设计等方面。针对一个实际的Data-Path布图系统，设计了Verilog文件到DEF文件的转换算法，进行了相关数据接口的实现，指出了数据管理的特点与实现方法。     

大规模混合模式初始详细布局算法

以大规模混合模式布局问题为背景,提出了有效的初始详细布局算法.在大规模混合模式布局问题中,由于受到计算复杂性的限制,有效的初始布局算法显得非常重要.该算法采用网络流方法来满足行容量约束,采用线性布局策略解决单元重叠问题.同时,为解决大规模设计问题,整体上采用分治策略和简化策略,有效地控制问题的规模,以时间开销的少量增加换取线长的明显改善.实验结果表明该算法能够取得比较好的效果,平均比PAFLO算法有16%的线长改善,而CPU计算时间只有少量增加.     

一种新型宏模块和标准单元的混合模式布局算法

本文针对包含有宏模块和标准单元的超大规模集成电路布局问题, 提出了一个新的混合模式布局算法MMP.该算法综合应用了自底向上的结群策略,数学规划和Slicing划分等技术.MMP算法可以对宏模块和小单元同时求解,算法稳定性好,实用性强,不但求解质量高,而且运算速度快.我们对一组来自工业界的设计实例进行了测试,实验结果表明,MMP是非常实用而高效的.     

基于不完全分解预优共轭梯度法的电源和地线网络求解器

在超大规模集成电路的电源和地线网络的设计中,求解由该网络上每个节点的电压和每条边上的电流是最基本的运算,它对电源和地线网络拓扑结构设计和线宽优化算法的质量具有直接的影响.针对电源和地线网络的特殊性,提出了一个高效的电源和地线网络求解器,包括电路网络中树结构的合并与恢复和用不完全分解的预优共轭梯度法来求解节点电压方程.该求解器的运算速度很快,所耗费的内存很小,同时具有很强的鲁棒性.     

基于不完全分解预优共轭梯度法的电源和地线网络求解器

在超大规模集成电路的电源和地线网络的设计中 ,求解由该网络上每个节点的电压和每条边上的电流是最基本的运算 ,它对电源和地线网络拓扑结构设计和线宽优化算法的质量具有直接的影响 .针对电源和地线网络的特殊性 ,提出了一个高效的电源和地线网络求解器 ,包括电路网络中树结构的合并与恢复和用不完全分解的预优共轭梯度法来求解节点电压方程 .该求解器的运算速度很快 ,所耗费的内存很小 ,同时具有很强的鲁棒性