Sequential logic synthesis expands the solution space compared to combinational logic synthesis by reasoning about the reachable states of memory elements, leading to better Power-Performance-Area (PPA) outcomes. As gate costs continue to rise in advanced technologies, sequential logic synthesis is gaining significant traction within the EDA community as a powerful alternative. This paper introduces a scalable algorithm for don’t-care-based sequential logic synthesis, leveraging sequential k-step induction to perform redundancy removal and resubstitution under Sequential Observability Don’t Cares (SODCs). SODCs generalize Observability Don’t Cares (ODCs) by explicitly considering reachable states, making SODC-based optimization a challenging problem due to dependencies and alignment issues between the base case and inductive case in k-step induction. Our approach overcomes these challenges, fully utilizing the potential of SODCs without limiting the solution space. We rigorously prove the correctness of our approach, discuss some limitations arising from bounded-step induction, and analyze how our approach can effectively be used in practice to exploit obscure optimization opportunities. Implemented as part of an industrial tool, our algorithm achieves an average -6.9% area improvement after technology mapping compared to state-of-the-art sequential synthesis methods, and further provides 3.16% and 1.06% reductions in combinational and sequential areas, respectively, in post place-and-route results. Furthermore, all optimizations are efficiently verified using industrial sequential verification tools.

Sequential logic synthesis can provide better Power-Performance-Area (PPA) than combinational logic synthesis since it explores a larger solution space. As the gate cost in advanced technologies keeps rising, sequential logic synthesis provides a powerful alternative that is gaining momentum in the EDA community. In this work, we present a new scalable algorithm for don't-care-based sequential logic synthesis. Our new approach is based on sequential k-step induction and can apply both redundancy removal and resubstitution transformations under Sequential Observability Don't Cares (SODCs). Using SODC-based optimizations with induction is a challenging problem due to dependencies and alignment of don't cares among the base case and the inductive case. We propose a new approach utilizing the full power of SODCs without limiting the solution space. Our algorithm is implemented as part of an industrial tool and achieves a 6.9% average area improvement after technology mapping when compared to state-of-the-art sequential synthesis methods. Moreover, all the new sequential optimizations can be verified using state-of-the-art sequential verification tools.

Design flows are the explicit combinations of design transformations, primarily involved in synthesis, placement, and routing processes, to accomplish the design of integrated circuits (ICs) and system-on-chip (SoC). Mostly, the flows are developed based on the knowledge of the experts. However, due to the large search space of design flows and the increasing design complexity, developing intellectual property (IP)-specific synthesis flows providing high quality of result (QoR) is extremely challenging. In recent years, machine learning (ML) has been increasingly used in electronic design automation (EDA), with the goal of reducing manual labor and speeding up the design closure process in current toolflows. Existing techniques, on the other hand, either necessitate a huge amount of labeled data and time-consuming training, or are constrained in terms of practical EDA toolflow integration due to computational overhead. This article presents a generic end-to-end sequential decision making framework FlowTune for synthesis tooflow optimization, with a novel high-performance domain-specific, multistage multiarmed bandit (MAB) approach. This framework addresses a wide range of optimization problems on Boolean optimization problems, such as And-Inv-Graphs (AIGs), conjunction normal form (CNF) minimization (# clauses) for Boolean satisfiability; logic synthesis and technology mapping, and, more importantly, end-to-end post place-and-route (PnR) optimizations. Moreover, we demonstrate the high extensibility and generalizability of the proposed domain-specific MAB approach with end-to-end FPGA design flow, evaluated at post-routing stage, with two different FPGA backend tools (OpenFPGA and VPR) and two different logic synthesis representations [AIGs and Majority-Inv-Graph (MIG)]. FlowTune is fully integrated with ABC (Mishchenko et al., 2010), Yosys (Wolf, 2016), VTR (Luu et al., 2014), LSOracle (Neto et al., 2019), OpenFPGA (Tang et al., 2019), and industrial tools, and is released publicly. The experimental results conducted on various design stages in the flow all demonstrate that our framework outperforms both handcrafted flows (Mishchenko et al., 2010) and ML explored flows (Yu et al., 2018), (Hosny et al., 2019) in QoRs, and is orders of magnitude faster compared to ML-based approaches.

LUT-based optimization techniques are finding new applications in synthesis of ASIC designs. Intuitively, packing logic into LUTs provides a better balance between functionality and structure in logic optimization. On this basis, the LUT-engine framework [1] was introduced to enhance the ASIC synthesis. In this paper, we present key improvements, at both algorithmic and flow levels, making a much stronger LUT-engine. We restructure the flow of LUT-engine, to benefit from a heterogeneous mixture of LUT sizes, and revisit its requirements for maximum scalability. We propose a dedicated LUT mapper for the new flow, based on FlowMap, natively balancing LUT-count and NAND2-count for a wide range LUT sizes. We describe a specialized Boolean factoring technique, exploiting the fanin bounds in LUT networks, resulting in a very fast LUT-based AIG minimization. By using the proposed methodology, we improve 9 of the best area results in the ongoing EPFL synthesis competition. Integrated in a complete EDA flow for ASICs, the new LUT-engine performs well on a set of 87 benchmarks: -4.60% area and -3.41% switching power at +5% runtime, compared to the baseline flow without LUT-based optimizations, and -3.02% area and -2.54% switching power with -1% runtime, compared to the original LUT-engine.

Approximate computing is an attractive paradigm for reducing the design complexity of error-resilient systems, therefore, improving performance and saving power consumption. In this work, we propose a new two-level approximate logic synthesis method based on cube insertion and removal procedures. The experimental results have shown significant literal count and runtime reduction compared to the state-of-the-art approach. The method scalability is illustrated for a high error threshold over large benchmark circuits. The obtained solutions have presented a literal number reduction up to 38%, 56%, and 93% with respect to an error rate of 1%, 3%, and 5%, respectively.

To tackle the involved complexity, Electronic Design Automation (EDA) tools are broken in well-defined steps, each operating at different abstraction levels. Higher levels of abstraction shorten the flow run-time while sacrificing correlation with the physical circuit implementation. Bridging this gap between Logic Synthesis tool and Physical Design (PnR) tools is key to improve Quality of Results (QoR), while possibly shorting the time-to-market. To address this problem, in this work, we formalize logic paths as sentences, with the gates being a bag of words. Thus, we show how word embedding can be leveraged to represent generic paths and predict if a given path is likely to be critical post-PnR. We present the effectiveness of our approach, with accuracy over than 90% for our test-cases. Finally, we give a step further and introduce an intelligent and non-intrusive flow that uses this information to guide optimization. Our flow presents up to 15.53% area delay product (ADP) and 18.56% power delay product (PDP), compared to a standard flow.

Recently we have seen many works that leverage Machine Learning (ML) techniques in optimizing Electronic Design Automation (EDA) process. However, the uses of ML techniques are limited to learning forecasting models of existing EDA algorithms, instead of developing novel algorithms. In this work, we focus on designing an novel cut-based technology mapping algorithms assisted by ML techniques, which matches results of exhaustive cut exploration but preserving a small footprint of utilized cuts. The proposed approach has been demonstrated with a wide range of benchmarks with 24% reductions in number of cuts utilized compared to the state-of-the-art, while improving the circuit delay, and Area-Delay-Product (ADP), by average about 10%, 7%, respectively, with a 2% area penalty. Compared to the exhaustive approach, i.e., considering all the cuts, we achieve similar or better results while saving over than $2 \times $ the number of considered cuts (runtime) on average. Finally, we provide a comprehensive explanation of heuristics learned by the ML model by feature ranking.

High Level Synthesis (HLS) speeds hardware development and opens the door to non-expert designers, focusing on functionality rather than implementation. The expense and rigidity of commercial electronic design automation (EDA) tool-chains can be an obstacle for these users. LSOracle is an opensource logic synthesis tool which leverages multiple underlying data structures, including and-inverter graphs (AIGs), majority-inverter graphs (MIGs), and xor-and graphs (XAGs) to automatically optimize circuits using the best representation for each region of a design, without manual intervention. The use of MIGs and XAGs gives particularly strong performance in arithmetic logic, cryptography cores, and machine-learning accelerators; applications which may be of particular interest for HLS users. Here we present an overview of the approach and demonstrate an open-source HLS-to-GDS II workflow using LSOracle, Bambu, and OpenROAD. We test the integration on a small benchmark suite and show a reduction in delay of up to 31%.

Logic synthesis is a fundamental step in hardware design whose goal is to find structural representations of Boolean functions while minimizing delay and area. If the function is completely-specified, the implementation accurately represents the function. If the function is incompletely-specified, the implementation has to be true only on the care set. While most of the algorithms in logic synthesis rely on SAT and Boolean methods to exactly implement the care set, we investigate learning in logic synthesis, attempting to trade exactness for generalization. This work is directly related to machine learning where the care set is the training set and the implementation is expected to generalize on a validation set. We present learning incompletely-specified functions based on the results of a competition conducted at IWLS 2020. The goal of the competition was to implement 100 functions given by a set of care minterms for training, while testing the implementation using a set of validation minterms sampled from the same function. We make this benchmark suite available and offer a detailed comparative analysis of the different approaches to learning.

We present a new logic synthesis framework which produces efficient post-technology mapped results on heterogeneous networks containing a mix of different types of logic. This framework accomplishes this by breaking down the circuit into sections using a hypergraph k-way partitioner and then determines the best-fit logic representation for each partition between two Boolean networks, And-Inverter Graphs (AIG) and Majority-Inverter Graphs (MIG), which have been shown to perform better over each other on different types of logic. Experimental results show that over a set of Open Piton Design Benchmarks (OPDB) and OpenCores benchmarks, our proposed methodology outperforms state-of-the-art academic tools in Area-Delay Product (ADP), Power-Delay Product (PDP), and Energy-Delay Product (EDP) by 5%, 2%, and 15% respectively after performing Application Specific Integrated Circuits (ASIC) technology mapping as well as showing a 54% improvement in runtime over conventional MIG optimization.

The increasing complexity of modern Integrated Circuits (ICs) leads to systems composed of various different Intellectual Property (IPs) blocks, known as System-on-Chip (SoC). Such complexity requires strong expertise from engineers, that rely on expansive commercial EDA tools. To overcome such a limitation, an automated open-source logic synthesis flow is required. In this context, this work proposes LSOracle: a novel automated mixed logic synthesis framework. LSOracle is the first to exploit state-of-the-art And-Inverter Graph (AIG) and Majority-Inverter Graph (MIG) logic optimizers and relies on a Deep Neural Network (DNN) to automatically decide which optimizer should handle different portions of the circuit. To do so, LSOracle applies k-way partitioning to split a DAG into multiple partitions and uses a to chose the best-fit optimizer. Post-tech mapping ASIC results, targeting the 7nm ASAP standard cell library, for a set of mixed-logic circuits, show an average improvement in area-delay product of 6.87% (up to 10.26%) and 2.70% (up to 6.27%) when compared to AIG and MIG, respectively. In addition, we show that for the considered circuits, LSOracle achieves an area close to AIGs (which delivered smaller circuits) with a similar performance of MIGs, which delivered faster circuits.