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%.
ET_IWLS16.pdf
openaccess
261.09 KB
Adobe PDF
5852ac6de83d954dde3a75648d52bea8