MIG algebraic rewriting

Header: mockturtle/algorithms/mig_algebraic_rewriting.hpp

Parameters

struct mig_algebraic_depth_rewriting_params

Parameters for mig_algebraic_depth_rewriting.

The data structure mig_algebraic_depth_rewriting_params holds configurable parameters with default arguments for mig_algebraic_depth_rewriting.

Public Types

enum strategy_t

Rewriting strategy.

Values:

enumerator dfs

DFS rewriting strategy.

Applies depth rewriting once to all output cones whose drivers have maximum levels

enumerator aggressive

Aggressive rewriting strategy.

Applies depth reduction multiple times until the number of nodes, which cannot be rewritten, matches the number of nodes, in the current network; or the new network size is larger than the initial size w.r.t. to an overhead.

enumerator selective

Selective rewriting strategy.

Like aggressive, but only applies rewriting to nodes on critical paths and without overhead.

Public Members

float overhead = {2.0f}

Overhead factor in aggressive rewriting strategy.

When comparing to the initial size in aggressive depth rewriting, also the number of dangling nodes are taken into account.

bool allow_area_increase = {true}

Allow area increase while optimizing depth.

Algorithm

template<class Ntk>
void mockturtle::mig_algebraic_depth_rewriting(Ntk &ntk, mig_algebraic_depth_rewriting_params const &ps = {}, mig_algebraic_depth_rewriting_stats *pst = nullptr)

Majority algebraic depth rewriting.

This algorithm tries to rewrite a network with majority gates for depth optimization using the associativity and distributivity rule in majority-of-3 logic. It can be applied to networks other than MIGs, but only considers pairs of nodes which both implement the majority-of-3 function.

Required network functions:

  • get_node

  • level

  • update_levels

  • create_maj

  • substitute_node

  • foreach_node

  • foreach_po

  • foreach_fanin

  • is_maj

  • clear_values

  • set_value

  • value

  • fanout_size

Note

The implementation of this algorithm was heavily inspired by an implementation from Luca Amarù.