随着集成电路信号频率的提高和集成电路特征尺寸的减小,越来越多在集成电路发展初期影响甚微的物理效应逐渐成为制约集成电路性能提升的主要因素。作为其中的代表性因素,互连线寄生效应不仅会增加电路中的信号延迟,还会带来信号完整性方面的问题,甚至会扰乱电路的逻辑功能,影响电路的正常工作。与此同时,为解决化学机械抛光(CMP)工艺所带来的芯片平整度问题,哑元填充(Dummy Fills)技术被越来越广泛地使用。然而,电路中存在的大量哑元单元不仅大幅增加了电路的寄生电容值,也向传统的寄生电容提取算法提出了新的挑战。如何快速而准确地提取含有大量哑元的电路寄生电容,已经成为计算机辅助设计领域中的重要问题,对于提高集成电路性能和成品率有着重要意义。针对含哑元电路的寄生电容提取问题,本文提出了一种考虑悬浮哑元的结构化随机行走寄生电容提取算法。本文首先利用区域分解技术,将电路中的哑元区域分离,并根据区域内部哑元单元的分配特点,对哑元区域进行再划分；然后,对于再划分后具有标准几何结构的子哑元区域,计算其马尔可夫转移矩阵(Markov Transition Matrix/MTM);最后,本文提出了基于概率转移的随机行走算法,将传统的阶跃式随机行走过程拆分为3个子过程——哑元区域内的概率转移过程、哑元区域内的随机行走过程和外部区域的随机行走过程。在计算电路的寄生电容矩阵时,本文方法不仅可以有效利用哑元阵列在几何结构和单元分布上的特点,还可以通过对标准哑元结构建立宏模型,提高MTM计算结果的复用率,进一步加快电容的提取速度。实验结果表明,同传统的基于随机行走的寄生电容提取算法相比,本文方法可以在保证算法精度的前提下提高寄生电容的提取速度。