Logic Synthesis and Digital Design

Giovanni De Micheli
LSI Director and Professor
Mathias Soeken
Postdoctoral Researcher
Logic Synthesis
Heinz Riener
Postdoctoral Researcher
Logic Synthesis
Winston Haaswijk Winston Jason Haaswijk
PhD Student
Logic Synthesis
PhD project page:
SAT-Based Exact Multi-Level 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, post-CMOS 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 technology-independent description of an application (e.g., a microprocessor) into a low-level 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 post-CMOS 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 post-CMOS technology on large-scale 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 post-CMOS 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.

Majority-based 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 CMOS-based applications such as standard cell or FPGA mapping.

At LSI, we investigate majority-based 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.

SAT-based logic synthesis

Boolean satisfiability solvers have made some remarkable progress in the last decade. They can now be integrated into various large-scale 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 off-the-shelf and easy-to-integrate 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), ESOP-based synthesis (easy), or truth table representation and manipulation (kitty).

The toolkit CirKit integrates the EPFL logic synthesis libraries and offers a front-end 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 (more-than-a-million) 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 Application-Specific 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., Ultra-Low Power (ULP) System-on-Chip (SoCs). Previous works demonstrate low-power SRAM-based FPGA designs where a low supply voltage is employed to save up to 50% of the power consumption. However, low-power SRAM- based FPGAs generally suffer from large delay degradation (up to 2×).