Cut rewriting

Header: mockturtle/algorithms/cut_rewriting.hpp

The following example shows how to rewrite an MIG using precomputed optimum networks. In this case the maximum number of variables for a node function is 4.

/* derive some MIG */
mig_network mig = ...;

/* node resynthesis */
mig_npn_resynthesis resyn;
cut_rewriting_params ps;
ps.cut_enumeration_ps.cut_size = 4;
mig = cut_rewriting( mig, resyn, ps );
mig = cleanup_dangling( mig );

It is possible to change the cost function of nodes in cut rewriting. Here is an example, in which the cost function only accounts for AND gates in a network, which corresponds to the multiplicative complexity of a function.

template<class Ntk>
struct mc_cost
{
  uint32_t operator()( Ntk const& ntk, node<Ntk> const& n ) const
  {
    return ntk.is_and( n ) ? 1 : 0;
  }
};

SomeResynthesisClass resyn;
ntk = cut_rewriting<SomeResynthesisClass, mc_cost>( ntk, resyn );

Parameters and statistics

struct cut_rewriting_params

Parameters for cut_rewriting.

The data structure cut_rewriting_params holds configurable parameters with default arguments for cut_rewriting.

Public Types

enum [anonymous]

Candidate selection strategy.

Values:

enumerator minimize_weight
enumerator greedy

Public Members

cut_enumeration_params cut_enumeration_ps = {}

Cut enumeration parameters.

bool allow_zero_gain = {false}

Allow zero-gain substitutions.

bool use_dont_cares = {false}

Use don’t cares for optimization.

enum mockturtle::cut_rewriting_params::[anonymous] candidate_selection_strategy = minimize_weight

Candidate selection strategy.

uint32_t min_cand_cut_size = {3u}

Minimum candidate cut size.

std::optional<uint32_t> min_cand_cut_size_override = {}

Minimum candidate cut size override (in conflict graph)

bool preserve_depth = {false}

If true, candidates are only accepted if they do not increase logic level of node.

bool progress = {false}

Show progress.

bool verbose = {false}

Be verbose.

bool very_verbose = {false}

Be very verbose.

struct cut_rewriting_stats

Statistics for cut_rewriting.

The data structure cut_rewriting_stats provides data collected by running cut_rewriting.

Public Members

stopwatch::duration time_total = {0}

Total runtime.

stopwatch::duration time_cuts = {0}

Runtime for cut enumeration.

stopwatch::duration time_rewriting = {0}

Accumulated runtime for rewriting.

stopwatch::duration time_mis = {0}

Runtime to find minimal independent set.

Algorithm

template<class Ntk, class RewritingFn, class NodeCostFn = unit_cost<Ntk>>
Ntk mockturtle::cut_rewriting(Ntk const &ntk, RewritingFn const &rewriting_fn = {}, cut_rewriting_params const &ps = {}, cut_rewriting_stats *pst = nullptr)

Cut rewriting algorithm.

This algorithm enumerates cut of a network and then tries to rewrite the cut in terms of gates of the same network. The rewritten structures are added to the network, and if they lead to area improvement, will be used as new parts of the logic.

The rewriting function must be of type NtkDest::signal(NtkDest&, kitty::dynamic_truth_table const&, LeavesIterator, LeavesIterator) where LeavesIterator can be dereferenced to a NtkDest::signal. The last two parameters compose an iterator pair where the distance matches the number of variables of the truth table that is passed as second parameter. There are some rewriting algorithms in the folder mockturtle/algorithms/node_resynthesis, since the resynthesis functions have the same signature.

In contrast to node resynthesis, cut rewriting uses the same type for the input and output network.

Parameters:

  • ntk – Network

  • rewriting_fn – Rewriting function

  • ps – Rewriting params

  • pst – Rewriting statistics

template<class Ntk, class RewritingFn, class NodeCostFn = unit_cost<Ntk>>
void mockturtle::cut_rewriting_with_compatibility_graph(Ntk &ntk, RewritingFn &&rewriting_fn, cut_rewriting_params const &ps = {}, cut_rewriting_stats *pst = nullptr, NodeCostFn const &cost_fn = {})

In-place cut rewriting algorithm with compatibility graph.

This algorithm enumerates cut of a network and then tries to rewrite the cut in terms of gates of the same network. The rewritten structures are added to the network, and if they lead to area improvement, will be used as new parts of the logic. The resulting network therefore has a lot of dangling nodes from unsuccessful candidates, which can be removed by calling cleanup_dangling after the rewriting algorithm.

The rewriting function must be of type NtkDest::signal(NtkDest&, kitty::dynamic_truth_table const&, LeavesIterator, LeavesIterator) where LeavesIterator can be dereferenced to a NtkDest::signal. The last two parameters compose an iterator pair where the distance matches the number of variables of the truth table that is passed as second parameter. There are some rewriting algorithms in the folder mockturtle/algorithms/node_resynthesis, since the resynthesis functions have the same signature.

In contrast to node resynthesis, cut rewriting uses the same type for the input and output network. Consequently, the algorithm does not return a new network but applies changes in-place to the input network.

Required network functions:

  • fanout_size

  • foreach_node

  • foreach_fanin

  • is_constant

  • is_pi

  • clear_values

  • incr_value

  • decr_value

  • set_value

  • node_to_index

  • index_to_node

  • substitute_node

  • make_signal

Parameters:

  • ntk – Network (will be modified)

  • rewriting_fn – Rewriting function

  • ps – Rewriting params

  • pst – Rewriting statistics

  • cost_fn – Node cost function (a functor with signature uint32_t(Ntk const&, node<Ntk> const&))

Rewriting functions

One can use resynthesis functions that can be passed to node_resynthesis, see Resynthesis functions.