An Enhanced Resubstitution Algorithm for Area-Oriented Logic Optimization

Logic synthesis is an ensemble of algorithms that optimizes digital circuit representations and maps them to a chosen technology. Minimizing the number of gates is essential to reduce area occupation and power consumption. As the problem is intractable, heuristic logic transformations are used. In particular, resubstitution attempts to express the function of a node using other nodes already present in the network. State-of-the-art resubstitution engines can only identify new implementations with the support of up to three inputs or being simply decomposable. This work aims at extending \emph{resubstitution} to non-decomposable functions with more than three inputs and it outperforms previous methods. % Experimental results show that our heuristic enables us to push further the optimization capabilities of resubstitution. We apply our method on highly optimized designs from the ISCAS and EPFL benchmarks, achieving additional average improvements of 18.50% and 8.36%.