Replacing Pattern Occurrences in a circuit graph¶

This notebook contains some examples on how to use the Netlist Carpentry framework for replacing patterns occurrences in netlists. In this example, chains of OR gates are identified in the given netlist and replaced by a tree-like structure. This notebook shows, how to find chains in a given digital circuit and replace them with tree structures, based on a given pattern. The given pattern consists of 3 OR gate instances, forming a chain. The replacement structure also consists of 3 OR gate instances, but connected in a tree form. The match pattern and the replacement pattern are both specified in Verilog, which can be found in pattern_matching_files/or_pattern_find.v and pattern_matching_files/or_pattern_replace.v.

Figure 1: Example of the replacement of a chain of OR gates with a tree

Importing the required modules and loading the example¶

• To find and replace occurrences in a given digital circuit, a circuit, a match pattern and a replacement pattern are required.
• Both the circuit and the patterns 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 replacement procedure.

In [ ]:

import netlist_carpentry

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

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

• The creation of a pattern to find matches and replace them is similar to the one shown in the pattern matching notebook
• Here, an additional path for the replacement structure is provided.

In [ ]:

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

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

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

• Execute the replacement procedure by callinging Pattern.replace with the module to be modified.
• This will replace all occurrences of the pattern in the given module with the structure specified in the Verilog file for replacement.

Info: The printed number of replacements may vary over different cell executions. This is due to overlapping of pattern occurrences in the circuit. Whenever a pattern occurrence has been found, it is immediately replaced with the replacement structure, interrupting other previously matched patterns. These interrupted pattern occurrences might then no longer match the pattern and will not be considered in subsequent iterations. Depending on the order of the replacements (which is partly random), this may result in a different number of replacements over multiple executions.

In [ ]:

nr_replacements = pattern.replace(module)
print(f"Executed {nr_replacements} replacements of the found pattern in module {module.name}!")

nr_replacements = pattern.replace(module) print(f"Executed {nr_replacements} replacements of the found pattern in module {module.name}!")

• After replacement, the modified circuit can then be written into a new Verilog file using netlist_carpentry.write.
• Execute the cell below to write the modified circuit into a new Verilog file at output/decentral_mux_replaced.v, overwriting any previously created files with the same name.

In [ ]:

netlist_carpentry.write(circuit, output_file_path='output/decentral_mux_replaced.v', overwrite=True)

netlist_carpentry.write(circuit, output_file_path='output/decentral_mux_replaced.v', overwrite=True)

Alternative: a Dedicated Function for Pattern Replacement¶

• The previously introduced pattern replacement algorithm can be compressed into a dedicated function.
• This has the advantage of being easily reused in other scripts.
• The dedicated function takes the path to an existing Verilog file as well as the name of the top-level module as input parameters, plus a path to an output file, into which the modified circuit is written.
• Execute the cell below to execute the pattern replacement procedure again, but this time using the dedicated function, which again saves a Verilog file in the specified location, being output/decentral_mux_replaced_function.v.

In [ ]:

from pathlib import Path


def cascading_or_replacement(netlist_path: str, top: str, output_path: str):
    out_v_path = Path(output_path)

    # Create the pattern with the find and replace structures and the cascading OR gate constraints
    find_pattern_file = 'files/or_pattern_find.json'
    replace_pattern_file = 'files/or_pattern_replace.json'
    pattern = PatternGenerator.build_from_yosys_netlists(find_pattern_file, replace_pattern_file, constraints=[CASCADING_OR_CONSTRAINT])

    # Replace all occurrences of the structure to find with the replacement structure in each module of the circuit
    circuit = netlist_carpentry.read(netlist_path, top=top)
    for module in circuit:
        pattern.replace(module)
    netlist_carpentry.write(circuit, out_v_path, overwrite=True)

# Execute the previously defined function with the appropriate parameters
cascading_or_replacement("files/decentral_mux.v", top="decentral_mux", output_path="output/decentral_mux_replaced_function.v")

from pathlib import Path def cascading_or_replacement(netlist_path: str, top: str, output_path: str): out_v_path = Path(output_path) # Create the pattern with the find and replace structures and the cascading OR gate constraints find_pattern_file = 'files/or_pattern_find.json' replace_pattern_file = 'files/or_pattern_replace.json' pattern = PatternGenerator.build_from_yosys_netlists(find_pattern_file, replace_pattern_file, constraints=[CASCADING_OR_CONSTRAINT]) # Replace all occurrences of the structure to find with the replacement structure in each module of the circuit circuit = netlist_carpentry.read(netlist_path, top=top) for module in circuit: pattern.replace(module) netlist_carpentry.write(circuit, out_v_path, overwrite=True) # Execute the previously defined function with the appropriate parameters cascading_or_replacement("files/decentral_mux.v", top="decentral_mux", output_path="output/decentral_mux_replaced_function.v")