Hardness of crosstalk minimization in two-layer channel routing
| Autor: | Alak Kumar Datta, Rajat Kumar Pal, Achira Pal, Atal Chaudhuri |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Very-large-scale integration
0209 industrial biotechnology Engineering Vlsi circuit design business.industry Two layer Approximation algorithm Hardware_PERFORMANCEANDRELIABILITY 02 engineering and technology Bottleneck 020901 industrial engineering & automation Crosstalk minimization Hardware and Architecture Hardware_INTEGRATEDCIRCUITS Electronic engineering Electrical and Electronic Engineering business Software Hardware_LOGICDESIGN Communication channel Electronic circuit |
| Zdroj: | Integration. 56:139-147 |
| ISSN: | 0167-9260 |
| DOI: | 10.1016/j.vlsi.2016.10.001 |
| Popis: | Crosstalk minimization is one of the most important aspects of high-performance VLSI circuit design. With the advancement of fabrication technology, devices and interconnecting wires are being placed in close vicinity, and circuits are operating at higher frequencies. This results in crosstalk between adjacent wire segments. In this paper, it has been shown that the crosstalk minimization problem in the reserved two-layer Manhattan routing model is NP-complete, even if channels are free from all vertical constraints. It has also been demonstrated that it is hard to approximate the crosstalk minimization problem. Besides, the issue of minimizing bottleneck crosstalk has been introduced that is a new problem for crosstalk minimization. It has been proven that this problem is also NP-complete. It has been further shown that all these results hold even if doglegging is allowed. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect