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.