Decreasing Channel Width Bounds by Channel Widening

Abstract:

Under the 2-layer Manhattan model for channel routing, the problem of minimizing the channel width, i.e., finding the smallest possible number of tracks required, is NP-complete. So, when a quick estimate of the width is needed (during placement, for example), one often uses a lower bound metric. Density is a commonly used metric, but another interesting metric is flux. When allowed to move some of the terminals in order to minimize the width, one usually tries to minimize a lower bound metric, hopefully thereby lowering the width. We consider the problem of decreasing a given metric to target value by
adding empty columns. The empty columns add spaces in the corresponding positions on the top and bottom rows, so there are no changes in either the relative terminal orderings or the vertical alignments. This addition of columns does not affect the channel's density, but it can decrease the flux. Unfortunately, flux is not monotonically non-increasing as columns are added, so we derive from flux a new measure, smooth-flux. We present a polynomial-time algorithm for adding as few columns as possible in order to achieve a given target value for smooth-flux. Our algorithm also solves the Weighted Clique Cover problem on interval graphs.