VLSI和PCB双层布线中的通孔最少化算法

本文提出了一个新的通孔最少化层分配的图模型．该模型克服了传统层分配算法对通孔度数和位置的限制，允许通孔自由地以任意度数和任何需要的位置出现．模型中还提出了通孔秩的概念，它比较能更精确地反映通孔的本质．在此基础上，本文将通孔最少化问题转化为图的最大割问题，并提出了一种启发式算法去求解图的最大割．算法已用Ｃ语言在ＳＵＮ工作站上实现．实验结果表明，算法十分有效且稳定．     

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

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

宏单元模式分级布图规划方法

本文提出一个新的宏单元模式分级布图规划方法.布图规划分三个阶段进行:芯片物理分级构造、布图规划和布图规划修正.主要特点包括:松弛对布图拓扑结构的约束、模块“自然”结群构造设计物理分级、采用解析方法求解面积规划问题、基于一个新的Steiner树算法求布线规划、包含模块面积估计和布线面积估计.实验结果表明提出的方法可以在满足不同形状和I/O设计目标的同时得到很高的芯片面积利用率.     

GEDS中的联机增量式设计规则检查及其实现

版图的联机增量式设计规则检查(IDRC)是指在版图设计过程中随设计的进行渐进完成版图设计规则检查.我们在版图交互编辑系统GEDS中嵌入并实现了一个IDRC过程.文中介绍了基本的设计规则检查算法和IDRC的实现策略.结合版图的分级设计还讨论了分级设计规则检查方法.     

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

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