Lower-Power and Min-Crosstalk Channel Routing for Deep-Submicron Layout Design

Consider a set of nets given by horizontal segments S = {s1, s2, ..., sn} and a set of tracks T ={t1,t2,...,tk} in a channel, then a track assignment consists in an assignmentof the nets to the tracks such that no two nets assigned to the same track overlap. Oneimportant goal is to find a track assignment with the minimum number of tracks suchthat the signal interference between nets assigned to neighboring tracks is minimized.This problem is called crosstalk minimization. For a given track assignment with ktracks, crosstalk can be reduced by finding another track assignment for S with k tracks (i.e., by permuting tracks). However, considering all possible permutations requiresexponential time. For general cost function for crosstalk measure, the problem is NPhard.Several heuristic approaches were previously presented. In this paper, we considerspecial instances of the crosstalk-minimization problem where the cost function dependsonly 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 presented. An extensionapplied to the instances with more general function of switching activity and mixedsignal sensitivity to reduce crosstalk and power consumption is also presented