The Association Operation

The association algorithm logically links devices, subcircuits, nets, and terminals between the schematic and layout. If association is successful, then LVS will pass.

At its core, the association algorithm works by comparing candidate similar objects from the schematic and layout, and computing a numerical score. The pair with the highest score ``wins'' and the two objects become duals of one another, i.e., become ``associated''. This is done for devices, subcircuits and nets/groups.

Unfortunately, reality is not that simple, and the actual association algorithm is quite complex. Some of the factors contributing to the complexity are listed below.

• The hierarchy tree may not be quite the same in the schematic and layout. The association algorithm has provision for detecting when necessary and logically flattening both the schematic and the layout.

• The circuit may have topological symmetry, where the comparison test fails because the top score is shared by two or more pairs. The algorithm will try various ways to break the symmetry, and if that fails, a random choice will be made. Finding the correct permutation in this type of case requires examination of the context of instances of the cell in the hierarchy.

• The layout may have split nets, where a logical net (as shown in the schematic) consists of two or more disjoint conductor groups in the layout. Instances of the cell have the disjoint conductor groups connected by metal from outside of the master cell. The association algorithm has provision for detecting and accommodating this case.

• The layout and schematic may show different connections to permutable subcell terminals, such as permutable inputs to a logic gate. The association algorithm attempts to detect this type of case and avoid flagging it as an LVS error.

Association is done in (at least) two passes. The first pass is done to the complete cell hierarchy from the bottom up, and corrections that involve comparison at different levels of the hierarchy are skipped. Each cell is associated as far as possible, with no attempt to break symmetries.

On the second pass, inter-hierarchy corrections are allowed (since the parameters to be compared have now presumably been set), and symmetry-breaking is allowed.

During the first pass, a list of symmetries is generated if association fails to complete due to symmetry. If this list is found in the second pass, ``symmetry trials'' will be initiated. Each symmetry trial represents one choice, or permutation, of the symmetries. Association proceeds with consistency tests applied. If a consistency test fails at a later iteration, the present symmetry trial is aborted, and all associations made in the trial are undone. A new symmetry trial, using a different permutation, begins. Eventually, unless limits are exceeded, the ``correct'' permutation will be found and association will complete without errors. The MaxAssocLoops and MaxAssocIters variables set the limits. The MaxAssocLoops is approximately the maximum number of permutations that can be accommodated. The MaxAssocIters variable sets the maximum number of calls to the comparison functions until no further associations are found. Only strange cases, such as long series arrays of identical devices, require more than a few iterations.

The Misc Config page of the Extraction Setup panel from the Extract Menu provides a number of controls affecting association.