Channel routing with non-terminal doglegs

Many automatic layout systems for VLSI circuits employ channel routing as the basic interconnection function. The wide range of uses and the importance of channel routing have inspired many good channel routing algorithms. However, many algorithms were developed with the geometric regularity of standard cell and gate array designs in mind. As a result these algorithms have difficulty routing channels with geometric generality (rectilinear boundaries and wires and terminals that can have different widths and irregular spacings) and simultaneously guaranteeing completion of all routes. This paper presents an algorithm for resolving cyclic vertical constraints using a general channel model. When this algorithm is combined with a constraint-based channel router, routing completion can be guaranteed, even for routing problems with generalized geometries. This algorithm is implemented with a constrain-based, alternating-edge, dogleg channel router. Extensions are described which permit the channel router to implement switchbox routing