2019 04 14

Netlist Compare

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:

1.) The netlist with it's nets, devices and subcircuits is transformed into a simple graph 2.) The graphs of both netlists are compared

Simple graph representation

A circuit's netlist is made from nets, devices and subcircuits. Nets make the nodes of the graph. Devices and subcircuits mitigate between these nodes. So essentially they created 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 transistor are identical and can be swapped. 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 such a case happens between IN and OUT of the inverter. All combined transitions between two nodes form one edge. So the nodes are connected by single edges.

Subcircuits form connections between nodes through their pins. 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 turned into net-to-net connections, the pin assignment needs to be known. So the algorithm does a bottom-up compare. 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.

The match algorithm

The match algorithm derives node equivalence 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. This scheme can be continue as long as unique edge configurations are present.

Tentative evaluation comes into play 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 match, the first match is taken and reported as "ambiguous match".

Script integration

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.

Here is an example script:

# 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

Run times are in the order of 18 seconds for the full script and the VexRiscV example.