Constructive AIG optimization through functional composition

Conference: ARCS 2011 - 24th International Conference on Architecture of Computing Systems
02/22/2011 - 02/23/2011 at Como, Italy

Proceedings: ARCS 2011

Pages: 5Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Figueiró, Thiago; Ribas, Renato; Reis, André (Universidade Federal do Rio Grande do Sul, Instituto de Informática, Porto Alegre, Brazil)

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.