Channel router

Figure 1: A channel routing problem. The numbered pins on the top and bottom of the channel must be connected. The nets specified on the left and right of the channel must be brought to that end of the channel

A channel router is a specific variety router for integrated circuits. Normally using two layers of interconnect, it must connect the specified pins on the top and bottom of the channel. Specified nets must also be brought out to the left and right of the channel, but may be brought out in any order. The height of the channel is not specified - the router computes what height is needed.

Figure 2: A solution to the channel routing problem shown above. Solutions are not unique, and this is just one of the many possible.

The density of a channel, defined for every x within the channel, is the number of nets that apear on both the left and right of a vertical line at that x. The maximum density is a lower bound on the height of the channel. A cyclic constraint occurs when two pins occur in the same column (but with different orders) in at least two columns. In the example shown, nets 1 and 3 suffer from cyclic constraints. This can only be solved by doglegs as shown on net of the example.