A new model for over-the-cell channel routing with three layers

The authors propose an approach to an over-the-cell channel routing problem using a model that consists of two channels and the routing area over a cell row between them. Three and two layers are available for routing in the channels and the over-the-cell routing area, respectively, The problem is decomposed into two phases: over-the-cell routing and channel routing. The authors formulate the problem in the first phase as that of channel routing with additional constraints. Based on this formulation, they present an efficient over-the-cell routing algorithm. The effectiveness of the approach is demonstrated by experimental results on sea-of-gates array chips. >