TY - GEN
T1 - Exact algorithms for coupling capacitance minimization by adding one metal layer
AU - Hua, Xiang
AU - Chao, Kai Yuan
AU - Wong, Martin D.F.
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
KW - Capacitance coupling
KW - Layer migration
KW - Max-cut
UR - http://www.scopus.com/inward/record.url?scp=84886712918&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84886712918&partnerID=8YFLogxK
U2 - 10.1109/ISQED.2005.55
DO - 10.1109/ISQED.2005.55
M3 - Conference contribution
AN - SCOPUS:84886712918
SN - 0769523013
SN - 9780769523019
T3 - Proceedings - International Symposium on Quality Electronic Design, ISQED
SP - 181
EP - 186
BT - Proceedings - 6th International Symposium on Quality Electronic Design, ISQED 2005
T2 - 6th International Symposium on Quality Electronic Design, ISQED 2005
Y2 - 21 March 2005 through 23 March 2005
ER -