Matching Patterns on a circuit graph¶

This notebook contains some examples on how to use the Netlist Carpentry framework for matching patterns in netlists. In this example, chains of OR gates are identified in the given netlist. Chains of OR gates are instances that are connected to each other in a cascading manner. This means, that the output of an OR gate is connected to the input of another OR gate. This notebook shows, how to find such chains in a given digital circuit, based on a given pattern. The given pattern consists of 3 OR gate instances, forming a chain. The pattern is specified in Verilog, which can be found in pattern_matching_files/or_pattern_find.v.

Importing the required modules and loading the example¶

• To find pattern occurrences in a given digital circuit, a circuit and a pattern are required.
• Both the circuit and the pattern may be specified in Verilog.
• The Verilog files for this example are located in the pattern_matching_files folder.
• Execute the cell below to initialize the framework and set up all stuff required for the pattern matching procedure.

In [ ]:

import netlist_carpentry

circuit = netlist_carpentry.read("files/decentral_mux.v", top="decentral_mux")
module_graph = circuit.top.graph()

import netlist_carpentry circuit = netlist_carpentry.read("files/decentral_mux.v", top="decentral_mux") module_graph = circuit.top.graph()

• After the circuit is initialized and the graph of the top module (and thus of the circuit) is created, the pattern can be created and scanned for pattern occurrences.
• Execute the cell below to create a pattern object from the provided Verilog design using the PatternGenerator class.

Info: The constraints list (which in the example only contains the cascading OR constraint) is used to define how the pattern should be matched in regards to boundary conditions. The provided CASCADING_OR_CONSTRAINT will ensure that only cascading OR gates are matched, which means that different structures (e.g. OR gates forming a tree) are ignored. This mechanic is still Work-In-Progress, in regards to its modifiability and extensibility, and may be changed or extended in future versions.

In [ ]:

from netlist_carpentry.core.graph.constraint import CASCADING_OR_CONSTRAINT
from netlist_carpentry.core.graph.pattern_generator import PatternGenerator

pattern = PatternGenerator.build_from_verilog("files/or_pattern_find.v", constraints=[CASCADING_OR_CONSTRAINT])

from netlist_carpentry.core.graph.constraint import CASCADING_OR_CONSTRAINT from netlist_carpentry.core.graph.pattern_generator import PatternGenerator pattern = PatternGenerator.build_from_verilog("files/or_pattern_find.v", constraints=[CASCADING_OR_CONSTRAINT])

• The pattern object can be used to scan the given circuit for pattern occurrences via Pattern.find_matches, which takes the graph of a module.
• Since the pattern does not depend on a specific circuit until Pattern.find_matches is called with a module graph, it can be reused for different circuits to find pattern occurrences in multiple circuits.
• Execute the cell below to apply the pattern on the module graph and print out how many matches were found.

In [ ]:

match = pattern.find_matches(module_graph)
print(f"Found {match.count} pattern occurrences in the provided circuit!")

# Alternative approach, if only the number of matches is needed
match_count = pattern.count_matches(module_graph)
print(f"Found {match_count} pattern occurrences in the provided circuit again!")

match = pattern.find_matches(module_graph) print(f"Found {match.count} pattern occurrences in the provided circuit!") # Alternative approach, if only the number of matches is needed match_count = pattern.count_matches(module_graph) print(f"Found {match_count} pattern occurrences in the provided circuit again!")

• The Match object returned by Pattern.find_matchesh contains the pattern matches as a list of graphs as an attribute.
• Each graph is a Directed, Multi-Edge Graph from networkx.
• Unfortunately, there is currently no built-in method in networkx to print a graph to the console.
• Execute the cell below to inspect the first of the found matches, to see which nodes from the circuit form the pattern occurrence.
• The arrows in the printed text represent the connections between the nodes, where the source node is on the left-hand side of the arrow and all sink nodes are on the right-hand side of the arrow.

In [ ]:

print("Match 0:")
first_match_graph = match.matches[0]
for node, succs in first_match_graph.adjacency():
    successor_str = ", ".join(succs) if succs else "No successors"
    print(f"\t{node} -> {successor_str}")

print("Match 0:") first_match_graph = match.matches[0] for node, succs in first_match_graph.adjacency(): successor_str = ", ".join(succs) if succs else "No successors" print(f"\t{node} -> {successor_str}")