**** Master Project or Semester Project ****
Contact: Dr. Mathias Soeken, Post-doctoral researcher, EPFL-IC-ISIM-LSI
Background of the project:
Logic synthesis based on the majority-of-three operation has been an intensively studied research topic for more than five decades. The majority-of-three operation M (x, y, z) = xy + xz + yz has remarkable algebraic properties. A function f(x1,x2,x3,…,xn) is called monotone, if f(x) ≤ f(y) whenever x ⊆ y . (We have x = x1…xn ⊆ y = y1…yn if xi ≤ yi for all i .) For monotone functions the majority expansion formula is
f(x1,x2,x3,…,xn) = M(f(x1,x1,x3,…,xn),f(x1,x2,x2,…,xn),f(x3,x2,x3,…,xn)).
The expansion can be applied recursively to the inner functions, which now each depend on one variable less. This eventually leads to an expression that consists only of majority-of-three operations, positive literals, and constants.
Overview of the project:
The project targets logic synthesis for the special case of monotone functions based on the majority expansion formula. Depending on the variable ordering, different expressions are obtained with a different number of majority operations. Hence, it is of interest to find a good or the best realization. The resulting expression can be considered as a decision diagram [1] or majority graph [2] which allow to share expressions if they are equal. This gives even further possibilities for logic optimization. Different data structures and optimization algorithms should be implemented as part of the project.
Further, one can investigate whether the majority expansion formula is generalizable for other classes of functions, e.g., negative functions or unate functions. Since only a small set of all Boolean functions, have this property, a direct application to practical problems is unlikely. However, subfunctions may have this property and can therefore be locally optimized.
Eligibility requirements:
● Good background in data structures
● Proficiency in C and C++
● Knowledge on logic synthesis is a plus
References:
[1] R.E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation. IEE Trans. on Computers 35(8): 677-691 (1986).
[2] L.G. Amarù, P.-E. Gaillardon, G. De Micheli: Majority-Inverter Graph: A Novel Data-Structure and Algoritjms for Efficient Logic Optimization. DAC 2014: 194:1 – 194:6.