Constructive AIG Optimization Considering Input Weights

Thiago Figueiró,  Renato Ribas,  André Reis
Universidade Federal do Rio Grande do Sul


This work presents a technology independent 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 factoring algorithm has presented interesting features and advantages when compared to other approaches. Moreover, considering different input weights (costs) lead to better synthesis when operating over separated portions of the circuit.