Finding All Minimal Shapes in a Routing Channel

Abstract:

We present an algorithm to find a set of all optimal solutions for a channel
replacement problem. A channel consists of two rows of horizontal line
segments (representing components). Each line segment contains some terminals
with fixed positions. Sets of terminals, called nets, are to be
connected. The relative ordering of line segments in each row is fixed. The
line segments can be shifted left or right, which will affect the width needed
for routing and the length of the channel. We want to find the tradeoff
between channel length and routing width. Since the channel routing problem
is NP--complete, we use a lower bound on routing width, called density. The
density of a placement is the maximum number of nets crossing each
vertical cut. We can increase the total length to minimize the channel
density, or minimize the total length by increasing the channel density. The
pair (density, total length) is called the shape of a placement.
A shape is minimal if a decrease in density would cause an increase in
total length, and vice versa. Our algorithm computes all the minimal
shapes in O(N4) time, where N is the number of nets. This is the
first known polynomial algorithm for this problem.