Efficient Approximation Algorithms for Chemical Mechanical Polishing Dummy Fill
Efficient Approximation Algorithms for Chemical Mechanical Polishing Dummy Fill
复制标题
DOI：
10.1109/tcad.2010.2088030
复制
发表时间：
2011-03
影响因子：
2.9
通讯作者：
Chunyang Feng;H. Zhou;Changhao Yan;Jun Tao;Xuan Zeng
中科院分区：
文献类型：
--
作者：
Chunyang Feng;H. Zhou;Changhao Yan;Jun Tao;Xuan Zeng
为了减少化学机械抛光工艺中的芯片级形貌变化，广泛使用虚拟填充来提高布局密度均匀性。先前的研究将密度驱动的虚拟填充问题表述为标准线性程序（LP）。然而，解决由现实设计形成的巨大线性程序非常昂贵，并且已成为部署该技术的障碍。即使存在有效的启发式方法，也无法保证其性能。此外，虚拟填充还可以改变互连耦合电容，这可能对电路延迟、串扰和功耗产生重大影响。在本文中，我们开发了一种虚拟填充算法，该算法可用于解决传统的密度驱动问题和考虑填充引起的耦合电容影响的问题。所提出的算法既高效又具有可证明的良好性能，该算法基于 Fleischer 用于覆盖 LP 问题的完全多项式时间逼近方案。此外，基于近似算法，我们还提出了一种新的贪婪迭代算法，比以前基于蒙特卡罗的启发式方法更有效地获得高质量的解决方案。最终的实验结果证明了我们算法的有效性和效率。
To reduce chip-scale topography variation in chemical mechanical polishing process, dummy fill is widely used to improve the layout density uniformity. Previous researches formulated the density-driven dummy fill problem as a standard linear program (LP). However, solving the huge linear program formed by real-life designs is very expensive and has become the hurdle in deploying the technology. Even though there exist efficient heuristics, their performance cannot be guaranteed. Furthermore, dummy fill can also change the interconnect coupling capacitance which might lead to a significant influence on circuit delay, crosstalk, and power consumption. In this paper, we develop a dummy fill algorithm that can be applied to solve both the traditional density-driven problem and the problem considering fill-induced coupling capacitance impact. The proposed algorithm is both efficient and with provably good performance, which is based on a fully polynomial time approximation scheme by Fleischer for covering LP problems. Moreover, based on the approximation algorithm, we also propose a new greedy iterative algorithm to achieve high quality solutions more efficiently than previous Monte Carlo based heuristic methods. Final experimental results demonstrate the effectiveness and efficiency of our algorithms.