LUT mapping 1

Dynamic-programming based heuristic

Header: mockturtle/algorithms/lut_mapper.hpp

LUT mapping with cut size \(k\) partitions a logic network into mapped nodes and unmapped nodes, where a mapped node \(n\) is assigned some cut \((n, L)\) such that the following conditions hold: i) each node that drives a primary output is mapped, and ii) each leaf in the cut of a mapped node is either a primary input or also mapped. This ensures that the mapping covers the whole logic network. LUT mapping aims to find a good mapping with respect to a cost function, e.g., a short critical path in the mapping or a small number of mapped nodes. The LUT mapping algorithm can assign a weight to a cut for alternative cost functions.

This implementation offers delay- or area-oriented mapping. The mapper can be configured using many options.

The following example shows how to perform a LUT mapping to an And-inverter graph using the default settings:

aig_network aig = ...;
klut_network klut = lut_map( aig );

Alternatively, the mapping information can be saved on the original network as follows:

aig_network aig = ...;
mapping_view mapped_aig{aig};
lut_map_inplace( mapped_aig );

Note that the AIG is wrapped into a mapping_view in order to equip the network structure with the required mapping methods.

The next example is more complex. It uses an MIG as underlying network structure, maps for area, changes the cut size \(k\) to 8, and also computes the functions for the cut of each mapped node:

mig_network mig = ...;
mapped_view<mig_network, true> mapped_mig{mig};

lut_map_params ps;
ps.area_oriented_mapping = true;
ps.edge_optimization = false;
ps.remove_dominated_cuts = false;
ps.recompute_cuts = false;
ps.cut_enumeration_ps.cut_size = 8;
lut_map_inplace<mapped_view<mig_network, true>, true>( mapped_mig, ps );

Parameters and statistics

struct lut_map_params

Parameters for map.

The data structure map_params holds configurable parameters with default arguments for map.

Public Members

cut_enumeration_params cut_enumeration_ps = {}

Parameters for cut enumeration.

The default cut limit is 8. The maximum value is 16. The maxiumum cut size is 16. By default, truth table minimization is performed.

bool area_oriented_mapping = {false}

Do area-oriented mapping.

uint32_t required_delay = {0u}

Required depth for depth relaxation.

uint32_t relax_required = {0u}

Required depth relaxation ratio (%).

bool recompute_cuts = {true}

Recompute cuts at each step.

uint32_t area_share_rounds = {2u}

Number of rounds for area sharing optimization.

uint32_t area_flow_rounds = {1u}

Number of rounds for area flow optimization.

uint32_t ela_rounds = {2u}

Number of rounds for exact area optimization.

bool edge_optimization = {true}

Use edge count reduction.

bool cut_expansion = {true}

Try to expand the cuts.

bool remove_dominated_cuts = {true}

Remove the cuts that are contained in others.

bool collapse_mffcs = {false}

Maps by collapsing MFFCs.

bool sop_balancing = {false}

Depth optimization by balancing ISOPs.

bool esop_balancing = {false}

Depth optimization by balancing ESOPs.

uint32_t cost_cache_vars = {3u}

Maximum number variables for cost function caching.

bool verbose = {false}

Be verbose.

struct lut_map_stats

Statistics for mapper.

The data structure map_stats provides data collected by running map.

Public Members

uint32_t area = {0}

Area result.

uint32_t delay = {0}

Worst delay result.

uint32_t edges = {0}

Edge result.

stopwatch::duration time_total = {0}

Total runtime.

cut_enumeration_stats cut_enumeration_st = {}

Cut enumeration stats.

std::vector<std::string> round_stats = {}

Depth and size stats for each round.

Algorithm

template<class Ntk, bool ComputeTruth = false, class LUTCostFn = lut_unitary_cost>
klut_network mockturtle::lut_map(Ntk &ntk, lut_map_params ps = {}, lut_map_stats *pst = nullptr)

LUT mapper.

This function implements a LUT mapping algorithm. It is controlled by one template argument ComputeTruth (defaulted to false) which controls whether the LUT function is computed or the mapping is structural. In the former case, truth tables are computed during cut enumeration, which requires more runtime.

This function returns a k-LUT network.

The template LUTCostFn sets the cost function to evaluate depth and size of a truth table given its support size if ComputeTruth is set to false, or its function if ComputeTruth is set to true.

This implementation offers more options such as delay oriented mapping and edges minimization compared to the command lut_mapping.

Required network functions:

  • size

  • is_ci

  • is_constant

  • node_to_index

  • index_to_node

  • get_node

  • foreach_co

  • foreach_node

  • fanout_size

template<class Ntk, bool StoreFunction = false, class LUTCostFn = lut_unitary_cost>
void mockturtle::lut_map_inplace(Ntk &ntk, lut_map_params const &ps = {}, lut_map_stats *pst = nullptr)

LUT mapper inplace.

This function implements a LUT mapping algorithm. It is controlled by one template argument StoreFunction (defaulted to false) which controls whether the LUT function is stored in the mapping. In that case truth tables are computed during cut enumeration, which requires more runtime.

The input network must be wrapped in a mapping_view. The computed mapping is stored in the view. In this version, some features of the mapper are disabled, such as on-the-fly decompositions, due to incompatibility.

The template LUTCostFn sets the cost function to evaluate depth and size of a truth table given its support size, if StoreFunction is set to false, or its function, if StoreFunction is set to true.

This implementation offers more options such as delay oriented mapping and edges minimization compared to the command lut_mapping.

Required network functions:

  • size

  • is_ci

  • is_constant

  • node_to_index

  • index_to_node

  • get_node

  • foreach_co

  • foreach_node

  • fanout_size

  • clear_mapping

  • add_to_mapping

  • set_lut_function (if StoreFunction is true)

Note

The implementation of this algorithm was inspired by the LUT mapping command &if in ABC.

LUT mapping 2

Dynamic-programming based heuristic

Header: mockturtle/algorithms/lut_mapping.hpp

LUT mapping with cut size \(k\) partitions a logic network into mapped nodes and unmapped nodes, where a mapped node \(n\) is assigned some cut \((n, L)\) such that the following conditions hold: i) each node that drives a primary output is mapped, and ii) each leaf in the cut of a mapped node is either a primary input or also mapped. This ensures that the mapping covers the whole logic network. LUT mapping aims to find a good mapping with respect to a cost function, e.g., a short critical path in the mapping or a small number of mapped nodes. The LUT mapping algorithm can assign a weight to a cut for alternative cost functions.

This implementation performs ony area-oriented mapping.

The following example shows how to perform a LUT mapping to an And-inverter graph using the default settings:

aig_network aig = ...;
mapping_view mapped_aig{aig};
lut_mapping( mapped_aig );

Note that the AIG is wrapped into a mapping_view in order to equip the network structure with the required mapping methods.

The next example is more complex. It uses an MIG as underlying network structure, changes the cut size \(k\) to 8, and also computes the functions for the cut of each mapped node:

mig_network mig = ...;
mapped_view<mig_network, true> mapped_mig{mig};

lut_mapping_params ps;
ps.cut_enumeration_ps.cut_size = 8;
lut_mapping<mapped_view<mig_network, true>, true>( mapped_mig, ps );

Parameters and statistics

struct lut_mapping_params

Parameters for lut_mapping.

The data structure lut_mapping_params holds configurable parameters with default arguments for lut_mapping.

Public Members

cut_enumeration_params cut_enumeration_ps = {}

Parameters for cut enumeration.

The default cut size is 6, the default cut limit is 8.

uint32_t rounds = {2u}

Number of rounds for area flow optimization.

The first round is used for delay optimization.

uint32_t rounds_ela = {1u}

Number of rounds for exact area optimization.

bool verbose = {false}

Be verbose.

struct lut_mapping_stats

Statistics for lut_mapping.

The data structure lut_mapping_stats provides data collected by running lut_mapping.

Public Members

stopwatch::duration time_total = {0}

Total runtime.

Algorithm

template<class Ntk, bool StoreFunction = false, typename CutData = cut_enumeration_mf_cut>
void mockturtle::lut_mapping(Ntk &ntk, lut_mapping_params const &ps = {}, lut_mapping_stats *pst = nullptr)

LUT mapping.

This function implements a LUT mapping algorithm. It is controlled by two template arguments StoreFunction (defaulted to true) and CutData (defaulted to cut_enumeration_mf_cut). The first argument StoreFunction controls whether the LUT function is stored in the mapping. In that case truth tables are computed during cut enumeration, which requires more runtime. The second argument is simuilar to the CutData argument in cut_enumeration, which can specialize the cost function to select priority cuts and store additional data. For LUT mapping using this function the type passed as CutData must implement the following three fields:

  • uint32_t delay

  • float flow

  • float costs

See include/mockturtle/algorithms/cut_enumeration/mf_cut.hpp for one example of a CutData type that implements the cost function that is used in the LUT mapper &mf in ABC.

Required network functions:

  • size

  • is_ci

  • is_constant

  • node_to_index

  • index_to_node

  • get_node

  • foreach_co

  • foreach_node

  • fanout_size

  • clear_mapping

  • add_to_mapping

  • set_lut_function (if StoreFunction is true)

Note

The implementation of this algorithm was heavily inspired but the LUT mapping command &mf in ABC.

SAT-based mapping

Header: mockturtle/algorithms/satlut_mapping.hpp

This algorithm has a similar interface to the heuristic described above, but uses SAT to find mappings with fewer number of cells.

Parameters and statistics

struct satlut_mapping_params

Parameters for satlut_mapping.

The data structure satlut_mapping_params holds configurable parameters with default arguments for satlut_mapping.

Public Members

cut_enumeration_params cut_enumeration_ps = {}

Parameters for cut enumeration.

The default cut size is 6, the default cut limit is 8.

uint32_t conflict_limit = {0u}

Conflict limit for SAT solver.

The default limit is 0, which means the number of conflicts is not used as a resource limit.

bool progress = {false}

Show progress.

bool verbose = {false}

Be verbose.

bool very_verbose = {false}

Be very verbose.

struct satlut_mapping_stats

Statistics for satlut_mapping.

The data structure satlut_mapping_stats provides data collected by running satlut_mapping.

Public Members

stopwatch::duration time_total = {0}

Total runtime.

stopwatch::duration time_sat = {0}

Total runtime.

uint64_t num_vars = {0u}

Number of SAT variables.

uint64_t num_clauses = {0u}

Number of SAT clauses.

Algorithm

template<class Ntk, bool StoreFunction = false, typename CutData = cut_enumeration_mf_cut>
void mockturtle::satlut_mapping(Ntk &ntk, satlut_mapping_params const &ps = {}, satlut_mapping_stats *pst = nullptr)

SAT-LUT mapping.

This algorithm implements the SAT-based area-oriented LUT mapping algorithm presented in [B. Schmitt, A. Mishchenko, and R.K. Brayton, ASP-DAC 23 (2018), 586-591].

The interface is similar to the one in lut_mapping.

This algorithm applies SAT-LUT mapping to the whole networking and therefore may show poor performance for larger networks. There exists a method with the same name that takes as input a window size to apply SAT-LUT mapping to windows.

Required network functions:

  • is_pi

  • index_to_node

  • node_to_index

  • foreach_gate

  • foreach_po

  • num_gates

  • num_cells

  • has_mapping

  • clear_mapping

  • add_to_mapping

  • set_cell_function if StoreFunction is true

Parameters:

  • ntk – Logic network to be mapped

  • ps – Parameters

  • st – Statistics

template<class Ntk, bool StoreFunction = false, typename CutData = cut_enumeration_mf_cut>
void mockturtle::satlut_mapping(Ntk &ntk, uint32_t window_size, satlut_mapping_params ps = {}, satlut_mapping_stats *pst = nullptr)

SAT-LUT mapping (windowed).

This algorithm applies SAT-LUT mapping to windows of a given size (e.g., 32, 64, 128) and can therefore better deal with larger networks. It has otherwise the same interface as satlut_mapping.

The initial network must already contain a mapping, e.g., found with lut_mapping.

Required network functions:

  • is_pi

  • index_to_node

  • node_to_index

  • foreach_gate

  • foreach_po

  • num_gates

  • num_cells

  • has_mapping

  • clear_mapping

  • add_to_mapping

  • is_cell_root

  • set_cell_function if StoreFunction is true

Parameters:

  • ntk – Logic network to be mapped

  • window_size – Maximum number of gates in a window

  • ps – Parameters

  • st – Statistics