Network Utils

Header: fiction/utils/network_utils.hpp

template<typename Ntk>
struct edge

Representation of an edge between two network nodes.

Template Parameters:

Ntk – mockturtle network type.

template<typename Ntk, typename Fn>
void fiction::foreach_edge(const Ntk &ntk, Fn &&fn)

Applies a function to all edges in a mockturtle network.

Template Parameters:

  • Ntk – mockturtle network type.

  • Fn – Unary function type that takes a mockturtle::edge<Ntk> object as parameter.

Parameters:

  • ntk – Network to iterate over.

  • fn – Function object to apply to each edge in ntk.

template<typename Ntk, typename Fn>
void fiction::foreach_outgoing_edge(const Ntk &ntk, const mockturtle::node<Ntk> &n, Fn &&fn)

Applies a function to all outgoing edges in a mockturtle network.

Template Parameters:

  • Ntk – mockturtle network type.

  • Fn – Unary function type that takes a mockturtle::edge<Ntk> object as parameter.

Parameters:

  • ntk – Network to iterate over.

  • n – Node of ntk whose outgoing edges are to be considered.

  • fn – Function object to apply to each outgoing edge of n in ntk.

template<typename Ntk, typename Fn>
void fiction::foreach_incoming_edge(const Ntk &ntk, const mockturtle::node<Ntk> &n, Fn &&fn)

Applies a function to all incoming edges in a mockturtle network.

Template Parameters:

  • Ntk – mockturtle network type.

  • Fn – Unary function type that takes a mockturtle::edge<Ntk> object as parameter.

Parameters:

  • ntk – Network to iterate over.

  • n – Node of ntk whose incoming edges are to be considered.

  • fn – Function object to apply to each incoming edge of n in ntk.

template<typename Ntk>
std::vector<mockturtle::node<Ntk>> fiction::fanouts(const Ntk &ntk, const mockturtle::node<Ntk> &n) noexcept

Returns a vector of all fanout nodes of some given network node.

Template Parameters:

Ntk – mockturtle network type.

Parameters:

  • ntk – Network in which the fanouts are to be gathered.

  • n – Node whose fanouts are desired.

Returns:

A vector of all outgoing nodes directly adjacent to n in ntk.

template<typename Ntk>
struct fanin_container

Container that stores fanins of a node in a network, including whether one of them is a constant.

Note that this container assumes that each node has a maximum of one constant fanin.

Template Parameters:

Ntk – mockturtle network type.

Public Members

std::vector<mockturtle::node<Ntk>> fanin_nodes = {}

A vector of all fanin nodes except for constants.

std::optional<bool> constant_fanin = {std::nullopt}

Has a value if a fanin node is constant. In that case, it represents the constant value.

template<typename Ntk>
fanin_container<Ntk> fiction::fanins(const Ntk &ntk, const mockturtle::node<Ntk> &n) noexcept

Returns a fanin container filled with all fanin nodes of some given network node.

Note that this function assumes that each node has a maximum of one constant fanin.

Template Parameters:

Ntk – mockturtle network type.

Parameters:

  • ntk – Network in which the fanins are to be gathered.

  • n – Node whose fanins are desired.

Returns:

A container of all incoming nodes directly adjacent to n in ntk.

template<typename Ntk>
uint32_t fiction::num_constant_fanins(const Ntk &ntk, const mockturtle::node<Ntk> &n) noexcept

Computes the number of constant fanin nodes of some network node n.

Template Parameters:

Ntk – mockturtle network type.

Parameters:

  • ntk – Network in which the constant fanins are to be counted.

  • n – Node whose constant fanins are to be counted.

Returns:

Number of constant fanins to n in ntk.

class high_degree_fanin_exception : public std::invalid_argument

Exception class that can be thrown if some network exceeds a legal number of fanins.

template<typename Ntk>
bool fiction::has_high_degree_fanin_nodes(const Ntk &ntk, const uint32_t threshold = 2) noexcept

Checks if a given network exceeds a given fanin threshold in any of its nodes.

Template Parameters:

Ntk – mockturtle network type.

Parameters:

  • ntk – Network to check.

  • threshold – Maximum number of legal fanins.

Returns:

true iff any node in ntk exceeds threshold fanins.

template<typename Ntk>
struct fanin_edge_container

Container that stores fanin edges of a node in a network, including whether one of them is a constant.

Template Parameters:

Ntk – mockturtle network type.

Public Members

std::vector<mockturtle::edge<Ntk>> fanin_edges = {}

A vector of all fanin edges excluding for constants.

template<typename Ntk>
fanin_edge_container<Ntk> fiction::fanin_edges(const Ntk &ntk, const mockturtle::node<Ntk> &n) noexcept

Returns a fanin edge container filled with all fanin edges (fanin, node) of some given network node.

Template Parameters:

Ntk – mockturtle network type.

Parameters:

  • ntk – Network in which the fanin edges are to be gathered.

  • n – Node whose fanins are desired.

Returns:

A container of all incoming edges (fanin, n) in ntk.

template<typename Ntk>
bool fiction::has_incoming_primary_input(const Ntk &ntk, const mockturtle::node<Ntk> &n) noexcept

Checks if a given node in a given network has fanins that are primary inputs.

Template Parameters:

Ntk – mockturtle network type.

Parameters:

  • ntk – Network to check in.

  • n – Node to check.

Returns:

true iff any of n’s fanins are primary inputs.

template<typename Ntk>
std::vector<edge_path<Ntk>> fiction::all_incoming_edge_paths(const Ntk &ntk, const mockturtle::node<Ntk> &n) noexcept

Returns a vector of all possible paths to reach the given node from the primary inputs within the given network.

Each node without predecessors is considered a terminal and a path is defined as a sequence of edges.

Parameters:

n – Node whose paths are desired.

Returns:

A vector of all possible edge paths leading from terminals to v.

template<typename Ntk>
std::vector<uint32_t> fiction::inverse_levels(const Ntk &ntk) noexcept

A clumsy implementation that returns the inverse level of each node in a given network. Its behavior is similar to mockturtle::depth_view but starting from the primary outputs instead of the primary inputs. An implementation along the lines of inv_depth_view would be a lot more sophisticated and desirable, but this quick hack does the job well so far. If anyone wants to build an inv_depth_view, please be my guest.

Template Parameters:

Ntk – mockturtle network type.

Parameters:

ntk – The network whose inverse levels are desired.

Returns:

A vector of inverse levels for each node where ntk.node_to_index(n) is the position where n’s inverse level is stored.

Truth Table Utils

Header: fiction/utils/truth_table_utils.hpp

inline kitty::dynamic_truth_table fiction::create_id_tt() noexcept

Creates and returns a truth table that implements the identity function in one variable.

Returns:

Identity function in one variable.

inline kitty::dynamic_truth_table fiction::create_not_tt() noexcept

Creates and returns a truth table that implements the negation in one variable.

Returns:

Negation in one variable.

inline kitty::dynamic_truth_table fiction::create_and_tt() noexcept

Creates and returns a truth table that implements the conjunction in two variables.

Returns:

Conjunction in two variables.

inline kitty::dynamic_truth_table fiction::create_or_tt() noexcept

Creates and returns a truth table that implements the disjunction in two variables.

Returns:

Disjunction in two variables.

inline kitty::dynamic_truth_table fiction::create_nand_tt() noexcept

Creates and returns a truth table that implements the negated conjunction in two variables.

Returns:

Negated conjunction in two variables.

inline kitty::dynamic_truth_table fiction::create_nor_tt() noexcept

Creates and returns a truth table that implements the negated disjunction in two variables.

Returns:

Negated disjunction in two variables.

inline kitty::dynamic_truth_table fiction::create_xor_tt() noexcept

Creates and returns a truth table that implements the exclusive disjunction in two variables.

Returns:

Exclusive disjunction in two variables.

inline kitty::dynamic_truth_table fiction::create_xnor_tt() noexcept

Creates and returns a truth table that implements the negated exclusive disjunction in two variables.

Returns:

Negated exclusive disjunction in two variables.

inline kitty::dynamic_truth_table fiction::create_maj_tt() noexcept

Creates and returns a truth table that implements the majority function in three variables.

Returns:

Majority function in three variables.

inline std::vector<kitty::dynamic_truth_table> fiction::create_double_wire_tt() noexcept

Creates and returns a vector of truth tables for a double wire multi-output function.

This function generates a vector of truth tables, each representing one of the outputs of a double wire multi-output function in two variables. The function returns a vector containing two truth tables.

Returns:

Vector of truth tables, each representing an output of the double wire function.

inline std::vector<kitty::dynamic_truth_table> fiction::create_crossing_wire_tt() noexcept

Creates and returns a vector of truth tables for a crossing wire multi-output function.

This function generates a vector of truth tables, each representing one of the outputs of a crossing wire multi-output function in two variables. The function returns a vector containing two truth tables.

Returns:

Vector of truth tables, each representing an output of the crossing wire function.

inline std::vector<kitty::dynamic_truth_table> fiction::create_fan_out_tt() noexcept

Creates and returns a vector of truth tables for a multi-output function with two variables.

This function generates a vector of truth tables, each representing one of the outputs of a multi-output function in two variables.

Returns:

Vector of truth tables, each representing an output of the identity function.

inline std::vector<kitty::dynamic_truth_table> fiction::create_half_adder_tt() noexcept

Creates and returns a vector of truth tables for a half adder multi-output function.

This function generates a vector of truth tables, each representing one of the outputs of a half adder multi-output function in two variables. The function returns a vector containing two truth tables.

Returns:

Vector of truth tables, each representing an output of the half adder function.

Layout Utils

Header: fiction/utils/layout_utils.hpp

template<typename Lyt>
uint8_t fiction::num_adjacent_coordinates(const Lyt &lyt, const coordinate<Lyt> &c) noexcept

Returns the number of adjacent coordinates of a given one. This is not a constant value because c could be located at a layout border.

Template Parameters:

Lyt – Layout type.

Parameters:

  • lyt – Layout.

  • c – Coordinate whose number of adjacencies are required.

Returns:

Number of c’s adjacent coordinates.

template<uint16_t GateSizeX, uint16_t GateSizeY, typename GateLyt, typename CellLyt>
cell<CellLyt> fiction::relative_to_absolute_cell_position(const GateLyt &gate_lyt, const tile<GateLyt> &t, const cell<CellLyt> &relative_c) noexcept

Converts a relative cell position within a tile to an absolute cell position within a layout. To compute the absolute position, the layout topology is taken into account.

Template Parameters:

  • GateSizeX – Horizontal tile size.

  • GateSizeY – Vertical tile size.

  • GateLyt – Gate-level layout type.

  • CellLyt – Cell-level layout type.

Parameters:

  • gate_lyt – The gate-level layout whose tiles are to be considered.

  • t – Tile within gate_lyt.

  • relative_c – Relative cell position within t.

Returns:

Absolute cell position in a layout.

template<typename Lyt>
coordinate<Lyt> fiction::port_direction_to_coordinate(const Lyt &lyt, const coordinate<Lyt> &c, const port_direction &port) noexcept

Port directions address coordinates relative to each other by specifying cardinal directions. This function converts such a relative direction to an absolute coordinate when given a layout and a coordinate therein to consider. That is, when presented with, e.g., a NORTH_EAST direction, it will return the coordinate that is to the NORTH_EAST of the given coordinate c in the layout lyt.

Template Parameters:

Lyt – Coordinate layout type.

Parameters:

  • lyt – Coordinate layout.

  • c – Coordinate to consider.

  • port – Port direction.

Returns:

Absolute coordinate specified by a coordinate c in layout lyt and a port direction.

template<typename Lyt>
Lyt fiction::normalize_layout_coordinates(const Lyt &lyt) noexcept

A new layout is constructed and returned that is equivalent to the given cell-level layout. However, its coordinates are normalized, i.e., start at (0, 0) and are all positive. To this end, all existing coordinates are shifted by an x and y offset.

Template Parameters:

Lyt – Cell-level layout type.

Parameters:

lyt – The layout which is to be normalized.

Returns:

New normalized equivalent layout.

template<typename LytSrc>
auto fiction::convert_to_siqad_coordinates(const LytSrc &lyt) noexcept

Converts the coordinates of a given cell-level layout (cds and defect surface can be layered on top) to SiQAD coordinates. A new equivalent layout based on SiQAD coordinates is returned.

Template Parameters:

Lyt – Cell-level layout type based on fiction coordinates, e.g., offset::ucoord_t or cube::coord_t.

Parameters:

lyt – The layout that is to be converted to a new layout based on SiQAD coordinates.

Returns:

A new equivalent layout based on SiQAD coordinates.

template<typename LytDest, typename LytSrc>
LytDest fiction::convert_to_fiction_coordinates(const LytSrc &lyt) noexcept

Converts the coordinates of a given SiDB cell-level layout (cds and defect surface can be layered on top) to alternative coordinates, such as offset::ucoord_t or cube::coord_t. Returns a new layout equivalent to the original layout but based on the specified coordinate system.

Template Parameters:

  • LytDest – Source SiDB cell-level layout type.

  • LytSrc – Target SiDB cell-level layout type.

Parameters:

lyt – The layout that is to be converted to a new layout based on fiction coordinates.

Returns:

A new equivalent layout based on fiction coordinates.

template<typename CoordinateType>
CoordinateType fiction::random_coordinate(CoordinateType coordinate1, CoordinateType coordinate2) noexcept

Generates a random coordinate within the region spanned by two given coordinates. The two given coordinates form the top left corner and the bottom right corner of the spanned region.

Template Parameters:

CoordinateType – The coordinate implementation to be used.

Parameters:

  • coordinate1 – Top left Coordinate.

  • coordinate2 – Bottom right Coordinate (coordinate order is not important, automatically swapped if necessary).

Returns:

Randomly generated coordinate.

template<typename CoordinateType>
inline std::vector<CoordinateType> fiction::all_coordinates_in_spanned_area(const CoordinateType &cell_nw, const CoordinateType &cell_se) noexcept

Generates a vector of all coordinates within an area spanned by two coordinates.

This function calculates and returns a vector of all coordinates that span the area between the northwest (cell_nw) and southeast (cell_se) cells, inclusive. The cells are generated in a top-down, left-to-right fashion within the specified area.

Template Parameters:

CoordinateType – Coordinate Type.

Parameters:

  • cell_nw – The northwest cell defining the starting point of the area.

  • cell_se – The southeast cell defining the ending point of the area.

Returns:

A vector containing all cells within the specified area.

Placement Utils

Header: fiction/utils/placement_utils.hpp

template<typename Lyt, typename Ntk>
mockturtle::node_map<mockturtle::node<Lyt>, Ntk> fiction::reserve_input_nodes(Lyt &lyt, const Ntk &ntk) noexcept

Reserve primary input nodes in a layout in the same order as they appear in a network. This is a useful function to call first when a layout is to be created from a network. The primary input nodes then exist in the layout, but are not placed anywhere and also do not have names. They are just registered to preserve their order.

This function can be seen as an equivalent to mockturtle::initialize_copy_network, but for layouts.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Ntk – Logic network type.

Parameters:

  • lyt – Gate-level layout where primary input nodes are to be reserved.

  • ntk – Network whose primary inputs are to be reserved in lyt.

Returns:

A mockturtle::node_map that maps from network nodes to layout nodes to be able to address the created nodes.

template<typename Lyt, typename Ntk>
mockturtle::signal<Lyt> fiction::place(Lyt &lyt, const tile<Lyt> &t, const Ntk &ntk, const mockturtle::node<Ntk> &n) noexcept

Place 0-input gates.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Ntk – Logic network type.

Parameters:

  • lyt – Gate-level layout in which to place a 0-input gate.

  • t – Tile in lyt to place the gate onto.

  • ntk – Network whose node is to be placed.

  • n – Node in ntk to place onto t in lyt.

Returns:

Signal pointing to the placed gate in lyt.

template<typename Lyt, typename Ntk>
mockturtle::signal<Lyt> fiction::place(Lyt &lyt, const tile<Lyt> &t, const Ntk &ntk, const mockturtle::node<Ntk> &n, const mockturtle::signal<Lyt> &a) noexcept

Place 1-input gates.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Ntk – Logic network type.

Parameters:

  • lyt – Gate-level layout in which to place a 1-input gate.

  • t – Tile in lyt to place the gate onto.

  • ntk – Network whose node is to be placed.

  • n – Node in ntk to place onto t in lyt.

  • a – Incoming signal to the newly placed gate in lyt.

Returns:

Signal pointing to the placed gate in lyt.

template<typename Lyt, typename Ntk>
mockturtle::signal<Lyt> fiction::place(Lyt &lyt, const tile<Lyt> &t, const Ntk &ntk, const mockturtle::node<Ntk> &n, const mockturtle::signal<Lyt> &a, const mockturtle::signal<Lyt> &b, const std::optional<bool> &c = std::nullopt) noexcept

Place 2-input gates.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Ntk – Logic network type.

Parameters:

  • lyt – Gate-level layout in which to place a 2-input gate.

  • t – Tile in lyt to place the gate onto.

  • ntk – Network whose node is to be placed.

  • n – Node in ntk to place onto t in lyt.

  • a – First incoming signal to the newly placed gate in lyt.

  • b – Second incoming signal to the newly placed gate in lyt.

  • c – Third optional incoming constant value signal to the newly placed gate in lyt. Might change the gate function when set, e.g., from a MAJ to an AND if c == false.

Returns:

Signal pointing to the placed gate in lyt.

template<typename Lyt, typename Ntk>
mockturtle::signal<Lyt> fiction::place(Lyt &lyt, const tile<Lyt> &t, const Ntk &ntk, const mockturtle::node<Ntk> &n, const mockturtle::signal<Lyt> &a, const mockturtle::signal<Lyt> &b, const mockturtle::signal<Lyt> &c) noexcept

Place 3-input gates.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Ntk – Logic network type.

Parameters:

  • lyt – Gate-level layout in which to place a 3-input gate.

  • t – Tile in lyt to place the gate onto.

  • ntk – Network whose node is to be placed.

  • n – Node in ntk to place onto t in lyt.

  • a – First incoming signal to the newly placed gate in lyt.

  • b – Second incoming signal to the newly placed gate in lyt.

  • c – Third incoming signal to the newly placed gate in lyt.

Returns:

Signal pointing to the placed gate in lyt.

template<typename Lyt, typename Ntk>
mockturtle::signal<Lyt> fiction::place(Lyt &lyt, const tile<Lyt> &t, const Ntk &ntk, const mockturtle::node<Ntk> &n, const mockturtle::node_map<mockturtle::signal<Lyt>, Ntk> &node2pos) noexcept

Place any gate from a network. This function automatically identifies the arity of the passed node and fetches its incoming signals from the given network and a provided mockturtle::node_map. This function does not update the mockturtle::node_map.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Ntk – Logic network type.

Parameters:

  • lyt – Gate-level layout in which to place any gate.

  • t – Tile in lyt to place the gate onto.

  • ntk – Network whose node is to be placed.

  • n – Node in ntk to place onto t in lyt.

  • node2pos – Mapping from network nodes to layout signals, i.e., a pointer to their position in the layout. The map is used to fetch location of the fanins. The mockturtle::node_map is not updated by this function.

Returns:

Signal to the newly placed gate in lyt.

template<typename Lyt, typename Ntk, uint16_t fanout_size = 2>
struct branching_signal_container

A container class to help identify layout locations of branching nodes like fanouts. When a node from a network is to placed in a layout, fetching the node’s fanins and looking for their locations in the layout does not work properly when branching nodes like fanouts are involved that got extended by wire nodes. This container solves that issue.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Ntk – Logic network type.

  • fanout_size – Maximum fanout size possible in the layout and/or the network.

Public Functions

inline mockturtle::signal<Lyt> operator[](const mockturtle::node<Ntk> &n) const

Accesses the branching container to find the location of a given node n. Returns the signal to that location if it was already stored or the default signal, otherwise.

Parameters:

n – Node whose branching position is desired.

Returns:

Signal to n’s layout location or the default signal if it wasn’t found.

inline void update_branch(const mockturtle::node<Ntk> &ntk_node, const mockturtle::signal<Lyt> &lyt_signal)

Updates the given node’s branch by another layout signal, thereby, creating a new branch or updating the position of an existing one, e.g., if further wire segments were moving the head of the branch.

Parameters:

  • ntk_node – Node whose branch is to be updated.

  • lyt_signal – New signal pointing to the end of the branch.

struct branching_signal

Branch type.

template<typename Lyt, typename Ntk, uint16_t fanout_size = 2>
mockturtle::signal<Lyt> fiction::place(Lyt &lyt, const tile<Lyt> &t, const Ntk &ntk, const mockturtle::node<Ntk> &n, const mockturtle::node_map<branching_signal_container<Lyt, Ntk, fanout_size>, Ntk> &node2pos) noexcept

Place any gate from a network. This function automatically identifies the arity of the passed node and fetches its incoming signals from the given network and a provided branching_signal_container mockturtle::node_map. This function does not update the mockturtle::node_map.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Ntk – Logic network type.

Parameters:

  • lyt – Gate-level layout in which to place any gate.

  • t – Tile in lyt to place the gate onto.

  • ntk – Network whose node is to be placed.

  • n – Node in ntk to place onto t in lyt.

  • node2pos – Mapping from network nodes to layout signals, i.e., a pointer to their position in the layout via branches. The map is used to fetch location of the fanins. The mockturtle::node_map is not updated by this function.

Returns:

Signal to the newly placed gate in lyt.

Routing Utils

Header: fiction/utils/routing_utils.hpp

template<typename Lyt>
struct routing_objective

Routing objectives are source-target pairs.

Template Parameters:

Lyt – Layout type whose coordinates are to be used.

Public Functions

template<typename OtherLyt>
inline bool operator==(const routing_objective<OtherLyt> &other) const noexcept

Equality operator.

Template Parameters:

OtherLyt – Type of other layout.

Parameters:

other – Routing objective to compare to.

Returns:

true iff the given objective is equal to this one.

template<typename Lyt>
class layout_coordinate_path : public std::vector<coordinate<Lyt>>

A path in a layout defined as an ordered sequence of coordinates.

Template Parameters:

Lyt – Coordinate layout type.

template<typename Path>
class path_collection : public std::vector<Path>

An ordered collection of multiple paths in a layout.

Template Parameters:

Path – Path type.

template<typename Path>
class path_set : public std::set<Path>

A set of multiple paths in a layout.

Template Parameters:

Path – Path type.

template<typename Lyt>
bool fiction::is_crossable_wire(const Lyt &lyt, const coordinate<Lyt> &src, const coordinate<Lyt> &successor) noexcept

Checks whether a given coordinate successor hosts a crossable wire when coming from coordinate src in a given layout. A wire is said to be crossable if a potential cross-over would not result in running along the same information flow direction. For example, a wire segment hosted by successor that is horizontal and runs from west to east is crossable by a wire segment coming from src that is vertical and runs from north to south. However, if the wire segment coming from src were also horizontal and ran from west to east, the cross-over would be prohibited.

@Note This function can be called on layout types other than gate-level layouts, but will then always return false. This is helpful for general routing in, e.g., clocked layouts.

Template Parameters:

Lyt – Layout type.

Parameters:

  • lyt – The layout.

  • src – Source coordinate in lyt.

  • successor – Successor coordinate in lyt reachable from src.

Returns:

true iff successor hosts a wire that is crossable from src.

template<typename Lyt, typename Path>
void fiction::route_path(Lyt &lyt, const Path &path) noexcept

Establishes a wire routing along the given path in the given layout. To this end, the given path’s source and target coordinates are assumed to be populated by other gates or wires that the new path shall connect to.

If path contains a tile that is allocated already, it will instead switch to the crossing layer. If path contains exactly source and target, no wires are created, but the source and target are connected.

Template Parameters:

  • Lyt – Gate-level layout type.

  • Path – Path type.

Parameters:

  • lyt – Gate-level layout in which a wire path is to be established.

  • path – Path to route wires along.

template<typename Lyt>
std::vector<routing_objective<Lyt>> fiction::extract_routing_objectives(const Lyt &lyt) noexcept

Extracts all routing objectives from the given layout. To this end, all routing paths in the layout are traversed, starting at each PI. Whenever the next regular node (non-IO, non-constant, non-wire) is encountered, this connection is added to the list of all objectives.

Example: Let a layout have connections from (0,0) to (2,3) via a cascade of wires and a direct connection from (2,2) to (2,3). The list of routing objectives extracted from that layout would contain {(0,0), (2,3)} and {(2,2), (2,3)}.

In other words, if all wires were removed from the layout and all connections ripped-up, an equivalent layout could be recreated from the list of routing objectives.

Template Parameters:

Lyt – Gate-level layout type.

Parameters:

lyt – Layout whose routing objectives are to be extracted.

Returns:

List of all routing objectives in the given layout.

template<typename Lyt>
void fiction::clear_routing(Lyt &lyt) noexcept

Removes the entire wire routing from the passed layout. This involves deleting all wire segments that have been placed on any tile as well as removing stored connections (children pointers) from all gates.

Template Parameters:

Lyt – Gate-level Layout type.

Parameters:

lyt – The layout whose routing is to be deleted.

Name Utils

Header: fiction/utils/name_utils.hpp

template<typename NtkOrLyt>
std::string fiction::get_name(const NtkOrLyt &ntk_or_lyt) noexcept

Helper function to conveniently fetch the name from a layout or network as they use different function names for the same purpose.

Template Parameters:

NtkOrLyt – Network or layout type.

Parameters:

ntk_or_lyt – Network or layout object.

Returns:

Name of given network or layout.

template<typename NtkOrLyt>
void fiction::set_name(NtkOrLyt &ntk_or_lyt, const std::string_view &name) noexcept

Helper function to conveniently assign a name to a layout or network as they use different function names for the same purpose.

Template Parameters:

NtkOrLyt – Network or layout type.

Parameters:

  • ntk_or_lyt – Network or layout object.

  • name – Name to assign to given network or layout.

template<typename NtkOrLytSrc, typename NtkOrLytDest>
void fiction::restore_network_name(const NtkOrLytSrc &ntk_or_lyt_src, NtkOrLytDest &ntk_or_lyt_dest) noexcept

Helper function to conveniently assign the name of a source network or layout to a target network or layout as they use different function names for the same purpose. This function comes in handy when networks are translated or layouts are being created from networks that are supposed to have the same name.

Template Parameters:

  • NtkOrLytSrc – Source network or layout type.

  • NtkOrLytDest – Target network or layout type.

Parameters:

  • ntk_or_lyt_src – Source network or layout whose name is to be assigned to ntk_or_lyt_dest.

  • ntk_or_lyt_dest – Target network or layout that is to be assigned ntk_or_lyt_src’s name.

template<typename NtkSrc, typename NtkDest>
void fiction::restore_input_names(const NtkSrc &ntk_src, NtkDest &ntk_dest) noexcept

Assigns input names from one network to another. Matching inputs are identified by their index. Since gate-level layout’s are network types as well, this function naturally works for them, too.

Template Parameters:

  • NtkSrc – Source network type.

  • NtkDest – Target network type.

Parameters:

  • ntk_src – Source logic network whose input names are to be transferred to ntk_dest.

  • ntk_dest – Target logic network whose inputs are to be assigned ntk_src’s names.

template<typename NtkSrc, typename NtkDest>
void fiction::restore_output_names(const NtkSrc &ntk_src, NtkDest &ntk_dest) noexcept

Assigns output names from one network to another. Matching outputs are identified by their order. Since gate-level layout’s are network types as well, this function naturally works for them, too.

Template Parameters:

  • NtkSrc – Source network type.

  • NtkDest – Target network type.

Parameters:

  • ntk_src – Source logic network whose output names are to be transferred to ntk_dest.

  • ntk_dest – Target logic network whose outputs are to be assigned ntk_src’s names.

template<typename NtkSrc, typename NtkDest>
void fiction::restore_signal_names(const NtkSrc &ntk_src, NtkDest &ntk_dest, const mockturtle::node_map<mockturtle::signal<NtkDest>, NtkSrc> &old2new) noexcept

Assigns all signal names from one network to another. For this purpose, a mapping between signals is needed in terms of a mockturtle::node_map. Since gate-level layout’s are network types as well, this function naturally works for them, too.

Template Parameters:

  • NtkSrc – Source network type.

  • NtkDest – Target network type.

Parameters:

  • ntk_src – Source logic network whose signal names are to be transferred to ntk_dest.

  • ntk_dest – Target logic network whose signal names are to be assigned ntk_src’s names.

  • old2new – Mapping of signals from ntk_src to ntk_dest.

template<typename NtkSrc, typename NtkDest, uint16_t fanout_size = 2>
void fiction::restore_signal_names(const NtkSrc &ntk_src, NtkDest &ntk_dest, const mockturtle::node_map<branching_signal_container<NtkDest, NtkSrc, fanout_size>, NtkSrc> &old2new) noexcept

Same as the other restore_signal_names function but this overload uses a mockturtle::node_map with a branching_signal_container that is specifically used for networks or layouts that allow branches to be distinct, e.g., by their position on the layout.

Template Parameters:

  • NtkSrc – Source network type.

  • NtkDest – Target network type.

  • fanout_size – Maximum fanout size in the network.

Parameters:

  • ntk_src – Source logic network whose signal names are to be transferred to ntk_dest.

  • ntk_dest – Target logic network whose signal names are to be assigned ntk_src’s names.

  • old2new – Mapping of signals from ntk_src to ntk_dest using a branching_signal_container.

template<typename NtkSrc, typename NtkDest>
void fiction::restore_names(const NtkSrc &ntk_src, NtkDest &ntk_dest) noexcept

Transfers all input and output names as well as the network/layout name from one network to another. This function calls restore_network_name, restore_input_names, and restore_output_names.

Template Parameters:

  • NtkSrc – Source network type.

  • NtkDest – Target network type.

Parameters:

  • ntk_src – Source logic network whose I/O names are to be transferred to ntk_dest.

  • ntk_dest – Target logic network whose I/O names are to be assigned ntk_src’s names.

template<typename NtkSrc, typename NtkDest, typename T>
void fiction::restore_names(const NtkSrc &ntk_src, NtkDest &ntk_dest, mockturtle::node_map<T, NtkSrc> &old2new) noexcept

Transfers all signal and output names as well as the network/layout name from one network to another. This function calls restore_network_name, restore_signal_names, and restore_output_names.

Template Parameters:

  • NtkSrc – Source network type.

  • NtkDest – Target network type.

  • T – Mapping type to identify signals by. Currently, mockturtle::signal<NtkDest> and branching_signal_container<NtkDest, NtkSrc, fanout_size> are supported.

Parameters:

  • ntk_src – Source logic network whose signal names are to be transferred to ntk_dest.

  • ntk_dest – Target logic network whose signal names are to be assigned ntk_src’s names.

  • old2new – Mapping of signals from ntk_src to ntk_dest using a signal identifier.

Array Utils

Header: fiction/utils/array_utils.hpp

template<std::size_t N, typename T>
constexpr auto fiction::create_array(const T &value)

Creates an array of size N and initializes its fields with value of type T at compile time.

Template Parameters:

  • N – Array size.

  • T – Type of array.

Parameters:

value – Initial value to each field.

Returns:

An object of type std::array<T, N> that is initialized with N copies of value.

template<typename ElementType, typename T, std::size_t N>
constexpr auto fiction::convert_array(const std::array<T, N> &a)

Converts an array of size N and type T to an array of size N and type ElementType by applying static_cast at compile time.

Template Parameters:

  • ElementType – New type of each element in the returned array.

  • T – Element type of the input array.

  • N – Size of both the input and the output array.

Parameters:

a – The array to be converted.

Returns:

An object of type std::array<ElementType, N> that was created by casting each element in a to ElementType.

template<typename ElementType, typename T, std::size_t N, std::size_t M>
constexpr auto fiction::convert_array_of_arrays(const std::array<std::array<T, M>, N> &a)

Same as convert_array but for 2D arrays.

Template Parameters:

  • ElementType – New type of each element in the returned array.

  • T – Element type of the input array.

  • N – Outer size of both the input and the output array.

  • M – Inner size of both the input and the output array.

Parameters:

a – The array to be converted.

Returns:

An object of type std::array<std::array<ElementType, M>, N> that was created by casting each element in a to ElementType using static_cast.

STL Extensions

Header: fiction/utils/stl_utils.hpp

template<class InputIt, class ForwardIt>
InputIt fiction::find_first_two_of(InputIt first, InputIt last, ForwardIt s_first, ForwardIt s_last) noexcept

A derivative of std::find_first_of that uses the example implementation given at https://en.cppreference.com/w/cpp/algorithm/find_first_of.

This version searches the range [first, last) for any two consecutive elements of the elements in the range [s_first, s_last), i.e., for a 2-element sub-sequence shared between the ranges.

Example: Let two ranges be [0, 1, 1, 2, 3, 3] and [1, 2, 3, 3]. A call to find_first_two_of would return an iterator to index 2, i.e., the second 1 in the first list, because the 2-element sub-sequence [1,2] is shared between the two ranges.

Template Parameters:

  • InputIt – must meet the requirements of LegacyInputIterator.

  • ForwardIt – must meet the requirements of LegacyForwardIterator.

Parameters:

  • first – Begin of the range to examine.

  • last – End of the range to examine.

  • s_first – Begin of the range to search for.

  • s_last – End of the range to search for.

Returns:

Iterator in the range [first, last) to the first position of the first 2-element sub-sequence shared between the two ranges, or last if no such shared sub-sequence exists.

template<class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>>
class searchable_priority_queue : public std::priority_queue<T, std::vector<T>, std::less<typename Container::value_type>>

An extension of std::priority_queue that allows searching the underlying container. The implementation is based on https://stackoverflow.com/questions/16749723/how-i-can-find-value-in-priority-queue.

Template Parameters:

  • T – The type of the stored elements.

  • Container – The type of the underlying container.

  • Compare – A Compare type providing a strict weak ordering.

Execution Policy Macros

Header: fiction/utils/execution_utils.hpp

Handling parallel STL algorithms is a bit cumbersome due to their platform dependence. The following macros are provided to simplify the usage of parallel STL algorithms while CMake and some pre-processor magic take care of all the boilerplate.

One can use the following macros to specify the execution policy for parallel STL algorithms in a (mostly) platform-independent way:

std::for_each(FICTION_EXECUTION_POLICY_PAR v.begin(), v.end(), lambda);
//                                        ^ note the missing comma

If parallelism or execution policies are not available, this will expand to:

std::for_each(v.begin(), v.end(), lambda);

Note

Only include this header and do not include <execution> directly. This header will include <execution> if available and will define the macros accordingly.

FICTION_EXECUTION_POLICY_SEQ

Sequential execution policy for STL algorithms.

Note

This macro automatically detetcs whether the C++ library supports execution policies and whether the compiler is able to compile them. If not, the macro defaults to nothing.

FICTION_EXECUTION_POLICY_PAR

Parallel execution policy for STL algorithms.

Note

This macro automatically detects whether the C++ library supports execution policies and whether the compiler is able to compile them. If not, the macro defaults to nothing.

FICTION_EXECUTION_POLICY_PAR_UNSEQ

Parallel unsequenced execution policy for STL algorithms.

Note

This macro automatically detects whether the C++ library supports execution policies and whether the compiler is able to compile them. If not, the macro defaults to nothing.

Ranges

Header: fiction/utils/range.hpp

template<typename I>
struct range_t

Defines a range type utilizing iterators. It implements begin() and end() as well as cbegin() and cend() as member functions to work for range based for-loops.

Template Parameters:

Iterator – type for which the range should be created.

Public Functions

inline explicit constexpr range_t(std::pair<I, I> &&range)

Standard constructor with forward reference.

Parameters:

range – Begin and end iterator pair.

inline constexpr I begin() const

Returns the iterator pointing to the begin of the represented range.

Returns:

Begin iterator.

inline constexpr I end() const

Returns the iterator pointing to the end of the represented range.

Returns:

End iterator.

inline constexpr I cbegin() const

Returns a const iterator pointing to the begin of the represented range.

Returns:

const begin iterator.

inline constexpr I cend() const

Returns a const iterator pointing to the end of the represented range.

Returns:

const end iterator.

Hashing

Header: fiction/utils/hash.hpp

This header defines implementations for std::hash for several data types.

template<typename T, typename ...Rest>
void fiction::hash_combine(std::size_t &seed, const T &v, const Rest&... rest)

A recursive hash_combine implementation from https://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x

Overrides the passed seed.

Template Parameters:

  • T – Type to hash.

  • Rest – Parameter pack.

Parameters:

  • seed – Hashing seed. This value is overridden with the hash value.

  • v – Value to hash next.

  • rest – Remaining values to hash.

Math Utils

Header: fiction/utils/math_utils.hpp

template<typename T>
T fiction::round_to_n_decimal_places(const T number, const uint64_t n) noexcept

Rounds a number to a specified number of decimal places.

Template Parameters:

T – The type of the number to round.

Parameters:

  • number – The number to round.

  • n – The number of decimal places to round to.

Returns:

The number rounded to n decimal places.

template<typename T>
T fiction::integral_abs(const T n) noexcept

Takes the absolute value of an integral number if it is signed, and otherwise computes the identity. This avoids a compiler warning when taking the absolute value of an unsigned number.

Template Parameters:

T – The type of the number to take the absolute value of. Must be integral.

Parameters:

n – The number to take the absolute value of.

Returns:

|n|.

inline uint64_t fiction::binomial_coefficient(uint64_t n, uint64_t k) noexcept

Calculates the binomial coefficient \(\binom{n}{k}\).

Parameters:

  • n – The total number of items.

  • k – The number of items to choose from n.

Returns:

The binomial coefficient \(\binom{n}{k}\).

inline std::vector<std::vector<std::size_t>> fiction::determine_all_combinations_of_distributing_k_entities_on_n_positions(const std::size_t k, const std::size_t n) noexcept

This function generates all possible combinations of distributing k entities onto n positions. Each combination is represented as a vector of indices, where each index indicates the position of an entity.

Parameters:

  • k – The number of entities to distribute.

  • n – The number of positions available for distribution.

Returns:

A vector of vectors representing all possible combinations of distributing k entities on n positions.

phmap

Header: fiction/utils/phmap_utils.hpp

template<typename K, typename V>
using fiction::locked_parallel_flat_hash_map = phmap::parallel_flat_hash_map<K, V, phmap::priv::hash_default_hash<K>, phmap::priv::hash_default_eq<K>, std::allocator<std::pair<const K, V>>, 4, std::mutex>

A parallel flat hash map with built-in mutexes. This enables thread-safe access to the map without the need to manually lock and unlock the map. Since the map uses internal buckets that can be accessed in parallel, this implementation is a lot faster than a regular hash map with a single mutex.