next up previous contents index
Next: Extraction System: Cell Hierarchy Up: Extraction System: Operations and Previous: The Extraction Operation   Contents   Index

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.

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.


next up previous contents index
Next: Extraction System: Cell Hierarchy Up: Extraction System: Operations and Previous: The Extraction Operation   Contents   Index
Stephen R. Whiteley 2024-09-29