Browse Prior Art Database

Single-Layer Router for Gate Array Cell Generation

IP.com Disclosure Number: IPCOM000119361D
Original Publication Date: 1991-Jan-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 6 page(s) / 257K

Publishing Venue

IBM

Related People

Mostow, M: AUTHOR

Abstract

Disclosed is a single-layer router called AGAR (Automatic Gate Array Router) which does internal wiring of VLSI gate array cells for a variety of technologies and background cell images. It starts by using image-specific heuristics to do a partial routing. The heuristics can be supplied by the circuit designer and may be coded using a rule-based shell or a standard programming language. Alternatively, the initial partial routing may be done by hand or omitted. The routing is completed using an image-independent algorithm which systematically generates legal routings on a virtual grid, in increasing order of cost, until a complete legal routing is found or the search fails.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 28% of the total text.

Single-Layer Router for Gate Array Cell Generation

      Disclosed is a single-layer router called AGAR (Automatic
Gate Array Router) which does internal wiring of VLSI gate array
cells for a variety of technologies and background cell images.  It
starts by using image-specific heuristics to do a partial routing.
The heuristics can be supplied by the circuit designer and may be
coded using a rule-based shell or a standard programming language.
Alternatively, the initial partial routing may be done by hand or
omitted. The routing is completed using an image-independent
algorithm which systematically generates legal routings on a virtual
grid, in increasing order of cost, until a complete legal routing is
found or the search fails.

      To deal with the variability of the background cell image, AGAR
was divided into two parts.  The first part, a heuristic partial
router, is specific to the technology and background image used.  The
second part, which systematically explores possible completions of
the partial routing given by the heuristic router, is technology and
image-independent, except for its dependence on an image definition
file.  When the image changes, only the image file and the heuristic
router must be changed.  Both routers were originally implemented as
Pascal programs, but the heuristic router was subsequently rewritten
as a set of rules, using the ECLPS rule-based shell (1, 2).  A
typical heuristic in rule form is shown in Fig. 1.  The symbolic
output of AGAR for a typical CMOS cell is shown in Fig. 3; output of
the heuristic pre- router for that example is shown in Fig. 2.  AGAR
was also used to complete the partial routings of bipolar gate array
cells (Figure 4); the partial routings were done interactively using
maze router of [3].

      Since the routing of a gate array cell is severely constrained
by the cell image, the restriction to routing in one layer, limited
wiring tracks and contact locations, and other requirements specific
to each image, the number of legal routings may be small or even
zero.  AGAR overcomes this problem by searching the space of possible
routings systematically.  It routes on a symbolic integer grid
corresponding to the vertical and horizontal lines (not necessarily
uniformly spaced) on which wires and contacts are permitted.  An
image file specifies legal wiring tracks and the locations and legal
contact positions in the background image of the features (PFET and
NFET gates and source-drains, I/O pins, and protective diodes).  AGAR
uses only that subset of the grid designated for routing, and takes
into account any user-defined blockages between grid lines.  For
example, the routing in Fig. 3 was generated under the restriction
that every fourth column may not have a vertical wire adjacent to a
wire or contact in another net.  A postprocessor which uses the
compactor of (4) converts AGAR's output to true geometric layout and
corrects small design rule violations if n...