2019 04 14
This blog is about the netlist compare feature. It wasn't planned or anticipated, yet I think it may be quite useful. I needed such a feature, because the netlist extractor tends to produce slightly different netlists on different platforms (due to STL differences, specifically in the hash container implementation). A pure text compare wasn't sufficient, so I started a netlist compare function, not being aware of the complexity that awaits me. There finally is a fairly robust implementation and I have successfully used to compare the VexRiscV sample from the repository.
The basic idea is twofold:
- The netlist with it's nets, devices and subcircuits is transformed into a simple graph
- The graphs of both netlists are compared
A circuit's netlist is made from nets, devices and subcircuits. Nets make the nodes of the graph. Devices and subcircuits mediate between these nodes. So essentially they create edges between the net nodes.
The following picture describes the idea for a simple inverter:
Devices are represented by edges connecting each terminal with each other terminal. These are three edges for a MOS3 transistor and four edges in case of a MOS4 transistor. Terminals may be regarded identical: source and drain of a MOS can be swapped as they can be exchanged physically. Hence they are represented by a single terminal type (SD).
Each device contributes edges, so multiple connections between two nodes may exist. In the example above this is case between IN and OUT of the inverter. All combined connections between two nodes form one edge. So the nodes are always connected by single edges. The edges are characteristic for the topology of a node (intuitively. Proof?).
Subcircuits form connections between nodes through their pins in the same way than devices form connections through their terminals. However, it's not realistic to model all connections from each pin to every other pin as this would lead to a huge number of edges for subcircuits with many pins. Hence the algorithm confines itself to a small number (typically 5) of other pins for each initial pin.
Subcircuits are also special in a sense that their pin order is not defined. So before they can be used for computing the edges, the pin assignment needs to be known. For this, the algorithm walks bottom-up in the compare process. If a circuit can't be mapped pin-wise against the equivalent circuit from the other netlist, other circuits depending on this circuit can't be matched. These are reported as "skipped".
The match algorithm derives node equivalences from the node configuration first. If a node has a certain unique configuration with respect to edges leading away from this node, it is matched with a node with the same configuration from the other netlist ("net pairing").
If a net is paired and a single edge type leads to another node in both netlists, these other node are paired too. If among all nodes connected to one paired node there is one with a unique configuration, it is paired with it's counterpart. This scheme can be continued as long as unique edge and node configurations are present. This scheme leads quite far for typical CMOS netlists.
However, every design contains ambiguous nets too. This is when tentative evaluation comes into play. It is used when multiple nodes are present with the same configuration in both netlists. In this case, multiple configurations are evaluated tentatively and unless a configuration leads to a contradiction with existing pairing, one configuration is accepted. If multiple configurations are valid, the first net pair is taken and reported as "ambiguous match". Ambiguities are inherent in some designs: for example the bits on a data base are ambiguous. To resolve ambiguities, an explicit net pairing can be imposed in the compare script.
As usual, the netlist compare feature is available as Ruby or Python classes. The central class is "NetlistComparer". A nice DSL is not there yet, so a netlist compare script needs to be based on this basic API. Some auxiliary methods are available to tune the netlists before compare, so more advanced compare schemes are feasible.
The following can be configured in the compare
- Explicit pairing of specific circuits ("NetlistComparer#same_circuits"). By default circuits with the same name are compared.
- Explicit pairing of specific nets ("NetlistComparer#same_nets"). By default, the comparer is agnostic with respect to nets.
- Equivalence of device classes ("NetlistComparer#device_classes"). By default device classes with the same name are paired.
- Skipping of parasitic elements ("NetlistComparer#min_capacitance" and "NetlistComparer#max_resistance").
- Marking pins of circuits as swappable ("NetlistComparer#equivalent_pins").
- Parameter tolerances for device compare (configured per device class via "DeviceClass#equal_parameters" and the "EqualDeviceParameters" object)
Other features can be implemented by netlist manipulation prior to compare (e.g. flattening of circuits).
Here is an example script. I hope the comments explain the functionality sufficiently. Run times are in the order of 18 seconds for the full script and the VexRiscV example. The data used in this example can be downloaded here: attachments/netlist_compare_sample.tar.gz.
# The netlist extracted from the layout
# - devices are not combined yet
# - the subcircuit hierarchy is present (standard cells)
# - no pins on top level circuit
fn1 = "netlist.cir"
# Original
# - this netlist doesn't have a hierarchy
# - the net names are aliased by numbers
# - devices are also not combined
# - it contains some parasitic capacitances we need to skip
fn2 = "vexriscv_clocked_r.spi"
# Set to true to produce netlists for intermediate steps
write_debug = false
# ----------------------------------------------------------------
# Prepare first netlist
# Read the first netlist
puts "Reading " + fn1 + " ..."
nl1 = RBA::Netlist::new
reader = RBA::NetlistSpiceReader::new
nl1.read(fn1, reader)
# Combine the devices (fingered transistors)
puts "Combining devices ..."
nl1.combine_devices
# Write the results of the device combination step to "combined.cir"
if write_debug
debug_out = "combined.cir"
puts "Writing netlist with combined devices to " + debug_out
writer = RBA::NetlistSpiceWriter::new
writer.use_net_names = true
nl1.write(debug_out, writer)
end
# Flatten all circuits except the top level circuit
# NOTE: it's more efficient to first collect all circuits and
# then to flatten them in a second pass
flatten = []
top_count = nl1.top_circuit_count
index = 0
nl1.each_circuit_top_down do |circuit|
if index >= top_count
flatten << circuit
end
index += 1
end
flatten.each do |circuit|
puts "Flatten #{circuit.name} ..."
nl1.flatten_circuit(circuit)
end
# write the results of the device combination step to "flattened.cir"
if write_debug
debug_out = "flattened.cir"
puts "Writing netlist with flattened cells to " + debug_out
writer = RBA::NetlistSpiceWriter::new
writer.use_net_names = true
nl1.write(debug_out, writer)
end
# ----------------------------------------------------------------
# Prepare second netlist
# Scan real names from the second netlist
# This netlist contains the real names as comments of the form
# * NET name = number
#
num2name = {}
top_name = ""
File.open(fn2, "r") do |file|
file.each_line do |l|
if l =~ /^\s*\*\s*NET\s+(\d+)\s*=\s*(.*)$/
num2name[$1] = $2
elsif l =~ /^\s*\.subckt\s+(.*?)\s+/i
top_name = $1
end
end
end
# Read the second netlist
puts "Reading " + fn2 + " ..."
nl2 = RBA::Netlist::new
reader = RBA::NetlistSpiceReader::new
nl2.read(fn2, reader)
# Replace the numeric names by the real ones
# NOTE: it's more efficient to first identify the nets and then
# rename them in a second pass
puts "Putting in real names ..."
net2name = []
c = nl2.circuit_by_name(top_name) || raise("Cannot find top circuit #{top_name}")
num2name.each do |k,v|
net2name << [ c.net_by_name(k), v ]
end
net2name.each do |net,name|
net.name = name
end
# Combine the devices on the second netlist
puts "Combining devices on (2) ..."
nl2.combine_devices
# Write the results of the device combination step to "combined2.cir"
if write_debug
debug_out = "combined2.cir"
puts "Writing netlist with combined devices to " + debug_out
writer = RBA::NetlistSpiceWriter::new
writer.use_net_names = true
nl2.write(debug_out, writer)
end
# ----------------------------------------------------------------
# Preparation of a logger to print individual results
# This logger will receive all events from the netlist comparer
# The objective of this implementation is to print the events.
# It dynamically creates most methods of the kind "x(a,b)" to
# print the method name and the arguments.
class NetlistComparePrintLogger < RBA::GenericNetlistCompareLogger
def out(text)
puts text
$stdout.flush
end
def begin_circuit(a, b)
out("begin_circuit " + obj2str(a) + " " + obj2str(b))
end
def end_circuit(a, b, matching)
out("end_circuit " + obj2str(a) + " " + obj2str(b) + " " + (matching ? "MATCH" : "NOMATCH"))
end
[ :circuit_skipped, :circuit_mismatch,
:match_nets, :match_ambiguous_nets, :net_mismatch,
:match_devices, :device_mismatch, :match_devices_with_different_parameters, :match_devices_with_different_device_classes,
:match_pins, :pin_mismatch,
:match_subcircuits, :subcircuit_mismatch ].each do |method|
class_eval <<-METHOD
def #{method}(a, b)
out("#{method} " + obj2str(a) + " " + obj2str(b))
end
METHOD
end
def obj2str(x)
if ! x
return("(null)")
end
if x.respond_to?(:expanded_name)
return(x.expanded_name)
end
x.name
end
end
# ----------------------------------------------------------------
# This is the actual compare step
logger = NetlistComparePrintLogger::new
comp = RBA::NetlistComparer::new(logger)
# Drop parasitic capacitances
comp.min_capacitance = 1e-6
# Identify device classes: tp is PMOS, tn is NMOS
comp.same_device_classes(nl2.device_class_by_name("tp"), nl1.device_class_by_name("PMOS"))
comp.same_device_classes(nl2.device_class_by_name("tn"), nl1.device_class_by_name("NMOS"))
# Increase the default complexity from 100 to 200
# This is required because the clock tree is incorrect and exhibits manifold ambiguities
# (the netlists are just samples, not necessarily functional).
# The algorithm needs enough freedom to follow all these branches and different variants.
comp.max_branch_complexity = 200
# Runs the actual comparison
if comp.compare(nl1, nl2)
puts "Congratulations! Netlists match."
end