Layout Versus Schematic by Partition Refinement

The idea

Layout versus schematic proves that the layout is the intended circuit. It runs in two steps.

Extraction. Recognize devices from how the layers overlap (a transistor where polysilicon crosses diffusion) and trace connectivity through metal and vias, producing a netlist of what the layout actually builds.

Comparison. Decide whether the extracted netlist and the reference netlist are the same circuit. Treat each one as a graph whose nodes are devices and nets, and the question becomes graph isomorphism, which has no known polynomial-time algorithm in general. Circuits, though, are far from adversarial. Ebeling and Zajicek (1983) label every node with local invariants (device type, number of connections), then repeatedly relabel each node from the labels of its neighbors, refining the partition. A node whose label is unique in both graphs is matched with its twin. When refinement stalls on symmetric groups, such as identical devices in parallel, one pair is matched by choice and refinement continues.

Watch it work: refining labels until every node has a twin

A two-input NAND gate as the designer drew it and as the layout was extracted, with other names. The walkthrough labels devices and nets, refines the labels round by round until every node is matched, then adds a short to show refinement failing.

The fine print

When the netlists differ, the algorithm stops with groups it cannot match, and turning those groups into a readable cause ("this net is shorted to that one") is the hard, heuristic part. Extraction depends on a process-specific rule deck describing how layers form devices. The Gemmini challenge on this site checks the layout's connectivity against the netlist directly, because the ASAP7 (Arizona State University 7 nanometer predictive) kit has no open deck for this check.

Where you meet it today

Netgen, the open-source comparison tool from the Magic flow, compares netlists by iterative refinement of this kind, and KLayout offers netlist comparison alongside its rule checks.