Bottleneck Crosstalk Minimization in Two- and Three-Layer Manhattan Channel Routing

Abstract

VLSI physical design is a domain of work as old as more than five decades. Even then, as technology progresses, there are several challenging issues from the perspective of theoretical computer science as well as the high-performance requirements of the chip to be designed. Crosstalk is a threat to achieving routing solutions in high-performance VLSI circuits. As fabrication technology advances, closeness occurs among the devices and their interconnecting wires, the size of the devices and chips reduces, and circuits’ operational frequencies increase. These result in crosstalk, a kind of electrical hazard, which over stresses wire segments that are placed sideways. In this paper, it has been proved that the bottleneck crosstalk minimisation problems in the reserved two- and three-layer Manhattan channel routing are NP-complete. It has also been established that the hardness proclaims in approximating all allied crosstalk minimisation problems. As a natural consequence, heuristics have been devised to realise two- and three-layer bottleneck crosstalk routing solutions for different predefined bottleneck values employed over already computed channel routing solutions. Exhaustive experimentation has been performed and promising experimental results have been accomplished often sacrificing a bit more channel area.

Keywords

• Approximation algorithm
• bottleneck crosstalk
• channel routing problem
• crosstalk minimization
• heuristic
• high-performance routing