LUT Mapping and Optimization for Majority-Inverter Graphs

A <i>Majority-Inverter Graph</i> (MIG) is a directed acyclic graph in which every vertex represents a three-input majority operation and edges may be complemented to indicate operand inversion. MIGs have algebraic and Boolean properties that enable efficient logic optimization. They have been shown to obtain superior synthesis results as compared to state-of-the- art <i>And-Inverter Graph</i> (AIG) based algorithms. In this paper, we extend MIGs to <i>Functionally Reduced</i> MIGs (FRMIGs), analogous to the extension of AIGs to <i>Functionally Reduced</i> AIGs (FRAIGs). This enables the use of MIGs in a <i>lossless synthesis</i> design flow. We present an FRMIG based technology mapper for <i>lookup tables</i> (LUTs). Any MIG may be mapped to a <i>k</i>- LUT network. Using <i>exact synthesis</i> we may decompose the <i>k</i>- LUT network back into an equivalent MIG. We show how LUT mapping and exact <i>k</i>-LUT decomposition can be used to create an MIG optimization method. Finally, we present the results of applying our new optimization method and LUT mapper to both logic optimization and technology mapping.

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

 Record created 2017-01-10, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)