`extresist` output can be nondeterministic due to pointer-address sorting in device grouping / driver selection

[LegumeEmittingDiode]

I am seeing nondeterministic extresist output across repeated RC extraction runs on the same SKY130 layout. The base extraction appears stable, but the .res.ext / RC SPICE output changes between runs.

In repeated runs on the same input:

• .nodes file: identical
• .sim file: same line multiset
• .ext file: same line multiset, but different line order
• .res.ext file: different
• RC SPICE output: different

The differences are localized to a few device-terminal nets. In one run, a net may be expanded into distributed RC subnodes, while in another run the same net may partially collapse back to the original named net.

The intermittent Magic stderr messages look like this:

Couldn't find device at 4074 2460
Error in extracting node opamp_fc_stage_0.nmos_inp

Couldn't find device at 4074 1726
Error in extracting node opamp_fc_stage_0.pmos_inp

Suspected source of nondeterminism

In resis/ResMain.c, ResSortByGate() uses qsort() with devSortFunc() as the comparator:

qsort(Devindexed, (size_t)listlen, (size_t)sizeof(devPtr *), devSortFunc);

The comparator is also documented as:

/*
 * qsort() sorting function for gates.
 */

However, devSortFunc() appears to compare ResExtNode * pointer addresses:

else if (rd1->gate > rd2->gate)
    return 1;
else if (rd1->gate == rd2->gate)
{
    ...
    rd1->drain > rd2->drain
    ...
}
return -1;

That makes the device order depend on allocation order / pointer address layout instead of stable layout content such as node names, device type, terminal type, or coordinates.

The comparator also appears not to return 0 for truly equal records. Since it is directly passed to qsort(), this can make the ordering implementation-dependent for equal keys.

This matters because driver-device selection later preserves the first device in a tie:

if (totWL > maxWL)
{
    maxWL = totWL;
    resisdata->rg_devloc = &t1->location;
    resisdata->rg_ttype = t1->rs_ttype;
}

If several equivalent devices are attached to a net, the selected driver location can therefore depend on the pointer-address sort order. In my case, some selected locations later fail FindStartTile(), causing the affected net’s resistance extraction to fail or partially collapse.

Why this seems tied to repeated-run nondeterminism

The same layout produced the same base extracted data as a line multiset, but not in the same .ext line order. extresist initializes ResExtNode objects as nodes are first encountered while reading .ext records. Different first-seen order can change allocation order and therefore pointer addresses.

Because devSortFunc() sorts using those pointer addresses, the grouped device order and equal-strength driver selection can change between runs even when the extracted layout content is otherwise the same.

Possible additional typo

There may also be a typo in the parallel-device grouping logic. I found a condition of this general form:

(t1->source != t2->drain || t2->drain != t2->source)

The second comparison looks suspicious and may have intended to compare t1->drain against t2->source:

(t1->source != t2->drain || t1->drain != t2->source)

I am not certain whether this typo is directly involved in the nondeterminism, but it appears related to the same source/drain-equivalence logic.

Expected behavior

Repeated extresist runs on the same extracted layout should produce deterministic .res.ext / SPICE output, independent of pointer allocation order or input record order.

Observed behavior

Repeated runs produce different .res.ext / SPICE node expansions for some device-terminal nets. The differences appear to be caused by nondeterministic selection among equivalent parallel devices, followed by occasional failure to find the selected device tile.

Suggested fixes

1. Make devSortFunc() deterministic:

   • compare stable node names or stable node IDs instead of ResExtNode * pointer addresses;
   • return 0 for truly equal keys;
   • add stable tie-breakers such as device type, terminal type, and device coordinates.

2. Make equal-W/L driver selection deterministic:

   • if totWL == maxWL, select a driver using a stable tie-breaker rather than preserving current list order.

3. Check the apparent source/drain comparison typo in the parallel-device grouping condition.

4. Optionally make FindStartTile() more robust:

   • if the stored device coordinate misses the extraction style’s device mask, search a small region around the stored device location/bbox before giving up.

This should make extresist output reproducible and avoid intermittent RC extraction failures on nets with multiple equal-strength parallel devices.

[RTimothyEdwards]

I am immediately fixing the typo and the lack of a zero return value from the sorting function. I am still analyzing the problem of sorting by pointer value; the simplest solution may be just to tag each node with a node number and use that for sorting, rather than relying on node location and type, which would take longer to check.