Cut enumeration

Header: mockturtle/algorithms/cut_enumeration.hpp

A cut of a Boolean network is a pair \((n,L)\), where \(n\) is a node, called root, and \(L\) is a set of nodes, called leaves, such that (i) each path from any primary input to \(n\) passes through at least one leaf and (ii) for each leaf \(l \in L\), there is at least one path from a primary input to \(n\) passing through \(l\) and not through any other leaf.

The function mockturtle::cut_enumeration() implements cut enumeration, which is an algorithm that computes all cuts of all nodes in a Boolean network. Since the number of cuts is very large, the number of enumerated cuts is bounded by a parameter \(l\) (cut_size) for the cut size and a parameter \(p\) (cut_limit) for the maximum number of cuts for each node. This technique is referred to as priority cuts as it selects the subset of all cuts with respect to some cost function, in our case the number of the cuts’ leaves. The returned cut sets are also irredundant and do not contain two cuts \((n, L_1)\) and \((n, L_2)\) such that \(L_1\) dominates \(L_2\), i.e., \(L_1 \subseteq L_2\).

The simplest way to enumerate cuts in some network ntk is by calling:

auto cuts = cut_enumeration( ntk );

ntk.foreach_node( [&]( auto node ) {
  std::cout << cuts.cuts( ntk.node_to_index( node ) ) << "\n";
} );

Parameters can be set to adjust the cut size and the number of maximum cuts for each node:

cut_enumeration_params ps;
ps.cut_size = 6;
ps.cut_limit = 8;

auto cuts = cut_enumeration( ntk, ps );

A template argument to cut_enumeration can enable truth table computation for each cut. The truth table for each cut can be retrieved from the return value for cut_enumeration. The following example enumerates all cuts and computes their truth tables. Afterwards, the truth table for each cut is printed. In the example, Ntk is the type of ntk.

auto cuts = cut_enumeration<Ntk, true>( ntk ); /* true enables truth table computation */
ntk.foreach_node( [&]( auto n ) {
  const auto index = ntk.node_to_index( n );
  for ( auto const& cut : cuts.cuts( index ) )
  {
    std::cout << "Cut " << *cut
              << " with truth table " << kitty::to_hex( cuts.truth_table( *cut ) )
              << "\n";
  }
} );

Parameters

struct cut_enumeration_params

Parameters for cut_enumeration.

The data structure cut_enumeration_params holds configurable parameters with default arguments for cut_enumeration.

Public Members

uint32_t cut_size = {4u}

Maximum number of leaves for a cut.

uint32_t cut_limit = {25u}

Maximum number of cuts for a node.

uint32_t fanin_limit = {10u}

Maximum number of fan-ins for a node.

bool minimize_truth_table = {false}

Prune cuts by removing don’t cares.

bool verbose = {false}

Be verbose.

bool very_verbose = {false}

Be very verbose.

Return value

template<typename Ntk, bool ComputeTruth, typename CutData>
struct network_cuts

Cut database for a network.

The function cut_enumeration returns an instance of type network_cuts which contains a cut database and can be queried to return all cuts of a node, or the function of a cut (if it was computed).

An instance of type network_cuts can only be constructed from the cut_enumeration algorithm.

Public Functions

inline cut_set_t &cuts(uint32_t node_index)

Returns the cut set of a node.

inline cut_set_t const &cuts(uint32_t node_index) const

Returns the cut set of a node.

template<bool enabled = ComputeTruth, typename = std::enable_if_t<std::is_same_v<Ntk, Ntk> && enabled>>
inline auto truth_table(cut_t const &cut) const

Returns the truth table of a cut.

inline auto total_tuples() const

Returns the total number of tuples that were tried to be merged.

inline auto total_cuts() const

Returns the total number of cuts in the database.

inline auto nodes_size() const

Returns the number of nodes for which cuts are computed.

inline uint32_t insert_truth_table(kitty::dynamic_truth_table const &tt)

Inserts a truth table into the truth table cache.

This message can be used when manually adding or modifying cuts from the cut sets.

Parameters:

tt – Truth table to add

Returns:

Literal id from the truth table store

Algorithm

template<typename Ntk, bool ComputeTruth, typename CutData>
network_cuts<Ntk, ComputeTruth, CutData> mockturtle::cut_enumeration(Ntk const &ntk, cut_enumeration_params const &ps, cut_enumeration_stats *pst)

Cut enumeration.

This function implements the cut enumeration algorithm. The algorithm traverses all nodes in topological order and computes a node’s cuts based on its fanins’ cuts. Dominated cuts are filtered and are not added to the cut set. For each node a unit cut is added to the end of each cut set.

The template parameter ComputeTruth controls whether truth tables should be computed for each cut. Computing truth tables slows down the execution time of the algorithm.

The number of computed cuts is controlled via the cut_limit parameter. To decide which cuts are collected in each node’s cut set, cuts are sorted. Unit cuts do not participate in the sorting and are always added to the end of each cut set.

The algorithm can be configured by specifying the template argument CutData which holds the application specific data assigned to each cut. Examples on how to specify custom cost functions for sorting cuts based on the application specific cut data can be found in the files contained in the directory include/mockturtle/algorithms/cut_enumeration.

Required network functions:

  • is_constant

  • is_ci

  • size

  • get_node

  • node_to_index

  • foreach_node

  • foreach_fanin

  • compute for kitty::dynamic_truth_table (if ComputeTruth is true)

Note

The implementation of this algorithm was heavily inspired buy cut enumeration implementations in ABC.

Warning

This algorithm expects the nodes in the network to be in topological order. If the network does not guarantee a topological order of nodes one can wrap the network parameter in a topo_view view.

Pre-defined cut types

Header: mockturtle/algorithms/cut_enumeration/gia_cut.hpp

struct cut_enumeration_gia_cut

Cut implementation based on ABC’s giaCut.c.

See giaCut.c in ABC’s repository.

Header: mockturtle/algorithms/cut_enumeration/mf_cut.hpp

struct cut_enumeration_mf_cut

Cut implementation based on ABC’s giaMf.c.

See giaMf.c in ABC’s repository.

Header: mockturtle/algorithms/cut_enumeration/cnf_cut.hpp

struct cut_enumeration_cnf_cut

Cut for CNF mapping applications.

This cut type uses the clause count in the CNF encoding of the cut function as cost function. It requires truth table computation during cut enumeration or LUT mapping in order to work.

Header: mockturtle/algorithms/cut_enumeration/spectr_cut.hpp

struct cut_enumeration_spectr_cut

Cut based on spectral properties.

This cut type uses the number of non-zero coefficients in the cut function as cost function. It requires truth table computation during cut enumeration or LUT mapping in order to work.

Header: mockturtle/algorithms/cut_enumeration/tech_map_cut.hpp

struct cut_enumeration_tech_map_cut

Cut implementation for technology mapping.

Header: mockturtle/algorithms/cut_enumeration/exact_map_cut.hpp

struct cut_enumeration_exact_map_cut

Cut implementation for graph mapping with a complete database.

Special-purpose implementations

template<typename Ntk, uint32_t NumVars, bool ComputeTruth, typename CutData>
fast_network_cuts<Ntk, NumVars, ComputeTruth, CutData> mockturtle::fast_cut_enumeration(Ntk const &ntk, cut_enumeration_params const &ps, cut_enumeration_stats *pst)

Fast cut enumeration.

This function implements the cut enumeration algorithm. The algorithm traverses all nodes in topological order and computes a node’s cuts based on its fanins’ cuts. Dominated cuts are filtered and are not added to the cut set. For each node a unit cut is added to the end of each cut set.

The template parameter ComputeTruth controls whether truth tables should be computed for each cut. Computing truth tables slows down the execution time of the algorithm.

The cut size is controlled using the template parameter NumVars instead of the cut_size parameter as in cut_enumeration.

Comparing to cut_enumeration, it uses static truth tables instead of dynamic truth tables to speed-up the truth table computation.

The number of computed cuts is controlled via the cut_limit parameter. To decide which cuts are collected in each node’s cut set, cuts are sorted. Unit cuts do not participate in the sorting and are always added to the end of each cut set.

The algorithm can be configured by specifying the template argument CutData which holds the application specific data assigned to each cut. Examples on how to specify custom cost functions for sorting cuts based on the application specific cut data can be found in the files contained in the directory include/mockturtle/algorithms/cut_enumeration.

Required network functions:

  • is_constant

  • is_ci

  • size

  • get_node

  • node_to_index

  • foreach_node

  • foreach_fanin

  • compute for kitty::static_truth_table (if ComputeTruth is true)

Note

The implementation of this algorithm was heavily inspired by cut enumeration implementations in ABC.

Warning

This algorithm expects the nodes in the network to be in topological order. If the network does not guarantee a topological order of nodes one can wrap the network parameter in a topo_view view.

template<typename Ntk>
std::optional<std::vector<std::vector<uint64_t>>> mockturtle::fast_small_cut_enumeration(Ntk const &ntk, const uint8_t cut_size = 4)

Cut enumeration.

This function implements a generic fast cut enumeration algorithm for graphs containing at most 64 nodes. It is generic as it supports graphs in which nodes can have variable fan-in. Speed and space-efficiency are achieved by representing cuts as 64-bit bit vectors, i.e. each bit represents whether or not a node is in a cut. Cut-set union and domination operations then transform into bitwise operations that can be performed in a few clock cycles each.

Like the larger cut_enumeration algorithm, this algorithm traverses all nodes in topological order and computes a node’s cuts based on its fanins’ cuts. Dominated cuts are filtered and are not added to the cut set. For each node a unit cut is added to the end of each cut set.

This function computes all cuts of the network (i.e. the number of generated cuts is not bounded). Though the number of cuts cannot be bounded, their size can be bound by passing a cut_size argument to the function.

Required network functions:

  • fanin_size

  • foreach_fanin

  • foreach_gate

  • foreach_ci

  • get_node

  • node_to_index

  • size

Note that this algorithm only works for graphs with at most 64 nodes. However, since we cannot know the size of a graph at compile-time, this function returns the results wrapped in an std::optional.

Warning

This algorithm expects the nodes in the network to be in topological order. If the network does not guarantee a topological order of nodes one can wrap the network parameter in a topo_view view.