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.


Publié dans:
Proceedings of the 25th International Workshop on Logic & Synthesis (IWLS)
Présenté à:
25th International Workshop on Logic & Synthesis (IWLS), Austin, Texas, USA, June 10-11, 2016
Année
Jun 11 2016
Note:
ERC Cybercare 669354 / SNF 200021-146600
Laboratoires:




 Notice créée le 2017-01-10, modifiée le 2019-03-17

n/a:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)