层次化方法是解决复杂问题的有效方法，也是系统化方法中最基本的手段。集成电路版图综合、设计验证是一个极其复杂的问题，一方面是由于版图综合、验证问题的规模庞大，例如目前单片VLSI包含的晶体管数已达几千万甚至上亿个个，另一方面是由于工艺的不断发展，版图特征线宽已发展到深亚微米阶段，芯片工作频率已达GHz级，对版图布局布线提出了更多的约束条件和目标，设计验证需要考虑更多的电路参数和复杂的相互作用。本论文包括两个部分，第一部分探讨了VLSI芯片P／G网验证问题，提出基于网络划分、子网等效压缩变换的大规模线性方程组求解方法；第二部分探讨了一个晶体管级宏单元自动版图布线系统的有关理论问题，并实现了一个实用的处理宏单元版图的自动布线系统。 由于芯片内互连线作用已占相当重要的地位，在对互连线网络作精确的设计验证，例如，芯片电源／地网的供电性能的验证，是芯片工作的可靠性的保证。由于电源／地网的网络极其庞大，采用通常的计算方法无法在内存占用／时间耗费上同时满足需求。应用层次化思想，本文通过对线性方程组求解的网络模型分析，提出了一种基于网络分割、等效压缩的算法。算法首先利用版图几何特征，按最小割原理将电源／地网划分成子网，利用对称正定矩阵Cholesky分解压缩子网内点；将子网等效成与网络其它部分连接的结点集的等效网络，最后通过计算压缩后的网络，获得线性方程组求解答案。该算法同时在验证运算的速度／内存空间占用上获得高效。 与设计验证问题一样，VLSI布图问题同样需要层次化方法解决。通常，基于标准单元布图模式将版图综合划分成单元内与单元间两个层次，以简化芯片级自动版图综合问题的复杂性；但随着芯片规模的不断扩大，基于主要以手工定制的小规模标准单元，芯片级版图综合问题的复杂性不断增大，且标准单元间布线无法充分利用单元内晶体管特征，影响芯片的整体性能。本文基于芯片、宏单元、晶体管群三级的层次化架构，实现了一个宏单元自动布线系统。 论文首先提出了晶体管群之间的线网布线问题，通过分析优化矩形斯坦纳树 的性质，提出了一种符合宏单元布局特征的近似矩形斯坦纳树构造算法，同时针 对晶体管群DVC内引线端点间走线互斥关系，提出斯坦纳树可选端点筛选策略。 硅栅工艺晶体管级布线利用多晶层走线，为了控制宏单元时延性能及改善信 号完整性形态，关键是不同线网间交叉的均衡分配以减少走线的换层次数，最大 化金属层走线以及每一线网多晶层走线长度的有效控制。本文提出了一个适用于 BBL结构的多线网交叉分布算法，能合理分配介线区域内不同线网的走线道位 置关系，和选择走线层分配的不同方案。 晶体管级实体布线阶段，由于库单元的复用性，要求库单元版图紧凑，即要 求单元版图在满足各约束条件的前提下面积、性能优化程度较高，能与手工设计 的版图相媲美。本文提出了一个无网变线宽、最小化走线换层的通道布线算法。 该算法基于非严格分层的布线模式hnxeserved layer model人基于拓扑交叉分析 实现无约束最小化换层层分配算法，最小化多晶线走线与最大化金属层走线；线 网划分、层分配可对关键线网实行预分配；对单层网段使用有关平面化布线算法 实现无网变线宽走线，并利用接触孔移动技术压缩布线面积。 晶体管级布线问题的特征是金属层与多晶层非对称布线，最大平面化和金属 层布线。完成优化层分配和金属一层布线之后的线网，其它层走线相当于连接相 应端点与该浮动点。文中分别提出了单端浮动、两端浮动两种浮动点的实用化布 线算法。