Constructive AIG optimization through functional composition

Inhalt:
This work presents a technology independent logic synthesis algorithm that works on top of an And-Inverter-Graph (AIG) data structure. The goal is to minimize the number of nodes and the depth of the AIG, by controlling both characteristics while building the graph. This paper introduces a novel approach for AIG construction based on a new synthesis paradigm called functional composition. The idea is to perform the synthesis by associating simpler AIGs, in a bottom-up approach. The method constructively controls characteristics of final and intermediate graphs, allowing the adoption of secondary criteria other than the number of AIG nodes for optimization. This multi-objective AIG synthesis algorithm has presented interesting features and advantages when compared to other approaches.