Exact algorithms for coupling capacitance minimization by adding one metal layer

Xiang Hua, Kai Yuan Chao, Martin D.F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Due to the rapid development of manufacturing process technology and tight marketing schedules, chip design and manufacturing always work towards an integrated solution to achieve an enhanced product for fast time-to-market and higher niche profit. For high-end high-volume products, one good option for further improving chip performance is to add extra metal layers based on an existing design after all easy circuit fixes and process tricks have been applied. This strategy has been applied by the main integrated device manufacturers. In contrast to most low volume ASIC, the additional metal layer cost is low due to cost averaging over huge volumes. We address the 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 metal layer newly inserted under the 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. For n wire segments, the time complexity of the algorithm is O(n/sup 3/2/log(n)). Finally, an LP approach is presented as post processing to adjust segment positions when the two layers have layer-dependent design spacing rules.

Original languageEnglish (US)
Title of host publicationProceedings - 6th International Symposium on Quality Electronic Design, ISQED 2005
Pages181-186
Number of pages6
DOIs
StatePublished - 2005
Event6th International Symposium on Quality Electronic Design, ISQED 2005 - San Jose, CA, United States
Duration: Mar 21 2005Mar 23 2005

Publication series

NameProceedings - International Symposium on Quality Electronic Design, ISQED
ISSN (Print)1948-3287
ISSN (Electronic)1948-3295

Other

Other6th International Symposium on Quality Electronic Design, ISQED 2005
Country/TerritoryUnited States
CitySan Jose, CA
Period3/21/053/23/05

Keywords

  • Capacitance coupling
  • Layer migration
  • Max-cut

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Exact algorithms for coupling capacitance minimization by adding one metal layer'. Together they form a unique fingerprint.

Cite this