Connectivity Verification
Connectivity Verification
(1) Read Network1 and Network2 into separate graph data structures (usually, node = transistor or gate, edge = connection).
(2) Compute signatures for nodes or edges or both.
Ô Type-specific: Gate type, #inputs, #outputsÔ Network-specific (local): Fanin types, #fanouts, fanout typesÔ Network-specific (global): Distance from primary inputs, primary outputs, nodes that are known to be the same in each network (e.g. named, primary inputs or outputs ("seeds")).
(3) Hash signatures from both networks into single hash table.
(4) If a hash table cell has:
Ô > 2 nodes: ignore for nowÔ = 2 nodes: a match has been foundÔ = 1 node: an (easy!) error has been found
(5) Add links between networks for nodes that have been matched.
(6) Recompute hash functions for un-bound nodes and repeat until done or no change.