A new approach to over-the-cell channel routing with three layers

We introduce a new model for over-the-cell channel routing with three layers. The model 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. We formulate the problem of over-the-cell routing as that of channel routing with additional constraints. Based on this formulation, we present an efficient over-the-cell routing algorithm that attempts to minimize the sum of channel densities of the trunks that remain in the channel. The effectiveness of our model and algorithm is demonstrated by our experimental results on industrial sea-of-gates array chips and a well-known benchmark circuit. >