In the layout design of LSI chips, CHANNEL ROUTING is one of the key problems. The problem is to route a specified net list between two rows of terminals across a TWO LAYER CHANNEL. Nets are routed with horizontal segments on the METAL layer and vertical segments on the POLYSILICON layer. Connection between two layers are made through VIA.
In this paper, the MAXIMUM MATCHING algorithm is used which merges nets instead of assigning horizontal tracks to individual nets.
This algorithm was coded in PASCAL and implemented on a VAX 11/750 computer. Experimental results, for examples in previously published papers, are quite encouraging.