模拟集成电路二维Stack生成及模块合并算法

在模拟集成电路设计中,关于X轴和y轴同时对称的Stack,以及模块之间的合并,对于增加器件之间的匹配和控制寄生是至关重要的.描述了模拟集成电路二轴对称Stack生成算法和模块合并算法.通过对于对称欧拉图和对称欧拉路径的研究,得出了多项理论结果.在此基础上,提出了时间复杂度为O(n)的伪器件插入算法、对称欧拉路径构造算法和二轴对称Stack生成算法.生成的Stack,不但关于X轴和y轴对称,而且具有公共质心(commoncentroid)的结构.还描述了模块合并算法,给出了计算最大合并距离的公式.该算法本质上是独立于任何拓扑表示的.实验结果验证了算法的有效性.     

考虑通孔电阻和耦合电容的时延驱动的层分配算法

针对集成电路设计的多层布线问题,提出了以直接优化互连时延为目标、同时考虑通孔电阻与耦合电容的层分配算法.通过基于路径的时延分析寻找电路的关键路径,以通孔的时延模型和概率耦合电容模型作为层分配模型计算资源分配的代价,利用基于启发式的贪婪算法进行层分配.实验结果表明:该算法比只控制通孔和耦合电容数量的层分配策略具有更大的优势.     

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

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

基于序列对表示的对齐约束模块布局算法

在片上系统(SOC)的设计中,常常需要把某些单元摆放在某一预定坐标线附近相对较小的区域内.这一约束的来源是,在总线结构中,通过总线传递的数据,应当同步地出现在总线上,不能有较大的时延.对带有预定坐标线对齐(PCA)约束的模块布局问题进行研究,导出了约束模块之间的一系列关系,由此得到满足约束布局的必要条件.并且设计了多项式时间复杂度的算法,能够确保得到可行的模块布局.使用ami33和ami49对该算法进行了测试.实验结果证明,算法是有效的.     

基于角模块布图表示的增量式布图规划算法

提出了一种基于CBL布图表示的新的增量式布图规划算法.该算法能很好地解决包括不可二划分结构在内的布图规划问题.针对现有增量式的一些需求,算法给出了相应的高速解决方案.在已有的初始布局的基础上,基于CBL表示方法建立水平约束和垂直约束图,利用图中关键路径和各模块之间的累加的距离松弛量进行增量式操作.对于新模块的插入,在力求面积最小,线长最短和移动模块数目最少的目标指引下能快速地找到最佳位置作为插入点,高效地完成相关操作,算法的时间复杂性仅为O(n).通过对一组来自工业界的设计实例的测试结果表明,该算法在保证芯片的面积、线长等性能不降低甚至有所改善的情况下,运行速度相当快,仅在μs量级,满足了工业界对增量式布图规划算法在速度上的首要要求,同时保证了基本性能的稳定.     

针对同步时序电路VHDL设计的有效模型判别器VERIS

介绍了一个针对同步时序电路VHDL设计的性质验证的解决方案-一个有效的符号模型判别器VERIS,该模型判别器利用同步时序电路设计的特点以及待验证性质的局部性,可显著地减少有限状态机（FSM）的状态空间;大大地提高可达性分析和性质验证的速度;同时,实现了反例生成机制,实验结果表明,与Deharbe的模型判别器相比,用这个模型判别器验证一些基准电路更加适用于同步时序电路。     

基于Sakurai模型的时延驱动Steiner树算法

时延驱动的Ｓｔｅｉｎｅｒ树构造算法是时延驱动总体布线的基础．本文首先简介了求解最佳Ｓｔｅｉｎｅｒ树的Ｄｒｅｙｆｕｓ－Ｗａｇｎｅｒ算法．随后通过引入Ｓａｋｕｒａｉ时延模型,提出了直接基于Ｓａｋｕｒａｉ模型的提高线网时延性能的时延驱动ＤＷ算法．当集成电路工艺的特征宽度较小时,该算法求得的Ｓｔｅｉｎｅｒ树中关键点的时延值,明显小于ＩＤＷ和ＣＦＤ算法的结果．     

深亚微米工艺下互连线串扰问题的研究与进展

集成电路工艺发展到深亚微米技术后,互连线串扰问题变得越来越严重,尤其在千兆赫兹的设计中,耦合电感的影响不能忽略.插入屏蔽的操作成为减小耦合电感噪声的有效方法.文中首先介绍共面、微带状线和带状线三种互连结构下的电感耦合特性,然后分别介绍了基于共面互连结构的用于计算互连线噪声的Keff模型和RL C精确噪声模型.实验表明两种模型都有很高的精确度,在解决互连线串扰的物理设计中有广泛的应用     

一个基于层次式PB角钩链结构的区域布线器

提出一个新的基于层次式PB角钩链结构的多层无网格布线器.该布线器基于PB层次式角勾链数据结构和网块扩展算法,使用朝向目标的加速策略提高算法的运行速度,并使用改进的二叉区间树管理算法的中间数据.还提出了基于拥挤度的无网格拆线重布算法.通过显式记录每个线网段周边的拥挤状况,并将其结合到网块扩展的费用当中,使拆除线网的选择和待布线网的路径搜索统一起来.实验结果表明,该布线器能有效地提高布通率,且算法运行速度较快.     

标准单元布局中的高效结群算法

本文提出了一个高效的结群算法,用以解决在超大规模条件下标准单元模式集成电路的布局问题.与传统结群算法相比,本算法的特色在于在结群之前,建立和组织了表示所有单元之间连接关系的信息库,使得结群算法具有全局优化性和无冗余计算的特点.本结群算法已应用于二次规划布局过程中.实验结果表明,本算法无论在结群质量和结群速度方面都非常理想,从而成功地解决了超大规模电路的布局问题.