-
Notifications
You must be signed in to change notification settings - Fork 211
Deep Verification Base
The Deep Verification Base development happens in the "dvb" branch: https://github.com/klayoutmatthias/klayout/tree/dvb
Updates:
- 2018-12-31 First functional implementation of a netlist extractor
- 2019-01-07 Stable implemenation + performance improvements, additional functionality
- 2019-01-19 Persistence and some reworks
- 2019-02-01 SPICE writer and more improvements
- 2019-02-03 Implicit connection of nets with same label
- 2019-02-05 Hierarchical merge and performance on a real testcase
- 2019-02-17 Hierarchical DRC operations
- 2019-03-02 More hierarchical operations and antenna check
- 2019-03-09 Better integration of netlisting into DRC script
- 2019-04-14 Netlist compare
- 2019-05-05 Netlist browser
- 2019-07-13 Close to release
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.
- Compare: both steps form layout vs. schematic verification (LVS) once a netlist compare feature is added.
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.
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).
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 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.
Having a hierarchical processing engine allows generating hierarchical device recognition markers. This is a prerequisite for hierarchical schematic extraction.
Device recognition consists of:
- Boolean operators (maybe others) that derive markers that identify each type of device and which derive the connectivity layers.
- Code to extract device parameters from specific layers.
- Code to extract nets (connected shapes) in a hierarchical fashion and their terminals
The first feature is provided by the hierarchical engine mentioned before. The formation of nets and devices requires non-local operations. More specificially "clustering" is required. "Clustering" means that shapes connect to other shapes using connectivity rules. All shapes connected directly or indirectly form clusters. Clusters are meant to be finite - they aggregate to a certain size, but do not cover the whole layout (except in pathological cases).
For the netlist extraction, hierarchical clustering is required.
The implementation of the hierarchical cluster engine consists of a data structure capable of holding local shape clusters and their connections across the hierarchy and the algorithms to derive the latter.
The details of the data structure are:
- local_cluster objects keep the shapes from one cluster. This is not necessarily a single layer - depending on the connectivity, clusters may consist or more than one layer.
- local_clusters objects keep all local clusters for a single cell.
- connected_clusters objects keep the local clusters plus connection objects which form the connections to clusters from subcells. A special case is a cluster consisting only of connections: such clusters arise when two cells interact without a shape in the upper hierarchy level on which they interact.
- hier_clusters objects keep the entire hierarchy of connected_clusters across all cells.
A useful assertion is that if a cluster of a cell is connected upwards in the hierarchy it is so in all placements. If necessary, dummy clusters are created in the parent cell for the purpose of providing this connection. This assertion greatly simplifies the implementation of the building algorithm because it does not need to look on different hierarchy levels and forking of instantiation paths does not happen.
The connectivity definition lists the interactions of layers. It consists of pairs of layer IDs which interact. Intra-layer interactions are explicitly included. Without explicit intra-layer connectivity the clustering algorithm reduces to local interactions. This may be useful for preventing huge long range aggregations, for example for treating bulk areas.
The algorithm walks the hierarchy bottom-up and performs the following operations:
- Collect local shapes into clusters
- Look for interactions between local clusters and clusters from child cells. For each such interaction create a connection. If required, place dummy clusters in each parent of a specific cluster (see above).
- Look for interactions between child cells and their clusters. On such an interaction, create a dummy cluster in the local cell with two connections to the child cell clusters.
Device recognition is based on the same cluster scheme, but this time with clusters formed by the device layers. A special connectivity definition connects these layers into clusters. The clusters are presented to the device extraction object. The task of this object is to derive the devices from these clusters. Typically some shapes act as seeds for the device recognitions (i.e. gate shapes for MOSFET devices).
The device extraction produces the devices with their parameters. In addition, the device terminals are provided which form connection points for the nets. In our implementation, these terminals are new shapes generated by the device extractor. These shapes are produced on standard connectivity layers included in the net extraction. But they are annotated is a special way (through properties), so the net extractor can derive the device connections at the net.
Device extraction happens for all devices supported in the same way. The effect of the device extraction is a pre-filled netlist with the devices, yet unconnected.
The netlist extraction step will create the actual nets in the netlist object. It takes a connectivity definition and performs the clustering described above. Each cluster forms a net. Cell instances for subcircuits. Connections between different cells form connections to pins of subcircuits.
The netlist data structure consists of these elements:
- A top-level Netlist object being the container for all objects.
In Netlist:
- Circuits corresponding to cells. A Circuit object has a name and a reference to a layout cell (cell_index).
- DeviceClass objects inside Netlist representing one kind of device. The main objective of the device class object is to supply the definition of the device terminals.
In Circuits:
- Pin objects describing one point each by which a net can connect to a circuit from outside.
- Device objects for one device instance each. A device instance has a reference to a DeviceClass object describing the device type.
- Subcircuit objects forming Circuit instances. The basic property of the SubCircuit is the reference to the Circuit object that it references.
- Net objects. Technically a Net object is a list of Device terminal references and pin references. Pin references are either connections to a subcircuit or outward pin connections.