graph module

exception graph.SynthesisException(message)

Bases: Exception

Mugen’s generic exception class that is thrown whenever something unexpected happens during synthesis.

__init__(message)
Parameters:message – The message to show when the exception is thrown.
graph.eval_gate(gate_type, inputs)

Evaluates a certain gate type on a list of binary input values. Returns the result.

Parameters:
  • gate_type – The type of gate to evaluate. Choices are EMPTY, WIRE, NOT, AND, OR, and MAJ.
  • inputs – List of input values.
graph.get_coords_in_direction(coords, direction)

Given a set of coordinates and a cardinal direction. Returns the coordinates of a node immediately adjacent to the current one in the given direction. Note that this may result in a set of coordinates that are not within the bounds of a clocking scheme (e.g. this may result in negative coordinates).

graph.get_direction(coords1, coords2)

Given a pair of coordinates, determines in which cardinal direction the information flows. Returns the result as a pair (d1, d2), where d1 is the direction in which the signal leaves from coords1 and d2 is the direction in which it arrives at coords2.

graph.is_east(coords1, coords2)

Returns true if and only if coords1 lies to the east of coords2. We say this is the case if they have the same vertical position but coords1 has a higher horizontal position.

graph.is_north(coords1, coords2)

Returns true if and only if coords1 lies to the north of coords2. We say this is the case if they have the same horizontal position but coords1 has a lower vertical position.

graph.is_south(coords1, coords2)

Returns true if and only if coords1 lies to the south of coords2. We say this is the case if they have the same horizontal position but coords1 has a higher vertical position.

graph.is_west(coords1, coords2)

Returns true if and only if coords1 lies to the west of coords2. We say this is the case if they have the same vertical position but coords1 has a lower horizontal position.

class graph.logic_network(shape, nr_pis, nr_pos)

Bases: object

A logic_network is the result of synthesis. Its design is similar to a clocking scheme graph. A major difference is that it cannot contain cycles. However, it can also be accessed using the same tile coordinate based API.

Variables:
  • shape – a 2-tuple containing the size of the grid (width x height).
  • nr_pis – number of PIs.
  • nr_pos – number of POs.
  • nodes – A list of all the nodes in the logic network, including the PIs.
  • node_map – A map from tile coordinates to nodes nodes in the logic network. E.g. to access the node corresponding to tile (0,0) one refers to node_map[(0,0)].
  • po_map – A list of size nr_pos mapping output indices to nodes in the network. E.g. to access the first output, one refers to po_map[0].
__init__(shape, nr_pis, nr_pos)

Creates a new logic network.

Parameters:
  • shape – a 2-tuple containing the size of the grid (width x height).
  • nr_pis – number of PIs.
  • nr_pos – number of POs.
has_border_io()

Checks if only border nodes are connected to PIs and POs. Returns True if this is the case and False otherwise.

has_designated_pi()

Checks if only WIREs are connected to PIs. Moreover, verifies that those designated PI WIREs have only one fanout. Returns True of this is the case and False otherwise.

has_designated_po()

Checks if only WIREs are connected to POs. Moreover, verifies that those designated PO WIREs have no other fanout. Returns True of this is the case and False otherwise.

rec_simulate(n, sim_vals, marked_nodes)

Recursive helper method for simulate().

set_output(h, coords, d)

Marks the output port in direction d for the node at coords as the h-th output of the network.

simulate()

Simulates the logic network and returns a list which contains the simulated function for each output.

to_png(filename)

Creates a PNG of the logic network using Graphviz. In the resulting PNG, all border nodes are filled in with a gray color. All internal nodes are white. PO nodes are marked by a double border. Every non-PI node is also marked with its tile-space coordinates as well as the function it computes.

verify_consecutive_not()

Verifies that the network contains no consecutive NOT gates. Raises a SynthesisException if it does.

verify_designated_pi()

The same as has_designated_pi() but raises a SynthesisException if the spec is not met.

verify_designated_po()

The same as has_designated_po() but raises a SynthesisException if the spec is not met.

verify_no_crossing_io()

Verifies that the network contains no crossings that are directly connected to I/O pins. Raises a SynthesisException if it does.

class graph.node(*, coords=None, is_pi=False, is_po=False)

Bases: object

A generic node class, used by both clocking scheme graphs and logic networks.

Variables:
  • coords – The grid coordinates of the node in the clocking scheme.
  • is_pi – Is the node a primary input.
  • is_po – Is the node a primary output.
  • fanin – A list of nodes containing the fanin of the current node.
  • fanout – A list of nodes containing the fanin of the current node.
  • is_border_node – This Boolean flag is True iff the node lies on the border of the clocking scheme.
  • gate_type – The gate type of the node.
  • dir_map – This optional attribute is set only for nodes with gate_type CROSS. It is a dictionary which maps fanin directions to output directions. For example, if dir_map = { ‘WEST’: ‘NORTH’, ‘EAST’: ‘SOUTH’}, then the western fanin is mapped to the northern fanout port and the eastern fanin is mapped to the southern fanout port.
__init__(*, coords=None, is_pi=False, is_po=False)

Creates a new logic node.

Parameters:
  • coords – the grid coordinates of the node in the clocking scheme.
  • is_pi – is the node a primary input.
  • is_po – is the node a primary output.
set_fanin(in_dir, innode, out_dir)

Sets the fanin port at direction d of this node to innode and updates the fanout of innode by appending this node to it.

class graph.scheme_graph(*, shape=(1, 1), enable_wire=True, enable_not=True, enable_and=True, enable_or=True, enable_maj=True, enable_crossings=True, designated_pi=False, designated_po=False, nr_threads=1, timeout=0)

Bases: object

A scheme_graph (short for clocking-scheme graph) is used to specify a clocking scheme and to synthesize logic networks according to that specification.

__init__(*, shape=(1, 1), enable_wire=True, enable_not=True, enable_and=True, enable_or=True, enable_maj=True, enable_crossings=True, designated_pi=False, designated_po=False, nr_threads=1, timeout=0)

Creates a new clocking scheme graph.

Parameters:
  • shape – A 2-tuple specifying the dimensions of the clocking scheme.
  • enable_not – Enable synthesis of WIREs.
  • enable_not – Enable synthesis of NOT gates.
  • enable_and – Enable synthesis of AND gates.
  • enable_or – Enable synthesis of OR gates.
  • enable_maj – Enable synthesis of MAJ gates.
  • enable_crossings – Enable wire crossings.
  • designated_pi – True iff only WIRES can have PI fanin.
  • designated_po – True iff only WIRES can have PO fanout.
  • nr_threads – How many threads to use in parallel solving.
  • timeout – the timeout for the synthesize call (in seconds)
add_virtual_edge(coords1, coords2)

Adds a virtual edge from the node corresponding to the tile at coords1 to the node corresponding to the tile at coords2. A virtual edge specifies that the node at coords2 may have the node at coords1 in its fanin. However, it does not force this to happen. Hence, the connection is virtual and may be actualized by the synthesis process.

find_cycles()

Examines the clocking scheme graph and finds any cycles it may contain.

model_to_network(model, nr_outputs, out_vars, nr_local_sim_vars, verbosity)

Decodes a SAT model (i.e. a list of integer values) and creates a logic_network from it.

print_model()

Prints the model of the latest successful SAT call (if any).

satisfies_spec(net, functions)

Verifies that a network satisfies the specifications represented by this scheme_graph object. Raises a SynthesisException if this is not the case.

synthesize(functions, verbosity=0)

Synthesizes the given list of functions. Returns an iterator of logic_network objects, so the caller may iterate on this method to synthesize all networks that satisfy the specifications given by the clocking scheme and the functions.

Parameters:
  • functions – A list of lists of binary integers. Every list is a function to be synthesized. Every list is to be computed by the resulting logic network and corresponds to one of its outputs. The n-th list corresponds to the n-th logic network output.
  • verbosity – Parameter to view debugging output.
to_png(filename)

Creates a PNG of the graph underlying the clock scheme using Graphviz.