Data Structures and Algorithms for Logic Synthesis in Advanced Technologies

EDIC candidacy exam
Exam president: Prof. Paolo Ienne
Thesis advisor: Prof. Giovanni De Micheli
Co-examiner: Prof. Viktor Kuncak

Abstract
Majority logic has recently gained much popularity; it has been employed in logic synthesis to optimize Boolean functions, and it naturally abstracts many emerging nanotechnologies. Majority logic is closely related to threshold logic, which is at the core of many neural networks. In this research plan, three papers on majority logic are presented: the first work (1962) presents a majority-based synthesis procedure that works with truth tables; the second paper (2016) introduces Majority-Inverter Graphs (MIGs), a data structure for Boolean functions based on the 3-input majority function; the last paper (2007) concerns the application of logic synthesis in nanotechnology. A detailed research plan is presented, focusing mainly on algorithms based on majority and threshold logic. The theoretical results in our research are validated on nanotechnology applications in a practical context.

Background papers
S. B. Akers. : Synthesis of combinational logic using three-input majority gates. SWCT, pages 149-157, 1962.
L.Amaru, P.-E. Gaillardon, and G. De Micheli: Majority-inverter graph: a new paradigm for logic optimization. TCAD, 35(5):806-819,2016.
R. Zhang, P. Gupta, and N. K. Jha. : Majority and minority network synthesis with application to QCA-, TPL- and SET- based
nanotechnologies. TCAD, 26(7):1233-1245, 2007.