Mapping Strategies

A mapping strategy provides a description of how the synthesizer should transpile a network.

All the mapping strategies have a method foreach_step that iterates over all the steps required to translate the network. A step is defined by a network node and by a mapping action: compute_action, uncompute_action, compute_inplace_action and uncompute_inplace_action.

All the strategies work on AIGs, XAGs, XMGs, MIGs and LUT networks, unless specifically noted otherwise.

Mapping strategies are solution to the reversible pebbling game problem.

template<class LogicNetwork>
class caterpillar::mapping_strategy

Subclassed by caterpillar::bennett_inplace_mapping_strategy< LogicNetwork >, caterpillar::bennett_mapping_strategy< LogicNetwork >, caterpillar::best_fit_mapping_strategy< LogicNetwork >, caterpillar::eager_mapping_strategy< LogicNetwork >, caterpillar::pebbling_mapping_strategy< LogicNetwork, Solver >

Public Functions

bool compute_steps(LogicNetwork const &ntk) = 0

Takes the logic network as input and defines the strategy’s steps sequence.

void foreach_step(step_function_t const &fn) const

Iterates through the strategy’s steps applying the given function.

Bennett strategy

Header: caterpillar/strategies/bennett_mapping_strategy.hpp

template<class LogicNetwork>
class bennett_mapping_strategy : public caterpillar::mapping_strategy<LogicNetwork>

A strategy that consists in computing all the nodes in topological order and uncomputing them in inverse topological order. It has been described in [Ben89] and it provides a solution that always returns the smallest number of reversible gates and the highest number of ancillae, with respect to the other methods.

Eager strategy

Header: caterpillar/strategies/eager_mapping_strategy.hpp

template<class LogicNetwork>
class eager_mapping_strategy : public caterpillar::mapping_strategy<LogicNetwork>

This strategy computes each node in topological order. At each primary output, all nodes in the transitive fanin are uncomputed that are not required any longer in successive steps.

This strategy only finds compute and uncompute steps, but no inplace steps.

Best-fit strategy

Header: caterpillar/strategies/best_fit_mapping_strategy.hpp

template<class LogicNetwork>
class best_fit_mapping_strategy : public caterpillar::mapping_strategy<LogicNetwork>

This strategy applies a k-LUT mapping that decomposes the network into cells. Cells are initially placed to form a reversible network following an eager strategy. The logic contained into each cell is decomposed by means of a second k-LUT mapping. The method selects the minimum k such that there are enough clean ancillae to save intermediate results. A different “best-fit” k is selected for each cell. Further details can be found in [MSR+18].

Pebbling strategy

Header: caterpillar/strategies/pebbling_mapping_strategy.hpp

template<class LogicNetwork, class Solver>
class pebbling_mapping_strategy : public caterpillar::mapping_strategy<LogicNetwork>

The pebbling strategy is obtained by solving iteratively the reversible pebbling game on the given network. The problem is encoded as a SAT problem. Details can be found in [MSM+19].

Parameters

struct caterpillar::pebbling_mapping_strategy_params

Public Members

bool progress = {false}

Show progress bar.

bool verbose = {false}

Print solution.

uint32_t pebble_limit = {0u}

Maximum number of pebbles to use, if supported by mapping strategy (0 means no limit).

uint32_t max_steps = {std::numeric_limits<uint32_t>::max()}

Maximum number of steps.

uint32_t conflict_limit = {0}

Conflict limit for the SAT solver (0 means no limit).

uint32_t solver_timeout = {0}

Timeout for the solver in milliseconds.

uint32_t search_timeout = {30}

Timeout for the iterative quests in seconds.

bool increment_pebbles_on_failure = {false}

Increment pebble numbers, if a failure occurs.

bool decrement_pebbles_on_success = {false}

Decrement pebble numbers, if satisfiable.

bool optimize_weight = {false}

Decrement max weight, if satisfiable.

XAG strategy

Header: caterpillar/strategies/xag_mapping_strategy.hpp

class xag_mapping_strategy : public caterpillar::mapping_strategy<xag_network>

This strategy is dedicated to XAG graphs and fault tolerant quantum computing. It exploits two main facts:

1. XORs are relatively cheap to be implemented in fault tolerant quantum computing

2. Toffoli gates visited to implement AND nodes can be uncomputed using 0 T gates

Details can be found in [MSC+19].