Lower-power and min-crosstalk channel routing for deep-submicron layout design

Consider a set of nets given by horizontal segments S = {s(1), s(2),...,s(n )} and a set of tracks T = {t(1), t(2),..., t(k)} in a channel, then a trac k assignment consists in an assignment of the nets to the tracks such that no two nets assigned to the same track overlap. One important goal is to fi nd a track assignment with the minimum number of tracks such that the signa l interference between nets assigned to neighboring tracks is minimized. Th is problem is called crosstalk minimization. For a given track assignment w ith k tracks, crosstalk can be reduced by finding another track assignment for S with k tracks (i.e., by permuting tracks). However, considering all p ossible permutations requires exponential time. For general cost function f or crosstalk measure, the problem is NP-hard. Several heuristic approaches were previously presented. In this paper, we consider special instances of the crosstalk-minimization problem where the cost function depends only on the length of the segments that runs in parallel and all pairs of segments intersect. An algorithm solving this problem in O(n log n) time is presente d. An extension applied to the instances with more general function of swit ching activity and mixed signal sensitivity to reduce crosstalk and power c onsumption is also presented.