Giovanni De Micheli LSI Director and Professor 

Mathias Soeken Postdoctoral Researcher Logic Synthesis 

Heinz Riener Postdoctoral Researcher Logic Synthesis 

Winston Jason Haaswijk PhD Student Logic Synthesis 
PhD project page: SATBased Exact MultiLevel Logic Synthesis 

Eleonora Testa PhD Student Logic Synthesis 
PhD project page: Data Structures and Algorithms for Logic Synthesis in Advanced Technologies 
Logic Synthesis
Nowadays, EDA tools face challenges tougher than ever. On the one hand, design goals in modern CMOS technology approach the frontier of what is physically achievable. On the other hand, postCMOS technologies bring new computational paradigms and logic devices for which standard EDA tools are not suitable. Logic synthesis is directly located at the intersection of application and technology. Its task is to transform a functional and technologyindependent description of an application (e.g., a microprocessor) into a lowlevel description that takes technology and architecture constraints into account (e.g., gate libraries and architectures). Typical considered optimization criteria are physical area, delay, and fabrication costs. At LSI, our research objective is to enable ideal tradeoffs at this interface between technology and application. Our findings allow designers to build better hardware with lower costs.
At LSI, we think that research in logic synthesis is key to address this challenge. In particular, innovative logic data structures and optimization techniques will be decisive. By using expressive Boolean primitives, the efficacy of logic optimization within a standard synthesis flow can be significantly improved. This enables smaller and faster CMOS circuits at lower costs. Considering postCMOS technologies, novel logic abstractions and synthesis techniques capable to fully exploit a device expressive power are the technology enablers. This is because they allow designers to validate a postCMOS technology on largescale benchmarks.
We develop new data structures and optimization methods mainly based on majority and comparator logic connectives. We have demonstrated tremendous improvements in contemporary CMOS design, especially for arithmetic circuits. Indeed, majority and comparators are the basis for arithmetic. Moreover, we have shown that majority data structures are natural and native design abstraction for a promising class of postCMOS technologies. We develop new optimization algorithms based on modern algorithms. As one example, we use SAT solvers at the core of our logic synthesis algorithms.
Majoritybased logic synthesis
The majority function evaluates to true, if at least two of its Boolean inputs evaluate to true. The majority function has frequently been studied as a central primitive in logic synthesis applications for many decades. Knuth refers to the majority function in the last volume of his seminal The Art of Computer Programming as “probably the most important ternary operation in the entire universe.” Majority logic sythesis has recently regained signficant interest in the design automation community due to nanoemerging technologies which operate based on the majority function. In addition, majority logic synthesis has successfully been employed in CMOSbased applications such as standard cell or FPGA mapping.
At LSI, we investigate majoritybased logic synthesis from both a practical and a theoretical perspective. We develop new algorithms optimize logic networks based on majority logic, and find new ways on decomposing large majority operations into networks of smaller ones.
SATbased logic synthesis
Boolean satisfiability solvers have made some remarkable progress in the last decade. They can now be integrated into various largescale logic synthesis algorithms in a robust manner. At LSI we mainly use SAT solvers to solve the exact synthesis problem, which should find a circuit that realizes a function under some input constraints, e.g., the input gate library, the size of the network, or the depth of the network. Besides that, we also use SAT solvers to implement Boolean decomposition and classification algorithms.
Open source software and benchmarks
At LSI, we are maintaining the open source EPFL logic synthesis libraries and the toolkit CirKit. The EPFL logic synthesis libraries contain several offtheshelf and easytointegrate libraries with a dedicated purpose, e.g., logic network representation and manipulation (mockturtle), command line interfaces (alice), logic synthesis file parsing (lorina), exact synthesis (percy), ESOPbased synthesis (easy), or truth table representation and manipulation (kitty).
The toolkit CirKit integrates the EPFL logic synthesis libraries and offers a frontend to invoke the underlying algorithms using a common command line interface. It is used to share algorithms and experimental results with other researchers and as a collaboration tool for research.
Further, we maintain a set of combinational logic synthesis benchmarks, called the EPFL combinational benchmark suite. The benchmark suite was introduced in 2015 with the aim of defining a new comparative standard for the logic optimization and synthesis community. It originally consisted of 23 combinational circuits designed to challenge modern logic optimization tools. The benchmark suite is divided into arithmetic, random/control and MtM (morethanamillion) circuits, and each circuit is distributed in Verilog, VHDL, BLIF and AIGER formats.
EDA for FPGAs
Static Random Access Memory (SRAM)based Field Programmable Gate Arrays (FPGAs) are more flexible than ApplicationSpecific Integrated Circuits (ASICs) at the cost of 20× larger area, 4× longer delay, and 12× higher power consumption approximately. The drawbacks of FPGAs lie in the expensive routing architecture, which accounts for about 70% of the area, 80% of the delay and 60% of the power of the entire chip. Power consumption is a serious barrier for the distribution of FPGAs in a large set of consumer applications, i.e., UltraLow Power (ULP) SystemonChip (SoCs). Previous works demonstrate lowpower SRAMbased FPGA designs where a low supply voltage is employed to save up to 50% of the power consumption. However, lowpower SRAM based FPGAs generally suffer from large delay degradation (up to 2×).