Hardness of crosstalk minimization in two-layer channel routing

详细信息    查看全文

• 作者：Achira Pal (nee Biswas)^a ; ^{achira.pal@gmail.com} ; Atal Chaudhuri^a ; ^{atalc23@gmail.com} ; Rajat Kumar Pal^b ; ^{pal.rajatk@gmail.com} ; Alak Kumar Datta^c ; ^{alak.datta@visva-bharati.ac.in}
• 关键词：Approximation algorithm ; Channel routing problem ; Crosstalk minimization ; Doglegging ; High-performance routing ; NP-hardness
• 刊名：Integration, the VLSI Journal
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：56
• 期：Complete
• 页码：139-147
• 全文大小：1315 K
• 卷排序：56

文摘

Crosstalk minimisation is one of the most important aspects of high-performance VLSI circuit design. Crosstalk minimisation in the reserved two-layer Manhattan routing model is NP-complete, even without vertical constraints. It is hard to approximate the crosstalk minimisation problem. The problem of minimising bottleneck crosstalk is also NP-complete. We have further shown that all these results hold even if doglegging is allowed. We have incorporated the reviewer suggestions to the best of our abilities.