In this paper, we consider the two row maximum planar subset (TRMPS) problem in over-the-cell routing. The TRMPS problem requires selection of the maximum planar subset of nets, which can be routed between two rows of terminals in a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They stated the complexity of this problem to be unknown, and presented a min {1,k/d(S)} approximation algorithm, where k is the number of tracks available over the cell area and d(S) is the density of a solution S. We show that TRMPS problem can be solved optimally in polynomial time. We present a O(kn/sup 2/) dynamic programming algorithm for the TRMPS problem, where n is the number of nets. We also present a parallel version of our algorithm, which has a complexity of O(kn). Our algorithm can also be extended to solve the TRMPS problem, in the presence of prerouted nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain a 0.5 approximation, for over the cell routing in middle terminal model, thus improving the best known existing algorithm. The weighted version of the TRMPS problem, as well as, all the extensions can also be solved in O(kn/sup 2/) time.

Several Ov er-the-Cell (OTC) routing algorithms have been proposed for two and three layer processes.All the existing OTC routers can be used only on the cell models for whic h they were developed for.In this paper, we develop a uni ed approach t o m ulti-layer routing, motiv ated by o v er-the-cell routing, which can be used for full-custom la youts.Our approac h can also be directly applied to standard cell layouts, irrespective of the cell model used in the design.Our router has been implemen ted in C and tested on industrial benchmarks, suc h as PRIMARY I and PRIMARY I I , for which it obtained channel-less layouts.

The Two Row Maximum Planar Subset (TRMPS) problem asks for finding the maximum planar subset of nets, that can be routed between two rows of terminals an a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They declared it open, and presented an approximation algorithm for this problem. In this paper we show that TRMPS problem can be solved optimally in polynomial time, and we present an O(kn/sup 2/) algorithm to solve this problem. Our algorithm can also be extended to solve the TRMPS problem, in the presence of pre-routed nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain an improved approximation algorithm, for over the cell routing in middle terminal model standard cell layouts.>

Recently four new cell models have been developed for over the cell routing. The usefulness of a cell model cannot simply be determined by utilization of OTC areas since cell widths, gate delays and layout parameters must also be considered. In this paper, we develop standard cells libraries in all the four models and compare the cell width and gate delay analysis of the cells. We also study the parameters which contribute to the variation in cell widths and gate delay between the different cell models. We show that the main parameters which contribute to the difference in cell widths in the four models are the number of terminals, intracell routing and cell functionality.>

Several Over-the-Cell (OTC) routing algorithms have been proposed for two and three layer processes. All the existing OTC routers assume that the terminals are laid out in a specific predetermined fashion. These restrictions on the terminals complicate the task of cell design and increase the width of the cells. In this paper, we develop a four layer OTC router which allows arbitrary terminal locations. Freed from fixed terminal placement restrictions, cell designers can aim to design with minimum width. Our router has been implemented and tested on several circuits. For most of the circuits, it obtained channel-less layouts.>

A new class of cell models called middle terminal models (MTM) is introduced. MTM-based cells allow flexibility in the selection of terminal locations and therefore utilize the over-the-cell (OTC) area more efficiently, as compared to cells based on existing models. For MTM-based designs, two new routers, MTM+V and MTM-V are presented. The first router is suitable for processes that allow vias over-the-cell and is based on an optimal Theta (K) algorithm for terminal row selection for over-the-cell channel routing, where K is the number of cell rows. The second router is suitable for the processes which do not allow vias in over-the-cell areas. This router consists of two key steps. The first step consists of the selection of a maximum planar set of nets for routing in between the terminal rows. For the second step, an optimal algorithm is developed for planar routing between the terminal row and the cell boundary. The experimental results on the PRIMARY I benchmark show that for a two-layer model, MTM-V performs 4.20% better than the best existing routers.>