Rewrite

Header: mockturtle/algorithms/rewrite.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 = ...;

/* rewrite */
mig_npn_resynthesis resyn{ true };
exact_library_params eps;
eps.np_classification = false;
exact_library<mig_network> exact_lib( resyn, eps );

It is possible to change the cost function of nodes in rewrite. 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;
exact_library_params eps;
eps.np_classification = false;
exact_library<xag_network> exact_lib( resyn, eps );
rewrite<decltype( Ntk ), decltype( exact_lib ), mc_cost>( ntk, exact_lib );

Rewrite supports also satisfiability don’t cares:

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

/* rewrite */
mig_npn_resynthesis resyn{ true };
exact_library_params eps;
eps.np_classification = false;
eps.compute_dc_classes = true;
exact_library<mig_network> exact_lib( resyn, eps );

/* rewrite */
rewrite_params ps;
ps.use_dont_cares = true;
rewrite( mig, exact_lib, ps );

Parameters and statistics

struct rewrite_params

Parameters for Rewrite.

The data structure rewrite_params holds configurable parameters with default arguments for rewrite.

Public Members

cut_enumeration_params cut_enumeration_ps = {}

Cut enumeration parameters.

bool preserve_depth = {false}

If true, candidates are only accepted if they do not increase logic depth.

bool allow_multiple_structures = {true}

Allow rewrite with multiple structures.

bool allow_zero_gain = {false}

Allow zero-gain substitutions.

bool use_dont_cares = {false}

Use satisfiability don’t cares for optimization.

uint32_t window_size = {8u}

Window size for don’t cares calculation.

bool verbose = {false}

Be verbose.

struct rewrite_stats

Statistics for rewrite.

The data structure rewrite_stats provides data collected by running rewrite.

Public Members

stopwatch::duration time_total = {0}

Total runtime.

uint32_t estimated_gain = {0}

Expected gain.

uint32_t candidates = {0}

Candidates.

Algorithm

template<class Ntk, class Library, class NodeCostFn = unit_cost<Ntk>>
void mockturtle::rewrite(Ntk &ntk, Library &&library, rewrite_params const &ps = {}, rewrite_stats *pst = nullptr, NodeCostFn const &cost_fn = {})

Boolean rewrite.

This algorithm rewrites enumerated cuts using new network structures from a database. The algorithm performs changes in-place and keeps the substituted structures dangling in the network.

Required network functions:

  • get_node

  • size

  • make_signal

  • foreach_gate

  • substitute_node

  • clear_visited

  • clear_values

  • fanout_size

  • set_value

  • foreach_node

Parameters:

  • ntk – Input network (will be changed in-place)

  • library – Exact library containing pre-computed structures

  • ps – Rewrite params

  • pst – Rewrite statistics

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

Rewriting functions

One can use resynthesis functions with a pre-computed database and process them using Exact library, see Resynthesis functions.