Node resynthesis

Header: mockturtle/algorithms/node_resynthesis.hpp

The following example shows how to resynthesize a k-LUT network derived from an AIG using LUT mapping into an MIG using precomputed optimum networks. In this case the maximum number of variables for a node function is 4.

/* derive some AIG */
aig_network aig = ...;

/* LUT mapping */
mapping_view<aig_network, true> mapped_aig{aig};
lut_mapping_params ps;
ps.cut_enumeration_ps.cut_size = 4;
lut_mapping<mapping_view<aig_network, true>, true>( mapped_aig, ps );

/* collapse into k-LUT network */
const auto klut = *collapse_mapped_network<klut_network>( mapped_aig );

/* node resynthesis */
mig_npn_resynthesis resyn;
const auto mig = node_resynthesis<mig_network>( klut, resyn );

Parameters and statistics

struct node_resynthesis_params

Parameters for node_resynthesis.

The data structure node_resynthesis_params holds configurable parameters with default arguments for node_resynthesis.

Public Members

bool verbose = {false}

Be verbose.

struct node_resynthesis_stats

Statistics for node_resynthesis.

The data structure node_resynthesis_stats provides data collected by running node_resynthesis.

Public Members

stopwatch::duration time_total = {0}

Total runtime.

Algorithm

template<class NtkDest, class NtkSource, class ResynthesisFn>
NtkDest mockturtle::node_resynthesis(NtkSource const &ntk, ResynthesisFn &&resynthesis_fn, node_resynthesis_params const &ps = {}, node_resynthesis_stats *pst = nullptr)

Node resynthesis algorithm.

This algorithm takes as input a network (of type NtkSource) and creates a new network (of type NtkDest), by translating each node of the input network into a subnetwork for the output network. To find a new subnetwork, the algorithm uses a resynthesis function that takes as input the input node’s truth table. This algorithm can for example be used to translate k-LUT networks into AIGs or MIGs.

The resynthesis 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.

Required network functions for parameter ntk (type NtkSource):

  • get_node

  • get_constant

  • foreach_pi

  • foreach_node

  • is_constant

  • is_pi

  • is_complemented

  • foreach_fanin

  • node_function

  • foreach_po

Required network functions for return value (type NtkDest):

  • get_constant

  • create_pi

  • create_not

  • create_po

Parameters:
  • ntk – Input network of type NtkSource

  • resynthesis_fn – Resynthesis function

Returns:

An equivalent network of type NtkDest

template<class NtkDest, class NtkSource, class ResynthesisFn>
void mockturtle::node_resynthesis(NtkDest &ntk_dest, NtkSource const &ntk, ResynthesisFn &&resynthesis_fn, node_resynthesis_params const &ps = {}, node_resynthesis_stats *pst = nullptr)

Node resynthesis algorithm.

This algorithm takes as input a network (of type NtkSource) and creates a new network (of type NtkDest), by translating each node of the input network into a subnetwork for the output network. To find a new subnetwork, the algorithm uses a resynthesis function that takes as input the input node’s truth table. This algorithm can for example be used to translate k-LUT networks into AIGs or MIGs.

The resynthesis 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.

Required network functions for parameter ntk (type NtkSource):

  • get_node

  • get_constant

  • foreach_pi

  • foreach_node

  • is_constant

  • is_pi

  • is_complemented

  • foreach_fanin

  • node_function

  • foreach_po

Required network functions for return value (type NtkDest):

  • get_constant

  • create_pi

  • create_not

  • create_po

Parameters:
  • ntk_dest – Output network of type NtkDest

  • ntk – Input network of type NtkSource

  • resynthesis_fn – Resynthesis function

Resynthesis functions

template<class Ntk, class DatabaseNtk = xag_network, xag_npn_db_kind DBKind = xag_npn_db_kind::xag_incomplete>
class xag_npn_resynthesis

Resynthesis function based on pre-computed AIGs.

This resynthesis function can be passed to cut_rewriting. It will produce a network based on pre-computed XAGs with up to at most 4 variables. Consequently, the nodes’ fan-in sizes in the input network must not exceed 4.

Example

const aig_network aig = ...;
xag_npn_resynthesis<aig_network> resyn;
aig = cut_rewriting( aig, resyn );

Note

The implementation of this algorithm was heavily inspired by the rewrite command in AIG. It uses the same underlying database of subcircuits.

class mig_npn_resynthesis

Resynthesis function based on pre-computed size-optimum MIGs.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. It will produce an MIG based on pre-computed size-optimum MIGs with up to at most 4 variables. Consequently, the nodes’ fan-in sizes in the input network must not exceed 4.

Example

const klut_network klut = ...;
mig_npn_resynthesis resyn;
const auto mig = node_resynthesis<mig_network>( klut, resyn );

class xmg_npn_resynthesis

Resynthesis function based on pre-computed size-optimum XMGs.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. It will produce an XMG based on pre-computed size-optimum XMGs with up to at most 4 variables. Consequently, the nodes’ fan-in sizes in the input network must not exceed 4.

Example

const klut_network klut = ...;
xmg_npn_resynthesis resyn;
const auto xmg = node_resynthesis<xmg_network>( klut, resyn );

class xag_minmc_resynthesis

Resynthesis function to minimize multiplicative complexity in XAGs.

This resynthesis function can be passed to cut_rewriting with a cut size of at most 6. It will produce an XAG based on pre-computed XAGs with a minimum multiplicative complexity.

Example

const xag_network xag = ...;
xag_minmc_resynthesis resyn;
xag = cut_rewriting( xag, resyn );

Public Functions

inline xag_minmc_resynthesis(std::string const &filename, xag_minmc_resynthesis_params const &ps = {}, xag_minmc_resynthesis_stats *pst = nullptr)

Default constructor.

Parameters:
  • filename – Database file with precomputed functions (information to be added)

  • ps – Parameters

  • pst – Statistics

template<class Ntk = klut_network>
class exact_resynthesis

Resynthesis function based on exact synthesis.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. The given truth table will be resynthized in terms of an optimum size k-LUT network, where k is specified as input to the constructor. In order to guarantee a reasonable runtime, k should be 3 or 4.

Example

const klut_network klut = ...;

exact_resynthesis<klut_network> resyn( 3 );
klut = cut_rewriting( klut, resyn );

A cache can be passed as second parameter to the constructor, which will store optimum networks for all functions for which resynthesis is invoked for. The cache can be used to retrieve the computed network, which reduces runtime.

Example

const klut_network klut = ...;

exact_resynthesis_params ps;
ps.cache = std::make_shared<exact_resynthesis_params::cache_map_t>();
exact_resynthesis<klut_network> resyn( 3, ps );
klut = cut_rewriting( klut, resyn );

The underlying engine for this resynthesis function is percy.

template<class Ntk = aig_network>
class exact_aig_resynthesis

Resynthesis function based on exact synthesis for AIGs.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. The given truth table will be resynthesized in terms of an optimum size AIG network.

Example

aig_network aig = ...;

exact_aig_resynthesis<aig_network> resyn;
aig = cut_rewriting( aig, resyn );

A cache can be passed as second parameter to the constructor, which will store optimum networks for all functions for which resynthesis is invoked for. The cache can be used to retrieve the computed network, which reduces runtime.

Example

aig_network aig = ...;

exact_resynthesis_params ps;
ps.cache = std::make_shared<exact_resynthesis_params::cache_map_t>();
exact_aig_resynthesis<aig_network> resyn( false, ps );
aig = cut_rewriting( aig, resyn );

The underlying engine for this resynthesis function is percy.

template<class Ntk, class ResynthesisFn>
class dsd_resynthesis

Resynthesis function based on DSD decomposition.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. The given truth table will be resynthized based on DSD decomposition. Since DSD decomposition may not be able to decompose the whole truth table, a different fall-back resynthesis function must be passed to this function.

Example

const aig_network aig = ...;

exact_aig_resynthesis<aig_network> fallback; // fallback
dsd_resynthesis<aig_network, decltype( fallback )> resyn( fallback );
cut_rewriting( aig, resyn );
aig = cleanup_dangling( aig );

template<class Ntk, class ResynFn = null_resynthesis<Ntk>>
class shannon_resynthesis

Resynthesis function based on Shannon decomposition.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. The given truth table will be resynthized based on Shanon decomposition.

Example

const klut_network klut = ...;

shannon_resynthesis<xag_network> resyn;
auto xag = node_resynthesis<xag_network>( klut, resyn );

template<class Ntk>
class sop_factoring

Resynthesis function based on SOP factoring.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. The method converts a given truth table in an ISOP, then factors the ISOP, and returns the factored form.

Example

aig_network aig = ...;

sop_factoring<aig_network> resyn;
refactoring( aig, resyn );

template<class Ntk, class ResynFn = null_resynthesis<Ntk>>
class positive_davio_resynthesis

Resynthesis function based on Davio decomposition.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. The given truth table will be resynthized based on Shanon decomposition.

Example

const klut_network klut = ...;

positive_davio_resynthesis<xag_network> resyn;
auto xag = node_resynthesis<xag_network>( klut, resyn );

template<class Ntk, class ResynFn = null_resynthesis<Ntk>>
class negative_davio_resynthesis

Resynthesis function based on Davio decomposition.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring. The given truth table will be resynthized based on Shanon decomposition.

Example

const klut_network klut = ...;

negative_davio_resynthesis<xag_network> resyn;
auto xag = node_resynthesis<xag_network>( klut, resyn );

template<class Ntk>
class direct_resynthesis

Resynthesis function that creates a gate for each node.

If it detects a function that can be constructed as a gate, it does so. Otherwise, it does not create a gate. In that case, a warning can be printed, if configured in the parameter struct.

The function works with all 0-, 1-, and 2-input node functions and with some 3-input node functions, e.g., 3-input majority for MIGs and XMGs, or 3-input XOR for XMGs.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring.

Example

const klut_network klut = ...;
direct_resynthesis resyn;
const auto mig = node_resynthesis<mig_network>( klut, resyn );

template<class Ntk>
class akers_resynthesis

Resynthesis function based on Akers synthesis.

This resynthesis function can be passed to node_resynthesis, cut_rewriting, and refactoring.

Example

const klut_network klut = ...;
akers_resynthesis<mig_network> resyn;
const auto mig = node_resynthesis<mig_network>( klut, resyn );

template<class Ntk>
class bidecomposition_resynthesis

Resynthesis function based on bi-decomposition.

This resynthesis function can be passed to refactoring.

Example

const xag_network xag = ...;
bidecomposition_resynthesis<xag_network> resyn;
const auto xag = refactoring( xag, resyn );