一种化学机械抛光工艺哑元填充方法

摘要

本发明属集成电路半导体制造技术领域，涉及一种化学机械抛光工艺的哑元填充方法。本发明将求解最小化哑元金属数目的哑元填充问题转化成一类特殊的覆盖线性规划CLP问题，然后根据CLP问题的特点，应用组合优化领域中一种完全多项式时间近似算法FPTAS来求解最小哑元填充问题。该方法既可以保证最终结果的ε最优性，又可以实现最终结果精度和计算速度的折中，解决了现有方法中存在的速度和精度不能兼顾的难题；该方法还可以在线性时间复杂度下，获得近似最少的哑元填充数目，可用于解决大规模版图哑元填充问题。

主权项

一种化学机械抛光工艺哑元填充方法，其特征在于包括如下步骤：步骤1：输入待填充的版图、给定版图金属密度的上下界、版图上允许哑元填充的可行区域以及近似精度ε；步骤2：将最小化哑元金属数目的哑元填充问题转化成一种特殊的覆盖线性规划问题；步骤3：应用完全多项式时间近似算法FPTAS求解最小哑元填充问题。