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 forcut_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.
-
uint32_t cut_size = {4u}
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 typenetwork_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 thecut_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
-
inline cut_set_t &cuts(uint32_t node_index)
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 directoryinclude/mockturtle/algorithms/cut_enumeration
.Required network functions:
is_constant
is_ci
size
get_node
node_to_index
foreach_node
foreach_fanin
compute
forkitty::dynamic_truth_table
(ifComputeTruth
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 thecut_size
parameter as incut_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 directoryinclude/mockturtle/algorithms/cut_enumeration
.Required network functions:
is_constant
is_ci
size
get_node
node_to_index
foreach_node
foreach_fanin
compute
forkitty::static_truth_table
(ifComputeTruth
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.