Automated Place & Route

The primary focus area for my work is automated digital logic layout, commonly
referred to as Automated Place & Route (APR or P&R). To understand what this is
and why it matters, let's first look at what layout involves.

In the beginning, layout engineers would draw each individual shape needed to
implement their logic by hand, on each layer needed to fabricate the device (N-
and P-wells, polysilicon, each of the metal layers needed to connect the
devices, etc. The drawings would then be transferred to hand-cut rubylith masks
that would be used for the photochemical processes used to "print" an integrated
circuit. Eventually, drawing by hand migrated to drawing in a CAD program (the
origins of Electronic Design Automation), with mask data extracted in digital
format to magnetic tape (which gives us the term "tapeout" for completing a
design, still used today). 

The above process worked well, and is still used for most analog and high-speed
custom digital logic where designer control is paramount. However, it doesn't
scale well to large numbers of logic gates, and complying with ever-more complex
design rules for fabrication can make even simple layouts Herculean in effort. 

In response, more automation was called for. The solution needed to scale easily
to vast numbers of devices, be tailored for the limitations of computers that
would have to implement it, and include devices that are correct-by-construction
to avoid the enormous cost of manual fix-up. This required collaboration between
the fabrication houses ("fabs" or "foundries") and the Design Automation vendors
to create a standard flow.

The foundations of the flow are the standard cell and the standard placement and
routing grids. The fab (or a licensed library provider) provides a library of
pre-packaged logic gates (AND, OR, NAND, full-adders, latches, etc.) that come in
fixed sizes and current drive strengths. These cells are integer multiples of a
fixed "site" in height and width, and are rectangular for easy processing. These
rectangular cells abstract away the complexities of the individual transistors
within, exposing only as much detail as the EDA software will need to make
connections (on metal layers) and satisfy design rules for fabrication (usually
related to certain layers that are implanted into the silicon wafer). 

                    Fig 1. - Some standard cells

                +--------+     +------------+     +--------------+
                | AND2_A |     |  AND2_B    |     |    AND2_C    |
                +--------+     +------------+     +--------------+


These cells are then placed onto a placement grid. The design is sliced into
(usually) horizontal rows of a fixed height (to match the library), and the
cells can then be dropped onto these rows and slid around to snap to the grid.
Power rails are run along the row edges to provide power and ground connections
to the cells (which are designed with their power/ground terminals at the
top/bottom edge to abut directly to these rails). If certain cells can't be
placed next to other cells (usually due to hard-to-access terminal pins), the
placement algorithm can be told this via the library or an external constraint
and moves cells as needed. 

                    Fig. 2 - Sample Standard Cell Grid
                     with some cells of various widths

              +--------------------------------------------+
              |XXXXXXXXX|    |    |YYYY|    |ZZZZZZZZZZZZZZ|
              +----+----+----+----+----+----+----+----+----+
              |    |YYYY|    |XXXXXXXXX|    |    |    |    |
              +----+----+----+----+----+----+----+----+----+
              |    |    |    |ZZZZZZZZZZZZZZ|YYYY|YYYY|    |
              +----+----+----+----+----+----+----+----+----+
              |    |XXXXXXXXX|    |XXXXXXXXX|    |YYYY|    |
              +----+----+----+----+----+----+----+----+----+
              |ZZZZZZZZZZZZZZ|    |YYYY|YYYY|    |    |    |
              +----+----+----+----+----+----+----+----+----+
              |    |    |    |    |UUUUUUUUUUUUUUUUUUU|    |
              +----+----+----+----+----+----+----+----+----+


Now that the cells are placed, a routing algorithm can make physical connections
to the pins on each cell using the wiring layers available. Each metal layer has
a grid similar to the placement grid, but with a few changes. First, the metal
layers generally have a preferred direction (horizontal or vertical) and the
layers will alternate direction as you move up from the cells. Second, as you
move up the metal layers, the pitch between wires and the width of each wire
increase, allowing for lower-resistance/faster signal propagation, but at a cost
of less available wiring on each progressive layer. The router will take
advantage of the different RC characteristics of the layers to improve timing
and avoid problems with crosstalk between wires. 

By combining the standard cell with a fixed grid, EDA tools can now scale to
many millions of standard cells, limited solely by the capacity of the machines
running the EDA tools. The switch to discrete cell sizes leaves some performance
on the table compared to a full custom layout, but the economies of scale are
simply impossible to match.