Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization

In this paper, we present <em>Majority-Inverter Graph</em> (MIG), a novel logic representation structure for efficient optimization of Boolean functions. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. We show that MIGs include any <em>AND/OR/Inverter Graphs</em> (AOIGs), containing also the well- known AIGs. In order to support the natural manipulation of MIGs, we introduce a new Boolean algebra, based exclusively on majority and inverter operations, with a complete axiomatic system. Theoretical results show that it is possible to explore the entire MIG representation space by using only five primitive transformation rules. Such feature opens up a great opportunity for logic optimization and synthesis. We showcase the MIG potential by proposing a delay-oriented optimization technique. Experimental results over MCNC benchmarks show that MIG optimization reduces the number of logic levels by 18%, on average, with respect to AIG optimization performed by ABC academic tool. Employed in a traditional <em>optimization-mapping</em> circuit synthesis flow, MIG optimization enables an average reduction of {22%, 14%, 11%} in the estimated {delay, area, power} metrics, before physical design, as compared to academic/commercial synthesis flows.

Published in:
Proceedings of the 51st Design Automation Conference (DAC)
Presented at:
51st Design Automation Conference (DAC), San Francisco, California, USA, June 1-5, 2014

 Record created 2014-02-27, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)