今天的信息化社会和生活很大程度上归功于集成电路的伟大发展。集成电路自诞生到如今单片集成上亿个晶体管,短短几十年的时间里其制造技术和设计方法都发生了很大改变。集成电路的制造工艺节点已经从微米级别减小到纳米级别。光刻和化学机械抛光等先进制造工艺都表现出对芯片版图图形的依赖,并分别造成了电路元件横向和纵向尺寸的偏差。这些偏差最终影响到电路的性能和成品率。工艺偏差和芯片可制造性已经成为制约集成电路性能和成品率的关键因素。哑元填充是新一代设计方法学：可制造性设计和成品率驱动的设计方法中的重要技术。针对铜互连和化学机械抛光工艺的哑元填充是其最重要的应用。通过在原有版图中添加非功能性的金属线段,哑元填充可以改善芯片互连线层的材料分布,从而减小互连线尺寸的制造偏差。哑元填充技术的核心工作是根据多种约束条件确定具体版图位置上的哑元插入数量,即哑元综合。本论文的研究工作主要针对哑元综合算法展开,主要贡献如下：首先,提出了一种同时考虑版图图形密度、密度梯度和哑元填充量的哑元综合问题,并设计了一种基于覆盖线性规划(CLP)及其快速算法的求解方法。版图的密度梯度对芯片可制造性和成品率的影响在日益严格的制造工艺中越来越突出。但是传统的哑元填充方法却只考虑了版图密度的范围限制而无法有效约束梯度。本论文提出了一种高效的哑元综合算法,可以同时处理密度约束和梯度约束,并且最小化哑元插入数量。该方法以覆盖线性规划及其快速解法为基础构造了种迭代求解策略,并通过一些启发式的技巧加速了迭代算法的收敛。与传统的线性规划方法相比,该算法以增加少量的哑元为代价把该问题求解的时间复杂度从O(n3)降低到O(n2logn)。本论文分别采用理论分析和数值实验对所提出算法的性能进行了分析和验证。其次,针对考虑梯度约束的哑元综合问题,提出另一种采用梯度热点聚类和局部区域求解的算法。该算法首次在哑元综合优化过程中考虑版图图形的分布特征。根据梯度热点分布相对集中的特点,该方法首先利用聚类算法对存在的梯度热点进行分组,然后在芯片局部范围内利用小规模线性规划求解的高效性快速消除梯度热点。该算法与本文提出的迭代算法相比计算精度和速度都进一步提升,在实际使用中表现出出色的性能。另外,本论文还对基于模型仿真的哑元填充方法研究做了初步探索。在制造要求日益严格的情况下,密度规则驱动的填充方法开始遇到挑战,而考虑更多图形特征和精确工艺过程的基于模型仿真的方法是哑元填充技术未来的发展方向。本论文提出一种基于双层模型仿真：全芯片精确仿真和局部快速仿真的填充方法。在初步的实验探索和分析中,该方法表现出比传统的基于密度规则的方法对芯片平整度更好的优化作用,在相同的填充量下芯片的平整度改进超过50%。