Abstract
A new cell model was recently introduced by B. Wu et al (Over-the-Cell Routers for New Cell Model, Proc. Design Automation Conf., p. 604-7, 1992). In this model, all the pins are along a horizontal line inside the cell instead of the cell boundaries. We study the over-the-cell channel routing problem for this new cell model under the assumption that only one layer is available for over-the-cell routing. Given two rows of cells separated by a channel, the objective of the problem is to determine in each over-the-cell region a planar routing which connects each pin to a proper position on the corresponding cell boundary such that the resulting channel density is minimized. We present a polynomial time optimal algorithm for a special case of the problem in which no consecutive pins in each cell row belong to the same net. We also show how to apply the algorithm to optimally solve the general case under the assumption that consecutive pins belonging to the same net are internally connected to the same position on the cell boundary