PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepGate2: Functionality-Aware Circuit Representation Learning

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

arXiv:2305.16373v1cs.LGcs.AIcs.AR

TL;DR

DeepGate’s logic-probability supervision can miss differences between circuits with equal probabilities, while repeated message passing limits efficiency. DeepGate2 uses pairwise truth-table differences and a single-round GNN; experiments report improved prediction and downstream SAT-sweeping runtime.

  • Problem

    Logic-1 probability does not identify which primary-input assignments produce 1, so circuits with equal probabilities but different functions can be indistinguishable under DeepGate’s supervision.

    Source: B. DeepGate Framework · p. 2

  • Method

    DeepGate2 uses pairwise truth-table differences as functional supervision and a single-round GNN with separate structural and functional embedding streams.

    Source: §I · p. 1

  • Results

    DeepGate2 improves prediction accuracy over DeepGate and reduces SAT-sweeping total runtime by an average of 49.46%.

    Source: B. Comparison with DeepGate on… · p. 5, 2) Results · p. 7

  • Takeaways & Limitations

    The framework is applied in EDA tools for logic synthesis and SAT solving, with experiments reported to validate its efficacy in these downstream tasks.

    Source: §I · p. 1

Abstract

from arXiv · show

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

I. INTRODUCTION

DeepGate2 addresses limitations in functionality supervision and message-passing efficiency with truth-table-difference supervision and a single-round GNN. Experiments report improved prediction and downstream EDA results.

A. Circuit Representation Learning

  • Circuit representation learning uses task-agnostic pretraining followed by task-specific fine-tuning, while structure-focused models are not suited to functionality-related tasks.Functionality-aware alternatives include contrastive learning and logic-probability supervision, each with limitations described in the introduction.Source: §I · p. 1, A. Circuit Representation Learning · p. 2

I. INTRODUCTION

  • DeepGate’s logic-1 probability supervision can treat gates with opposite truth tables as equivalent when their probabilities match.A NOT gate and its fan-in gate can both have logic-1 probability 0.5 despite opposite truth tables.Source: §I · p. 1
  • DeepGate assigns identical initial embeddings to primary inputs, requiring repeated propagation to distinguish reconvergent structures and making large-circuit processing inefficient.The model needs multiple forward and backward rounds to recover logical correlations from local structure.Source: §I · p. 1
  • DeepGate2 supervises gate representations with pairwise truth-table differences, using incomplete truth tables from rapid simulation and a loss matching embedding distance to functional difference.This adds functional information beyond statistical properties such as logic-1 probability.Source: §I · p. 1
  • Its single-round GNN uses separate functional and structural embeddings, initialized uniformly and with orthogonal PI vectors, then aggregates them through two streams.The architecture combines structural and functional information in one forward message-passing round.Source: §I · p. 1
  • DeepGate2 improves logic-probability prediction accuracy and achieves an order-of-magnitude speedup over DeepGate, with downstream applications in logic synthesis and SAT solving.The experiments are reported as validating the framework’s efficacy in those applications.Source: §I · p. 1

B. DeepGate Framework

DeepGate embeds both structural and functional information, but its probability supervision and repeated message passing limit functional discrimination and efficiency. DeepGate2’s formulation aims to align embedding distances with truth-table similarity.

B. DeepGate Framework

  • DeepGate represents digital circuits with gate-level embeddings of structural and functional information, using logic-1 probability supervision and attention-based, levelized aggregation.Its inputs are preprocessed into an And-Inverter Graph format.Source: B. DeepGate Framework · p. 2
  • Logic-1 probability records how many truth-table entries are 1, not which input assignments produce 1, so equal probabilities can conceal different functions.Thus, DeepGate cannot distinguish circuits with the same probability using this supervision alone.Source: B. DeepGate Framework · p. 2
  • DeepGate’s identical initial embeddings make some first-round messages identical, so distinguishing nodes by their connections requires repeated forward and backward propagation.The framework performs 20 rounds, limiting efficiency on large circuits.Source: B. DeepGate Framework · p. 2
  • DeepGate2 addresses these shortcomings with unique PI identification, one-round message passing, and pairwise truth-table-difference supervision.The stated aim is to capture both structural information and functional differences between gates.Source: B. DeepGate Framework · p. 2

A. Problem Formulation

  • The problem formulation seeks embeddings whose distances reflect functional similarity, so equivalent circuits are close while differing truth tables yield differentiated representations.The examples contrast circuits that share logic probability but differ in truth-table similarity.Source: A. Problem Formulation · pp. 2–3

B. Dataset Preparation

Dataset preparation uses sampled gate pairs and incomplete truth tables to provide functional supervision without exhaustive simulation. The sampling rules constrain which pairs contribute to training.

B. Dataset Preparation

  • Truth tables provide direct functional supervision, but their length grows exponentially with the number of primary inputs, making complete simulation impractical.The chosen supervision should be readily obtained while remaining closely related to the truth table.Source: B. Dataset Preparation · p. 3
  • Training maps node pairs into an embedding space so embedding distance is positively correlated with the Hamming distance between their truth tables.The truth-table vector and embedding vector for node i are denoted T_i and h_i, respectively.Source: B. Dataset Preparation · p. 3
  • Treating each gate as the output of a logic cone with the original primary inputs yields many training circuits from one parsed circuit.This converts graph learning into node-level representation learning and reduces data-collection difficulty.Source: B. Dataset Preparation · p. 3
  • Pairs share primary inputs, have logic probabilities within 5% and logic levels within 5, and represent extreme truth-table differences of at most 20% or at least 80%.Incomplete truth tables are obtained by imposing a maximum simulation time; circuits use an AIG netlist format.Source: B. Dataset Preparation · p. 3

C. Functionality-Aware Loss Function

DeepGate2 aligns embedding distances with pairwise truth-table differences and uses a one-round GNN to represent both circuit function and structure. Its separated embeddings are updated differently as information propagates from primary inputs to primary outputs.

C. Functionality-Aware Loss Function

  • The functionality-aware objective minimizes the difference between embedding distance and truth-table Hamming distance for sampled node pairs.Embedding distance is based on cosine similarity, and should vary proportionally with truth-table distance.Source: C. Functionality-Aware Loss Function · p. 3

D. One-round GNN Model

  • Primary inputs receive uniform initial functional embeddings and unique orthogonal structural embeddings.The functional initialization reflects equal logic probability under random simulation; the structural initialization identifies each input.Source: D. One-round GNN Model · p. 3
  • The model uses separate aggregators for structural and functional embeddings of AND and NOT gates.The described design includes structural and functional aggregators for AND gates and updates for NOT gates.Source: D. One-round GNN Model · pp. 3–4
  • Self-attention aggregators assign greater importance to controlling inputs when updating gate embeddings.For an AND gate, any logic-0 fan-in forces a logic-0 output.Source: D. One-round GNN Model · p. 4
  • One-round propagation updates structural embeddings from predecessor structure and functional embeddings from predecessor structure and function.Propagation proceeds level by level from primary inputs to primary outputs.Source: D. One-round GNN Model · p. 4

E. Model Training Strategies

Training proceeds in two stages, beginning with logic-probability prediction and structural-correlation identification, then adding functionality-aware learning. The later stage combines all three task losses, allowing the model to learn functional similarity among probability-equivalent nodes.

Stage 1

  • Stage 1 trains the one-round GNN on logic-probability prediction and structural-correlation identification.The model reads functional embeddings to predict logic probability and structural embedding pairs to predict reconvergence.Source: E. Model Training Strategies · p. 4
  • Logic-probability prediction uses L1 loss against ground-truth probabilities obtained through random simulation.Structural-correlation prediction uses a binary target indicating whether two nodes have a common predecessor.Source: E. Model Training Strategies · p. 4

Stage 2

  • Stage 2 adds the more difficult functionality-aware Task 3 while retaining the probability and structural-correlation losses.The Stage 2 loss weights the three task losses by wprob, wrc, and wfunc.Source: E. Model Training Strategies · p. 4

Training strategy

  • Stage 1 distinguishes gates with different probabilities, while Stage 2 learns functional similarity among probability-equivalent nodes.Logic-equivalent pairs have the same probability, according to the passage.Source: E. Model Training Strategies · p. 4

IV. EXPERIMENTS

The experiments evaluate DeepGate2's representation learning on two function-related tasks and compare it with DeepGate and FGNN. They also investigate model design and training strategies.

Comparisons

  • The experiments compare DeepGate2 with DeepGate and FGNN on logic-probability prediction and logic-equivalent-gate identification.These are described as two function-related tasks.Source: §IV · p. 4

Experimental scope

  • The experiments include preliminary details on dataset preparation, evaluation metrics, and model settings.These details are assigned to Section IV-A.Source: §IV · p. 4
  • Separate investigations assess the effectiveness of model design and training strategies.These investigations are assigned to Sections IV-D and IV-E.Source: §IV · p. 4

A. Experiment Settings

The experiments use a dataset of circuit AIGs and evaluate logic-probability prediction and logic-equivalent-gate identification. The reported performance comparisons cover ten industrial circuits.

1) Dataset Preparation:

  • The dataset contains 10,824 AIGs from ITC’99, IWLS’05, EPFL, and OpenCore, with gate counts ranging from 36 to 3,214.The dataset includes 894,151 node pairs, with an 80/20 training/test split.Source: 1) Dataset Preparation · p. 4

2) Evaluation Metrics:

  • Logic-probability prediction is evaluated by average prediction error, while gate-equivalence identification uses Recall, Precision, F1-Score, and AUC.A gate pair is positive when its truth-table Hamming distance is zero; the similarity threshold is selected using the ROC.Source: 2) Evaluation Metrics · p. 5
  • Performance comparisons use ten industrial circuits ranging in size from 3.18k to 40.50k gates.Source: 2) Evaluation Metrics · p. 5

3) Model Settings:

DeepGate2 improves probability prediction and logic-equivalence identification over prior models, while PI encoding supports more accurate recognition of reconvergent structure.

3) Model Settings:

  • The one-round GNN uses 64-dimensional structural and functional embeddings, and models are trained for 80 epochs with batch-size 16 on one Nvidia V100 GPU.DeepGate2 is trained for 60 epochs to ensure convergence; the other models retain their original settings and are trained until convergence.Source: 3) Model Settings · p. 5

B. Comparison with DeepGate on Probability Prediction

C. Comparison with other Models on Logic Equivalence Gates Identification

  • DeepGate2 achieves an average F1-score of 0.9434 on logic-equivalence identification, versus 0.6778 for DeepGate and 0.4402 for FGNN.DeepGate's average recall is 91.46% but its precision is 54.00%; 80.83% of its false positives involve pairs with similar logic probability.Source: C. Comparison with other Models on… · p. 6

D. Effectiveness of PI Encoding Strategy

  • Without PI encoding, average logic-equivalence F1-score falls from 0.9434 to 0.7541, while reconvergence-identification accuracy drops from 93.22% to 74.56%.The passage attributes the decline to the one-round GNN's inability to model circuit structure without unique PI identifiers.Source: D. Effectiveness of PI Encoding Strategy · p. 6

E. Effectiveness of Training Strategies

The section motivates staged functionality learning and describes DeepGate2's integration into practical EDA workflows, including functionality-guided SAT sweeping.

E. Effectiveness of Training Strategies

  • Multi-stage training reaches an average F1-score of 0.9434, compared with 0.7137 without staging; its functionality loss is 51.47% smaller.The first stage learns logic probability and structural correlation; the second learns functionality, using pairs with similar logic probability because pairwise comparisons scale with circuit size squared.Source: E. Effectiveness of Training Strategies · p. 6, Table IV · p. 7, Table V · p. 7

V. DOWNSTREAM TASKS

  • DeepGate2 is applied to logic synthesis and SAT solving, with functional similarity guiding synthesis and dissimilar-function variables assigned the same decision value in SAT solving.The passage says this SAT approach shrinks the search space by enabling solvers to encounter more constraints.Source: §V · p. 6

A. Logic Synthesis

  • SAT-sweeping managers are described as selecting candidate equivalence classes structurally; the proposed manager instead ranks classes by embedding cosine similarity and prioritizes more-similar pairs for solver calls.The SAT sweeper checks selected pairs, merges proven equivalents, and uses counterexamples to refine candidate classes.Source: 1) Experiment Settings · pp. 6–7, A. Logic Synthesis · p. 6

1) Experiment Settings:

  • The model is integrated as an ABC plug-in in the '&fraig' SAT sweeper, and resulting AIGs are checked with ABC's '&cec' command for functional correctness.The comparison is against the original '&fraig' engine.Source: 1) Experiment Settings · p. 7

2) Results:

Across six industrial circuits, DeepGate2-guided SAT sweeping reduces solver calls and runtime relative to the baseline. The section also connects learned functional correlation to SAT solving.

2) Results:

  • 53.37% average reduction in satisfiable SAT calls and 49.46% average runtime reduction are reported for the DeepGate2-based sweeper.The comparison is against '&fraig'; the tested circuits are swept to the same size.Source: 2) Results · p. 7, Table VI · p. 8
  • For circuit C1, guidance from DeepGate2 reduces SAT calls by 95.88% and runtime by 57.77% by prioritizing gates with similar behavior.The passage contrasts this with '&fraig', which selects gates without considering their behavior.Source: 2) Results · p. 8

B. Boolean Satisfiability Solving

  • The SAT-solving application builds on prior work using logic-gate functional correlation for variable decisions, which relied on time-consuming logic simulation to obtain functionality.The paper presents DeepGate2 as a way to model functional correlation efficiently and accelerate SAT solving.Source: B. Boolean Satisfiability Solving · p. 8

1) Experiment Settings:

DeepGate2 uses gate-function similarity to guide CaDiCal’s variable decisions, reducing total runtime across the tested instances. The conclusion also reports improved representation performance and tenfold model-efficiency gains over DeepGate.

1) Experiment Settings:

  • Gate similarities transfer through the gate-to-CNF mapping to variable correlations; assigning correlated unassigned variables the reverse value is intended to prompt conflicts.The joint-decision rule compares similarity against 1−δ.Source: 1) Experiment Settings · p. 8, 2) Results · p. 8
  • The SAT comparison tests the hybrid solver against original CaDiCal on five industrial instances using one 2.40GHz Intel Xeon E5-2640 v4 CPU.Overall runtime includes both model inference and solver runtime.Source: 1) Experiment Settings · p. 8, 2) Results · p. 8

2) Results:

  • 40.05% average runtime reduction across all test cases; for I1, runtime fell from 88.01s to 32.02s, a 63.62% reduction.Overall runtime combines model inference and solver runtime.Source: Table VII · p. 8, 2) Results · p. 8
  • DeepGate2 inference takes a few seconds, averages less than 10% of overall runtime, and runs in time proportional to instance size.The largest instances I4 and I5 showed smaller reductions, but I2, of similar size, showed a significant reduction; the paper attributes variation to instance characteristics.Source: 2) Results · p. 8

VI. CONCLUSION

  • The conclusion reports improved logic-probability prediction and equivalent-gate identification, with model efficiency improved tenfold over DeepGate.DeepGate2 separates structural and functional embeddings and updates both through one round of GNN message-passing.Source: §VI · p. 8

Related papers

Loading 2305.16373v1…