Custom Search and Replace¶

This notebook shows how to implement custom search and replace operations on a netlist. As an example the Verilog design files for the openMSP430 project are used. The design has a sufficiently large complexity and hierarchy to demonstrate the usage of the framework on a larger design. To use this notebook, the design files of the openMSP430 must be cloned from the repository and then pre-processed using Yosys to retrieve a unified design (in the form of a generic netlist), where all modules are defined in a single file.

Info: Before using this notebook, clone the openMSP430 repository and update the openMSP_hdl_path variable in the box below accordingly.

Initialization¶

• Similar to the previous notebooks, the design must be loaded first.
• Execute the cell below to load the design.

Info: The Yosys-generated Verilog file containing the design of the openMSP430 is rather large (approx. 9k lines), and the JSON netlist is even larger (more than 80k lines). Accordingly, executing the cells that perform operations on the design (e.g. reading the file, or replacing objects) will require a lot more time than in the small designs in the previous notebooks. Depending on the system, the execution of the cells may thus range between a couple of seconds up to minutes.

In [ ]:

from pathlib import Path

import netlist_carpentry
from netlist_carpentry.scripts.script_builder import build_and_execute


def gen_nl_and_read():
    yosys_script_path = Path("files/openMSP430/openMSP430_synthesis_script.sh")
    # Path within the openMSP430 submodule
    openMSP_hdl_path = Path("../../../openmsp430/core/rtl/verilog/*.v")

    # Target path of the netlist
    nl_path = Path("files/openMSP430/openMSP430.json")
    top = "openMSP430"
    techmap_path = Path("files/openMSP430/pmux2mux_techmap.v")

    build_and_execute(yosys_script_path, [openMSP_hdl_path], nl_path, top=top, techmap_paths=[techmap_path])
    return netlist_carpentry.read_json(nl_path)

circuit = gen_nl_and_read()
module = circuit.top

from pathlib import Path import netlist_carpentry from netlist_carpentry.scripts.script_builder import build_and_execute def gen_nl_and_read(): yosys_script_path = Path("files/openMSP430/openMSP430_synthesis_script.sh") # Path within the openMSP430 submodule openMSP_hdl_path = Path("../../../openmsp430/core/rtl/verilog/*.v") # Target path of the netlist nl_path = Path("files/openMSP430/openMSP430.json") top = "openMSP430" techmap_path = Path("files/openMSP430/pmux2mux_techmap.v") build_and_execute(yosys_script_path, [openMSP_hdl_path], nl_path, top=top, techmap_paths=[techmap_path]) return netlist_carpentry.read_json(nl_path) circuit = gen_nl_and_read() module = circuit.top

• The graph of a module does by default represent each instance as a single nodes, even if the instance is a submodule which itself may contain many instances.
• Execute the cell below to see the node number in the graph of the top module, as well as the names of the submodules instantiated in the top module.

In [ ]:

module_graph = module.graph()
print(f"The module graph of {module.name} consists of {len(module_graph.nodes)} nodes, comprised of {len(module.instances)} instances and {len(module.ports)} ports!")

print(f"The module contains {len(module.submodules)} submodule instances:")
for s in module.submodules:
    print(f"\tInstance of module '{s.instance_type}' with name '{s.name}'")

module_graph = module.graph() print(f"The module graph of {module.name} consists of {len(module_graph.nodes)} nodes, comprised of {len(module.instances)} instances and {len(module.ports)} ports!") print(f"The module contains {len(module.submodules)} submodule instances:") for s in module.submodules: print(f"\tInstance of module '{s.instance_type}' with name '{s.name}'")

Finding all Instances of a specific type recursively (Depth-First Search)¶

• Since circuit designs contain instances of many different types, but often only specific types are relevant to the design analysis or modification, it is often useful to search for all instances of a specific type.
• The cells below provide a short introduction on how to implement a Depth-First Search (DFS) to search a graph recursively.
• Depth-First Search is a graph traversal algorithm, where it starts at a given node and explores as far as possible along each branch before backtracking.
• To find all Adder instances (for example) in the whole design, execute the cell below.
• The function returns a generator that yields all adders found in the design.

In [ ]:

from netlist_carpentry import Circuit, Module


def find_all_adders_in_module_recursively(circuit: Circuit, module: Module):
    for instance in module.instances.values():
        if "add" in instance.instance_type:
            yield instance
        elif instance.is_module_instance:
            submodule = circuit.get_module(instance.instance_type)
            yield from find_all_adders_in_module_recursively(circuit, submodule)

instances = list(find_all_adders_in_module_recursively(circuit, module))
print("These are all adders in the openMSP430 design:")
for instance in instances:
    print(f"\t{instance.raw_path}")

from netlist_carpentry import Circuit, Module def find_all_adders_in_module_recursively(circuit: Circuit, module: Module): for instance in module.instances.values(): if "add" in instance.instance_type: yield instance elif instance.is_module_instance: submodule = circuit.get_module(instance.instance_type) yield from find_all_adders_in_module_recursively(circuit, submodule) instances = list(find_all_adders_in_module_recursively(circuit, module)) print("These are all adders in the openMSP430 design:") for instance in instances: print(f"\t{instance.raw_path}")

• Alternatively, to retrieve the full instance paths, the hierarchy layers could be passed in the form of a list of instance hierarchies to retrieve the full path for an instance (not just to the module it belongs to).
• For this, the current hierarchy level (which is initially only the top module openMSP430) is appended to the list of paths in each recursion and the function is called recursively with the updated list of paths.
• Hence, the length of the list of paths is equal to the hierarchy level of the design in the current step.
• Execute the cell below to see the full paths of all adders in the design.
• The function returns a generator that yields the full paths of all adders found in the design.

In [ ]:

from typing import List


def find_all_adder_paths_in_module_recursively(circuit: Circuit, module: Module, current_hierarchy_paths: List[str] = []):
    for instance in module.instances.values():
        if "add" in instance.instance_type:
            yield ".".join([*current_hierarchy_paths, instance.name])
        elif instance.is_module_instance:
            submodule = circuit.get_module(instance.instance_type)
            current_hierarchy_paths.append(instance.name)
            yield from find_all_adder_paths_in_module_recursively(circuit, submodule, current_hierarchy_paths)
            current_hierarchy_paths.pop()

instances = list(find_all_adder_paths_in_module_recursively(circuit, module, ["openMSP430"]))
print("These are the full paths of all adders in the openMSP430 design:")
for instance in instances:
    print(f"\t{instance}")

from typing import List def find_all_adder_paths_in_module_recursively(circuit: Circuit, module: Module, current_hierarchy_paths: List[str] = []): for instance in module.instances.values(): if "add" in instance.instance_type: yield ".".join([*current_hierarchy_paths, instance.name]) elif instance.is_module_instance: submodule = circuit.get_module(instance.instance_type) current_hierarchy_paths.append(instance.name) yield from find_all_adder_paths_in_module_recursively(circuit, submodule, current_hierarchy_paths) current_hierarchy_paths.pop() instances = list(find_all_adder_paths_in_module_recursively(circuit, module, ["openMSP430"])) print("These are the full paths of all adders in the openMSP430 design:") for instance in instances: print(f"\t{instance}")

Finding all Instances of a specific type with queueing (Breadth-First Search)¶

• In Breadth-First Search, all nodes directly reachable from the start node are traversed first.
• Only then are the nodes one level deeper in the graph traversed.
• This is done by using a queue to keep track of the nodes that need to be visited.
• Furthermore, nodes that have already been visited are marked as such to avoid being visited again.
• This is done by setting a custom attribute already_visited to True.

Info: All objects based on the class Netlist Element have the instance dictionary variables attributes and parameters. While parameters are considered in Verilog write-out since they may have a direct impact on the circuit (e.g. in regards to module or instance parameters), attributes do not affect the circuit at all and are mainly used for metadata (such as a link to the HDL source). Thus, the variable attributes can be used to apply custom or user-defined data to an object. This is done here with the attribute already_visited.

In [ ]:

from collections import deque
from typing import Tuple

from netlist_carpentry import Instance


def find_all_adders_in_circuit_bfs(circuit: Circuit):
    # The queue stores both the instance object and the path in the graph to the object.
    queue: deque[Tuple[Instance, str]] = deque()
    for instance in circuit.top.instances.values():
        queue.append((instance, f"{circuit.top.name}.{instance.name}"))
        instance.metadata.add("already_visited", True)
    while queue:
        node, path = queue.popleft()
        if "add" in node.instance_type:
            yield path
        elif node.is_module_instance:
            submodule = circuit.get_module(node.instance_type)
            for child in submodule.instances.values():
                if not child.metadata.get("already_visited", False):
                    # Add the current child to the queue as well as the path to the child
                    queue.append((child, f"{path}.{child.name}"))
                    child.metadata.add("already_visited", True)

# Re-initialize the circuit to allow for multiple subsequent executions of this cell.
# By re-initializing the circuit, all custom attributes (such as "already_visited") will be removed,
# since they are not present in the read circuit.
circuit = gen_nl_and_read()
instances = list(find_all_adders_in_circuit_bfs(circuit))
print("These are all adders in the openMSP430 design as found via BFS:")
for instance in instances:
    print(f"\t{instance}")
print("As visible by the printed cells, the algorithm first traverses the cells in the top level module and then moves on to their children.")
print("This can be seen by the hierarchy of the printed paths (the number of dots in the path), where the number of dots in the paths increases, as we move deeper into the circuit.")

from collections import deque from typing import Tuple from netlist_carpentry import Instance def find_all_adders_in_circuit_bfs(circuit: Circuit): # The queue stores both the instance object and the path in the graph to the object. queue: deque[Tuple[Instance, str]] = deque() for instance in circuit.top.instances.values(): queue.append((instance, f"{circuit.top.name}.{instance.name}")) instance.metadata.add("already_visited", True) while queue: node, path = queue.popleft() if "add" in node.instance_type: yield path elif node.is_module_instance: submodule = circuit.get_module(node.instance_type) for child in submodule.instances.values(): if not child.metadata.get("already_visited", False): # Add the current child to the queue as well as the path to the child queue.append((child, f"{path}.{child.name}")) child.metadata.add("already_visited", True) # Re-initialize the circuit to allow for multiple subsequent executions of this cell. # By re-initializing the circuit, all custom attributes (such as "already_visited") will be removed, # since they are not present in the read circuit. circuit = gen_nl_and_read() instances = list(find_all_adders_in_circuit_bfs(circuit)) print("These are all adders in the openMSP430 design as found via BFS:") for instance in instances: print(f"\t{instance}") print("As visible by the printed cells, the algorithm first traverses the cells in the top level module and then moves on to their children.") print("This can be seen by the hierarchy of the printed paths (the number of dots in the path), where the number of dots in the paths increases, as we move deeper into the circuit.")

Replacing all instances of a certain type with another instance¶

• As a simple example, consider replacing all adders by multipliers (for whatever reason -- this obviously makes no sense).
• Every adder instance must thus be removed and a multiplier instance must be inserted at the exact same place with the same connections.
• Execute the cell below, which replaces all adder instances in the circuit with multiplier instances, using a modified version of the find_all_adder_paths_in_module_recursively function.

Info: There are two methods already implemented that can replace instances within a module:

• Module.substitute_instance(old_instance, new_instance) to replace an instance directly with another instance -- the objects must both exist already. The instance interfaces must match, i.e. both instances have the same ports and port widths.
• Module.refine_instance(instance, new_type_defintion) to also replace a given instance, but a module definition (or a primitive gate) is given as second parameter. The module definition can either be a Module instance or a gate class. In both cases, the interface is applied to the given instance and the instance's type is updated accordingly.

In [ ]:

from itertools import islice

from netlist_carpentry.utils.gate_lib import Multiplier


def find_and_replace_all_adders_by_multipliers(circuit: Circuit, module: Module, current_hierarchy_paths: List[str] = []):
    instances = list(module.instances.values())
    for instance in instances:
        if "add" in instance.instance_type:
            # Now also replace the found instances!
            new_inst = replace_single_instance(module, instance)
            yield ".".join([*current_hierarchy_paths, new_inst.name]) + f" (class {new_inst.__class__.__name__})"
        elif instance.is_module_instance:
            submodule = circuit.get_module(instance.instance_type)
            current_hierarchy_paths.append(instance.name)
            yield from find_and_replace_all_adders_by_multipliers(circuit, submodule, current_hierarchy_paths)
            current_hierarchy_paths.pop()

def replace_single_instance(module: Module, adder_instance: Instance):
    """Replaces a single adder instance in the given module with a multiplier instance."""
    multiplier_name = f"{adder_instance.name}_now_multiplier"
    multiplier_inst = Multiplier(name=multiplier_name)

    print_connections(adder_instance)
    for port in adder_instance.ports.values():
        # Copy ports from the adder instance and set them accordingly in the new multiplier instance
        for idx, segment in port:
            # Copy port segment and set it accordingly in the instance
            # Using connect_modify to overwrite default settings of the instance from the gate library
            multiplier_inst.connect_modify(port.name, ws_path=segment.ws_path, direction=port.direction, index=idx)
    print_connections(multiplier_inst)

    module.remove_instance(adder_instance)
    module.add_instance(multiplier_inst)
    return multiplier_inst

def print_connections(instance: Instance):
    """Print the connections of the given instance to the console."""
    print(f"Connections of the {instance.__class__.__name__} instance {instance.name}:")
    for port in instance.ports.values():
        print(f"\tPort {port.name} is connected to wire segments: {', '.join(w.raw for w in port.connected_wires)}")

# Re-initialize the circuit to allow for multiple subsequent executions of this cell.
# By re-initializing the circuit, all modifications will be removed.
circuit = gen_nl_and_read()
max_replacements_nr = 3
instances = list(islice(find_and_replace_all_adders_by_multipliers(circuit, module, ["openMSP430"]), max_replacements_nr))
print(f"\nThese are the full paths of all adders that were replaced with multipliers in the openMSP430 design in {max_replacements_nr} replacement steps:")
for instance in instances:
    print(f"\t{instance}")

from itertools import islice from netlist_carpentry.utils.gate_lib import Multiplier def find_and_replace_all_adders_by_multipliers(circuit: Circuit, module: Module, current_hierarchy_paths: List[str] = []): instances = list(module.instances.values()) for instance in instances: if "add" in instance.instance_type: # Now also replace the found instances! new_inst = replace_single_instance(module, instance) yield ".".join([*current_hierarchy_paths, new_inst.name]) + f" (class {new_inst.__class__.__name__})" elif instance.is_module_instance: submodule = circuit.get_module(instance.instance_type) current_hierarchy_paths.append(instance.name) yield from find_and_replace_all_adders_by_multipliers(circuit, submodule, current_hierarchy_paths) current_hierarchy_paths.pop() def replace_single_instance(module: Module, adder_instance: Instance): """Replaces a single adder instance in the given module with a multiplier instance.""" multiplier_name = f"{adder_instance.name}_now_multiplier" multiplier_inst = Multiplier(name=multiplier_name) print_connections(adder_instance) for port in adder_instance.ports.values(): # Copy ports from the adder instance and set them accordingly in the new multiplier instance for idx, segment in port: # Copy port segment and set it accordingly in the instance # Using connect_modify to overwrite default settings of the instance from the gate library multiplier_inst.connect_modify(port.name, ws_path=segment.ws_path, direction=port.direction, index=idx) print_connections(multiplier_inst) module.remove_instance(adder_instance) module.add_instance(multiplier_inst) return multiplier_inst def print_connections(instance: Instance): """Print the connections of the given instance to the console.""" print(f"Connections of the {instance.__class__.__name__} instance {instance.name}:") for port in instance.ports.values(): print(f"\tPort {port.name} is connected to wire segments: {', '.join(w.raw for w in port.connected_wires)}") # Re-initialize the circuit to allow for multiple subsequent executions of this cell. # By re-initializing the circuit, all modifications will be removed. circuit = gen_nl_and_read() max_replacements_nr = 3 instances = list(islice(find_and_replace_all_adders_by_multipliers(circuit, module, ["openMSP430"]), max_replacements_nr)) print(f"\nThese are the full paths of all adders that were replaced with multipliers in the openMSP430 design in {max_replacements_nr} replacement steps:") for instance in instances: print(f"\t{instance}")

Optimizing the circuit¶

• After all modifications are finished, the circuit (or individual modules) can be optimized via Circuit.optimize and Module.optimize.
• This removes wires without loads and instances with unconnected outputs.
• Both methods return a boolean indicating whether any changes were made.
• In the future, additional optimization algorithms may be implemented.
• Execute the cell below to optimize the circuit.

In [ ]:

module_optimized = module.optimize()
if module_optimized:
    print(f"Module {module.name} was optimized.")
else:
    print(f"Module {module.name} is already optimized.")

circuit_optimized = circuit.optimize()
if circuit_optimized:
    print(f"Circuit {circuit.name} was optimized.")
else:
    print(f"Circuit {circuit.name} is already optimized.")

module_optimized = module.optimize() if module_optimized: print(f"Module {module.name} was optimized.") else: print(f"Module {module.name} is already optimized.") circuit_optimized = circuit.optimize() if circuit_optimized: print(f"Circuit {circuit.name} was optimized.") else: print(f"Circuit {circuit.name} is already optimized.")