Data Structures and Algorithms for Logic Synthesis in Advanced Technologies


Eleonora Testa, PhD student, EPFL-IC-LSI
Mathias Soeken, Post-doc, EPFL-IC-LSI
Giovanni De Micheli, Professor, EPFL-IC-LSI


Logic synthesis is an enabling technology to realize integrated computing systems, and it entails solving computationally-intractable problems through a plurality of heuristic techniques. A recent push towards further formalization of synthesis problems has shown to be very useful towards both attempting to solve some logic problems exactly—which is computationally possible for instances of limited size today—as well as creating new and more powerful heuristics based on problem decomposition. Moreover, technological advances including nano-devices, optical computing, and quantum cellular computing require new and specific synthesis flows to assess feasibility and scalability.

There are many theoretical and experimental arguments that majority logic has several advantages compared to currently used logic synthesis representations. Preliminary investigations clearly confirm these capabilities, but the surface of the full potential has barely been scratched.


This PhD project aims at following up the investigations on majority logic and to develop logic synthesis algorithms and applications based on it. It concentrates on new data structures and algorithms, in particular on majority and majority-n logic synthesis. It also focuses on disruptive computation paradigms offered by emerging nanotechnologies. Examples of majority- based beyond CMOS technologies include, but are not limited to, Quantum-dot Cellular Automata (QCA), NanoMagnet Logic, spin-based devices, and plasmonic-based devices.

Main publications available here