Deep Verification Base

The problem

Verification is a fundamental task in the chip design process. KLayout basically offers a good basis for verification as it already includes a capable layout database, a lot of algorithms for layout extraction and verification and an integrated error review environment.

Two important verification methods are addressed here:

• Design rule check (DRC)
• Schematic extraction plus schematic compare. Both steps form layout vs. schematic verification (LVS)

KLayout supports DRC verification to some extent:

• The most important methods are provided (boolean operations, sizing, measurement, edge operations)
• The functionality provided seems to be sufficient in general, but has some weaknesses - e.g. in the area of width/space dependent rules. Rules involving connectivity are not available.
• The engine is flat meaning it does not take advantage of the hierarchical structure of a layout. All operations will be performed in the top-level cell. To mitigate memory consumption and performance issues, the area can be split into parts which are computed individually (tiling)

LVS is not available. The only functionality related to connectivity extraction is the net tracer. This tool allows deriving all shapes connected to a see shape. This is a very basic form of netlist extraction. As the net tracer can be scripted it is basically possible to perform connectivity extraction net by net and finally forming a netlist. However, this approach is clumsy and not readily available. In addition, the incremental netlist extraction algorithm suffers from performance issues on very large nets (i.e. power nets).

The enhanced verification base project is supposed to deal with these shortcomings.

Basic plan

The basic plan is this:

• Enhance the layout engine to support hierarchical operations. This should improve performance and allows generating device recognition shapes down in the hierarchy. This should basically enable hierarchical device extraction.
• Provide a "all in once" connectivity extraction tool. This tool can be based on the hierarchical algorithms prepared in the first step. A representation for the hierarchical netlist is required.
• Provide readers and writers for the netlist to and from external file formats (initially SPICE)
• Provide netlist vs. netlist compare rendering an LVS

In contrast to the flat operations provided so far, the new verification base operates in "deep" mode. Hence the name "Deep Verification Base" (DVB).

Hierarchical enhancements of the layout engine

The layout engine is based on the Region, Edges and EdgePairs classes. Currently those are monolithic structures, but after some refactoring they can be used as providers for the hierarchical algorithms.

• Implement delegates to represent empty, flat, as-if-flat original and (new) deep collections
• The deep collections utilize temporary layouts to store the shapes, edges and edge pairs away from the original layouts. This is required, as some operations will modify or optimize the original shapes and we don't want to destroy the original data. The temporary layouts are kept in the "deep shape store".
• Operations acting on the new deep collections will utilize a hierarchical processor instead of the flat one. Not all operations will be migrated to hierarchical processing mode initially. Top priority are boolean polygon-vs-polygon and polygon-vs-edge operations as they are required mainly for device recognition.
• When writing the deep collection data back to the original layout, hierarchy mapping from the temporary store to the original layout's hierarchy has to happen. KLayout already provides several methods to implement this mapping.

Finally, the suggested use model could be like this

# A sample DRC script using deep mode

l1 = input(1, 0)
l2 = input(2, 0)

# enable deep mode
deep

(l1 - l2).output(100, 0)

Deep mode can basically be combined with tiling. In this case, the tiles form hierarchical clips. In other words, tiling will happen before the hierarchical processor comes into play.

The hierarchical engine

The hierarchical engine can be based on a subject shape/intruder approach.

Consider a simple boolean operation - for example a NOT operation. In this case there is a subject shape from the first layer and zero or many intruder shapes per subject shape. The intruder shapes come from the second layer. Knowing all intruders for each subject shape allows implementing the NOT operation by simply subtracting the intruders from the subject. This operation is local: only intruders within a limited distance - in this less than zero, i.e. overlapping - will participate and the output of the operation is fully defined from the inputs (subject shape, intruders).

The hierarchical approach only needs to identify intruders for each subject shape in a hierarchical fashion. For each subject shape inside a cell, intruders can originate from:

• shapes from the current cell (shape-shape interactions)
• outside the tree of the current cell - i.e. siblings of the current cell (cell context interactions)
• child cells (bottom-up interactions)

Taking these three interactions into account renders the following algorithm:

• We start from the top cell. There is no context because there are no siblings of the top cell.
• Collect all shape-shape interactions between subject and intruder layer
• Collect shape-child cell interactions where the shapes come from the subject layer and the intruders from the child cells
• From the collected intruders per local shape compute the output and keep it in stock for the current cell
• For each child cell instance detect intruders by looking at
  • Overlapping child cells adding intruders to the subject shapes of another instance
  • Local intruder shapes adding intruders to subject shapes of an instance
• The intruder shapes for one instance form the cell context
• Treat each instance recursively by additionally taking the context into account: the context will add intruder shapes when considering subject shapes and instances inside this cell
• To harvest the benefit of the hierarchical approach we can skip each child cell if it has been handled before with identical context

A further step involves recombination of the various context-dependent outputs of an operation into a part common to all cells and context-specific parts. The latter need to be placed into the parent cells where the context was derived from.

This is a brief description of the idea.

Schematic extraction tool

Having a hierarchical processing engine allows generating hierarchical device recognition markers. This is a prerequisite for hierarchical schematic extraction.

Device recognition consists of:

• DRC rules that derive markers that identify each type of device
• Code to extract device parameters from these markers
• DRC rules that derive device ports to which the connectivity extraction can connect to

The result of device recognition is a (per-cell) list of devices with their parameters and port shapes.

Connectivity layers are either taken from their original layers or derived using DRC rules (i.e. boolean operations). Having a hierarchical engine allows maintaining the hierarchy of where possible. The connectivity rules define which of the connectivity layers connect to each other. DRC rules for deriving the layers plus the connectivity rules form a connectivity description similar to the layer stack of the net tracer.

After device recognition, schematic extraction can proceed bottom-up to connect shape by shape and form growing clusters of connected shapes. The incremental nature of the connection extraction forms sub-circuits for each cell. When moving up in the hierarchy, nets from these sub-circuits are connected with nets either from the parent cell or with nets from sibling cells. The result is a hierarchical netlist.

Here is a rough idea for a schematic extraction script:

# ---------------------------------------------
# device definitions

# generic MOS device definitions
class MOSDevice < DeviceExtractor

  def extract(layout, seed, body)

    body.size == 1 || raise("MOS device requires exactly one body layer")

    sd = body[0]
    sd.size == 2 || raise("Exactly two body shapes (S,D) are required for MOS devices")

    sides = seed.edges * sd.edges
    width = sides.length * 0.5 * layout.dbu

    faces = seed.edges - sd.edges
    length = faces.length * 0.5 * layout.dbu

    params = { "W" => width, "L" => length }

    ports = [
      Port::new(SEED, "G", seed), 
      Port::new(BODY1, "S", sd[0]), 
      Port::new(BODY1, "D", sd[1])
    ]

    return Device::new(self.DEVICE_NAME, params, ports)

  end

end

# NMOS device definition
class NMOSDevice < MOSDevice
  self.DEVICE_NAME = "NMOS"
end

# PMOS device definition
class PMOSDevice < MOSDevice
  self.DEVICE_NAME = "PMOS"
end

# ---------------------------------------------
# extraction script

deep

# input layers

nwell = input(1, 0)
active = input(2, 0)
poly = input(3, 0)
contact = input(4, 0)
metal1 = input(5, 0)
metal1_texts = texts(5, 0)
via1 = input(6, 0)
metal2 = input(7, 0)
metal2_texts = texts(7, 0)

# generation rules

sd = active - poly
gate = active * poly
pmos = gate * nwell
nmos = gate - nwell

# net extraction

extract_nets do

  connect metal2, via1
  connect via1, metal1
  connect metal1, contact
  connect contact, sd
  connect contact, poly
  connect contact, gate

  label metal1, metal1_texts
  label metal2, metal2_texts

  device NMOSDevice, nmos, sd
  device PMOSDevice, pmos, sd

end