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
Year:
2014
ISBN:
978-1-4503-2730-5
Keywords:
Laboratories:




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

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)