Allow equivalent group of terminals for symmetric devices or circuits when comparing netlists

[srooks10]

Hi Matthias,

In a LVS deck, when comparing netlists, it is currently possible to allow swapping device terminals in a pair. For example (e1, e2, e3) is equivalent to (e3, e2, e1) when e1 and e3 can be swapped. Same for circuits.

In photonics, it is common to have devices with symmetries with functionally equivalent groups of terminals. For example, for a 4-ports device with one symmetry axis, have (o1, o2, o3, o4) and (o4, o3, o2, o1) are equivalent. Or with 2 symmetry axes, (o1, o2, o3, o4), (o4, o3, o2, o1), (o2, o1, o4, o3) and (o3, o4, o1, o2) are all equivalent.
Would it be possible to extend the the solver to try the different equivalent groups when comparing netlists?

[klayoutmatthias]

Hi @srooks10,

thanks for this suggestion and initiating this discussion.

The implementation is not based on "trying", that would be prohibitive in case of many equivalent pins. The concept is also available for subcircuits and if you think about a 16-input gate subcircuit (you may have that in decoders), "trying" would boil down to 16! = 20922789888000 combinations :)

So the algorithm is based on assigning integer IDs for the terminals, using the same ID for equivalent ones and comparing the net-to-terminal assignment based on these IDs.

In other words, this feature can't be implemented within this scheme, because you can assign two IDs for o1/o3 and o2/o4 in the one symmetry axis case, but that cannot detect if o1/o2 are swapped without o3/o4 being swapped for example.

I see an implementation path however by providing a post-matching test.

Let me explain:

After the netlists are matched successfully, a cross reference is built which lists schematic net vs. layout net. It will also list the device terminals or subcircuit pins attached to a certain net.

The idea is: you first start with a uncorrelated equivalence and after successfully matching the netlists you identify illegal swaps and produce an error in that case.

For example for the one-axis case, you start with equivalent terminals o1+o4 and o2+o3. After the extraction you check the nets attached to the four terminals and you can build a correspondence table between schematic and layout ports for that device. If that correspondence table does not match one of the listed cases, an error is produced that will show up in the log page for example.

For the two-axis case, the initial equivalence is fully: o1+o2+o3+o4. So initially all connection combinations are possible. Again, after the match was successful, you can test if the correspondence table is among the four allowed combinations are raise an error in that case.

I think you can even implement this right now by doing that analysis in Ruby right in the LVS script, but of course it can be turned into a built-in feature later.

Does that sound reasonable?

The additional degrees of freedom introduced in the initial matching usually are good for the backtracking algorithm as they reduce the number of branches. Theoretically you could have cases however, where this additional freedom creates ambiguities which are not there initially.

For example, one might have the idea to apply this scheme to differential logic. With differential logic, you can use port swapping to create an inverted input. Like for this part of an differential-logic 2-to-4 decoder:

                     +-----------+
                     |           |
        +------------| A+        |
        |            |           |
        |  +---------| A-     Q+ |---- Q3+
        |  |         |     &     |          H on A[0-1] == 11, L otherwise
        |  |  +------| B+     Q- |---- Q3-
        |  |  |      |           |
        |  |  |  +---| B-        |
A0+ ----o  |  |  |   |           |
        |  |  |  |   +-----------+
A0- -------o  |  |       AND1
        |  |  |  |
A1+ ----------o  |
        |  |  |  |
A1- -------------o
        |  |  |  |   +-----------+
        |  |  |  |   |           |
        |  +---------| A+        |
swapped |  |  |  |   |           |
        +------------| A-     Q+ |---- Q2+
        |  |  |  |   |     &     |          H in A[0-1] == 10, L otherwise
        |  |  +------| B+     Q- |---- Q2-
        |  |  |  |   |           |
        |  |  |  +---| B-        |
        |  |  |  |   |           |
        |  |  |  |   +-----------+
        |  |  |  |       AND2  
        |  |  |  |             
     to further stages

If I wanted to apply the port swapping to the AND gates, I had to make A+, A-, B+ and B- equivalent initially. That creates an ambiguity that makes AND1 and AND2 equivalent in the first place and confuse the solver. That is not a new problem however and the solution is typically providing labels on the output signals to help resolving these ambiguities.

Matthias