Technology mapping and network conversion

Header: mockturtle/algorithms/mapper.hpp

A versatile mapper that supports technology mapping and graph mapping (optimized network conversion). The mapper is independent of the underlying graph representation. Hence, it supports generic subject graph representations (e.g., AIG, and MIG) and a generic target representation (e.g. cell library, XMG). The mapper aims at finding a good mapping with respect to delay, area, and switching power.

The mapper uses a library (hash table) to facilitate Boolean matching. For technology mapping, it needs tech_library while for graph mapping it needs exact_library. For technology mapping, the generation of both NP- and P-configurations of gates are supported. Generally, it is convenient to use NP-configurations for small or medium size cell libraries. For bigger libraries, P-configurations should perform better. You can test both the configurations to see which one has the best run time. For graph mapping, NPN classification is used instead.

The following example shows how to perform delay-oriented technology mapping from an and-inverter graph using the default settings:

aig_network aig = ...;

/* read cell library in genlib format */
std::vector<gate> gates;
std::ifstream in( ... );
lorina::read_genlib( in, genlib_reader( gates ) )
tech_library tech_lib( gates );

/* perform technology mapping */
binding_view<klut_network> res = map( aig, tech_lib );

The mapped network is returned as a binding_view that extends a k-LUT network. Each k-LUT abstracts a cell and the view contains the binding information.

The next example performs area-oriented graph mapping from AIG to MIG using a NPN resynthesis database of structures:

aig_network aig = ...;

/* load the npn database in the library */
mig_npn_resynthesis resyn{ true };
exact_library<mig_network, mig_npn_resynthesis> exact_lib( resyn );

/* perform graph mapping */
map_params ps;
ps.skip_delay_round = true;
ps.required_time = std::numeric_limits<double>::max();
mig_network res = map( aig, exact_lib, ps );

For graph mapping, we suggest reading the network directly in the target graph representation if possible (e.g. read an AIG as a MIG) since the mapping often leads to better results in this setting.

As a default setting, cut enumeration minimizes the truth tables. This helps improving the results but slows down the computation. We suggest to keep it always true. Anyhow, for a faster mapping, set the truth table minimization parameter to false. The maximum number of cuts stored for each node is limited to 49. To increase this limit, change max_cut_num in fast_network_cuts.

Parameters and statistics

struct mockturtle::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 49. By default, truth table minimization is performed.

double required_time = {0.0f}

Required time for delay optimization.

bool skip_delay_round = {false}

Skip delay round for area 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.

uint32_t eswp_rounds = {0u}

Number of rounds for exact switching power optimization.

uint32_t switching_activity_patterns = {2048u}

Number of patterns for switching activity computation.

bool enable_logic_sharing = {false}

Exploit logic sharing in exact area optimization of graph mapping.

uint32_t logic_sharing_cut_limit = {8u}

Maximum number of cuts evaluated for logic sharing.

bool verbose = {false}

Be verbose.

struct mockturtle::map_stats

Statistics for mapper.

The data structure map_stats provides data collected by running map.

Public Members

double area = {0}

Area result.

double delay = {0}

Worst delay result.

double power = {0}

Power result.

stopwatch::duration time_mapping = {0}

Runtime for covering.

stopwatch::duration time_total = {0}

Total runtime.

cut_enumeration_stats cut_enumeration_st = {}

Cut enumeration stats.

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

Delay and area stats for each round.

bool mapping_error = {false}

Mapping error.

Algorithm

template<class Ntk, unsigned CutSize = 5u, typename CutData = cut_enumeration_tech_map_cut, unsigned NInputs, classification_type Configuration>
binding_view<klut_network> mockturtle::map(Ntk const &ntk, tech_library<NInputs, Configuration> const &library, map_params const &ps = {}, map_stats *pst = nullptr)

Technology mapping.

This function implements a technology mapping algorithm. It is controlled by a template argument CutData (defaulted to cut_enumeration_tech_map_cut). The argument is similar to the CutData argument in cut_enumeration, which can specialize the cost function to select priority cuts and store additional data. The default argument gives priority firstly to the cut size, then delay, and lastly to area flow. Thus, it is more suited for delay-oriented mapping. The type passed as CutData must implement the following four fields:

  • uint32_t delay

  • float flow

  • uint8_t match_index

  • bool ignore

See include/mockturtle/algorithms/cut_enumeration/cut_enumeration_tech_map_cut.hpp for one example of a CutData type that implements the cost function that is used in the technology mapper.

The function takes the size of the cuts in the template parameter CutSize.

The function returns a k-LUT network. Each LUT abstacts a gate of the technology library.

Required network functions:

  • size

  • is_pi

  • is_constant

  • node_to_index

  • index_to_node

  • get_node

  • foreach_po

  • foreach_node

  • fanout_size

The implementation of this algorithm was inspired by the mapping command map in ABC.

Parameters

  • ntk – Network

  • library – Technology library

  • ps – Mapping params

  • pst – Mapping statistics

template<class Ntk, unsigned CutSize = 4u, typename CutData = cut_enumeration_exact_map_cut, class NtkDest, class RewritingFn, unsigned NInputs>
NtkDest mockturtle::map(Ntk &ntk, exact_library<NtkDest, RewritingFn, NInputs> const &library, map_params const &ps = {}, map_stats *pst = nullptr)

Exact mapping.

This function implements a mapping algorithm using a database of structures. It is controlled by a template argument CutData (defaulted to cut_enumeration_exact_map_cut). The argument is similar to the CutData argument in cut_enumeration, which can specialize the cost function to select priority cuts and store additional data. The default argument gives priority firstly to area flow, then delay, and lastly to the cut size. The type passed as CutData must implement the following four fields:

  • uint32_t delay

  • float flow

  • uint8_t match_index

  • bool ignore

See include/mockturtle/algorithms/cut_enumeration/cut_enumeration_exact_map_cut.hpp for one example of a CutData type that implements the cost function that is used in the technology mapper.

The function takes the size of the cuts in the template parameter CutSize.

The function returns a mapped network representation generated using the exact synthesis entries in the exact_library.

Required network functions:

  • size

  • is_pi

  • is_constant

  • node_to_index

  • index_to_node

  • get_node

  • foreach_po

  • foreach_node

  • fanout_size

Parameters

  • ntk – Network

  • library – Exact library

  • ps – Mapping params

  • pst – Mapping statistics