Channel routing order for building-block layout with rectilinear modules

A feasible channel-ordering algorithm for building-block layout using rectilinear blocks is presented. Existing approaches for layout involving rectangular modules only straight and L-shaped channels are not applicable. A class of channels called monotone channels is introduced. A monotone channel is a generalization of an L-shaped channel that has the form of a staircase. Routing is achieved by expanding the channel in both the horizontal and vertical directions. The algorithm produces a feasible channel order the minimizes the number of nonmonotone channels and the maximum number of corners in a channel used.