Exact Algorithms for Coupling Capacitance Minimization by Adding One Metal Layer

Due to the rapid development of manufacturing process technology and tight marketing schedule, the chip design and manufacturing always work toward an integrated solution to achieve enhanced product for fast time-to-market and higher niche profit. For high-end "high-volume" products, one good option of further improving chip performance is to add extra metal layers based on an existing design after all easy circuit fixes and process tricks are already applied. This strategy has recently been applied by main integrated device manufacturers. Contrast to most low volume ASIC, additional metal layer cost is low due to cost averaging over huge volume (e.g., millions per week for x86 mainstream microprocessors). In this paper, we address NLM (New Layer Migration) problem which eliminates coupling capacitance violations for speed push in a given routing solution by migrating some wire segments to a newly inserted metal layer under commonly used metal filling post process for manufacturability and coupling control. We first propose an exact linear-time algorithm to judge whether a feasible solution exists or not. Then we present a provably optimal algorithm to eliminate as many coupling violations as possible. At the same time, the total coupling capacitance on both metal layers is minimized. The time complexity of the algorithm is . Finally an LP approach is presented as post processing to adjust segment positions when the two layers have layer-dependent design spacing rules.