How to create a GenericDeviceParameterCompare subclass for LVS

Using KLayout 0.27 on Xubuntu 18.04, I made a naive attempt at creating a simple resistor comparator:

class ResistorComparator < RBA::GenericDeviceParameterCompare

  def equal(device_a, device_b)
    [ 
      [RBA::DeviceClassResistor::PARAM_A, "A"],    
      [RBA::DeviceClassResistor::PARAM_L, "L"],  
      [RBA::DeviceClassResistor::PARAM_P, "P"],  
      [RBA::DeviceClassResistor::PARAM_R, "R"],
      [RBA::DeviceClassResistor::PARAM_W, "W"],
    ].each do |param_id, param|
      result = device_a.parameter(param_id) == device_b.parameter(param_id)
      puts "Comparing parameter #{param} of two devices (#{device_a.class}, #{device_b.class}): a=#{device_a.parameter(param_id)}, b=#{device_b.parameter(param_id)} --> equal=#{result}"      
      return result
    end
  end

which I installed like so:

netlist.device_class_by_name("RES").equal_parameters = ResistorComparator::new()

To my surprise, the output when I run the LVS compare step is as follows (tail):

Comparing parameter A of two devices (RBA::Device, RBA::Device): a=15.732000000000008, b=15.732000000000008 --> equal=true
Comparing parameter A of two devices (RBA::Device, RBA::Device): a=15.732000000000008, b=0.0 --> equal=false
Comparing parameter A of two devices (RBA::Device, RBA::Device): a=15.732000000000008, b=0.0 --> equal=false
Comparing parameter A of two devices (RBA::Device, RBA::Device): a=15.732000000000008, b=0.0 --> equal=false
Comparing parameter A of two devices (RBA::Device, RBA::Device): a=15.732000000000008, b=15.732000000000008 --> equal=true
Comparing parameter A of two devices (RBA::Device, RBA::Device): a=15.732000000000008, b=0.0 --> equal=false
Comparing parameter A of two devices (RBA::Device, RBA::Device): a=15.732000000000008, b=0.0 --> equal=false
Comparing parameter A of two devices (RBA::Device, RBA::Device): a=15.732000000000008, b=0.0 --> equal=false

I was surprised by the facts that

  1. The loop over the param_id in didn't appear to be working,
  2. the two devices both appear to be of the generic Device class, rather than one of the more specific subclasses such as DeviceClassResistor,
  3. there are only 3 resistors in the layout and schematic but there are 20 comparison lines in total and
  4. the other parameters weren't compared at all, maybe due to...

In addition to that, I also received an internal error:

ERROR: ../../../src/db/db/dbNetlistCompare.cc,2125,e->first == e_other->first
ERROR: In /project/verify_klayout/lvs.lylvs: Internal error: ../../../src/db/db/dbNetlistCompare.cc:2125 e->first == e_other->first was not true in LayoutVsSchematic::compare
ERROR: /project/verify_klayout/lvs.rb:146: Internal error: ../../../src/db/db/dbNetlistCompare.cc:2125 e->first == e_other->first was not true in LayoutVsSchematic::compare in Executable::execute
  /project/verify_klayout/lvs.rb:146:in `execute'
  /project/verify_klayout/lvs.lylvs:8:in `instance_eval'
  /project/verify_klayout/lvs.lylvs:8:in `execute'
  :/built-in-macros/lvs_interpreters.lym:27:in `instance_eval'
  :/built-in-macros/lvs_interpreters.lym:27:in `execute' (class RuntimeError)

I am clearly doing something wrong here, but I'm not sure where to look yet, so any hint would be appreciated.

Comments

  • OK, the first problem with my script was that the loop simply exited after the first comparison, which explains my surprises no. 1 and no. 3. Fixing the equal method to

      def equal(device_a, device_b)
        result = true
        [ 
          [RBA::DeviceClassResistor::PARAM_A, "A"],    
          [RBA::DeviceClassResistor::PARAM_L, "L"],  
          [RBA::DeviceClassResistor::PARAM_P, "P"],  
          [RBA::DeviceClassResistor::PARAM_R, "R"],
          [RBA::DeviceClassResistor::PARAM_W, "W"],
        ].each do |param_id, param|
          result &= device_a.parameter(param_id) == device_b.parameter(param_id)
          puts "Comparing parameter #{param} of two devices (#{device_a.class}, #{device_b.class}): a=#{device_a.parameter(param_id)}, b=#{device_b.parameter(param_id)} --> equal=#{result}"      
        end
        return result
      end
    

    makes all parameters being compared as I had intended. But the other questions/problems persisted.

    So I also tried to add an implementation for the less method:

      def less(device_a, device_b)
        [ 
          [RBA::DeviceClassResistor::PARAM_A, "A"],    
          [RBA::DeviceClassResistor::PARAM_L, "L"],  
          [RBA::DeviceClassResistor::PARAM_P, "P"],  
          [RBA::DeviceClassResistor::PARAM_R, "R"],
          [RBA::DeviceClassResistor::PARAM_W, "W"],
        ].each do |param_id, param|
          result = device_a.parameter(param_id) < device_b.parameter(param_id)
          puts "Comparing parameter #{param} of two devices (#{device_a.class}, #{device_b.class}): a=#{device_a.parameter(param_id)}, b=#{device_b.parameter(param_id)} --> less=#{result}"
          return true if result
        end
        return false
      end
    

    Unfortunately, the internal error shown above still occurs, so I can't use my simple ResistorComparator class yet.

  • @cgelinek_radlogic Yes, the second solution clearly is better :)

    For the internal error, it's very important to provide an implementation ensuring "strict weak ordering" as internally the algorithms are based on C++ STL sets and maps.

    For the compare this means:

    • a < b == true => b < a == false
    • a < b == false && b < a == false => a == b

    Your implementation boils down to this code for two parameters:

    def less(a, b):
      if a.p1 < b.p1:
        return true
      if a.p2 < b.p2:
        return true
      return false
    

    For example for a = (p1,p2) = (1, 2) and b = (2, 1) this gives: less(a, b) = true and less(b, a) = true which is a violation of the first rule.

    A "less" implementation which ensures this condition is that:

    def less(device_a, device_b)
        [ 
          [RBA::DeviceClassResistor::PARAM_A, "A"],    
          [RBA::DeviceClassResistor::PARAM_L, "L"],  
          [RBA::DeviceClassResistor::PARAM_P, "P"],  
          [RBA::DeviceClassResistor::PARAM_R, "R"],
          [RBA::DeviceClassResistor::PARAM_W, "W"],
        ].each do |param_id, param|
          if device_a.parameter(param_id) != device_b.parameter(param_id)
            return device_a.parameter(param_id) < device_b.parameter(param_id)
          end
        end
        return false
      end
    

    (I have not tested this, but it's the coding scheme I'm using all the time).

    Please also note that floats don't compare well - instead of "a != b" you should use "(a - b).abs > eps" and instead of "a == b" you should use "(a - b).abs < eps" where eps is a small value like 1e-6. Otherwise, the strict weak ordering may also be violated just because of floating-point rounding effects.

    Regards,

    Matthias

  • DRC sometimes is given or allowed a tolerance value
    for "good enough", so that trivial rounding or math
    resolution error does not throw a bunch of errors for
    (say) 10.000 != 10.00000000000000000001; is this
    something that is "known art" for klayout Ruby DRC?
    Seems like it would want to be bedded in with the
    above logic, if that's desired here.

  • @Matthias,

    For the internal error, it's very important to provide an implementation ensuring "strict weak ordering" as internally the algorithms are based on C++ STL sets and maps.

    For the compare this means:

    a < b == true => b < a == false
    a < b == false && b < a == false => a == b

    That is important information, thanks for letting us know.

    Following your advice (also on the important floating point comparison issue), I have now changed the code of my ResistorComparator to the following:

    class ResistorComparator < RBA::GenericDeviceParameterCompare
    
      def equal(device_a, device_b)
        eps = 1e-9
        [ 
          [RBA::DeviceClassResistor::PARAM_A, "A"],    
          [RBA::DeviceClassResistor::PARAM_L, "L"],  
          [RBA::DeviceClassResistor::PARAM_P, "P"],  
          [RBA::DeviceClassResistor::PARAM_R, "R"],
          [RBA::DeviceClassResistor::PARAM_W, "W"],
        ].each do |param_id, param|
          result = (device_a.parameter(param_id) - device_b.parameter(param_id)).abs < eps
          puts "Comparing parameter #{param} of two devices: a=#{device_a.parameter(param_id)}, b=#{device_b.parameter(param_id)} --> equal=#{result}"      
          return false if !result
        end
        return true
      end
      def less(device_a, device_b)
        eps = 1e-9
        [ 
          [RBA::DeviceClassResistor::PARAM_A, "A"],    
          [RBA::DeviceClassResistor::PARAM_L, "L"],  
          [RBA::DeviceClassResistor::PARAM_P, "P"],  
          [RBA::DeviceClassResistor::PARAM_R, "R"],
          [RBA::DeviceClassResistor::PARAM_W, "W"],
        ].each do |param_id, param|
          if (device_a.parameter(param_id) - device_b.parameter(param_id)).abs > eps
            result = device_a.parameter(param_id) < device_b.parameter(param_id)
            puts "Comparing parameter #{param} of two devices: a=#{device_a.parameter(param_id)}, b=#{device_b.parameter(param_id)} --> less=#{result}"      
            return result
          end
        end
        return false
      end
    
    end
    

    Note that I used a smaller eps value (1e-9) than the one you suggested (1e-6) as I felt that in order to resolve 10nm differences in, say resistor length, that'd be more appropriate. For e.g. capacitance values, that would probably need to be reduced even further... in practice (once I get over this initial hurdle), the eps value will be replaced by the allowed tolerance for LVS and therefore different for each one of the parameters.

    That aside, I am still getting the internal error I mentioned previously... let me see if I can generate a minimal test case.

  • edited May 2021

    OK, luckily I already had a variant of your si4all sample's devices.gds with some added texts at the device pins as terminals to play around with and a LVS netlist file I created for it; in the attached si4all_withpins.zip file.

    The si4all_lvs_rescomp.zip file includes two LVS runsets:

    • si4all_devices_minimal.lylvs is more or less just the default LVS sample with added resistor recognition (which works fine) and
    • si4all_devices_rescomp.lylvs which is identical except for my ResistorComparator added (which causes the internal error).

    Hoping this can help debug the issue.

    (Please ignore the missing MOS extraction in the runsets, I had not gotten around yet to get the distinction between LV and HV devices working.)

    (While testing with an open Netlist Database Browser window, I also could cause KLayout crashes when opening the tree of the incomplete netlist, but that's not the main point of this thread.)

  • @cgelinek_radlogic Thanks for providing the test case.

    I debugged the problem and actually the cause is still the strict weak ordering, but this time it's not the fault of your code :(

    I have created an issue on GitHub: https://github.com/KLayout/klayout/issues/806 - please see there for more details.

    As of now there is not workaround. But it's easy to fix, so I'm going to put the solution into 0.27.1. In addition, I think we can skip the "equal" implementation as it's redundant ("equal(a,b)" is equivalent to "!less(a,b) && !less(b,a)" in the strict weak ordering scheme).

    Regards,

    Matthias

  • From the cheap seats this looks like good stuff....
  • Hi @Matthias, thanks for looking into this. Glad my testcase could help with finding the problem, looking forward to the 0.27.1 release :smile:

    If we can skip the equal implementation, does that mean this method will go (e.g. will be deprecated) from 0.27.1 going forward? Depending on KLayout's implementation, it may be beneficial to keep it for performance reasons (one equal call instead of two less calls)... if equal stays, it may be worthwhile to add a default implementation inside GenericDeviceParameterCompare to do what you said, namely

    def equal(device_a, device_b)
      return !less(a,b) && !less(b,a)
    end
    

    so users who forget to implement equal themselves get a working comparator by just implementing less. Oh, and maybe have a default less implementation that raises an exception like "'less' method not implemented in subclass", so a user knows what they have to do.

  • edited June 2021

    @cgelinek_radlogic

    From 0.27.1 on, "equal" will simply be ignored. I thought about the performance issue too, but I cannot make STL's std::map to use "equal" anyway, so there is no use in having it. I called it outside std::map myself but I realized that this is a weak optimization at the cost of a twofold (and consistent) implementation.

    The default "less" will compare the parameters using the default scheme, so if you do not implement it, the compare will still work but compare exactly. I thought about a warning if the compare isn't strict weak ordering, but again, the main customers are std::map and std::set and it will silently (or noisily) crash :(

    I also considered shifting to std::unordered_map or std::unodered_set, but then you'd need to provide a hash function instead of "less" (still equal needs to be there). So no real gain.

    The GenericDeviceParameterCompare class currently is a bit special anyway, so that's expert mode. The vanilla way is to use "tolerance" (see https://www.klayout.de/doc-qt5/manual/lvs_compare.html#h2-99)

    BTW: 0.27.1 is released :)

    Matthias

  • @Matthias

    From 0.27.1 on, "equal" will simply be ignored.

    Great, I like simplicity :smile:

    BTW: 0.27.1 is released :smile:

    Awesome, that was quick! B)

    The default "less" will compare the parameters using the default scheme, so if you do not implement it, the compare will still work but compare exactly.
    The GenericDeviceParameterCompare class currently is a bit special anyway, so that's expert mode. The vanilla way is to use "tolerance"

    My main reason for looking into GenericDeviceParameterCompare was that the default comparator only seemed to compare one parameter, namely the resistor value, and I'd like to also compare their width and length (L and W) parameters.

    To achieve this, I did some more experiments on the si4all technology. All files mentioned below are in the attached lvs_matching_custom_parameters.zip. I started with

    • a fairly generic layout (based on the one I posted above), devices_with_pins_2resclasses.gds which has two resistors (of different device classes because I wanted to test differentiation between them and stop using the built-in "RES" device class).
    • A LVS script si4all_devices_2resclasses.lylvs which is able to extract both resistor classes, using the built-in LVS resistor extractor and comparator. Note that I also added writing out the extracted netlist before (.raw.cir) and after the call to simplify (.simplify.cir).
    • A schematic schematic_2resclasses.cir which has the correct resistance and W values, but for R6 (the one instance of the "POLYHIRES" class), L is incorrect.

    Using this setup, LVS matches both resistors R5 and R6, even though R6 has a different L in the schematic than in the layout. Because W and L aren't reported at all in the Netlist Database Browser or the written .extracted.cir file, I was wondering whether the extracted W and L are actually being recorded by the built-in resistor extractor.

    Following your advice, I tried adding tolerance(res_class, "W", 0.01, 0.01) to the script, but even though the W parameter values are correct for both res_classes, none of the resistors matched any more.

    • So I added a custom extractor based on the great work by @tagger5896, aiming to create a drop-in replacement for the built-in extractor and making sure all parameters are propagated (see si4all_devices_customextractor.lylvs for the complete script):
    # Resistor extraction
    class ResistorExtractor < RBA::GenericDeviceExtractor
    
      def initialize(name, sheet_rho)
        self.name = name
        @sheet_rho = sheet_rho
      end
    
      def setup
        define_layer("C", "Conductor")
        define_layer("R", "Resistor")
        register_device_class(RBA::DeviceClassResistor::new)
      end
    
      def extract_devices(layer_geometry)
        # layer_geometry provides the input layers in the order they are defined with "define_layer"
        conductor = layer_geometry[0]
        resistor  = layer_geometry[1]
    
        resistor_regions = resistor.merged
    
        resistor_regions.each do |r|
          terminals = conductor.interacting(resistor)
          if terminals.size != 2
            error("Resistor shape does not touch marker border in exactly two places", r)
          else
            double_width = 0
            (terminals.edges & resistor.edges).merged.each do |e|
              double_width += e.length
            end
            # A = L*W
            # -> L = A/W
            a = r.area*dbu*dbu
            w = (double_width / 2.0)*dbu
            l = a / w
    
            device = create_device
            device.set_parameter(RBA::DeviceClassResistor::PARAM_R, @sheet_rho * l / w);
    
            device.set_parameter(RBA::DeviceClassResistor::PARAM_A, a)
            device.set_parameter(RBA::DeviceClassResistor::PARAM_L, l)
            device.set_parameter(RBA::DeviceClassResistor::PARAM_P, 2*l+2*w)
            device.set_parameter(RBA::DeviceClassResistor::PARAM_W, w)
            define_terminal(device, RBA::DeviceClassResistor::TERMINAL_A, 0, terminals[0]);
            define_terminal(device, RBA::DeviceClassResistor::TERMINAL_B, 0, terminals[1]);
          end
        end
      end
    
      def get_connectivity(layout, layers)
        # This is not a connectivity in a sense of electrical connections.
        # Instead, 'Connected' shapes are collected and presented to the device extractor.
        conn = RBA::Connectivity::new
        conductor = layers[0]
        resistor  = layers[1]
        conn.connect(conductor, resistor)
        return conn
      end
    
    end
    
    

    Unfortunately, I couldn't see any evidence (in either the Browser or the written netlists) that those extra parameters were propagated to the extracted netlist or made any difference in the compare step.

    • That's when I tried to do the comparison myself using the GenericDeviceParameterCompare subclass, for which I now added the following code to the script (si4all_customcomparator.lylvs):
    class ResistorComparator < RBA::GenericDeviceParameterCompare
    
      def less(device_a, device_b)
        puts "Calling `less` with devices (#{device_a}, #{device_b}):"
        [ 
    #      [RBA::DeviceClassResistor::PARAM_A, "A"],    # not interested in this at the moment
          [RBA::DeviceClassResistor::PARAM_L, "L"],  
    #      [RBA::DeviceClassResistor::PARAM_P, "P"],      # not interested in this at the moment
          [RBA::DeviceClassResistor::PARAM_R, "R"],
          [RBA::DeviceClassResistor::PARAM_W, "W"],
        ].each do |param_id, param|
          result = device_a.parameter(param_id) < device_b.parameter(param_id)
          puts "  parameter #{param}: a=#{device_a.parameter(param_id)}, b=#{device_b.parameter(param_id)} --> less=#{result}"
          return true if result
        end
        return false
      end
    
    end
    

    Using this comparator class along with the custom extractor finally led to matching R5 but a mis-match for R6. (The debug puts statements proved very useful for debugging its operation!)

    I also tried to use the custom comparator with the built-in resistor extractor, but without success - both R devices couldn't be matched... looking at the debug output, it seems the W and L values extracted by the built-in resistor extractor are double their actual values?

    These experiments led to some suggestions for an upcoming release:

    1. Could the other parameters be made visible in the Netlist Database Browser,
    2. and (probably more importantly) saved when writing out a netlist?
    3. It would also be nice show them as "half-matching" devices (a single line with a /!\ symbol) if a minority of parameters doesn't match, especially when the devices match topologically, so we don't end up with a comparison result like for the POLYHIRES devices where everything shown is the same: R6 that looks like it should match
    4. This is probably tricky, as custom comparators probably don't give enough information to the matching algorithm, but it would be nice to see (highlighted) the parameters which are reported as mismatching. For this, I'm imagining some API changes: The GenericDeviceParameterCompare subclass - instead of computing the relationship between two devices in a single less call - would register parameters (IDs) it is interested in (maybe at ::new), and less gets an additional argument for the parameter it should compare, (as in less(device_a, device_b, param_id)) which could be used in a case statement to select which comparison (tolerances etc) should be applied. Then the matching algorithm would call less once for each parameter of interest and so find out which parameter caused the mismatch... but I'm just dreaming at this point ;)
  • @cgelinek_radlogic

    Your request makes sense and basically it's possible to extend the frameworks towards that flexibility, but the path will be a different one and there are a couple of extensions required toward more flexibility - which is essentially what you ask for.

    First of all, the framework consists of these components:

    • The device class: a device class is basically the device type. A device class specifies the terminals, the parameters, the way parallel or serial devices combine and basically provides a descriptor for devices. For resistors currently there is one class for a 2-terminal device and one for a 3-terminal device. Objects of device classes have a name or rather a model name which make them representative for a particular type and model.
    • A device comparer: this is an optional object attached to a device class (a delegate) providing the algorithm for comparing the devices.
    • The device object: this object represents the actual device. It refers to a device class and provides the actual parameter values. Device objects are put into a circuit when forming the netlist.
    • The device extractor: this object provides the algorithm for generating a device object from geometry and computing the parameters.
    • Spice netlist reader and writer delegates: these classes are responsible for turning devices to Spice and back.

    All these classes act together to implement the device handling scheme.

    Currently, only the device comparer, the device extractor and the Spice netlist reader and writer delegates can be customized. Unless someone wants to implement exotic devices, customizable device classes should not be required. But I'll consider this as an enhancement.

    For the problem of L and W extraction: These parameters are defined and extracted already, but there is the concept of primary and secondary parameters: each parameter is declared primary or secondary. Only primary layers and printed in the device string and with the default comparer, only primary parameters are compared. Currently, W and L (and A and P) are secondary parameters.

    In addition, the W and L parameters are not read from or written to Spice by default.

    So in order to fix this, you'd need to

    1. Include W and L in compare - either by using a comparer, but also using a tolerance should do the job
    2. Enable these parameter for reading and writing to Spice: that should be possible using special delegates

    For showing the parameters in the netlist browser, there is no customization available for now.

    I feel that W and L are actually parameters which should be added to Spice reader and writer too. Maybe there are other parameters for caps. Resistors also carry A and P for area and perimeter. These could be enabled as well. That would eliminate need for step 2. A similar feature already is present for MOS devices and the AS/AD/PS/PD parameters which are secondary ones but still are read from and written to Spice.

    I might also show secondary parameters in the netlist browser too. Maybe configurable as an option.

    As secondary parameters can conveniently be enabled in the compare using "tolerance", there should not be need for a custom comparer.

    So bottom line is I'd not drop the concept of primary and secondary parameters as this provides a quite useful classification in simple cases.

    Regarding the idea about the "mismatch": there actually is no such concept - either you want parameters to match or you don't. If a device matches topologically you'd get a parameter mismatch anyway. But device parameters do not just make a device match - they also act as guidelines for the topology match, so there is no skipping them.

    Regards,

    Matthias

Sign In or Register to comment.