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 forlut_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.
-
cut_enumeration_params cut_enumeration_ps = {}¶
-
struct mockturtle::lut_mapping_stats¶
Statistics for lut_mapping.
The data structure
lut_mapping_stats
provides data collected by runninglut_mapping
.
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 totrue
) andCutData
(defaulted tocut_enumeration_mf_cut
). The first argumentStoreFunction
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 theCutData
argument incut_enumeration
, which can specialize the cost function to select priority cuts and store additional data. For LUT mapping using this function the type passed asCutData
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
(ifStoreFunction
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 forsatlut_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.
-
cut_enumeration_params cut_enumeration_ps = {}¶
-
struct mockturtle::satlut_mapping_stats¶
Statistics for satlut_mapping.
The data structure
satlut_mapping_stats
provides data collected by runningsatlut_mapping
.
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
ifStoreFunction
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
ifStoreFunction
is true
- Parameters
ntk – Logic network to be mapped
window_size – Maximum number of gates in a window
ps – Parameters
st – Statistics