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 forcut_rewriting
.Public Types
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.
-
cut_enumeration_params cut_enumeration_ps = {}
-
struct cut_rewriting_stats
Statistics for cut_rewriting.
The data structure
cut_rewriting_stats
provides data collected by runningcut_rewriting
.
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)
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. There are some rewriting algorithms in the foldermockturtle/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)
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. There are some rewriting algorithms in the foldermockturtle/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.