Circuit Graph - kyupy.circuit

Core module for handling non-hierarchical gate-level circuits.

The class Circuit is a container of nodes connected by lines. A node is an instance of class Node, and a line is an instance of class Line.

The data structures are designed to work together nicely with numpy arrays. For example, all the nodes and connections in the circuit graph have consecutive integer indices that can be used to access ndarrays with associated data. Circuit graphs also define an ordering of inputs, outputs and other nodes to easily process test vector data and alike.

class kyupy.circuit.Node(circuit, name, kind='__fork__')

A node is a named entity in a circuit (e.g. a gate, a standard cell, a named signal, or a fan-out point) that is connected to other nodes via lines.

The constructor automatically adds the new node to the given circuit.

circuit

The Circuit object the node is part of.

name

The name of the node.

Names must be unique among all forks and all cells in the circuit. However, a fork (kind is set to ‘__fork__’) and a cell with the same name may coexist.

kind

A string describing the type of the node.

Common types are the names from a standard cell library or general gate names like ‘AND’ or ‘NOR’. If kind is set to ‘__fork__’, it receives special treatment. A fork describes a named signal or a fan-out point in the circuit and not a physical cell like a gate. In the circuit, the namespaces of forks and cells are kept separate. While name must be unique among all forks and all cells, a fork can have the same name as a cell. The index, however, is unique among all nodes; a fork cannot have the same index as a cell.

index

A unique and consecutive integer index of the node within the circuit.

It can be used to associate additional data to a node n by allocating an array or list my_data of length len(n.circuit.nodes) and accessing it by my_data[n.index] or simply by my_data[n].

ins: GrowingList[Line]

A list of input connections (Line objects).

outs: GrowingList[Line]

A list of output connections (Line objects).

remove()

Removes the node from its circuit.

Lines may still reference the removed node. The user must connect such lines to other nodes or remove the lines from the circuit. To keep the indices consecutive, the node with the highest index within the circuit will be assigned the index of the removed node.

class kyupy.circuit.Line(circuit: Circuit, driver: Node | tuple[Node, None | int], reader: Node | tuple[Node, None | int])

A line is a directional 1:1 connection between two nodes.

It always connects an output of one driver node to an input of one reader node. If a signal fans out to multiple readers, a ‘__fork__’ node needs to be added.

The constructor automatically adds the new line to the given circuit and inserts references into the connection lists of connected nodes.

When adding a line, input and output pins can either be specified explicitly Line(circuit, (driver, 2), (reader, 0)), or implicitly Line(circuit, driver, reader). In the implicit case, the line will be connected to the first free pin of the node. Use the explicit case only if connections to specific pins are required. It may overwrite any previous line references in the connection list of the nodes.

circuit

The Circuit object the line is part of.

index

A unique and consecutive integer index of the line within the circuit.

It can be used to store additional data about the line l by allocating an array or list my_data of length len(l.circuit.lines) and accessing it by my_data[l.index] or simply by my_data[l].

driver: Node

The Node object that drives this line.

driver_pin

The output pin position of the driver node this line is connected to.

This is the position in the list Node.outs of the driving node this line referenced from: self.driver.outs[self.driver_pin] == self.

reader: Node

The Node object that reads this line.

reader_pin

The input pin position of the reader node this line is connected to.

This is the position in the list Node.ins of the reader node this line referenced from: self.reader.ins[self.reader_pin] == self.

remove()

Removes the line from its circuit and its referencing nodes.

To keep the indices consecutive, the line with the highest index within the circuit will be assigned the index of the removed line.

class kyupy.circuit.Circuit(name=None)

A Circuit is a container for interconnected nodes and lines.

It provides access to lines by index and to nodes by index and by name. Nodes come in two flavors: cells and forks (see Node.kind). The name spaces of cells and forks are kept separate.

The indices of nodes and lines are kept consecutive and unique. Whenever lines or nodes are removed from the circuit, the indices of some other lines or nodes may change to enforce consecutiveness.

A subset of nodes can be designated as primary input- or output-ports of the circuit. This is done by adding them to the io_nodes list.

name

The name of the circuit.

nodes: list[Node]

A list of all Node objects contained in the circuit.

The position of a node in this list equals its index self.nodes[42].index == 42. This list must not be changed directly. Use the Node constructor and Node.remove() to add and remove nodes.

lines: list[Line]

A list of all Line objects contained in the circuit.

The position of a line in this list equals its index self.lines[42].index == 42. This list must not be changed directly. Use the Line constructor and Line.remove() to add and remove lines.

io_nodes: list[Node]

A list of nodes that are designated as primary input- or output-ports.

Port-nodes are contained in nodes as well as io_nodes. The position of a node in the io_nodes list corresponds to positions of logic values in test vectors. The port direction is not stored explicitly. Usually, nodes in the io_nodes list without any lines in their Node.ins list are primary inputs, and all other nodes in the io_nodes list are regarded as primary outputs.

cells: dict[str, Node]

A dictionary to access cells by name.

This dictionary must not be changed directly. Use the Node constructor and Node.remove() to add and remove nodes.

forks: dict[str, Node]

A dictionary to access forks by name.

This dictionary must not be changed directly. Use the Node constructor and Node.remove() to add and remove nodes.

property s_nodes

A list of all primary I/Os as well as all flip-flops and latches in the circuit (in that order).

The s_nodes list defines the order of all ports and all sequential elements in the circuit. This list is constructed on-the-fly. If used in some inner toop, consider caching the list for better performance.

io_locs(prefix)

Returns the indices of primary I/Os that start with given name prefix.

The returned values are used to index into the io_nodes array. If only one I/O cell matches the given prefix, a single integer is returned. If a bus matches the given prefix, a sorted list of indices is returned. Busses are identified by integers in the cell names following the given prefix. Lists for bus indices are sorted from LSB (e.g. data[0]) to MSB (e.g. data[31]). If a prefix matches multiple different signals or busses, alphanumerically sorted lists of lists are returned. Therefore, higher-dimensional busses (e.g. data0[0], data0[1], ..., data1[0], data1[1], ...) are supported as well.

s_locs(prefix)

Returns the indices of I/Os and sequential elements that start with given name prefix.

The returned values are used to index into the s_nodes list. It works the same as io_locs. See there for more details.

property stats

A dictionary with the counts of all different elements in the circuit.

The dictionary contains the number of all different kinds of nodes, the number of lines, as well various sums like number of combinational gates, number of primary I/Os, number of sequential elements, and so on.

The count of regular cells use their Node.kind as key, other statistics use dunder-keys like: __comb__, __io__, __seq__, and so on.

eliminate_1to1_forks()

Removes all forks that drive only one node.

Such forks are inserted by parsers to annotate signal names. If this information is not needed, such forks can be removed and the two neighbors can be connected directly using one line. Forks that drive more than one node are not removed by this function.

This function may remove some nodes and some lines from the circuit. Therefore that indices of other nodes and lines may change to keep the indices consecutive. It may therefore invalidate external data for nodes and lines.

substitute(node, impl)

Replaces a given node with the given implementation circuit.

The given node will be removed, the implementation is copied in and the signal lines are connected appropriately. The number and arrangement of the input and output ports must match the pins of the replaced node.

This function tries to preserve node and line indices as much as possible. Usually, it only adds additional nodes and lines, preserving the order of all existing nodes and lines. If an implementation is empty, however, nodes and lines may get removed, changing indices and invalidating external data.

resolve_tlib_cells(tlib)

Substitute all technology library cells with kyupy native simulation primitives.

See substitute() for more detail.

copy()

Returns a deep copy of the circuit.

topological_order()

Generator function to iterate over all nodes in topological order.

Nodes without input lines and nodes whose Node.kind contains the substrings ‘dff’ or ‘latch’ are yielded first.

topological_line_order()

Generator function to iterate over all lines in topological order.

reversed_topological_order()

Generator function to iterate over all nodes in reversed topological order.

Nodes without output lines and nodes whose Node.kind contains the substrings ‘dff’ or ‘latch’ are yielded first.

fanin(origin_nodes)

Generator function to iterate over the fan-in cone of a given list of origin nodes.

Nodes are yielded in reversed topological order.

fanout(origin_nodes)

Generator function to iterate over the fan-out cone of a given list of origin nodes.

Nodes are yielded in topological order.