PhD student
Integrated Systems Laboratory
EPFL, Lausanne, Switzerland

 

Webpage

The Majority Logic Optimization Paradigm

Thursday, 10 December 2015 at 11:00 in room BC 420

 

Abstract:

In this talk, we propose a paradigm shift in representing and optimizing logic by using only majority (MAJ) and inversion (INV) functions as basic operations. Majority logic circuits have an enhanced expressive power as compared to traditional AND/OR circuits. For example, depth-3 majority circuits can represent arithmetic functions such as division, multiplication and n-ary addition in polynomial size while AND/OR counterparts require an exponential size. In order to exploit such expressive power in logic synthesis, we define in this talk the Majority-Inverter Graph (MIG) representation form: a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. We present a new Boolean algebra to manipulate MIGs, based exclusively on majority and inversion operations. We show that, in theory, it is possible to explore the entire MIG representation space by using the new Boolean algebra axioms. In practice, such feature enables powerful MIG algebraic optimization. When algebraic methods cannot improve a result quality, stronger Boolean methods are needed to attain further optimization. For this purpose, we also present MIG Boolean methods exploiting the error masking property of majority operators. Our MIG Boolean methods insert logic errors that strongly simplify an MIG while being successively masked by the voting nature of majority nodes. Thanks to the datastructure/methodology fitness, our MIG Boolean methods run in principle as fast as algebraic counterparts. Experiments show that MIG algebraic and Boolean methods together attain very high optimization quality. For example, when targeting depth reduction, MIG optimization is capable of transforming a ripple carry adder into a carry look-ahead one. Results on state-of-the-art benchmark suites, but also on industrial designs, confirm the efficacy of MIG optimization in a complete design flow, down to physical design.

 

About the speaker:

Luca Amaru is a research assistant and PhD student in Computer Science at EPFL, Integrated Systems Laboratory, Lausanne, Switzerland. He received his Bachelor's Degree in Electronic Engineering, with honors, from Politecnico di Torino, Italy, in 2009. In 2011 he received his double Master's Degree in Electronic Engineering, with honors, from Politecnico di Torino, Italy, and Politecnico di Milano, Italy. In 2014, he was a visiting researcher at Stanford University, Palo Alto, CA, USA.

Mr. Amaru currently works on new data structures and axiomatizations of Boolean logic with application to Electronic Design Automation, under the direction of Prof. De Micheli, Dr. Gaillardon and Prof. Burg.
At present, Mr. Amaru is author or coauthor of 47 technical articles and inventor or coinventor of 6 patents.