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 fornode_resynthesis
.Public Members
-
bool verbose = {false}
Be verbose.
-
bool verbose = {false}
-
struct node_resynthesis_stats
Statistics for node_resynthesis.
The data structure
node_resynthesis_stats
provides data collected by runningnode_resynthesis
.
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 typeNtkDest
), 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)
whereLeavesIterator
can be dereferenced to aNtkDest::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 typeNtkDest
), 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)
whereLeavesIterator
can be dereferenced to aNtkDest::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
, andrefactoring
. 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
, andrefactoring
. 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
-
inline xag_minmc_resynthesis(std::string const &filename, xag_minmc_resynthesis_params const &ps = {}, xag_minmc_resynthesis_stats *pst = nullptr)
-
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
, andrefactoring
. The given truth table will be resynthized in terms of an optimum sizek
-LUT network, wherek
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
, andrefactoring
. 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
, andrefactoring
. 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
, andrefactoring
. 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
, andrefactoring
. 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
, andrefactoring
. 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
, andrefactoring
. 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
, andrefactoring
.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
, andrefactoring
.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 );