Logic resynthesis

Headers: mockturtle/algorithms/resyn_engines/mig_resyn.hpp, mockturtle/algorithms/resyn_engines/xag_resyn.hpp

The problem of logic resynthesis is defined as follows:

Given a target function \(f\) and a set of divisor functions \(g_1, ..., g_n\), find a dependency function \(h\) such that \(f=h(g_1, ..., g_n)\).

Specifically, the dependency function is represented by a dependency circuit of a certain network type and we aim at finding a small dependency circuit. The logic resynthesis engines can be used in resubstitution to find the replacement for the root node. Interfacing resubstitution functors (see Structure of the resubstitution framework) are provided in mockturtle/algorithms/mig_resub.hpp and mockturtle/algorithms/sim_resub.hpp.

template<class TT, class static_params = xag_resyn_static_params_default<TT>>
class xag_resyn_decompose

Logic resynthesis engine for AIGs or XAGs.

The algorithm is based on ABC’s implementation in giaResub.c by Alan Mishchenko.

Divisors are classified as positive unate (not overlapping with target offset), negative unate (not overlapping with target onset), or binate (overlapping with both onset and offset). Furthermore, pairs of binate divisors are combined with an AND operation and considering all possible input polarities and again classified as positive unate, negative unate or binate. Simple solutions of zero cost (one unate divisor), one node (two unate divisors), two nodes (one unate divisor + one unate pair), and three nodes (two unate pairs) are exhaustively examined. When no simple solutions can be found, the algorithm heuristically chooses an unate divisor or an unate pair to divide the target function with and recursively calls itself to decompose the remainder function.

Example

using TT = kitty::static_truth_table<6>;
const std::vector<aig_network::node> divisors = ...;
const node_map<TT, aig_network> tts = ...;
const TT target = ..., care = ...;
xag_resyn_stats st;
xag_resyn_decompose<TT, node_map<TT, aig_network>, false, false, aig_network::node> resyn( st );
auto result = resyn( target, care, divisors.begin(), divisors.end(), tts );

Public Functions

template<class iterator_type, bool enabled = static_params::uniform_div_cost && !static_params::preserve_depth, typename = std::enable_if_t<enabled>>
inline std::optional<index_list_t> operator()(TT const &target, TT const &care, iterator_type begin, iterator_type end, typename static_params::truth_table_storage_type const &tts, uint32_t max_size = std::numeric_limits<uint32_t>::max())

Perform XAG resynthesis.

tts[*begin] must be of type TT. Moreover, if static_params::copy_tts = false, *begin must be of type static_params::node_type.

Parameters:

  • target – Truth table of the target function.

  • care – Truth table of the care set.

  • begin – Begin iterator to divisor nodes.

  • end – End iterator to divisor nodes.

  • tts – A data structure (e.g. std::vector<TT>) that stores the truth tables of the divisor functions.

  • max_size – Maximum number of nodes allowed in the dependency circuit.

template<class TT, class static_params = mig_resyn_static_params>
class mig_resyn_topdown

Logic resynthesis engine for MIGs with top-down decomposition.

This algorithm resynthesizes the target function with divisor functions by first building the topmost node, and then iteratively refining its output function by expanding a leaf with a new node. The three fanins of the newly-created node are chosen from the divisors based on some scoring functions aiming at covering more care bits.

Public Functions

template<class iterator_type, class truth_table_storage_type, bool enabled = static_params::uniform_div_cost && !static_params::preserve_depth, typename = std::enable_if_t<enabled>>
inline std::optional<index_list_t> operator()(TT const &target, TT const &care, iterator_type begin, iterator_type end, truth_table_storage_type const &tts, uint32_t max_size = std::numeric_limits<uint32_t>::max())

Perform MIG resynthesis.

*pTTs[*begin] must be of type TT.

Parameters:

  • target – Truth table of the target function.

  • care – Truth table of the care set.

  • begin – Begin iterator to divisor nodes.

  • end – End iterator to divisor nodes.

  • tts – A data structure (e.g. std::vector<TT>) that stores the truth tables of the divisor functions.

  • max_size – Maximum number of nodes allowed in the dependency circuit.

template<class TT, class static_params = mig_resyn_static_params>
class mig_resyn_bottomup

Logic resynthesis engine for MIGs with a bottom-up approach.

This algorithm resynthesizes the target function with divisor functions by building a chain of majority gates from bottom to top. Divisors are chosen as side fanins based on some scoring functions aiming at covering more uncovered bits.

template<class static_params = mig_resyn_static_params>
class mig_resyn_akers

Logic resynthesis engine for MIGs by Akers’ majority synthesis algorithm.

This engine is a re-implementation of Akers’ algorithm based on the following paper:

Akers, S. B. (1962, October). Synthesis of combinational logic using three-input majority gates. In 3rd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1962) (pp. 149-158). IEEE.