Data Structures and Algorithms for Logic Synthesis in Advanced Technologies

Logic synthesis is a key component of digital design and modern EDA tools; it is thus an essential instrument for the design of leading-edge chips and to push the limits of their performance. In the last decades, the electronic circuits community has evolved dramatically, facing many technological changes. Consequently, EDA and logic synthesis have adapted to accurately design the new generation of digital systems. In the present day, logic synthesis is an important area of research for two main reasons: (i) Diverse ways of computation, alternative to CMOS, have been presented in the last years. Post-silicon technologies have been shown to be feasible and may provide us with better electronic devices. Similarly, novel areas of applications are emerging, ranging from deep learning to cryptography applications. (ii) The current computing and storage means make it possible to solve exactly problems that were only approximated before. Moreover, new reasoning engines, covering from deep learning to new SAT-solvers, can be used as a mean of computation, thus possibly unlocking novel optimization opportunities.

The objective of this thesis is to advance state-of-the-art logic synthesis and present a variety of novel data structures and algorithms, addressing diverse types of applications in modern logic synthesis flows, considering standard CMOS design as well as emerging technology and cryptography.

Motivated by the many emerging technologies that implement majority gates, we first focus on majority-based logic synthesis. We present algorithms over the recently introduced majority-inverter graphs. First, a size optimization flow based on Boolean transformations is proposed. Then, we demonstrate how technology-dependent logic synthesis is an essential step for the abstraction of majority-based emerging technologies and, more important, their technological constraints. Moreover, we advance theoretical results on majority logic. In particular, we mainly focus on the problem of ''how best can the n-argument majority function (majority-n) be realized with a network of 3-input majority gates?''. For this purpose, we present general upper bounds and decompositions, together with optimum results for majority-5 and -7 and best-known results for the majority-9. In the second part, we shift into more pragmatic results and show practical aspects of logic synthesis, designed to be successful in modern logic synthesis flows. We focus on XOR-based logic synthesis. Motivated by the novel computing capabilities, we propose an optimization flow based on the Boolean difference for area optimization of standard CMOS technologies. Finally, we establish a novel application of logic synthesis to cryptography. It has been demonstrated that the number of AND gates in a xor-and graph (XAG) correlates with the degree of vulnerability (security) of cryptography benchmarks and plays an important role for high-level cryptography protocols. We thus introduce a complete and automatic synthesis flow which consists of the main transformations of logic synthesis but aims instead at minimization of the number of AND gates over XAGs, obtaining significant results over cryptography benchmarks.

We argue that given the progress and novel opportunities of technology, logic synthesis has to be revisited to consider the plurality of primitives and novel engines that can be of interest, and, consequently, the corresponding objective functions and optimisation problems.

New Data Structures and Algorithms for Logic Synthesis and Verification

Luca Gaetano Amarù

The strong interaction between Electronic Design Automation (EDA) tools and Complementary Metal-Oxide Semiconductor (CMOS) technology contributed substantially to the advancement of modern digital electronics. The continuous downscaling of CMOS Field Effect Transistor (FET) dimensions enabled the semiconductor industry to fabricate digital systems with higher circuit density at reduced costs. To keep pace with technology, EDA tools are challenged to handle both digital designs with growing functionality and device models of increasing complexity. Nevertheless, whereas the downscaling of CMOS technology is requiring more complex physical design models, the logic abstraction of a transistor as a switch has not changed even with the introduction of 3D FinFET technology. As a consequence, modern EDA tools are fine tuned for CMOS technology and the underlying design methodologies are based on CMOS logic primitives, i.e., negative unate logic functions. While it is clear that CMOS logic primitives will be the ultimate building blocks for digital systems in the next ten years, no evidence is provided that CMOS logic primitives are also the optimal basis for EDA software. In EDA, the efficiency of methods and tools is measured by different metrics such as (i) the result quality, for example the performance of a digital circuit, (ii) the runtime and (iii) the memory footprint on the host computer. With the aim to optimize these metrics, the accordance to a specific logic model is no longer important. Indeed, the key to the success of an EDA technique is the expressive power of the logic primitives handling and solving the problem, which determines the capability to reach better metrics. In this thesis, we investigate new logic primitives for electronic design automation tools. We improve the efficiency of logic representation, manipulation and optimization tasks by taking advantage of majority and biconditional logic primitives. We develop synthesis tools exploiting the majority and biconditional expressiveness. Our tools show strong results as compared to state-of-the-art academic and commercial synthesis tools. Indeed, we produce the best results for several public benchmarks. On top of the enhanced synthesis power, our methods are the natural and native logic abstraction for circuit design in emerging nanotechnologies, where majority and biconditional logic are the primitive gates for physical implementation. We accelerate formal methods by (i) studying properties of logic circuits and (ii) developing new frameworks for logic reasoning engines. We prove non-trivial dualities for the property checking problem in logic circuits. Our findings enable sensible speed-ups in solving circuit satisfiability. We develop an alternative Boolean satisfiability framework based on majority functions. We prove that the general problem is still intractable but we show practical restrictions that can be solved efficiently. Finally, we focus on reversible logic where we propose a new equivalence checking approach. We exploit the invertibility of computation and the functionality of reversible gates in the formulation of the problem. This enables one order of magnitude speed up, as compared to the state-of-the-art solution. We argue that new approaches to solve EDA problems are necessary, as we have reached a point of technology where keeping pace with design goals is tougher than ever.

EPFL2015

Single-Photon Techniques for Standard CMOS Digital ICs

Claudio Favi

The advent of single-photon detectors known as Single-Photon Avalanche Diodes in standard CMOS technology opened the way to new perspectives in integrating these ultra sensitive light sensors with digital logic. Light has some interesting properties that attracted researchers in computer and electronics for a long time. Its weightlessness nature makes it a candidate to replace electrons when it didn't already do so. This is particularly true for long distance data transfers. However a new trend can be observed. Researchers are looking into photonics, the science of light, for short distance communications as well. Power efficiency is one of the reasons of this trend. In fact, photons, the elementary particles of light, don't suffer of resistive, capacitive, or inductive effects like electrons do. The wavelike nature of light can also free designers from problems such as cross-talk and side-channel noise injection while taking advantage of interference. However photonics is still not the panacea and we don't believe it will ever completely replace electronics. Most certainly a combination of the two will be adopted to take advantage of both worlds. CMOS digital Integrated Circuit (IC) design faces many challenges and it is not clear whether technology will still provide small footprints, high performance, and low power in the future. Photonics with SPADs can answer some of these questions. In this work, we present three investigations where SPAD photonics is integrated within digital CMOS technology. The main contributions of this thesis are threefold: single-photon CMOS communication paradigms, single-photon processing and readout techniques, single-photon clocking and synchronization methods. Single-photon communication was achieved using a combination of SPADs and ultra-fast TDCs in a pulse position modulation scheme. In this context, theoretical channel capacity limits in the presence of noise and other non-idealities typical of SPADs were derived; a TDC with a resolution of 17 ps was demonstrated in a standard FPGA fabric. To the best of our knowledge, at the time of this writing, this is the highest reported resolution for a TDC of this kind. Single-photon processing and readout was achieved in several technologies, focusing on image sensor design, whereby massive parallel architectures were studied and implemented in CMOS. Single-photon clocking and synchronization was demonstrated allowing potentially zero skew systems irrespective of the chip area. The power benefits of this approach in embedded systems with instruction set extensions are particularly interesting. The thesis makes use of SPAD technology implemented in CMOS for a number of applications creating a bridge between digital design and high performance photonics. We believe that this is the first attempt in this direction focused on CMOS technology.

EPFL2011

SOI mixed-mode design techniques and case studies

Marija Blagojevic

Since the emergence of Silicon On Insulator (SOI) technology the research activities have been concentrated on a detailed analysis of SOI devices and their use in different application fields (low-voltage, low-power circuits, high temperature electronics, digital circuits, etc.). The present thesis deals with low-voltage, low-power mixed-mode design using a SOI technology. The goal is to establish the concepts that allow one to design SOI mixed-mode circuits, and to apply these concepts to the design of fully depleted (FD) and partially depleted (PD) SOI circuits and systems. Two studies have been realized in the scope of this work: a Hall sensor based microsystem design using an experimental FD SOI technology a DRAM design using capacitor-less 1T floating-body PD SOI memory cells. At the beginning of this thesis, two major types of SOI devices are introduced, namely FD and PD devices. The most important properties of these devices are then presented and compared to those of CMOS bulk devices. A design methodology based on design retargeting from bulk to SOI technology is further proposed. This methodology is developed with the aim of being implemented for the design of FD SOI circuits. It consists in using the same device dimensions and bias currents for the bulk and the corresponding FD SOI design. The analysis performed proves that such an approach permits one to obtain better circuit performances using the FD SOI technology. The EKV model is chosen for Spice simulations. For that purpose the extraction of the EKV intrinsic parameters has been performed for the experimental 0.5 μm FD SOI technology. The EKV model card obtained from transistor measurements is implemented straightforwardly for circuit simulations. The first study presented in this thesis is an FD SOI Hall sensor front-end for energy measurement. The mixed-mode microsystem design is completely based on the proposed design methodology. The system level solutions are also included, such as the spinning-current method that serves for reduction of the offset and low frequency noise of the analog front-end, and a high resolution analog-to-digital conversion technique. The integrated microsystem is entirely functional. Furthermore, according to the existing literature, this integrated circuit is the first microsystem completely realized using FD SOI technology. The overall system error that is obtained is less than 1.5 %. During the second part of this work, a novel sensing scheme that exploits an automatic reference generation based on successive approximations has been developed for the PD SOI capacitor-less 1T DRAM. The 1T DRAM reference current is generated by an adjustable current source. The electrical calibration of the reference current is performed using a digital-to-analog converter and successive approximations algorithm. The proposed scheme is evaluated in a 2 kb test chip. The circuit integrated using PD SOI technology contains a 2 kb 1T memory array, as well as automatic reference generators and peripheral circuits. The automatic reference generator comprises current mode sense amplifier, M/3M converter, and successive approximations register. All blocks implemented in the test chip are described in detail, and PD SOI design issues are discussed. A number of experimental results demonstrate the potential of the PD SOI 1T DRAM for future embedded DRAM applications. The measured retention time under holding conditions is higher than 1s. In the continuous read mode, a few hundreds of the read cycles can be performed without a refresh operation. The test chip has a measured access time of 25 ns with a read cycle time of 70 ns.

EPFL2005