MIG Optimization with Technology Mapping

**** Master Project or Semester Project ****


Contact: Dr. Mathias Soeken, Post-doctoral researcher, EPFL-IC-ISIM-LSI


Background of the project:

Majority-inverter graphs (MIG) are a recently introduced logic representation for logic synthesis. MIGs are homogenous logic representations that allow inversion and majority-of-three as only logic operations. Several algorithms have been proposed that minimize MIGs with respect to a cost metric [1,2,3]. Common cost metrics are the number of Majority operations (size) and the number of logic levels (depth) in the logic representation or area and delay in the mapped netlist after technology mapping.

Technology mapping [4,5] describes the process of translating a logic representation (such as an MIG) into a netlist with respect to a gate library that minimizes area and/or delay. Mapping typically is carried out in two steps which is enumerating of candidate substructures and then finding a covering of them which covers the whole logic representation without overlaps.

Overview of the project:

The project should evaluate whether technology mapping can be exploited in order to derive an MIG from an optimized logic representation, in this case AND-inverter graphs (AIG). This can be achieved by allowing only majority-of-three operations and inverters in the gate library that is used for mapping. A large amount of optimization techniques exist for AIGs and therefore such an approach can enable these techniques for MIG optimization. So far, AIGs are translated naïvely to MIGs by mapping each AND gate to a Majority gate which third input is assigned 0.

In the project one will learn about MIGs, AIGs, and technology mapping. Known mapping algorithms will be applied and evaluated, but also adapted in order to achieve better results. The development of an own technology mapping from scratch is also a possible outcome of this project.

Eligibility requirements:

●    Good background in data structures
●    Proficiency in C and C++
●    Knowledge on logic synthesis is a plus


[1] L.G. Amarù, P.-E. Gaillardon, G. De Micheli: Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization. DAC 2014: 194:1-194:6.

[2] L.G. Amarù, P.-E. Gaillardon, G. De Micheli: Majority-Inverter Graph: A New Paradigm for Logic Optimization. TCAD.

[3] M. Soeken, P.-E. Gaillardon, L.G. Amarù, G. De Micheli: Optimizing majority-inverter graphs with functional hashing. DATE 2016.

[4] S. Chatterjee, A. Mishchenko, R.K. Brayton, X. Wang, T. Kam: Reducing Structural Bias in Technology Mapping. IEEE Trans. on CAD of Integrated Circuits and Systems 25(12): 2894-2903 (2006).

[5] A. Mishchenko, S. Cho, S. Chatterjee, R.K. Brayton: Combinational and sequential mapping with priority cuts. ICCAD 2007: 354-361