FINDING ALL MINIMAL SHAPES IN A ROUTING CHANNEL

We present an algorithm to find a set of all optimal solutions for a c hannel placement problem. A channel consists of two rows of horizontal line segments (representing components). Each line segment contains s ome terminals with fixed positions. Sets of terminals, called nets, ar e 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 a ffect the width needed for routing and the length of the channel. We w ant to find the tradeoff between channel length and routing width. Sin ce the channel routing problem is NP-complete, we use a lower bound on routing width, called density. The density of a placement is the maxi mum number of nets crossing each vertical cut. We can increase the tot al length to minimize the channel density, or minimize the total lengt h by increasing the channel density. The pair (density, total length) is called the shape of a placement. A shape is minimal if a decrease i n density would cause an increase in total length, and vice versa. Our algorithm computes all the minimal shapes in O(N-4) time, where N is the number of nets. This is the first known algorithm for this problem whose running time is polynomial in the number of nets and independen t of the length of the channel.