A New Paradigm for Logic Optimization
Introduction:
Majority-Inverter Graph (MIG) is a promising data structure for logic optimization and synthesis recently introduced by [1]. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. MIGs offer a more compact representation for logic as compared to traditional AND/OR-Inverter graphs (see figure below for an example).
MIG manipulation is supported by a consistent algebraic framework. Algebraic optimization of MIGs showed strong synthesis results [1]. As a complement to algebraic optimization, MIG Boolean methods exploit global properties of majority logic, such as bit-error masking, and optimize MIGs even further [2].
For the sake of visualization, the figure below shows the effect of the MIG logic optimization on the MCNC benchmark f51m. After logic optimization using the state-of-the-art ABC synthesis tool [3] this benchmark counts 10 levels of depth and 83 AND nodes. After MIG logic optimization, this benchmarks counts just 7 levels of depth and 70 MAJ nodes [4].
We provide a large set of logic benchmarks optimized by our MIG-synthesis tool (MIGhty) together with their AND/OR optimized counterpart. All MIG files are in Verilog HDL. Original and AND/OR optimized files are in Verilog HDL and AIGER format [5].
Basic characteristics of these circuits are discussed in [2]. If available, newer and more optimized versions of these benchmarks are given.
Other MIG synthesis samples and dedicated runs are available under email request to [email protected] (for academic, non-commercial purposes).
Download link:
Please click here to download. You will access a short on-line survey; after answering the questions you will be able to download the MIG package.
Contact:
Please contact me for any questions you might have about MIG optimization, at luca dot amaru at epfl dot ch.
Related publications:
[1] L. Amarù, P.-E. Gaillardon, G. De Micheli, “Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization”, Design Automation Conference (DAC), San Francisco, CA, USA, 2014.
[2] L. Amarù, P.-E. Gaillardon, G. De Micheli, “Boolean Logic Optimization in Majority-Inverter Graphs”, Design Automation Conference (DAC), San Francisco, CA, USA, 2015.
[3] ABC Synthesis tool available at http://www.eecs.berkeley.edu/~alanmi/abc/
[4] L. Amarù, A. Petkovska, P.-E. Gaillardon, D. Novo, P. Ienne, G. De Micheli, “Majority-Inverter Graph for FPGA Synthesis”, Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI 2015), Yilan, Taiwan, 2015.
[5] AIGER format description available at http://fmv.jku.at/aiger/