LUT mapping

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.

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 );

Parameters and statistics

struct mockturtle::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 mockturtle::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_pi

  • is_constant

  • node_to_index

  • index_to_node

  • get_node

  • foreach_po

  • foreach_node

  • fanout_size

  • clear_mapping

  • add_to_mapping

  • set_lut_funtion (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 mockturtle::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 mockturtle::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