Majority-Inverter Graph: A New Paradigm for Logic Optimization

In this paper, we propose a paradigm shift in representing and optimizing logic by using only majority (MAJ) and inversion (INV) functions as basic operations. We represent logic functions by <i>Majority-Inverter Graph</i> (MIG): a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. We optimize MIGs via a new Boolean algebra, based exclusively on majority and inversion operations, that we formally axiomatize in this work. As a complement to MIG algebraic optimization, we develop powerful Boolean methods exploiting global properties of MIGs, such as bit-error masking. MIG algebraic and Boolean methods together attain very high optimization quality. Considering the set of IWLS’05 benchmarks, our MIG optimizer (<i>MIGhty</i>) enables a 7% depth reduction in LUT-6 circuits mapped by ABC while also reducing size and power activity, with respect to similar AIG optimization. Focusing on arithmetic intensive benchmarks instead, <i>MIGhty</i> enables a 16% depth reduction in LUT-6 circuits mapped by ABC, again with respect to similar AIG optimization. Employed as front-end to a delay-critical 22-nm ASIC flow (logic synthesis + physical design) <i>MIGhty</i> reduces the average delay/area/power by 13%/4%/3%, respectively, over 31 academic and industrial benchmarks. We also demonstrate delay/area/power improve- ments by 10%/10%/5% for a commercial FPGA flow.

Published in:
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), 35, 5, 806-819
Piscataway, Ieee-Inst Electrical Electronics Engineers Inc

 Record created 2015-09-17, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)