2024 TCAD

PowerSyn: A Logic Synthesis Framework With Early Power Optimization

Authors: Sunan Zou; Jiaxi Zhang; Bizhao Shi; Guojie Luo

Affiliation: National Key Laboratory for Multimedia Information Processing, School of Computer Science, and the Center for Energy-Efficient Computing and Applications, Peking University

Abstract:

Power is a great concern in integrated circuits (ICs) design flow, especially in portable devices. As an early stage in electronic design automation (EDA), logic synthesis can significantly affect the quality of the design. It is essential to optimize power in logic synthesis. However, logic synthesis only has a limited concern in power due to its inaccurate estimation. This is because critical physical information is missing at this stage. Furthermore, the empirical optimization sequences need enhancement, and they are not optimal for power, while optimizing power in the early stage is effective. Technology mapping can also improve power optimization with comprehensive power metrics in this sub-15 nm era. Therefore, we propose PowerSyn, a logic synthesis framework with early power optimization. It consists of a practical power model, a power-oriented logic optimization module, and a technology mapping stage. The power model leverages probability propagation considering glitches and static power. The acrlong RL-based logic optimization generates high-quality and rapid-convergence command sequence with early power optimization. We also modify traditional technology mapping with novel power-related metrics. We evaluate PowerSyn on the EPFL benchmark suite. Experiment results show that our flow achieves an average power savings of 16.1% compared to the state-of-the-art open-source logic optimization flow. It also delivers an 8.8% and a 2.1% reduction in latency and area, respectively. The flow incurs less than 12.2% execution time overhead during inference for command generation.

 

 

 

 

 

2024 DATE

BESWAC: Boosting Exact Synthesis via Wiser SAT Solver Call

Authors：Sunan Zou; Jiaxi Zhang; Bizhao Shi; Guojie Luo

Affiliation: National Key Laboratory for Multimedia Information Processing, School of Computer Science, and the Center for Energy-Efficient Computing and Applications, Peking University

Abstract:

SAT-based exact synthesis is a critical technique in logic synthesis to generate optimal circuits for given Boolean functions. The lengthy trial-and-error process limits its application in on-the-fly logic optimization and optimal netlist library construction. Previous research focuses on reducing the execution time of each trial. However, unnecessary SAT solver calls and varying execution times among encoding methods remained issues. This paper presents BESWAC to boost exact synthesis from the flow level. It leverages initial value prediction, encoding method selection, and an optional early exit to call SAT solvers efficiently and wisely. Moreover, BESWAC can seamlessly integrate existing acceleration methods focusing on individual trials. Experimental results show that BESWAC achieves a 1.79x speedup compared to state-of-the-art exact synthesis flows.

 

 

 

 

2023 DAC

AGD: A Learning-based Optimization Framework for EDA and its Application to Gate Sizing

Author: Phuoc Pham, Jaeyong Chung

Affiliation: Department of Electronics Engineering, Incheon National University, South Korea

Abstract:

In electronic design automation (EDA), most simulation models are not differentiable, and many design choices are discrete. As a result, greedy optimization methods based on numerical gradients have been widely used, although they suffer from suboptimal solutions. On the other hand, analytic methods may offer better solutions, but at the cost of enormous research efforts. Reinforcement learning (RL) has been leveraged to tackle this problem owing to its generality; however, RL also suffers from notorious sample inefficiency, which is exaggerated in EDA because data sampling in EDA is very expensive due to slow simulations. This paper proposes an alternative to RL for EDA, namely analytic gradient descent (AGD). Our method calculates analytic gradients of a design objective with respect to continuous and discrete design choices through a neural network learned by a simulation model. Then it performs a gradient descent procedure optimizing the design objective directly. We demonstrate AGD on the well-known gate sizing problem and show that our method can be very close to an industry-leading commercial tool in terms of design quality of result (QoR), while it only takes several person-months in comparison to dedicated efforts of human engineering over decades to develop. In addition, we also show that AGD can generalize to unseen circuits, with less training specific in a small amount of execution time.

 

 

 

 

2023 DAC

On EDA-Driven Learning for SAT Solving

Author: Min Li, Zhengyuan Shi, Qiuxia Lai, Sadaf Khan, Shaowei Cai, Qiang Xu  

Affiliation: State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China; Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong S.A.R; Communication University of China, China  

Abstract:

We present DeepSAT, a novel end-to-end learning framework for the Boolean satisfiability (SAT) problem. Unlike existing solutions trained on random SAT instances with relatively weak supervision, we propose applying the knowledge of the well-developed electronic design automation (EDA) field for SAT solving. Specifically, we first resort to logic synthesis algorithms to pre-process SAT instances into optimized and-inverter graphs (AIGs). By doing so, the distribution diversity among various SAT instances can be dramatically reduced, which facilitates improving the generalization capability of the learned model. Next, we regard the distribution of SAT solutions as being a product of conditional Bernoulli distributions. Based on this observation, we approximate the SAT solving procedure with a conditional generative model, leveraging a novel directed acyclic graph neural network (DAGNN) with two polarity prototypes for conditional SAT modeling. To effectively train the generative model, with the help of logic simulation tools, we obtain the probabilities of nodes in the AIG being logic ‘1’ as rich supervision. We conduct comprehensive experiments on various SAT problems. Our results show that DeepSAT achieves significant accuracy improvements over state-of-the-art learning-based SAT solutions, especially when generalized to SAT instances that are relatively large or with diverse distributions.

 

 

 

 

2023 DAC

Gamora: Graph Learning Based Symbolic Reasoning for Large-Scale Boolean Networks

Author: Nan Wu, Yingjie Li, Cong Hao, Steve Dai, Cunxi Yu, Yuan Xie

Affiliation: University of Utah; University of California, Santa Barbara; NVIDIA; Georgia Institute of Technology; Alibaba DAMO Academy

Abstract:

Reasoning high-level abstractions from bit-blasted Boolean networks (BNs) such as gate-level netlists can significantly benefit functional verification, logic minimization, datapath synthesis, malicious logic identification, etc. Mostly, conventional reasoning approaches leverage structural hashing and functional propagation, suffering from limited scalability and inefficient usage of modern computing power. In response, we propose a novel symbolic reasoning framework exploiting graph neural networks (GNNs) and GPU acceleration to reason high-level functional blocks from gate-level netlists, namely Gamora, which offers high reasoning performance with respect to exact reasoning algorithms, strong scalability to BNs with over 33 million nodes, and generalization capability from simple to complex designs. To further demonstrate the capability of Gamora, we also evaluate its reasoning performance after various technology mapping options, since technology-dependent optimizations are known to make functional reasoning much more challenging. Experimental results show that (1) Gamora reaches almost 100% and over 97% reasoning accuracy for carry-save-array (CSA) and Booth-encoded multipliers, respectively, with up to six orders of magnitude speedups compared to the state-of-the-art implementation in the ABC framework; (2) Gamora maintains high reasoning accuracy (>92%) in finding functional modules after complex technology mapping, and we comprehensively analyze the impacts on Gamora reasoning from technology mapping. Gamora is available at [https://github.com/Yu-Utah/Gamora] (https://github.com/Yu-Utah/Gamora).

 

 

 

 

2023 ICCAD

DeepGate2: Functionality-Aware Circuit Representation Learning

Author: Zhengyuan Shi, Hongyang Pan, Sadaf Khan, Min Li, Yi Liu, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, Zhufei Chu, and Qiang Xu

Affiliation: The Chinese University of Hong Kong, Noah's Ark Lab, Huawei, Ningbo University

Abstract:

Circuit representation learning aims to obtain neural representations of circuit elements and has emerged as a promising research direction that can be applied to various EDA and logic reasoning tasks. Existing solutions, such as DeepGate, have the potential to embed both circuit structural information and functional behavior. However, their capabilities are limited due to weak supervision or flawed model design, resulting in unsatisfactory performance in downstream tasks. In this paper, we introduce DeepGate2, a novel functionality-aware learning framework that significantly improves upon the original DeepGate solution in terms of both learning effectiveness and efficiency. Our approach involves using pairwise truth table differences between sampled logic gates as training supervision, along with a well-designed and scalable loss function that explicitly considers circuit functionality. Additionally, we consider inherent circuit characteristics and design an efficient one-round graph neural network (GNN), resulting in an order of magnitude faster learning speed than the original DeepGate solution. Experimental results demonstrate significant improvements in two practical downstream tasks: logic synthesis and Boolean satisfiability solving. The code is available at [https://github.com/cure-lab/DeepGate2] (https://github.com/cure-lab/DeepGate2).

 

 

 

 

2023 ICCAD

EasySO: Exploration-enhanced Reinforcement Learning for Logic Synthesis Sequence Optimization and a Comprehensive RL Environment

Author: Jianyong Yuan, Peiyu Wang, Junjie Ye, Mingxuan Yuan, Jianye Hao, Junchi Yan

Affiliation: Department of CSE, MoE Key Lab of AI, Shanghai Jiao Tong University, Shanghai, China; Huawei Noah's ark Lab, Shenzhen & Hong Kong, Beijing, China

Abstract:

Optimizing the quality of results (QoR) of a circuit during the logic synthesis (LS) phase in chip design is critical yet challenging. While most existing methods often mitigate the computational hardness by restricting the action space to a small set of operators and fixing the operator's parameters, they are susceptible to local minima and may not meet the high demand from industrial cases. In this paper, we develop a more comprehensive optimization approach via sample-efficient reinforcement learning (RL). Specifically, we first build a complete logic synthesis-RL environment, where the action space consists of three types of operators: logic optimization, technology mapping, and post-mapping, along with their associated continuous/binary parameters for optimization as well. Based on this environment, we devise a hybrid proximal policy optimization (PPO) model to handle both discrete operators and parameters and design a distributed architecture to improve sample collection efficiency. Furthermore, we devise a dynamic exploration module to improve the exploration efficiency under the constraint of limited samples. We term our method as Exploration-enhanced RL for Logic Synthesis Sequence Optimization (EasySO). Results on the EPFL benchmark show that our method significantly outperforms current state-of-the-art models based on Bayesian optimization (BO) and the previous RL-based methods. Compared to resyn2, our EasySO achieves an average of 25.4% LUT-6 count optimization without sacrificing level values. Moreover, as of the time for this submission, we rank 26 first places among 40 optimization targets in the EPFL competition.

 

 

 

 

2023 ICCAD

DeepGate2: Functionality-Aware Circuit Representation Learning

Author: Zhengyuan Shi, Hongyang Pan, Sadaf Khan, Min Li, Yi Liu, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, Zhufei Chu, Qiang Xu  

Affiliation: The Chinese University of Hong Kong; Ningbo University; Noah's Ark Lab, Huawei

Abstract:

Circuit representation learning aims to obtain neural representations of circuit elements and has emerged as a promising research direction that can be applied to various EDA and logic reasoning tasks. Existing solutions, such as DeepGate, have the potential to embed both circuit structural information and functional behavior. However, their capabilities are limited due to weak supervision or flawed model design, resulting in unsatisfactory performance in downstream tasks. In this paper, we introduce DeepGate2, a novel functionality-aware learning framework that significantly improves upon the original DeepGate solution in terms of both learning effectiveness and efficiency. Our approach involves using pairwise truth table differences between sampled logic gates as training supervision, along with a well-designed and scalable loss function that explicitly considers circuit functionality. Additionally, we consider inherent circuit characteristics and design an efficient one-round graph neural network (GNN), resulting in an order of magnitude faster learning speed than the original DeepGate solution. Experimental results demonstrate significant improvements in two practical downstream tasks: logic synthesis and Boolean satisfiability solving. The code is available at [https://github.com/cure-lab/DeepGate2] (https://github.com/cure-lab/DeepGate2).

 

 

 

 

2023 ICCAD

EffiSyn: Efficient Logic Synthesis with Dynamic Scoring and Pruning

Authors: Xing Li; Lei Chen; Jiantang Zhang; Shuang Wen; Weihua Sheng; Yu Huang; Mingxuan Yuan

Affiliation: Huawei Noah's Ark Lab, Hong Kong SAR, China

Abstract:

Logic synthesis tools synthesize circuit structures to optimize specific targets given reasonable constraints and runtime using a set of well-defined operators. The efficiency of these operators is critical to achieving better runtime and optimization convergence. However, most synthesis operators are designed heuristically with fixed and sub-optimal traversal orders of nodes, cuts, and candidate subgraphs that are independent of circuit structures and functionalities. This leads to redundant computation and loss of optimization opportunities. Due to the spatial structure similarity, sub-circuits already synthesized in the same circuit contain meaningful information to guide more efficient synthesis for unvisited sub-circuits. Historical evaluation and gain features can learn from conflicts and be utilized to predict synthesis gain and prune invalid sub-circuits. Instead of using high-weight feature extraction and models, we utilize efficient prediction models with lightweight structural and functional features to reduce overhead. We thus propose a generalizable and dynamic scoring and pruning framework EffiSyn to accelerate logic synthesis operators while maintaining synthesis effectiveness. For example, we further improve the highly optimized operator drw by scoring and pruning invalid cuts and precomputed subgraphs. Extensive experiments on 20 public and industrial circuits validate that EffiSyn can accelerate drw by about 35% with negligible effectiveness loss or even with effectiveness improvement. Experiments over diverse circuits and synthesis sequences also validate the generalization of the proposed framework.

 

 

 

 

2023 ICCAD

EasyMap: Improving Technology Mapping via Exploration-Enhanced Heuristics and Adaptive Sequencing

Authors: Peiyu Wang; Anqi Lu; Xing Li; Junjie Ye; Lei Chen; Mingxuan Yuan; Jianye Hao; Junchi Yan

Affiliation: MoE Key Lab of Artificial Intelligence, Shanghai Jiao Tong University

Abstract:

Technology mapping is a crucial step in the logic synthesis in chip design e.g. Field Programmable Gate Arrays (FPGAs) design, where a logic network is transformed into a K-bounded lookup tables (K-LUTs) network. Traditional mapping algorithms converges quickly to a suboptimal result, which limits the exploration capacity for further improvement. In this paper, we propose a new mapping method called Exploration-enhanced heuristics and Adaptive sequencing for Technology Mapping (EasyMap). EasyMap includes a pool of new heuristics and considers the mapping exploration as a conditional sequence optimization problem. During the mapping exploration procedure, heuristic algorithms with specific parameters are selected and applied sequentially. Our EasyMap outperforms the widely used IfMap in ABC by a significant margin. In particular, when optimizing area with a level constraint, EasyMap outperforms IfMap by reducing 9.1% more area on arithmetic circuits of the EPFL benchmark. Moreover, when optimizing area without level constraints at the same time, EasyMap can reduce 19% more area than IfMap on arithmetic circuits.

 

 

 

 

2023 MICRO

Fast, Robust, and Transferable Prediction for Hardware Logic Synthesis

Author: Ceyu Xu, Pragya Sharma, Tianshu Wang, Lisa Wu Wills

Affiliation: Duke University

Abstract:

The increasing complexity of computer chips and the slow logic synthesis process have become major bottlenecks in the hardware design process, also hindering the ability of hardware generators to make informed design decisions while considering hardware costs. While various models have been proposed to predict physical characteristics of hardware designs, they often suffer from limited domain adaptability and open-source hardware design data scarcity.

In this paper, we present SNS v2, a fast, robust, and transferable hardware synthesis predictor based on deep learning models. Inspired by modern natural language processing models, SNS v2 adopts a three-phase training approach encompassing pre-training, fine-tuning, and domain adaptation, enabling it to leverage more abundant unlabeled and off-domain training data. Additionally, we propose a novel contrastive learning approach based on circuit equivalence to enhance model robustness. Our experiments demonstrate that SNS v2 achieves two to three orders of magnitude faster speed compared to conventional EDA tools, while maintaining state-of-the-art prediction accuracy. We also show that SNS v2 can be seamlessly integrated into hardware generator frameworks for real-time cost estimation, resulting in higher quality design recommendations in a significantly reduced time frame.

 

 

 

 

2023 ICCD

AiMap: Learning to Improve Technology Mapping for ASICs via Delay Prediction

Author: Junfeng Liu, Liwei Ni, Xingquan Li, Min Zhou, Lei Chen, Xing Li, Qinghua Zhao, Shuai Ma

Affiliation: SKLSDE Lab, Beihang University, Beijing, China;Peng Cheng Laboratory

Abstract:

Technology mapping is an essential process in the EDA flow which aims to find an optimal implementation of a logic network from a technology library. In ASIC designs, the estimated cell delay w.r.t. the cut has a significant impact on both area and delay of the mapped network. In this work, we first propose formulating cell delay estimation as a regression learning task by incorporating multiple perspective features, such as the structure of logic networks and non-linear cell delays, to guide the mapper search. We design a learning model that incorporates a customized attention mechanism to be aware of the pin delay and jointly learns the hierarchy between the logic network and library, with the help of proposed parameterizable strategies to generate learning labels. Experimental results show that our proposed  ethod noticeably improves area by 12% and delay by 1%, compared with ABC.

 

 

 

 

2022 ASAP

Lostin: Logic Optimization via Spatio-Temporal Information with Hybrid Graph Models

Author: Nan Wu, Jiwon Lee, Yuan Xie, Cong Hao

Affiliation: University of California, Santa Barbara, CA, USA, Georgia Institute of Technology, GA, USA

Abstract:

Despite the recent progress in machine learning (ML)-based performance modeling, two major concerns that may impede production-ready ML applications in electronic design automation (EDA) are the stringent accuracy requirements and generalization capability. To address these challenges, we propose a novel approach, namely LOSTIN, which exploits hybrid graph neural networks (GNNs) to provide highly accurate quality-of-result (QoR) estimations with great generalization capability, specifically targeting logic synthesis optimization. The key idea is to simultaneously leverage spatio-temporal information from hardware designs and logic synthesis flows to forecast performance (i.e., delay/area) of various synthesis flows on different designs. Specifically, the structural characteristics inside hardware designs are distilled and represented by GNNs; the temporal knowledge (i.e., the relative ordering of logic transformations) in synthesis flows can be imposed on hardware designs by combining a virtually added supernode or a sequence processing model with conventional GNN models. Evaluation on 3.3 million data points shows that the testing mean absolute percentage error (MAPE) on designs seen and unseen during training are no more than 1.2% and 3.1%, respectively, which are significantly lower than existing studies. Our dataset and ML models are publicly available at [https://github.com/lydiawunan/LOSTIN] (https://github.com/lydiawunan/LOSTIN).

 

 

 

 

2022 ICCAD

Heterogeneous Graph Neural Network-Based Imitation Learning for Gate Sizing Acceleration

Author: Xinyi Zhou, Junjie Ye, Chak-Wa Pui, Kun Shao, Guangliang Zhang, Bin Wang, Jianye Hao, Guangyong Chen, Pheng-Ann Heng

Affiliation: The Chinese University of Hong Kong

Abstract:

Gate Sizing is an important step in logic synthesis, where the cells are resized to optimize metrics such as area, timing, power, leakage, etc. In this work, we consider the gate sizing problem for leakage power optimization with timing constraints. Lagrangian Relaxation is a widely employed optimization method for gate sizing problems. We accelerate Lagrangian Relaxation-based algorithms by narrowing down the range of cells to resize. In particular, we formulate a heterogeneous directed graph to represent the timing graph, propose a heterogeneous graph neural network as the encoder, and train in the way of imitation learning to mimic the selection behavior of each iteration in Lagrangian Relaxation. This network is used to predict the set of cells that need to be changed during the optimization process of Lagrangian Relaxation. Experiments show that our accelerated gate sizer could achieve comparable performance to the baseline with an average of 22.5% runtime reduction.

 

 

 

 

2022 TCAS-II

Logic Synthesis Optimization Sequence Tuning Using RL-Based LSTM and Graph Isomorphism Network

Author: Chenghao Yang, Yinshui Xia, Zhufei Chu, Xiaojing Zha

Affiliation: Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo, China

Abstract:

As a key step in the IC design flow, logic synthesis involves various logic optimization algorithms to be iteratively applied to the circuit. However, how these algorithms are used is usually determined by heuristics, and it does not always yield well optimizations on all circuits. To achieve well optimized results, engineers need to tune the sequence consisting of these logic optimization algorithms based on their knowledge. To overcome this limitation, in this brief, reinforcement learning (RL) proximal policy optimization (PPO) is proposed to train an agent to tune the optimization sequence. Specifically, graph isomorphic network with edge feature aggregation capability (GINE) is used to learn circuit representations and use circuit representations as state representations for the reinforcement learning agent. Furthermore, to enable the agent learning from historical operations, the Long Short-Term Memory (LSTM) is further embedded in reinforcement learning. The evaluation of the EPFL arithmetic benchmark shows that our model improves the area optimization under the delay constraint by 21.21% over existing methods.

 

 

 

 

2022 ISCA

SNS's not a Synthesizer: A Deep-Learning-Based Synthesis Predictor

Author: Ceyu Xu, Chris Kjellqvist, Lisa Wu Wills

Affiliation: Duke University

Abstract:

The number of transistors that can fit on one monolithic chip has reached billions to tens of billions in this decade thanks to Moore's Law. With the advancement of every technology generation, the transistor counts per chip grow at a pace that brings about an exponential increase in design time, including the synthesis process used to perform design space explorations. Such a long delay in obtaining synthesis results hinders an efficient chip development process, significantly impacting time-to-market. In addition, these large-scale integrated circuits tend to have larger and higher-dimension design spaces to explore, making it prohibitively expensive to obtain physical characteristics of all possible designs using traditional synthesis tools. In this work, we propose a deep-learning-based synthesis predictor called SNS (SNS's not a Synthesizer) that predicts the area, power, and timing physical characteristics of a broad range of designs at two to three orders of magnitude faster than the Synopsys Design Compiler while providing on average a 0.4998 RRSE (root relative square error). We further evaluate SNS via two representative case studies, a general-purpose out-of-order CPU case study using RISC-V Boom open-source design and an accelerator case study using an in-house Chisel implementation of DianNao, to demonstrate the capabilities and validity of SNS.

 

 

 

 

2022 DAC

Generative Self-Supervised Learning for Gate Sizing: Invited

Author: Siddhartha Nath, Geraldo Pradipta, Corey Hu, Tian Yang, Brucek Khailany, Haoxing Ren

Affiliation: NVIDIA

Abstract:

Self-supervised learning has shown great promise in leveraging large amounts of unlabeled data to achieve higher accuracy than supervised learning methods in many domains. Generative self-supervised learning can generate new data based on the trained data distribution. In this paper, we evaluate the effectiveness of generative self-supervised learning on combinational gate sizing in VLSI designs. We propose a novel use of Transformers for gate sizing when trained on a large dataset generated from a commercial EDA tool. We demonstrate that our trained model can achieve 93% accuracy, 1440X speedup, and fast design convergence when compared to a leading commercial EDA tool.

 

 

 

 

2022 ASP-DAC

Techniques for CAD Tool Parameter Auto-tuning in Physical Synthesis: A Survey (Invited Paper)

Author: Hao Geng, Tinghuan Chen, Qi Sun, Bei Yu

Affiliation: Department of Computer Science and Engineering, The Chinese University of Hong Kong, NT, Hong Kong, China

Abstract:

As the technology node of integrated circuits rapidly goes beyond 5nm, synthesis-centric modern very large-scale integration (VLSI) design flow is facing ever-increasing design complexity and suffering the pressure of time-to-market. During the past decades, synthesis tools have become progressively sophisticated and offer countless tunable parameters that can significantly influence design quality. Nevertheless, owing to the time-consuming tool evaluation plus a limitation to one possible parameter combination per synthesis run, manually searching for optimal configurations of numerous parameters proves to be elusive. What's worse, tiny perturbations to these parameters can result in very large variations in the Quality-of-Results (QoR). Therefore, automatic tool parameter tuning to reduce human cost and tool evaluation cost is in demand. Machine-learning techniques provide chances to enable the auto-tuning process of tool parameters. In this paper, we will survey the recent pace of progress on advanced parameter auto-tuning flows of physical synthesis tools. We sincerely expect this survey can enlighten the future development of parameter auto-tuning methodologies.

 

 

 

 

2021 DAC

SLAP: A Supervised Learning Approach for Priority Cuts Technology Mapping

Author: Walter Lau Neto, Matheus T. Moreira, Yingjie Li, Luca Amarù, Cunxi Yu, Pierre-Emmanuel Gaillardon

Affiliation: University of Utah, Salt Lake City, Utah, USA, Chronos Tech, San Diego, California, USA, Synopsys Inc., Design Group, Sunnyvale, California, USA

Abstract:

Recently, we have seen many works that leverage Machine Learning (ML) techniques in optimizing the Electronic Design Automation (EDA) process. However, the use of ML techniques has been limited to learning forecasting models of existing EDA algorithms, instead of developing novel algorithms. In this work, we focus on designing a novel cut-based technology mapping algorithm assisted by ML techniques, which matches the results of exhaustive cut exploration while preserving a small footprint of utilized cuts. The proposed approach has been demonstrated with a wide range of benchmarks, achieving a 24% reduction in the number of cuts utilized compared to the state-of-the-art, while improving circuit delay and Area-Delay-Product (ADP) by about 10% and 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 2× the number of considered cuts (runtime) on average. Finally, we provide a comprehensive explanation of heuristics learned by the ML model by feature ranking.

 

 

 

 

2021 DAC

RL-Sizer: VLSI Gate Sizing for Timing Optimization Using Deep Reinforcement Learning

Author: Yi-Chen Lu, Siddhartha Nath, Vishal Khandelwal, Sung Kyu Lim

Affiliation: School of ECE, Georgia Institute of Technology, Atlanta, GA; Synopsys Inc., Mountain View, CA; Synopsys Inc., Hillsboro, OR; School of ECE, Georgia Institute of Technology, Atlanta, GA

Abstract:

Gate sizing for timing optimization is performed extensively throughout electronic design automation (EDA) flows. However, increasing design sizes and time-to-market pressure force EDA tools to maintain pseudo-linear complexity, thereby limiting the global exploration done by the underlying sizing algorithms. Furthermore, high-performance low-power designs are pushing the envelope on power, performance, and area (PPA), creating a need for last-mile PPA closure using more powerful algorithms. Reinforcement learning (RL) is a disruptive paradigm that achieves high-quality optimization results beyond traditional algorithms. In this paper, we formulate gate sizing as an RL process, and propose RL-Sizer, an autonomous gate sizing agent, which performs timing optimization in an unsupervised manner. In the experiments, we demonstrate that RL-Sizer can improve the native sizing algorithms of an industry-leading EDA tool, Synopsys IC-Compiler II (ICC2), on 6 commercial designs in advanced process nodes (5 – 16nm). RL-Sizer delivers significantly better total negative slack (TNS) and number of violating endpoints (NVEs) on 4 designs with negligible power overhead, while achieving parity on the others.

 

 

 

 

2021 ICCAD

Generalizable Cross-Graph Embedding for GNN-based Congestion Prediction

Author: Amur Ghose, Vincent Zhang, Yingxue Zhang, Dong Li, Wulong Liu, Mark Coates

Affiliation: Noah's Ark Lab, Huawei; McGill University

Abstract:

Presently with technology node scaling, an accurate prediction model at early design stages can significantly reduce the design cycle. Especially during logic synthesis, predicting cell congestion due to improper logic combination can reduce the burden of subsequent physical implementations. There have been attempts using Graph Neural Network (GNN) techniques to tackle congestion prediction during the logic synthesis stage. However, they require informative cell features to achieve reasonable performance since the core idea of GNNs is built on the message passing framework, which would be impractical at the early logic synthesis stage. To address this limitation, we propose a framework that can directly learn embeddings for the given netlist to enhance the quality of our node features. Popular random-walk based embedding methods such as Node2vec, LINE, and DeepWalk suffer from the issue of cross-graph alignment and poor generalization to unseen netlist graphs, yielding inferior performance and costing significant runtime. In our framework, we introduce a superior alternative to obtain node embeddings that can generalize across netlist graphs using matrix factorization methods. We propose an efficient mini-batch training method at the sub-graph level that can guarantee parallel training and satisfy the memory restriction for large-scale netlists. We present results utilizing open-source EDA tools such as DREAMPLACE and OPENROAD frameworks on a variety of openly available circuits. By combining the learned embedding on top of the netlist with the GNNs, our method improves prediction performance, generalizes to new circuit lines, and is efficient in training, potentially saving over 90% of runtime.

 

 

 

 

2021 ICCAD

Sampling-Based Approximate Logic Synthesis: An Explainable Machine Learning Approach

Author: Wei Zeng, Azadeh Davoodi, Rasit Onur Topaloglu

Affiliation: University of Wisconsin-Madison, USA; IBM, USA

Abstract:

Recent years have seen promising studies on machine learning (ML) techniques applied to approximate logic synthesis (ALS), especially based on logic reconstruction from samples of input-output pairs. This "sampling-based ALS" supports integration with conventional logic synthesis and optimization techniques, as well as synthesis for a constrained input space (e.g., when primary input values are restricted using Boolean relations). To achieve an effective sampling-based ALS, for the first time, this paper proposes the use of adaptive decision trees (ADTs), and in particular variations guided by explainable ML. We adopt SHAP importance, which is a feature importance metric derived from a recent advance in explainable ML, to guide the training of ADTs. We also include approximation techniques for ADTs which are specifically designed for ALS, including don't-care bit assertion and instantiation. Comprehensive experiments show that we can achieve 39%-42% area reduction with 0.20%-0.22% error rate on average, based on 15 logic functions in the IWLS'20 benchmark suite.

 

 

 

 

2021 ICCAD

RL-Guided Runtime-Constrained Heuristic Exploration for Logic Synthesis

Author: Yasasvi V. Peruvemba, Shubham Rai, Kapil Ahuja, Akash Kumar

Affiliation: Computer Science and Engineering, IIT Indore, India; Chair of Processor Design, TU Dresden, Germany

Abstract:

Within logic synthesis, most optimization scripts are well-defined heuristics that generalize over a variety of Boolean circuits. These heuristic-based scripts comprise various optimization algorithms which are applied sequentially in a specific order over a logic graph representation of Boolean circuits (typically in the form of And Inverter Graphs (AIGs) or Majority Inverter Graphs (MIGs)). These heuristics, despite being well-defined generalizations, may not perform well over all kinds of circuits. In order to develop custom heuristics specific to a particular Boolean circuit that performs well, we propose a runtime-constrained reinforcement learning (RL) approach which is able to generate scripts to carry out logic synthesis flows. Within our approach, we incorporate a graph convolution network (GCN) in order to perform a holistic exploration of the search space. To carry out an extensive evaluation, we identify three different classes of environments consisting of different baseline optimization sequences. The experimental results reveal that our model outperforms the prevalent state-of-the-art work and the best heuristic-based scripts of Berkeley-ABC. Our evaluations show that our framework provides up to an average of 8.3% further reduction in level over the EPFL Benchmark Suite as compared to the Berkeley-ABC scripts. Further, we develop a framework for the EPFL mockturtle logic synthesis libraries and generate custom scripts using our RL-based approach.

 

 

 

 

2021 ASP-DAC

Read Your Circuit: Leveraging Word Embedding to Guide Logic Optimization

Author: Walter Lau Neto, Matheus Trevisan Moreira, Luca Amaru, Cunxi Yu, Pierre-Emmanuel Gaillardon

Affiliation: Department of Computer and Electrical Engineering, University of Utah, Salt Lake City, Utah, USA, Chronos Tech, San Diego, California, USA, Design Group, Synopsys Inc., Sunnyvale, California, USA

Abstract:

To tackle the involved complexity, Electronic Design Automation (EDA) tools are broken into well-defined steps, each operating at different abstraction levels. Higher levels of abstraction shorten the flow runtime while sacrificing correlation with the physical circuit implementation. Bridging this gap between Logic Synthesis tools and Physical Design (PnR) tools is key to improving Quality of Results (QoR), while possibly shortening 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 90% for our test cases. Finally, we take a step further and introduce an intelligent and non-intrusive flow that uses this information to guide optimization. Our flow presents up to a 15.53% improvement in area delay product (ADP) and 18.56% improvement in power delay product (PDP) compared to a standard flow.

 

 

 

 

2020 ASP-DAC

DRiLLS: Deep Reinforcement Learning for Logic Synthesis

Author: Abdelrahman Hosny, Soheil Hashemi, Mohamed Shalan, Sherief Reda

Affiliation: Computer Science Dept., Brown University, Providence, RI, Computer Science Dept., American University in Cairo

Abstract:

Logic synthesis requires extensive tuning of the synthesis optimization flow where the quality of results (QoR) depends on the sequence of optimizations used. Efficient design space exploration is challenging due to the exponential number of possible optimization permutations. Therefore, automating the optimization process is necessary. In this work, we propose a novel reinforcement learning-based methodology that navigates the optimization space without human intervention. We demonstrate the training of an Advantage Actor Critic (A2C) agent that seeks to minimize area subject to a timing constraint. Using the proposed methodology, designs can be optimized autonomously with no humans in the loop. Evaluation on the comprehensive EPFL benchmark suite shows that the agent outperforms existing exploration methodologies and improves QoRs by an average of 13%.

 

 

 

 

2020 MLCAD

Decision Making in Synthesis across Technologies using LSTMs and Transfer Learning

Author: Cunxi Yu, Wang Zhou

Affiliation: University of Utah, Salt Lake City, UT, USA, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USA

Abstract:

We propose a general approach that precisely estimates the Quality-of-Result (QoR), such as delay and area, of unseen synthesis flows for specific designs. The main idea is leveraging an LSTM-based network to forecast the QoR, where the inputs are synthesis flows represented in novel timed-flow modeling, and QoRs are ground truth. This approach is demonstrated with 1.2 million data points collected using 14nm, 7nm regular-voltage (RVT), and 7nm low-voltage (LVT) technologies with twelve IC designs. The accuracy of predicting the QoRs (delay and area) is evaluated using mean absolute prediction error (MAPE). While collecting training data points in EDA can be extremely challenging, we propose to elaborate transfer learning in our approach, which enables accurate predictions across different technologies and different IC designs. Our transfer learning approach obtains estimation MAPE ≤3.7% over 960,000 test points collected on 7nm technologies, with only 100 data points used for training the pre-trained LSTM network using the 14nm dataset.

 

 

 

 

2020 MLCAD

Exploring Logic Optimizations with Reinforcement Learning and Graph Convolutional Network

Author: Keren Zhu, Mingjie Liu, Hao Chen, Zheng Zhao, David Z Pan

Affiliation: ECE Department, UT Austin

Abstract:

Logic synthesis for combinational circuits is to find the minimum equivalent representation for Boolean logic functions. A well-adopted logic synthesis paradigm represents the Boolean logic with standardized logic networks, such as and-inverter graphs (AIG), and performs logic minimization operations over the graph iteratively. Although the research for different logic representation and operations is fruitful, the sequence of using the operations is often determined by heuristics. We propose a Markov decision process (MDP) formulation of the logic synthesis problem and a reinforcement learning (RL) algorithm incorporating a graph convolutional network to explore the solution search space. The experimental results show that the proposed method outperforms the well-known logic synthesis heuristics with the same sequence length and action space.

 

 

 

 

2020 ISLPED

Deep-PowerX: A Deep Learning-Based Framework for Low-Power Approximate Logic Synthesis

Author: Ghasem Pasandi, Mackenzie Peterson, Moisés Herrera, Shahin Nazarian, Massoud Pedram, Sunwha Koh, Yonghwi Kwon, Youngsoo Shin

Abstract:

This paper aims at integrating three powerful techniques, namely Deep Learning, Approximate Computing, and Low Power Design, into a strategy to optimize logic at the synthesis level. We utilize advances in deep learning to guide an approximate logic synthesis engine to minimize the dynamic power consumption of a given digital CMOS circuit, subject to a predetermined error rate at the primary outputs. Our framework, Deep-PowerX, focuses on replacing or removing gates on a technology-mapped network and uses a Deep Neural Network (DNN) to predict error rates at the primary outputs of the circuit when a specific part of the netlist is approximated. The primary goal of Deep-PowerX is to reduce the dynamic power, whereas area reduction serves as a secondary objective. Using the said DNN, Deep-PowerX is able to reduce the exponential time complexity of standard approximate logic synthesis to linear time. Experiments are done on numerous open source benchmark circuits. Results show significant reductions in power and area by up to 1.47× and 1.43× compared to exact solutions, and by up to 22% and 27% compared to state-of-the-art approximate logic synthesis tools, while having orders of magnitude lower run-time.

 

 

 

 

2019 DATE

Accurate_Wirelength_Prediction_for_Placement-Aware_Synthesis_through_Machine_Learning

Author: Daijoon Hyun, Yuepeng Fan, and Youngsoo Shin

Affiliation: School of Electrical Engineering, KAIST, Daejeon 34141, Korea

Abstract:

Placement-aware synthesis, which combines logic synthesis with virtual placement and routing (P&R) to better take account of wiring, has been popular for timing closure. The wirelength after virtual placement is correlated to actual wirelength, but correlation is not strong enough for some chosen paths. An algorithm to predict the actual wirelength from placement-aware synthesis is presented. It extracts a number of parameters from a given virtual path. A handful of synthetic parameters are compiled through linear discriminant analysis (LDA), and they are submitted to a few machine learning modes. The final prediction of actual wirelength is given by the weighted sum of prediction from such machine learning modes, in which weight is determined by the population of neighbors in parameter space. Experiments indicate that the predicted wirelength is 93% accurate compared to actual wirelength; this can be compared to conventional virtual placement, in which wirelength is predicted with only 79% accuracy.

 

 

 

 

2019 ICCAD

LSOracle: A Logic Synthesis Framework Driven by Artificial Intelligence (Invited Paper)

Author: Walter Lau Neto, Max Austin, Scott Temple, Luca Amaru, Xifan Tang, Pierre-Emmanuel

Affiliation: LNIS, University of Utah, Salt Lake City, UT, USA, Synopsys Inc., Sunnyvale, CA, USA

Abstract:

The increasing complexity of modern Integrated Circuits (ICs) leads to systems composed of various different Intellectual Property (IP) 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 choose 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.

 

 

 

 

2018 ISCAS

Deep Learning for Logic Optimization Algorithms

Author: Winston Haaswijk, Edo Collins, Benoit Seguin, Mathias Soeken, Frédéric Kaplan, Sabine Süsstrunk, Giovanni De Micheli

Affiliation: Integrated Systems Laboratory, EPFL; Image and Visual Representation Lab, EPFL; Digital Humanities Laboratory, EPFL, Lausanne, VD, Switzerland

Abstract:

The slowing down of Moore's law and the emergence of new technologies put increasing pressure on the field of EDA. There is a constant need to improve optimization algorithms. However, finding and implementing such algorithms is a difficult task, especially with the novel logic primitives and potentially unconventional requirements of emerging technologies. In this paper, we cast logic optimization as a deterministic Markov decision process (MDP). We then take advantage of recent advances in deep reinforcement learning to build a system that learns how to navigate this process. Our design has a number of desirable properties. It is autonomous because it learns automatically and does not require human intervention. It generalizes to large functions after training on small examples. Additionally, it intrinsically supports both single- and multi-output functions, without the need to handle special cases. Finally, it is generic because the same algorithm can be used to achieve different optimization objectives, e.g., size and depth.

 

 

 

 

AI+EDA

Synthesis, gate sizing, technology mapping