Inversion Minimization in Majority-Inverter Graphs

In this paper, we present new optimization techniques for the recently introduced <i>Majority-Inverter Graph</i> (MIG). Our optimizations exploit intrinsic algebraic properties of MIGs and aim at rewriting the complemented edges of the graph without changing its shape. Two exact algorithms are proposed to minimize the number of complemented edges in the graph. The former is a dynamic programming method for trees; the latter finds the exact solution with a minimum number of inversions using <i>Boolean satisfiability</i> (SAT). We also describe a heuristic rule based algorithm to minimize complemented edges using local transformations. Experimental results for the exact algorithm to fanout-free regions show an average reduction of 12.8% on the EPFL benchmark suite. Applying the heuristic method on the same instances leads to a total improvement of 60.2%.

Published in:
Proceedings of the 25th International Workshop on Logic & Synthesis (IWLS)
Presented at:
25th International Workshop on Logic & Synthesis (IWLS), Austin, Texas, USA, June 10-11, 2016

Note: The status of this file is: Anyone

 Record created 2017-01-10, last modified 2020-04-20

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)