Haaswijk, Winston Jason
Soeken, Mathias
Amaru, Luca
Gaillardon, Pierre-Emmanuel
De Micheli, Giovanni
LUT Mapping and Optimization for Majority-Inverter Graphs
Proceedings of the 25th International Workshop on Logic & Synthesis (IWLS)
Proceedings of the 25th International Workshop on Logic & Synthesis (IWLS)
Proceedings of the 25th International Workshop on Logic & Synthesis (IWLS)
Proceedings of the 25th International Workshop on Logic & Synthesis (IWLS)
2016
2016-06-11
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.
Proceedings of the 25th International Workshop on Logic & Synthesis (IWLS)
ERC Cybercare 669354 / SNF 200021-146600
Conference Papers