Crosstalk minimization in channel routing for VLSI circuit synthesis

Abstract

The channel routing problem (CRP) is the problem of computing a feasible routing solution for the nets present in a channel so that the number of tracks required to route the channel is minimized. A channel is a rectangular routing region that has two open ends, the left and right sides of the region, and the other two sides of the channel contains two rows of fixed terminals. The major cost factors that, in isolation or in combination, are normally minimized in CRP are the area, net wire length, via, and layer of interconnection. Besides, there are several other high performance factors like signal delay, power consumption, heat generation, hot spot formation, electrical hazards, and so on and so forth that are all research issues nowadays and these objectives are needed to be considered in channel routing to maximize the chip performance, even after a feasible routing solution is there. In this thesis, we have considered the problem of crosstalk minimization as a kind of electrical hazard that need to be reduced to enhance circuit performance. As fabrication technology advances and feature size reduces, devices are placed in closer to each other and interconnecting wire segments are assigned with narrower pitch, whereas the circuits’ operations are realized at higher frequencies. As a result, electrical hazards, viz., crosstalk between wire segments are evolved. More crosstalk means more noise and more signal delay that reduce the circuit performance. Therefore, it is desirable to develop channel routing algorithms that not only reduce the channel area but also crosstalk. Work on routing channels with reduced crosstalk is very important from high performance requirement for VLSI circuit synthesis. There are several theoretical problems on crosstalk minimization in two-layer channel routing, some of which are posed and proved as NP-complete in this thesis. Subsequently, this thesis includes algorithms that have been designed for reducing crosstalk in two-layer channel routing, devises algorithms for generation of a large number of random channel specifications, parallel algorithms for minimizing crosstalk, heuristics for lessening crosstalk for reduced area routing solutions in order to optimize cost and maximize circuit performance that are some of the prime contributions in brief to mention. In this work, we have studied the computational complexity issues of the crosstalk minimization problem for simple and general instances of channel specification with a partition of nets so that the nets in a class of the given partition are to be assigned to the same track, the simple as well as general instances of channel specifications with only two-terminal nets but without any imposed partition of (non-overlapping) nets to tracks, the bottleneck crosstalk minimization problem, and so on and so forth in the reserved no-dogleg two-layer VH channel routing model. In all these cases, the problems are considered when doglegging is allowed as well. We further investigate the existence of exact or heuristic algorithms and approximation algorithms for the abovementioned problems of crosstalk minimization in two-layer channel routing. This thesis also identifies that the crosstalk minimization problem in the three-layer VHV and HVH channel routing models are yet open for future researchers.