PWCoreLichen is a checking tool. It works in the context of PWCore. That means this: PWCore will generate a ChipNDale description of a circuit from a source Core description; from that ChipNDale description another Core description can be extracted (we'll call it the extracted Core); PWCoreLichen checks that the extracted Core is equivalent to the source Core. Equivalence is not quite as strict as being absolutely identical, because creating layout via PWCore and then extracting cannot quarantee that an absolutely identical structure is produced. PWCoreLichen is blind to exactly those differences that might be produced. PWCoreLichen is also blind to a class of differences (those cause by fusion of extracted wires) that is partially hidden from it by the extractor. There is a complementary tool, called the ConnectivityChecker, that checks that the extractor didn't hide any bugs.

The input to PWCoreLichen is a source Core cell type, which is taken to be the root of a hierarchy that is to be entirely checked. It can actually be invoked on any subpart of a design. It saves some of its results on source Core cell types, and so can be repeatedly invoked on various parts of a design, without duplicating work.

There is a ChipNDale command interface to PWCoreLichen.

There is a source Core hierarchy to be compared to an extracted Core hierarchy. They don't have to be absolutely identical. Here are the ways they may differ.

An automorphism is a symmetry. It is two or more subgroups of stuff that may be swapped without changing the structure. Parallel transistors are an example, but they present no problem because they get fused, and thus the automorphism is eliminated. Less trivial automorphisms, however, do cause a problem. They will cause the structural comparison to fail, with a complaint pointing at the subgroups. There are two things that can be done about this.

One is called the automorphism hack. It is a bit that can be set; when it is on, the comparison deals with automorphisms by picking one particular permutation of the automorphic stuff and proceeding. This can lead to false negatives, and for that reason is not normally enabled.

The other way to deal with it is to remove the automorphism by artificially distinguishing certain elements of the circuit. This is done by putting a property one a wire or cell instance in one description that names the corresponding element from the other description. The property is $StructuralComparisonMatch, and the value should be a ROPE that is a wire's short name or a cell instance's name.

PWCoreLichen stores on each paired source cell type something that indicates it's been there. This avoids duplicating the work of doing the comparison when a cell type is used from multiple places. Normally, clients and users don't need to worry about clearing this cache. But if you do, there's a procedure that will clear this bit on every source cell type in the subtree rooted at a given cell type.

If there is a gross mismatch, like a difference in the numbers of transistors or wires, PWCoreLichen sees this early, and may quit early. Whether it quits early is controlled by a mode, which is set through the interface.

PWCoreLichen conceptually does the partial flattenening, described above, that removes the cell types that don't participate in the PWCore pairing. That leaves it with a bunch of cell types that are paired one-to-one. For each such pair, the cell types are converted into graphs that encode the relevent circuit properties, and a graph test isomorphism is applied. A cell type is encoded as an bipartate colored graph. Each cell instance becomes a vertex in the graph, as does each atomic wire. Except that only one vertex is used for a group of parallel transistors, and only one vertex is used for a group of extracted wires that the extractor says should be fused, and wires connected to nothing don't even make it into the graph. The color given a cell instance's vertex is uniquely associated with the source type of that cell instance. [The source type of a source cell instance is its type; of an extracted cell instance is the source cell type that corresponds to the type of the instance.] The color given a public wire is unique for each source-extracted pair. All internal wires are given the same, bland, color. Each connection between a wire and a cell instance becomes an edge in the graph, colored according to the role of the connection. The role of a connection can be identified with the source public wire, except in the case of transistors, where both channel connections share the same role, making PWCoreLichen blind to permutations of source and drain. The graph isomorphism check proceeds by iteratively refining the coloring of the vertices until each color is applied to exactly two vertices: one from the source and one from the extracted. The iterative step is to compute a new color for a set of vertices based on their old colors, and the colors of the edges of that vertex and the old colors of the vertices on the other sides of those edges. When there are automorphisms, the iteration ceases to make progress before all colors have two vertices. When it happens that a color is applied to a different number of source vs. extracted vertices, you know trouble is coming. The vertices bearing these colors are ignored as long as possible, so as to not propogate the difference beyond its origin. If the initial coloring is thus troubled, the iterative refinement is not even attempted, and an indicative warning is issued.

PWCoreLichen.Mesa

The user interface for PWCoreLichen consists of main commands accessible via the <space>-P menu. In addition, the user needs to be familiar with the usual ChipNDale commands. Warnings are issued via messages in the ChipNDale Terminal and Action Areas for uncaught SIGNALs, which may be resumed. Additionally, a typescript called the "Structural Comparison Debug Log" is created to hold a printout of the progress of the graph isomorphism tester; this may be of some help to the user in figuring out what's wrong with the circuit.

PWCoreLichen works in the context of PWCore. It is built on top of another package, StructuralComparison, that exports structural comparison of any two Core descriptions. That package layers Core comparison on top of a kernel that will compare any two graphs.