Logic synthesis for established and emerging technologies

Dewmini Marakkalage, Alessandro Tempia-Calvino, Andrea Costamagna and Giovanni De Micheli

Logic synthesis is the task of transforming (and optimizing) a description of a digital circuit from a high-level abstraction to the interconnection of logic gates to be placed and routed. Logic synthesis entails solving computationally-intractable problems through a plurality of heuristic techniques. Logic synthesis is a necessary step in the design of integrated circuits and is highly responsible for their quality in terms of Performance, Power, and Area (P/P/A).

In the last two decades, electronic circuits and digital systems have evolved rapidly, facing many new architectural and technological changes. Consequently, Electronic Design Automation (EDA) and logic synthesis have adapted and changed to be able to accurately design the new generation of digital systems. Nowadays, logic synthesis is an important area of research for two main reasons: (i) Many and diverse ways of computation, alternative to the established CMOS technology, have been presented in the last years. Post-silicon technologies, called emerging technologies, have been shown to be feasible and may provide us with better – more efficient – electronic devices. In a similar way, novel areas of applications of logic synthesis are emerging, ranging from deep learning to cryptography and security 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 and enabling hardware of higher quality.

Technology-Aware Logic Synthesis For High-Performance Hardware

We search for new strategies for optimizing circuits after mapping, focusing on metrics such as area, delay, and power. Traditionally, logic synthesis optimizes circuits in two steps: first, a technology-independent circuit representation is optimized, next, the circuit is mapped to an interconnection of gates in a given technology. The motivation behind the two-step approach is the desire for higher quality and scalability. In this paradigm, the optimization of the technology-independent representation is guided by simple cost functions, that are assumed to correlate with some optimization metrics after mapping. For instance, reducing the number of gates and logic levels in the technology-independent representation is considered an effective heuristic for reducing area and delay after mapping. However, experimental evidence shows that high-effort optimization of the technology-independent representation, using the technology-independent cost functions, does not always correlate with corresponding benefits in the mapped circuit. Our research aims at i) investigating the validity of the technology-independent assumptions, ii) to introduce more technological information at the logic synthesis level, and iii) to perform logic optimization directly on mapped circuits.

Logic synthesis flow

Scalable and Generic Logic Synthesis

This research proposes a new logic synthesis and verification paradigm based on circuit simulation. In this paradigm, high-quality, expressive simulation patterns are pre-generated to be reused in multiple runs of optimization and verification algorithms, resulting in reduced time-consuming Boolean computations such as SAT-solving. Methods to generate expressive simulation patterns are presented and compared, and a bit-packing technique to compress them is integrated into the implementation. We show that the generated patterns are reusable across different algorithms and after network incrementa improvements.

A logic synthesis algorithm, Boolean resubstitution, and a verification algorithm, combinational equivalence checking, are two examples of using this paradigm. In simulation-guided Boolean resubstitution, simulation patterns are used for efficient filtering of optimization choices, leading to a lower cost in expanding the search space. By adopting the proposed paradigm, we achieve a 5.9% reduction in the number of network graph nodes (AIG), compared to 3.7% by a state-of-the-art resubstitution algorithm, within comparable runtime. In simulation-guided equivalence checking, the number of SAT solver calls is reduced by 9.5% with the use of the expressive simulation patterns accumulated in earlier logic synthesis stages.

Logic mapping and restructuring

This research addresses the design of a versatile logic mapping and restructuring tool with two objectives: i) it can transform a logic network from one technology-independent graph representation to another; ii) it can map a logic network to a cell library.

Automatic manipulation and optimization of logic networks

The motivation for the first task is the following. Originally, 2-input NANDs and NORs, together with inverters, were used as primitives in graph representations thanks to their universality. As logic synthesis evolved, the And-Inverter graph (AIG) became the most common technology-independent representation. As an alternative, Majority-Inverter graphs(MIGs) have been proposed and motivated by a more expressive potential and by majority-based emerging technologies, e.g., quantum-dot cellular automata. Additionally, Xor-And graphs (XAGs) and Xor-Majority graphs (XMGs) have been proposed for their compactness in arithmetic circuits and as a basis for logic rewriting. Recently, 3-input gates have also been explored as new graph representations to address logic synthesis.

Since multiple graph representations are available to support logic synthesis, we developed the first mapper that supports mapping across graph representations and cell libraries while optimizing the circuit for delay or area. Thus, these steps support the mapping of networks of various kinds to cell libraries. Our mapper can also be used as an optimization tool for logic restructuring.

In the experiments, we showed that our approach enables an average reduction up to 27% and 40 % in size and depth respectively when mapping for size reduction from AIGs to MIGs in the EPFL benchmark suite. We then showed that our approach leads to better results when used for logic restructuring reducing the average size by 10% and 14% further as compared to LUT-based rewriting and cut rewriting methods. Finally, we map to a standard cell library and compare it to ABC showing an average improvement of 1.75%, 0.10%, and 18% in area, delay, and total run-time respectively.

Three-Input Gates for Logic Synthesis

Most logic synthesis algorithms work on graph representations of logic functions. In such representations, nodes are associated with arbitrary logic expressions or simple logic functions. A popular approach in this regard is to consider homogeneous representation where all nodes are associated with the same (up to fanin-in and fanout inversions) logic function. A widely used such representation is the And-Inverter graph (AIG) where each node is a 2-input And gate. Recently, EPFL researchers at LSI have proposed a new paradigm for logic synthesis where Majority-Inverter graphs (MIG) are used as the logic representation and successfully demonstrated its effectiveness for logic optimizations.

Pushing the idea of using 3-input primitives even further, we have studied the suitability of other 3-input gates as logic primitives. There are ten 3-input NPN classes that depend on all three variables. In this regard, we have evaluated the expressive powers of different 3-input logic functions and shown that the 3-input Dot ( x xor (z or xy)) and Onehot ( xy’z’ xor x’yz’ xor x’y’z) gates exhibit the highest expressibility.

The 10 3-input logic functions relevant for synthesis

The high expressive power of Dot gates yields concise logic representations, and hence, Dot-Inverter Graphs (DIG) are attractive candidates for technology-independent intermediary logic representations. Optimization algorithms can run faster with less memory on smaller logic representations. Moreover, this also inspires emerging technologies to consider physical implementations of Dot gates.

Our current research focuses on developing improved synthesis algorithms for these non-traditional representations. Specifically, we try to understand the manipulation capabilities of homogenous logic representations with different 3-input primitives.

Majority synthesis

The majority function is a logic function of an odd number of inputs that evaluates to TRUE if the number of inputs assigned to TRUE outnumbers those assigned to FALSE. For typical 3-input functions, the function is TRUE when at least two of its inputs evaluate to TRUE, and thus used to compute the carry in adders. The majority function has frequently been studied as a central primitive in logic synthesis applications for many decades. As an example, Donald Knuth refers to the majority function as “probably the most important ternary operation in the entire universe.” Despite many years of study, effective EDA tools based on the majority function were developed only recently at EPFL/LSI. Current research at LSI investigates majority-based logic synthesis from both a theoretical and a practical perspective. We develop new algorithms to optimize logic networks based on majority logic, and find new ways on decomposing large majority operations into networks of smaller ones.

The new data structures and optimization methods researched at EPFL/LSI are mainly based on majority and comparator logic connectives. We have demonstrated large improvements in contemporary CMOS design, especially for arithmetic circuits. Indeed, majority and comparators are the basis for arithmetic. We also research algorithms for the exact decomposition of large majority functions into smaller primitives. In particular, even the decomposition of the 9-input majority function into 3-input primitives turns out to be an open problem.

Decomposition of majority-9 into a network of majority-3. The optimum solution is unknown

Exact synthesis and synthesis for enhanced security

Exact synthesis aims at finding optimum representations of logic circuits in some metric. As the problem is computationally intractable, only circuits of limited size can be exactly optimized. Nevertheless, exact solutions shed some light on some logic network structures.

Boolean satisfiability (SAT) 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 EPFL/LSI we 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.

We have also established a way to measure resilience to security attacks to logic circuits. We leveraged a classic result by Boyer and Peralta linking the circuit vulnerability to the multiplicative complexity of a logic function. We devised a new automatic synthesis flow that aims at minimization of the number of AND gates in an EXOR - AND network graph (XAG) which is an upper bound on the multiplicative complexity. Our tool and methods obtain significant results over both EPFL and cryptography and security benchmarks.

Optimization of number of AND gates over XAGs for cryptography applications

Synthesis for emerging technologies

We have shown that majority data structures are natural and native design abstraction for a promising class of post-CMOS technologies. Examples include Spin-Wave (SW) devices, Quantum-dot Cellular Automata (QCA), NanoMagnet Logic, Plasmonic-based devices and Superconducting electronics. Majority logic-based algorithms and tools are crucial to map technology-independent logic representations to netlists of gates in these technologies. In particular, it was shown that majority logic can outperform other techniques for SW and QCA technologies. New computational structures for fast parallel multipliers with plasmonic technology have also been shown to be promising. Emerging technologies follow different operational principles as compared to established CMOS technologies and demand for novel abstractions, data structures, and optimization algorithms. The advantages of these new technologies are demonstrated in theory and crafted examples, but the real potential in comparison to conventional technologies remains unknown because complete design flows from logic to technology as well as realistic benchmarks do not exist. To address this research gap, software infrastructure and tool support for new technologies have been developed.

Examples of majority-based emerging technologies

Open science software and benchmarks

EPFL/LSI has a large effort aimed at developing logic synthesis design tools, libraries and benchmarks that are made publicly available. In the last four years, we developed a collection of modular software libraries and benchmarks to support various logic synthesis applications. Nowadays, the EPFL Logic Synthesis Libraries consist of several C++ libraries designed for the development of logic synthesis applications. This includes a command-shell library (alice), a library for parsing file formats used in logic synthesis and formal verification (lorina), a library to represent logic networks (mockturtle), libraries for efficient manipulation of truth tables (kitty) and exclusive-or sum-of-products expressions (easy), an exact synthesis libraries (percy) and libraries for supporting quantum compilation (tweedledum) and quantum circuit synthesis (caterpillar). Together with these libraries, open EDA benchmarks suites have been developed to challenge existing EDA design tools in different applications.

The EPFL Logic Synthesis Libraries and Benchmarks aim at building up an active open-source community in the field of logic synthesis as well as developing a methodology to share best practices and support new libraries and benchmarks in the EDA field. The libraries provide state-of-the-art solutions for standard tasks that can be readily composed in a plug-and-play fashion to address advanced synthesis and verification problems. This allows scientists to focus on more complex tasks in their research and eases the comparison to the state of the art in a unified framework. The benchmarks serve as a comparative standard to evaluate the performance and quality of logic synthesis and optimization algorithms.

Open source development & community-building

The developed libraries and benchmarks are open source and freely accessible to the community via the web-based version control service GitHub, which allows users to manage changes/releases of the software/benchmarks and provides a community platform to interact with other researchers and developers. It allows its users to keep track of issues such as tasks, enhancements, and bug reports, to review and to discuss code contributions, and to improve correctness and code quality using continuous integration services and automated testing. Moreover, open-source development targets rigor documentation of subtle algorithmic details, reproducibility of experimental results, and building up a research and development community that keeps the project alive beyond its funding period.

Modular ecosystem for logic synthesis

The developed libraries are further intended to form an ecosystem for the development of logic synthesis applications. Each library modularly deals with one specific aspect of a logic synthesis application, e.g., parsing of specific benchmark formats or providing an efficient implementation of a specific commonly-used data structure. Existing libraries are designed to be easily modifiable and extensible using modern programming techniques such as template meta-programming and concept-oriented design. The modularity of the libraries allows scientists to compose complex logic synthesis applications from existing state-of-the-art components, such that they can focus on specific and novel research challenges. Furthermore, the developed software solutions can be integrated into the library infrastructure and shared with other researchers guarantying better reproducibility and comparability of results.

Comparability of experimental results

The libraries enable improved comparability of experimental results by providing state-of-the-art algorithmic solutions for complex logic synthesis applications. The freely available software implementations allow researchers to evaluate new algorithms and data structures by comparing them to state-of-the-art implementations. Moreover, due to the availability of a large number of existing logic optimizations, the overall impact of new algorithms and data structures can be analyzed in complete design flows. This analysis is crucial to guarantee that experimental improvements are significant in the overall application and can be well combined with other existing optimizations.

Distribution of knowledge

The industrial need for high-end logic synthesis algorithms in the EDA field makes algorithms often particularly challenging to understand or re-implement. The libraries are well-document and provide open glass-box implementations. These open implementations make the libraries readily usable for educational purposes, e.g., as supplemental learning material for logic synthesis courses or as the basis for coding exercises. They allow students as well as researchers to study subtle implementation details and to try out the effect of modifications on the algorithms and data structures.

Downloads

EPFL/LSI open source libraries are available in the logic synthesis library showcase repository.

Large-scale combinatorial logic benchmarks are available in the logic synthesis benchmarks repository and on Zenodo.

CirKit and RevKit tools for classical logic optimization and quantum compilation, respectively, are available in the CirKit and RevKit repository.

Engineering changing order (ECO) benchmarks are available here.

Main recent publications

D. Marakkellage and G. De Micheli, Fanout-Bounded Logic Synthesis for Emerging Technologies, IEEE Transactions on Computer Aided Design (TCAD) (early access).
A.Costamagna and G.De Micheli, Accuracy recovery: A Decomposition Procedure for the Synthesis of Partially-specified Boolean Functions, Integration, the VLSI Journal 89, 2003, pp.248-260.
S.-Y. Lee and G. De Micheli, Heuristic Logic Resynthesis Algorithms at the Core of Peephole Optimization, TCAD (early access)
S. Rai, A. Tempia Calvino, H. Riener and G. De Micheli, Utilizing XMG-based Synthesis to Preserve Self-Duality for RFET-Based Circuits, IEEE TCAD, Vol. 452, No. 3, March 2023, pp. 914-927.
D. Sudara Marakkalage and G. De Micheli, Fanout-Bounded Logic Synthesis for Emerging Technologies - A Top-Down Approach, Proceedings of DATE, March 2023.
A.Tempia Calvino, Al. Mishchenko, H. Schmit, E. Mahintorabi, G. De Micheli1, and X. Xu, Improving Standard-Cell Design Flow using Factored Form Optimization, DAC 2023.
G. De Micheli, Logic Synthesis for Emerging Technologies, Proceedings ASICON, Nanjing, 2023.
A. Tempia Calvino and G. De Micheli, Technology Mapping using Multi-output Library cells, Proceedings ICCAD, 2023.
A. Costamagna and G. De Micheli, Logic Synthesis From Incomplete Specifications Using Disjoint Support Decomposition, Prime, Cagliari, 2022.
D. S. Marakkalage, E. Testa, H. Riener, A. Mishchenko, M. Soeken and G. De Micheli, Three-Input Gates for Logic Synthesis, IEEE Transactions on CAD , Vol. 40, No. 10, October 2021, pp. 2184-2188.
S.Y. Lee, A. Mishchenko, H. Riener and G. De Micheli, A Simulation-Guided Paradigm for Logic Synthesis and Verification, IEEE TCAD vol. 41, no. 8, pp. 2573-2586, Aug. 2022.
H. Riener, S.-Y. Lee, A. Mishchenko and G.De Micheli Boolean Rewriting Strikes Back: Reconvergence- Driven Windowing meets Resynthesis, Proceedings ASPDAC, January 2022.
A. Tempia Calvino, H. Riener, S.Rai A. Kumar and G. De Micheli A Versatile Mapping Approach for Technology Mapping and Graph Optimization, Proceedings ASPDAC, January 2022.
S-Y Lee, H. Riener and G. De Micheli, Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition, DDECS, Vienna, April 2021.
L. Amaru, V. Possani, E. Testa, F. Marranghello, C.Casares, J. Luo, P. Vuillod, A. Mishchenko and G. De Micheli, LUT-Based Optimization For ASIC Design Flow, Design Automation Conference, San Francisco, CA, 2021. rs and Actuators B: Chemical, 328, February 2021.
D. S. Marakkalage, E. Testa, H. Riener, A. Mishchenko, M. Soeken,and G. De Micheli, “Three-input gates for logic synthesis,” 29th International Workshop on Logic and Synthesis (IWLS),Virtual Conference, July 27-30, 2020
D. S. Marakkalage, E. Testa, H. Riener, A. Mishchenko, M. Soeken and G. De Micheli, "Three-Input Gates for Logic Synthesis," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, doi: 10.1109/TCAD.2020.3032625
Siang-Yun Lee, Heinz Riener, Alan Mishchenko, Robert K. Brayton, and Giovanni De Micheli. "Simulation-Guided Boolean Resubstitution," 2020 International Workshop on Logic and Synthesis (IWLS)
Siang-Yun Lee, Heinz Riener, Alan Mishchenko, Robert K. Brayton, and Giovanni De Micheli. "Simulation-Guided Logic Synthesis and Verification," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD).
Siang-Yun Lee, Heinz Riener, and Giovanni De Micheli. "Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition," 2021 International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS).
Heinz Riener, Siang-Yun Lee, Alan Mishchenko, and Giovanni De Micheli. "Boolean Rewriting Strikes Back: Reconvergence-Driven Windowing Meets Resynthesis," 2021 International Workshop on Logic and Synthesis (IWLS).
E. Testa, M. Soeken, L.G. Amaru, G. De Micheli, Logic Synthesis for Established and Emerging Computing, Proceedings of the IEEE. vol. 107, no. 1, pp. 165–184. 2019.
Z. Chu, M. Soeken, Y. Xia, L. Wang, G. De Micheli, Advanced Functional Decomposition Using Majority and Its Applications, Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019.
W. Haaswijk, M. Soeken, A. Mischenko, G. De Micheli, SAT-based Exact Synthesis: Encoding, Topology Families and Parallelism, IEEE Transactions on CAD, February 2019.
E. Testa, M. Soeken, L. Amaru, G. De Micheli, Reducing the Multiplicative Complexity in Logic Networks for Cryptography and Security Applications, DAC 2019, Las Vegas, USA, June 2019.
M. Soeken, E. Testa, A. Mishchenko, G. De Micheli, Pairs of majority-decomposing functions, Information Processing Letters, vol. 139, pp. 35–38. 2018.
E. Testa, M. Soeken, L. Amaru, W. Haaswijk, G. De Micheli, Mapping Monotone Boolean Functions into Majority, IEEE Transactions on Computers, 2018.
W. J. Haaswijk, A. Mishchenko, M. Soeken, G. De Micheli, SAT Based Exact Synthesis using DAG Topology Families, Proceedings of the ACM/IEEE Design Automation Conference (DAC), pp. 1–6. San Francisco, CA, USA. June 2018.
H. Riener, E. Testa, L. Amaru, M. Soeken, and G. De Micheli, Size Optimization of MIGs with an Application to QCA and STMG Technologies, 14th IEEE / ACM International Symposium on Nanoscale Architectures (NANOARCH), Athens, Greece, 2018.
M. Soeken, L. Amaru, P.-E. Gaillardon and G. De Micheli, Exact Synthesis of Majority-Inverter Graphs and Its Applications, in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 36, num. 11, pp. 1842–1855, 2017.
L. Amaru, P.-E. Gaillardon, A. Chattopadhyay and G. De Micheli, A Sound and Complete Axiomatization of Majority-n Logic, in IEEE Transactions on Computers, vol. 65, num. 9, pp. 2889–2895, 2016.
L. Amaru, P.-E. Gaillardon and G. De Micheli, Majority-Inverter Graph: A New Paradigm for Logic Optimization, in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 35, num. 5, pp. 806–819, 2016.
H. Riener, W. Haaswijk, A. Mishchenko, G. De Micheli, and M. Soeken, On-the-fly and DAG-aware: Rewriting Boolean Networks with Exact Synthesis, DATE 2019, Firenze, Italy, March 2019.
E. Testa, L. Amaru, M. Soeken, A. Mishchenko, P. Vuillod, J. Luo, C. Casares, P.-E. Gaillardon, G. De Micheli, Scalable Boolean Methods in a Modern Synthesis Flow, DATE 2019, Firenze, Italy, March 2019.
L. Amaru, P.-E. Gaillardon, S. Mitra and G. De Micheli, New Logic Synthesis As Nanotechnology Enabler (invited paper), in Proceedings of the IEEE, vol. 103, num. 11, pp. 2168–2195, 2015.
E. Testa, M. Soeken, H. Riener, L. Amaru, G. De Micheli, A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks, DATE 2020, Grenoble, France, March 2020.
H. Riener, E. Testa, W. Haaswijk, A. Mishchenko, L. G. Amaru, G. De Micheli, M. Soeken, Scalable Generic Logic Synthesis: One Approach to Rule Them All, DAC 2019, Las Vegas, NV, USA, June 02-06, 2019.
M. Soeken, H. Riener, W. Haaswijk, E. Testa, B. Schmitt, G. Meuli, F. Mozafari, G. De Micheli, The EPFL Logic Synthesis Libraries, ArXiv 1805.05121v2, 2019.