Retrieval-Guided Reinforcement Learning for Boolean Circuit Minimization
Authors: Animesh Basak Chowdhury
Marco Romanelli
Benjamin Tan
Ramesh Karri
Siddharth Garg
Venue: ICLR 2024 poster (2024)
Keywords: Electronics Design Automation (EDA)
Logic Synthesis
Reinforcement Learning
Hardware design
Circuits
Primary area: infrastructure, software libraries, hardware, etc.
TL;DR: We propose Retrieval Guided RL for logic synthesis to generalize for diverse hardware. Pre-trained agents, combined with MCTS fails on novel designs. We adjusts agent recommendations using nearest neighbor similarity scores for improved synthesis.

Abstract: Logic synthesis, a pivotal stage in chip design, entails optimizing chip specifications encoded in hardware description languages like Verilog into highly efficient implementations using Boolean logic gates. The process involves a sequential application of logic minimization heuristics (``synthesis recipe"), with their arrangement significantly impacting crucial metrics such as area and delay. Addressing the challenge posed by the broad spectrum of hardware design complexities — from variations of past designs (e.g., adders and multipliers) to entirely novel configurations (e.g., innovative processor instructions) — requires a nuanced 'synthesis recipe' guided by human expertise and intuition. This study conducts a thorough examination of learning and search techniques for logic synthesis, unearthing a surprising revelation: pre-trained agents, when confronted with entirely novel designs, may veer off course, detrimentally affecting the search trajectory. We present ABC-RL, a meticulously tuned $\alpha$ parameter that adeptly adjusts recommendations from pre-trained agents during the search process. Computed based on similarity scores through nearest neighbor retrieval from the training dataset, ABC-RL yields superior synthesis recipes tailored for a wide array of hardware designs. Our findings showcase substantial enhancements in the Quality of Result (QoR) of synthesized circuits, boasting improvements of up to 24.8\% compared to state-of-the-art techniques. Furthermore, ABC-RL achieves an impressive up to 9x reduction in runtime (iso-QoR) when compared to current state-of-the-art methodologies.

Published as a conference paper at ICLR 2024
RETRIEVAL-GUIDED REINFORCEMENT LEARNING FOR BOOLEAN CIRCUIT MINIMIZATION
Animesh Basak Chowdhury'
Marco Romanelli'
Benjamin Tan?
Ramesh Karri'
Siddharth Garg'
New York University
University of Calgary
(abc586,,m63822rkarii,,, @nyu.edu, (benjamin.tan I) Baaaannlluuuararr
@ucalgary.ca
ABSTRACT
Logic synthesis, a pivotal stage in chip design, entails optimizing chip specifica- tions encoded in hardware description languages like Verilog into highly efficient implementations using Boolean logic gates. The process involves a sequential application of logic minimization heuristics ("synthesis recipe"), with their arrange- ment significantly impacting crucial metrics such as area and delay. Addressing the challenge posed by the broad spectrum design complexities from variations of past designs (c.g., adders and multipliers) to entirely novel configurations (e.g., innovative processor instructions) - requires a nuanced 'synthesis recipe' guided by human expertise and intuition. This study conducts thorough examination of learning and search techniques for logic synthesis, unearthing a surprising revela- tion: pre-trained agents, when confronted with entirely novel designs, may veer off course, detrimentally affecting the search trajectory. We present ABC-RL, a metic- ulously tuned parameter that adeptly adjusts recommendations from pre- tre-trained agents during the search process. Computed based on similarity scores through nearest neighbor retrieval from the training dataset, ABC-RL yields superior syn- thesis recipes tailored for a wide array of hardware designs. Our findings showcase substantial enhancements in the Quality-of-result (QoR) of synthesized circuits, boasting improvements of up to 24.8% compared to state-of-the-ar techniques. Fur- thermore, ABC-RL achieves an impressive up to 9x reduction in runtime (iso-QoR) when compared to current ofate-of-the-as methodologies.
INTRODUCTION
Modern chips are designed using sophisticated electronic design automation (EDA) algorithms that automatically convert logic functions expressed a hardware description language (HDL) like Verilog to physical layout that can be manufactured at semiconductor foundry. EDA involves sequence of steps, the first of which logic synthesis. Logic synthesis converts HDL into a low-level "netlist" of Boolean logic gates that implement the desired function. A netlist is graph whose nodes are logic gates (e.g., ANDs, NOTs,, ORs) and whose edges represent connections between gates. Subsequent EDA steps like physical design then place gates on an x-y surface and route wires between them. As the first step in the EDA flow, any inefficiencies in this step, e.g., redundant logic gates, flow down throughout the EDA flow. Thus, the quality of logic synthesis-the area, power and delay of the synthesized netlist- is crucial to the quality of the final design (Amarú et al. 2017).
As shown in Fig. [ state-of-art logic synthesis algorithms perform a sequence of functionality- preserving transformations, e.g., eliminating redundant nodes, reordering Boolean formulas, and streamlining node representations, to arrive at final optimized netlist Yang et al. (2012); Mishhhenko al..)
et al. (2019): Yu (2020) (2020) et al. (2022). A specific sequence of transformations is called a "synthesis recipe." " Typically, designers use experience and intuition to pick a "good" synthesis recipe from the solution space of all recipes and iterate if the quality of result is poor. This manual process is costly and consuminnn,ng, especially for modern, complex chips. Further, the design space of synthesis recipes is large. ABC (Brayton & Mishchenko 2010)) tfte-offart open-source synthesis tool, provides a toolkit of 7 transformations, yielding a design space of 10? recipes (assuming 10-step recipes). A growing body of work has sought to leverage machine learning

---

Published as a conference paper at ICLR 2024
and reinforcement learning (RL) to automatically identify high-quality synthesis recipes (Yu et al.
2018; Hosny et al. 2020; Zhu et al. 2020: Yu 2020: Neto et al.) 2022: Chowdhury et al. 2022 showing promising results.
Prior work in this area falls within one of two cat- egories. The first line of work YYul 2020 Neto
module L Jn sanuoon)
In2
Noces
And- Invert Graph
et a 2022) proposes efficient search heuristics, Monte-Carlo tree search (MCTS) in particular, to explore the solution space of synthesis recipes for given netlist. These methods train a policy agent during MCTS iterations, but the agent is initialized from scratch for a given netlist and does not learn from past data, e-g., repositories of previously synthesized designs abundant in chip design companies, or sourced from public repositories (Chowdhury et al. 2021 Thakur et al. 2023).
In
Sum
Depth:
Cout
suppat
Cholces (M) 7
x1.22.3xx
Nodes:
anage omm a1rr2han
Depth:
aesign oou'
balance (b)
Ax1x22x3.d
Nodes:
3 Degth
RTL verllog
Technology mapping
QoR
Best
length (L/m 10
Recipe
xIX2
Figure 1: (Left) A hardware design in Verilog is first transformed into an and-inverter-gret -gaphh (AIG), i.e., a netlist containing only AND and NOT gates. Then a sequence of functionality-presed (here, picked from set (rw, generate an optimized AIG. Each such sequence called a synthesis recipe. The synthesis recipe with the best quality of result (QoR) (e.g., area or delay) is shown in green. (Right) Applying rw and b to AIG results results in an AIG with fewer nodes and lower depth.
To leverage experience from past designs, a sec- ond line of work seeks to augment search with learning. Chowdhury et al. (2022) show that predictive QoR model trained on past designs with simulated annealing-base baaeidnggg-ddeddddeee search can out- perform prior search-only methods by as much as 20% in area and delay. The learned model replaces consuming synthesis runs- a sin- gle synthesis run can take around 10.9 minutes in our experiments-wwe wwith fast but approximate QoR estimates from pre-trained deep network.
transformations .... b }) is applied
Reduction (%) N. t
16
14
10
MCTS
MCTS MCTS-Learning
Motivational Observation. Given the tree- structured search space (see F. we begin by building and evaluating a baseline solution that: 1) pre-trains an offline RL agent on dataset of past designs; and then 2) performs RL-agent guided MCTS search over synthesis recipe space for new designs. Although details vary, this strategy has been successful in other tree-search problems, most prominently in AlphaGoo (Silver et al. 2016) and AlphaZero Silver et al. (017). Interestingly, we found that although the agent learned on past data helps slightly on average, on 11 out of 20 designs, the baseline strategy underperformed simple MCTS search (see Table 2 for detailed results). Fig. 2 shows two examples: in both, pure MCTS achieves better solutions faster than learning augmented MCTS. Ideally, we seek solutions that provide consistent improvements over search-only methods by leveraging past data.
MCTS-Learning
20 40 60 80
100
60 BD Iterations
Iterations
(a) square
(b) cavle
Figure 2: Reduction in area-delay product (greater re- duction is better) over search iterations for a pure search strategy (MCTS) and search augmented with learning (MCTS+Learinng). Learning an offfine policy does not help in both cases.
One reason for poor performance is the large diversity of netlists in logic synthesis benchmarks. Netlists vary significantly in size (100-46K nodes) and function. The EPFL benchmarks, for example, partition netists into those that perform arithmetic functions (e.g. adders, dividers, square-roots) and control functions (e.g., finite state machines, pattern detectors, etc.) because of large differences in their graph structures. In practice, while designers often reuse components from past designs, they frequently come up with new designs and novel functions. For netlists that differ significantly from those in the training dataset, pre-trained agents hurt by diverting search towards suboptimal recipes.
Overview of Approach. We propose ABC-RL, a new retrieval guided RL approach that adaptively tunes the contribution of the pre-trained policy agent in the online search stage depending on the input netlist. ABC-RL computes a tuning factor a E [0. 1] by computing a similarity score of the input netlist and its nearest neighbor retrieved from the training dataset. Similarity is computed neural network (GNN) features learned during training. If the new netlist is identical to one in the training dataset, we a O, and only the pre-trained agent is used output the synthesis recipe. Conversely, when a = 1 (i.c., the netlist is novel), the pre-trained agent is ignored and ABC-RL
graph
2

---

Published as a conference paper at ICLR 2024
defaults search strategy. Real-world netlists lie in between these extremes; accordingly ABC-RL modulating the relative contributions of the pre-trained agent and pure MCTS search to the final result. We make careful architectural choices in implementation of ABC-RL, including the choice of netlist and synthesis recipe encoders and state-space representation. They are described in [eeciion 2.3 Although our main contribution is ABC-RI., the MCTS+ baseline (i.e., without retrieval) has not been evaluated for logic synthesis. Our evaluations highlight its benefits and drawbacks.
Snapshot of Results and Key Contributions. Across three common logic synthesis benchmark suites ABC-RL consistently outperforms prior SOTA ML-based logic synthesis solutions, our own MCTS+ MCTS+Learming baseline, and an MCTS+ Learnigg solution for chip placement Mirhoseini al. (2021). different EDA problem, adapted to logic synthesis. ABC-RL achieves upto 24.8% geo. mean improvements in QoR (here, area-delay product) over SOTA, At iso-QoR, ABC-RL reduces synthesis runtime by up to 9x.
In summary, our key contributions are:
We propose ABC-RL, a new retrieval-guided RL approach for logic synthesis that learns from past historical data, i.e., previously seen netlists, optimize the QoR for a new netlist test time. In doing so, we identify distribution shift between training and test data as key problem this domain, and show that a baseline strategy that augments MCTS with pre-trained policy agent Silverr et al. (2016) fails to improve upon pure MCTS search.
To address these concerns, we introduce new lightweight retrieval mechanism in ABC-RL that uses the similarity score between the new test netlist and its nearest neighbor in the training set. This score modulates the relative contribution of pre-trained RI. agent using modulation parameter o, down-weighting the learned policy depending on the novelty of the test netlist.
We make careful architectural choices for ABC-RL's 's policy agent, including new transformer based synthesis encoder, and evaluate across three of common logic synthesis benchmarks. ABC- RL consistently outperforms prior SOTA ML for logic synthesis methods QoR and runtime, as also a recent ML for chip-placement method (Mirhoseini et al.] (021) adapted to our problem setting. Ablation studies establish the importance of a-tuning ABC-RL.
We now describe ABC-RL, starting with a precise problem formulation and background.
PROPOSED APPROACH
2.1 PROBLEM STATEMENT AND BACKGROUND
We begin by formally defining the logic synthesis problem using ABC (Brayton & Mishchenko 2010), the leading open-source synthesis tool, as an exemplar. As shown in Figure ABC first converts the Verilog description of a chip into unoptimized And-Invert-Graph (AIG) Go E G. where G is the set of all directed acyclic graphs. The AIG represents AND gates as nodes, wires/NOT gates solid/dashed edges, and implements the same Boolean function as the input Verilog. Next, ABC performs a series of functionality-pressvvinn
transformations on Gg. Transfornations are picked from finite set of M actions, A = {rf, rm,..... b). For ABC, M 7. Applying an action on an AIG yields new AIG as determined by the synthesis function S G x A + G. A synthesis recipe R E A is a sequence P = {ag, Q1..... a (a: E A). we obtain G++1 S(G,, 0;) for all i E [0, L - 1] where G', is the final optimized AIG. Finally, let QoR G IR measure the quality of graph G, for instance, its inverse area-delay product (so larger is better). Then, we seek to solve this optimization problem:
L actions that are applied to Go in order. Given a synthesis recipe
argmax QoR(GL), s.t. G S(G,, a,) Vi E L. 1].
PEAL
We now discuss ABC-RL, our proposed approach to solve this optimization problem. In addition to Go. the AIG to be synthesized, we will assume access to training set of AIGs to aid optimization.
2.2 BASELINE MCTS -BASED OPTIMIZATION
The sree-structured solution space for logic synthesis motivated prior work (Yu 2020; Neto et al. 2022) adopt MCTS- based search strategy that we briefly review here. A state here is the
3

---

Published as a conference paper at ICLR 2024
current AIG after transformations. In given state, any action E A can be picked described above. Finally, the reward QoR(GL) is delayed to the final synthesis step. In iteration & of the search, MCTS keeps track of two functions: QMTTs (s, a) which is measure the "goodness" of state action pair, and U (c a) which represents upper confidence tree (UCT) factor that encourages exploration of less visited states and actions. The policy (MOTs(s) (8) balances exploitation against exploration by combining the two terms. Further details are in A.3
k MCTs(() = argmax (OMCTs(s, U (cT)s(t,))
aeA
2.3 PROPOSED ABC-RL METHOODOLOGY
We describe our proposed solution two steps. First, we describe MCTS+Learning, which builds similar principles as [Silver et al. (2016) by training an reinforcement learning (RL) policy agent on prior netlists to guide Monte Carlo tree search (MCTS) search, highlighting how prior work is adapted to the logic synthesis problem. Then, describe our full solution, ABC-RL, that uses novel retrieval-guided augmentation to significantly improve MCTSLLeerming
MCTS+Learning Learning: As noted, that outputs the probability of taking action a in state s by approximating the pure MCTS policy on the training set. We first describe our state-space representation and policy network architecture.
dataset of Ner training circuits to learn policy agent na (s(s, a)
Initial AIG
Past heuristies sequence (0-10)
State-space and policy network architecture: We encode state as as a two-tuple of the input AIG, Go. and sequence of S. L synthesis actions, i.e., A = {ag, ai,... . at taken so far. Because the two inputs are in different formats, our policy network has two parallel branches that learn embeddings of AIG Go and partial recipe.
Node features (1x2)
GCN (1x32)
Transfommer enuoder
GCN (Lx32)
BN W
For the AIG input, we employ 3-layer graph convolutional net- work (GCN)
Sequicee emibedding (1x768)
Welling (2016) architecture to obtain an embed- ding hG.- We use LeakyREi.U as the activation function and apply batch normalization before each layer. (See appendix $B.11 for de- tails.) In contrast to prior work that directly encodes recipes Chowd hury et al. 2022), we use simple single attention layer BERT trans- former architecture Devlin al. (2018) compute partial recipe embeddings, A which we concatenate with AIG embeddings. We make this choice since partial synthesis recipes are variable length, and to better capture contextual relationships within a sequence of actions. Ablation studies demonstrate the advantages of this ap- proach. The final embedding is a concatenation on the AIG and partial synthesis recipe embeddings.
pool
pool
AIG embolding
FC (832x256) IBN RELLU
FC (256x256) +BN HLaakyRELU
FC (256x))
Softmax
(s-))
Figure 3: Policy network archi- tecture. GCN: Graph convolution network. BN: Batch normaliza-
RI RL-agent training: With the policy network in place, policy (s, a) is learned on training dataset of past netlists using cross-entrops loss between the learned policy and the MCTS policy over samples picked from a replay buffer. The learned policy is used during inference to bias the upper confidence tree (UCT in Eq. 2 of MCTS towards favorable paths by computing new U U a). For completeness, we outline the pseudocode for RI.-training in the appendix (Algorithm
tion, FC: Fully connected layer
U*k UNters(s, a) = ne(s, a) Uk UMCrsss.a).
2.4 RETRIEVAL-GUIDED LOGIC SYNTHESIS (ABC-RL)
As we noted, hardware designs frequently contain both familiar and entirely new components. In the latter case, our results indicate that the leamned RL-agents can sometimes hurt performance novel inputs by biasing search towards sub-optimal synthesis recipes. In ABC-RL, we introduce a new term [0, 1] in Equation 3 that strategically weights the from pre- pre-trained agents contribution, completely turning it off when a 1 (novel circuit) and defaulting to the baseline approach when
=
4

---

Published as a conference paper at ICLR 2024
valdaatin
Winner ?
cincuity
Quary
Training
corpus
Piva
Guide
Collact dala
Quary
Agent
6yais
MCTS
MCTS LLearning
MOTS+a luned leaming
Agent
Nearest neighbour
ratrieual
Train
AUROC
O
3)(0,4)
neighbbou
Set temp, (T), Divesfold 6z.
Agent
Dywes
retreval
Generatee recipe
Figure ABC-RI. flow: Training the agent (left), setting temperature 7 and threshold 8en (mid) and Recipe generation at inference-tine (right)
(1) Similarity score computation: To quantify novelty new netlist, Gg. at test-time, we compute similarity score with respect to its nearest neighbor in the training dataset Drr {G ..... G ,,,), To avoid expenseive nearest neighbor queries in the graph space, for instance, via sub-graph iso- morphisms, we leverage the graph encodings, lig already learned by the policy agent. Specifically, we output the smallest cosine distance (A (ha,, hG,)
he, -he, between the test AIG hha, llbog! embedding and all graphs in the training set: dG. min, eos (hG. hat))
(2) Tuning agent's s recommendation during MCTS: To modulate the balance between the prior learned policy and pure search, we update the prior UCT with a E [0, 1] as follows:
U UMCTts(s a) = (o(s, a))s)))(aa) U MMTs(ssa))
(4)
and a is computed by passing similarity score, dGg through sigmoid function, a o. (66.). with threshold (6tz) and temperature (T) hyperparameters.
defined as o..,
Itc
4 allows a to smoothly vary in [0. 1] as intended, while threshold and temperature hyperparameters control the shape of the sigmoid. Threshold 8en controls how close new netlists have to be to the training data to be considered "novel." In general, small thresholds bias ABC-RL towards more search and less learning from past data. Temperature &th, controls the transition from "previously seen" novel. Small temperatures cause ABC-RL to create a harder thresholds between previously seen and novel designs. Both hyperparameters are chosen using validation data.
(3) Putting it all together: In Fig. 4 we present an overview of the ABC-RL. We begin by training an RL-agent on training dataset D.,. Then, we use a separate held-out validation dataset to tune threshold, duh and temperature, T, by comparing wins/losses of baseline MCTS+Leariig RL and performing a grid-search. During inference on a new netlist Go. ABC-RL retrieves the nearest neighbor from the training data, computes and performs online a-guided search using weighted recommendations from the pre-trained RI. agent.
ABC-
3 EMPIRICAL EVALUATION
3.1 EXPERIMENTAL SETUP
Datasets: We consider three datasets used by logic synthesis community: MCNC Yang 1991), EPFL arithmetic and EPFL random control benchmarks Amarú et al. (2015). MCNC benchmarks have 38 netlists ranging from 100-8K nodes. EPFL arithmetic benchmarks have operations like additions, multiplications etc. and have 1000-44K nodes. EPFL random control benchmarks have finite-state machines, routing logic and other functions with 100 -46K nodes.
Train-test split: We randomly split the 56 total netlists obtained from all three bench- marks into 23 netlists for training 13 for val- idation (11 MCNC. 1 EPFL-arith, 1 EPFL- rand) and remaining
Split
Circuits
alu2, apex3, apex5, b2, c1355, c5315, c2670, c6288, prom2, fig i7, 18, m3, max512, table5, adder, log2, max, multiplier, arhiter, ctrl, int2float, priority
Truin
Valid
apex7, c1908, c3540, frg2, max 128, apex6, c432, c499, sey, table3, i10, sin, i2c
alu4, apex 1, apex2, apex4, 19, m4, promt, 69, c880, c7552, pair, max bar, div, square, sqrt (AI-A4), cavle, mem couter, voter (RI-R4)
max1024 1024 (CI-C12).
Test.
Table 1: Training, validation and test splits in experiments. Netlists from each benchmark are represented in each split. the test set, MCNC netlists are relabeled [C1-C12], EPFL-arith to [A1-A4] and EPFL-control to [RI-R4].
5

---

Published as a conference paper at ICLR 2024
20 for test (see Table D. We ensure that netlists from each benchmark are represented propor- tionally in training, validation and test data.
Optimization objective and metrics: We seek to identify the best L = 10 synthesis recipes. Consistent with prior works Hosny et al. (2020); Zhu ct al. (2020); Neto et al. (2022), we use area- delay product (ADP) as QuR metrie. Area and delay values are obtained using 7nm technology library post-technology mapping of the synthesized AIG. As a baseline, we compare against ADP of the resyn2 synthesis recipe as is also done in prior work Neto et al. (2022); Chowdhury et al. (2022). In addition to ADP reduction, we report runtime reduction of ABC-RL at iso-QoR, i.e., how much faster ABC-RL is in reaching the best ADP achieved by competing methods. During evaluations on test circuits, we give each technique total budget of 100 synthesis runs.
Training details and pyper-parameters: To train our RL-agents, we use He initialization He et al. (2015) for weights and following Andrychowicz et al. 2020), multiply weights of the final layer with 0.01 to prevent bias towards any one action. Agents are trained for 50 epochs using Adam with an initial learning rate of 0.01. In each training epoch, we perform MCTS on all netlists with an MCTS search budget K 512 per synthesis level. After MCTS simulations, we sample L Ntr (Ner is the number of training circuits) experiences from the replay buffer (size 2 x L x Nor) for training. To stabilize training, we normalize QoR rewards (Appendix C.I and clip to [-1, +1] Mnih et al. (2015). We set T 100 and d'h 0.007 based on our validation data.
We performed the training on a server machine with one NVIDIA RTX A4000 with 16GB VRAM. The major bottleneck during training is the synthesis time for running ABC; actual gradient updates are relatively inexpensive. Fully training the RL-agent training took around 9 days.
Baselines for comparison: We compare ABC-RL with five main methods: (1) MCTS: Search-only
MCTS Neto et al. 20022; (2) DRiLLS: RL agent trained via A2C using hand-crafted AIG features
(not on past-training data) Hosny et al. (2020) (3) Online-RL:: RL: RL agent trained online via PPO
using Graph Convolutional Networks for AIG feature extraction (but not on past training data) (Zhu ct al. 2020 (4) SA+Pred: simulated annealing (SA) with QoR predictor learned from training data Chowdhury et al. (2022); and (5) (eannn(ea our own baseline MCTS+Learning solution using a pre-trained RL-agent (Section ??). MCTS and SA+Pred are the current state-of- the-art( (SOTA) methods. DRiLLS and Online-RL. are similar and under-perfone MCTS. We report results versus exisitng methods for completeness. MCTS+L is new and has not been evaluated on logic synthesis. A final and sixth baseline for comparison is MCTS+L+FT (Mirhoseini al.) 2021) which is proposed for chip placement, a different EDA problem, but we adapt for logic synthesis. MCTS+FT is similar to MCTS+L but continues to fine-tune its pre- pre-trained RL-agent on test inputs.
3.2
EXPERIMENTAL RESULTS
3.2.1
ABC-RL Vs. SOTA
In Table 2 we compare ABC-RL over SOTA methods Hosny al. (2020); : Zhu et al. (2020): Neto et al. (2022); [hhowdhury et al. (2022) in terms of percentage area-delay product (ADP) reduction (relative the baseline resyn2 recipe). We also report speed-ups of ÁBC-RL to reach the same QoR as the SOTA methods. Given the long synthesis runtimes, speed-up at iso-QoR as an equally important metrie. Overall, ABC-RL achieves the largest geo. mean reduction in ADP, reducing ADP by 25% (smaller ADP is better) over resyn2. The next best method is our own MCTS+L implementation which achieves 20.7% ADP reduction, although it only slightly better than MCTS.
ABC-RL is also consistently the winner in all but four netlists, and in each of these cases ABC- RL finishes second only marginally behind the winner. Interestingly, the winner in these cases is Online+RI, method that overall has the poorest performance. Importantly, ABC-RL is consistently better than MCTS+L and MCTS. That is, we show that both learning on past data and using retrieval are key to good performance. Finally, ABC-RL is also faster than competing methods with a geo. mean speed-up of 3.8x over SOTA. We dive deeper into specific benchmark suite to understand where ABC-RL's improvements stem from.
ABC-RL provides with substantial improvements on benchmarks such as Cl (apex1), C7 (proml), C9 (c88C), and C12 (max1 02 Fig. Figoos the ADP reductions over search iterations for MCTS, SA+Pred, and ABC-RL over four netlists from MCNC. Note from Fig [ that ABC-RL in most cases achieves higher ADP reductions earlier than competing methods. Thus,
MCNC benchmarks:

---

Published as a conference paper at ICLR 2024
20
22
17.5
18
14
15.0
10
12.5
14
12
MCTS
7.5
10
Pred.
5.0
ABC-RL
20
40
100
20
40
60
100
20
40
60
100
20
40
60
100
lterations
Iterations
Iterations
Iterati ons
(a) alu4
(b) apex
(c) c880
(d) apex4
Figure 5: Arca-delay product reduction (in %) compared resyn2 on MCNC circuits.
16-
30
25
14-
12-
16
28
20
Reduction
10
14
26
15
10
10
ABC-BL (wio tune)
ABC-BL
80
100
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
Iterations
Iter Iterations
Iterations
Iterations
square
(b) cavle
(c) voter
(d) c7552
Figure 6: Area-delay product reduction %) using ABC-RL compared MCTS+Leaming.
designers can terminate search when desired ADP is achieved. This results in run-time speedups upto 5.9x at iso-QoR compared to standard MCTS, (see Appendix D.I.I for complete results)
Table 2: Arca-delay reduction (%) compared to resyn2: DRiLLS Hosny et al, (222)), Online-Ro RL Zhu et al. (220), SA+Pred. ShhoPrelCCowdhury et al. 2002 MCTS et al. 2022), LCTSnLe (MCTS+L) and ABC-RL. Speed-up vs. MCTS
ADP reduction (in %)
Methods
MCNC
EPFL
random
C1
C2
C3
C4
CS
C6
C7
C8
C9
C10
CII
C12
A1
A2
A3
A4
RI
R2
R3
R4
mean
DRiLLS
18.9
6.7
8.0
13.0
38.4
19.1
5.4
18.0
14.3
18.6
6.6
11.0
28.8
34.7
11.1
22.7
1544
23.0
12.9
10.1
16.1
Online-RL
20.6
8.1
13.5
39.4
21.0
5.0
17.9
16.2
20.2
4.
11.4
36.9
34.8
24.1
16.3
22.5
10.7
8.3
16.1
Pred.
17.6
17.0
15.6
13.0
46.5
18.2
8.5
23.6
19.9
17.6
10.0
20.3
36.9
25.2
8.2
21.1
16.8
21.5
25.7
26.2
19.7
MCTS
17.1
15.9
13.1
13.0
46.9
14.9
6.5
23.2
17.7
20.5
13.1
19.7
25.4
46.0
10.7
18.7
15.9
21.6
21.6
27.1
19.8
MCTS+L
17.0
168
55,9
22.7
20.7
ABC-RL
19.9
19.6
16.8
15.0
46.9
19.1
12.1
24.3
21.3
21.1
13.6
21.6
36.9
56.2
14.0
23.8
19.8
30.2
38.9
30.0
25.3
Iso-QoR
Speed-up
1.9x 5.9x
1.8x
1.6x
1.2x
1.xx
3.2x
4.1x
2.2x
1.2x 0.9x 1.8x
3.7x 9.0k
4.2x 8.3x
5.0x
6.4x
3.1x
5.7x
3.8x.
EPFL benchmarks: ABC-RL excels 7 of EPFL designs, particularly demonstrating significant improvements on A3 (square). ), RI (cavlc), and R3 (mem ctrl) compared to prior methods Hosny et al. (2020); Zhu et al. (020): Chowdhury et al. (2022) Neto et (2022). Notably, baseline MCTS+ MCTS+Learing performs poorly on A3 (square). RI (cavlc), and R4 (voter). In Fig. 6 we illustrate how ABC-RL fine-tunes for various circuits, carefully adjusting pre-trained recommendations to avoid unproductive exploration paths. Across all EPFL benchmarks, ABC-RL consistently achieves superior ADP reduction compared to pure MCTS, with a geometric ADP reduction of 28.85% over resyn2. This significantly improves QoR over standard MCTS and SA+Pred., by 5.99% and 6.12% respectively. Morcover, ABC-RL delivers an average of 1.6x runtime speed-up at iso-QoR compared to standard MCTS Neto et al. (022), up to 9x speed-up.
3.2.2 BENCHMARK SPECIFIC ABC-RL AGENTS VS. SOTA
To further examine the benefits of ABC-RL in terms of netlist diversity, train three benchmark- specific ABC-RL agents on each benchmark suite using, as before, the train-vaidation-esy splits in Table I Although trained on each benchmark individually, evaluation of benchmark-sppeciinn agents on the full test dataset. This has two objectives: 1) Assess how benchmark-speccnn agents compare against the benchmark-wide agents their test inputs, and 2) Study how ABC-RL's benchmark-
7

---

Published as a conference paper at ICLR 2024
specific agents adapt when deployed test inputs from other benchmarks. Benchmark-specine agents are referred to as ABC-RL+X, where X is the benchmark name (MCNC, ARITH, or RC).
Table 3: Area- delay reduction (in %) obtained using benchmark specific agents (MCNC, ARITH and RC).
MCTS represents tree search adopted in Neto et al. (2022)
ABC-RL
ADP reduction (in %)
iMethods
agents
MCNC
EPFL arith
EPFL random
Geo.
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
A1
A2
A3
A4
R2
R3
R4
mean
ABC-RL 19.9
19.6
16.8
15.0
46.9
19.1
12.1
24,3
21.3
21.1
13.6
21.6
36.9
56.2
14.0
23.8
19.8
30.2
38,9
30.0
25.3
+MCNC
20,9
19.2
17.5
15.0
52.5
18.1
10.9
24.1
24.7
21.1
16.8
22.0
32,9
47.9
1099
18.7
18.2
24.0
24.5
27.1
21.3
+ARITH
18.0
16.0
17.3
13.0
46.9
20.3
8.8
23.2
20.0
24.1
13.1
20.8
36,9
55.9
12.1
25.1
16.9
21.5
21.8
27.7
21.4
17.4
12.5
11.9
23.3
22.5
20.4
13.1
20.0
36.5
10.8
17.8
26.6
21.7
MCTS 17.1
15.9
13.1
13.0
46.9
14.9
6.5
23.2
17.7
20.5
13.1
25.4
45,9
10.7
18.7
15.9
21.6
21.6 2
19.8
In Table 3 we present the performance of ABC-RL using benchnark-specífic agents. Notably, ABC- RL+X agents often outperform the general ABC-RL agent on test imputs from their own benchmark suites. For example, ABC-RL+MCNC outperforms ABC-RL on 7 of 12 benchmarks. In return, the performance of benchmark-speccie new netlists are novel for the agent. Nonetheless, our benchmark-specife agents still outperform the SOTA MCTS approach in geo. mean ADP reduction. In fact, if except ABC-RL, each of our benchmark-specific agents would still outperform other SOTA methods including MCTS+L. These results emphasize ABC-RL's ability fine-tune a effectively, even in the presence of a substantial distribution gap between training and test data.
agents drops test inputs from other benchmarks because these
3.3 ABC-RL Vs. MCTS+L+FT
In recent work, Mirhoseini et al. (2021) proposed pre-trained PPO agent for chip placement. This problem seeks to place blocks on the chip surface so as to reduce total chip area, wire-length and congestion. Although the input to chip placement is also a graph, the graph only encodes connectivity and not functionality. Importantly, an action in this setting, e.g. moving or swapping blocks, is quick, allowing for millions of actions to be explored. In contrast, for logic synthesis, actions (synthesis steps) involve expensive peeetionality-reeserve
graph-level transformations on the entire design taking up to minutes for larger designs. To adapt to new inputs, MMrrhoseini et al. (202T) adopt a different strategy: they continue to fine-tune (FT) their agents as they perform search test inputs. Here we ask if the FT strategy could work for ABC-RL instead of our retrieval-guided solution.
Table 4: Arca-delay reduction (in %). BERTT is ABC-RI. trained with naive synthesis encoder instead of BERT. MCTS FT indicate MCTS+I .caming with online fine-tuning.
ADP reduction (in %)
Ablation study
MCNC
EPFL arith
EPFL random
Goo.
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
CII
C12|
Al
A2
A3
A4|
R1
R2
R3
R4
mean
ABC-RL
19.9
19.6
168
15.0
46.9
19.1
12
24.3
21.
21.1
13.6
21.6
369
562
14.0
23.8
19.8
30.2
38.9
30.0
25.3
17.1
18.0
15.0
14.1
37.9
10.1
24.3
173
19.6
10.0
20.0
369
55.9
10.7
22.1
20.0
30.2
38.9
28.3
23.3
ABC RL. BERT
17.0
16.5
14.9
13.1
446
16.9
10.0
23.5
16.
18.8
10.6
19.0
36.9
51.7
9.9
20.0
15.5
23.0
28.0
26.9
21.2
To test this, we fine-tune ABC-RL's benchmark- agent during online MCTS within our evaluation budget of 100 synthesis runs. Table 4 compares ABC-RL vs. the new MCTS+L#FT approach. ABC- RL outperforms MCTS+L+FT on all but one netlist, and reduces ADP by 2.66%, 2.40% and 0.33% on MCNC, EPFL., and random control benchmarks, with 9.0% decline on C5 (1
3.3. 1 IMPACT OF ARCHITECTURAL CHOICES
We inspect the role of BERT-based recipe encoder in ABC-RL by replacing it with a fixed length (L = 10) encoder where, using the approach from (Chowdhury et al. 2022), we directly encode the synthesis commands in numerical form and apply zero-padding for recipe length less than L. The results are shown in Table 4 ABC-RL reduces ADP by 2,51%, 4.04% and 4. 4.11% on MCNC, EPFL arithmetic and random control benchmarks, and upto -1090% decline R3 (router), compared encoder in extracting meaningful features from synthesis recipe sub-sequences for state representation.
to the version without BERT. This shows the importance of transformer-
8

---

Published as a conference paper at ICLR 2024
4 RELATED WORK
Learning-based approaches for logic synthesis: This can be classified into two sub-categories: 1)
Synthesis recipe classification (Yu et al. 2018: Neto et al. 2019) and prediction (Chowdhury et al.
2021 2022 based approaches. and 2) R based approaches (Haaswijk et al., 2018 Hosny et al.
2020 Zhu et al., 2020). Neto al. (2019) partition the original graph into smaller sub-networks and pertorms binary classification on sub-networks to pick which recipes work best. On the other hand, RI.-based solutions Haaswijk et al. (2018); Hosny et al. (2020); Zhu al. (2020) use online
RL algorithms to craft synthesis recipes, but do not leverage prior data. We show that ABC-RL outperforms them.
ML for EDA: ML has been used for a range of EDA problems Mirhoseini et al. (202 Kurin et al. (2020); Lai et al. (2022 2023); Schmitt et al. (202T) Yolcu & Póczos (2019); Vasudevan et al. (2021): Yang et al. (2022. Closer to this work, Mirhoseini et al. (2021) used a deep-RL agent to optimize chip placement, a different problem, and use the pre-trained agent (with online fine-tuning) to place the new design. This leaves limited scope for online exploration. Additionally, each move action in placement, i.e., moving the x-y co-ordinates of modules in the design, is cheap unlike time-consuming actions in logic synthesis. Thus placement agents can be fine-tuned with larger amounts of test-time data relative to ABC-RL which has a constrained online search budget. Our ablation study shows ABC-RL defeats search combined with fine-tuned agent for given synthesis budget. related body of work developed general representations of boolean circuits, for instance, DeepGate Li et al. (2022); ;
Shi al. (2023). CORTES Chowdhury et al. (2023) and "functionality matters" Wang et al. (2022) learned on signal probability estimation and functionality prediction, respectively. These embeddings
could enhance the quality of our GCN embeddings and are interesting avenues for future work.
RL and search for combinatorial optimization: Fusing learning and search finds applications across diverse domains such as branching heuristics (He et al. 2014), Go and chess playing (Silver (et al. 2016 Scchritwiessrr et al. (2020), traveling salesman (TSP) (Xing & Tu 2020), and common subgraph detection (Bai et al. 2021). Each of these problems has unique structure. TSP and common subgraph detection both have graph inputs like logic synthesis but do not perform transformations on graphs. Branching problems have tree-structun self-play during training and must anticipate opponents. Thus these works have each developed specialized solutions tailored to the problem domain, as we do with ABC-RI. Further, these previous works have not identified distribution shift as a problem and operate atleast under the assumption that train-test state distributions align closely.
but do not operate on graphs. Go and Chess involve
Retrieval guided Reinforcement learning: Recent works (Goyal et al. 2022 Humphreys et al. 2022) have explored the benefits of retrieval in game-playing RL-agents. However, they implement retrieval differently: trajectories from prior episodes are retrieved and the entire trajectory is an additonal input to the policy agent. This also requires the policy-agent to be aware of retrieval during training. In contrast, our retrieval strategy lightweight; instead of an entire graph/netlist, we only retrieve the similarity score from the training dataset and then fix a. In addition, we do not need to incorporate the retrieval strategy during training, enabling off-the-shelf use of pre-trained RL agents. ABC-RL already significantly outperforms SOTA methods with this strategy, but the approach might be beneficial in other settings where online costs are severely constrained.
5 CONCLUSION
We introduce ABC-RL, novel methodology that optimizes learning and search through retrieval- guided mechanism, significantly enhancing the identification of high-quality synthesis recipes for new hardware designs. Specifically, tuning the a parameter of the RL agent during MCTS search within the synthesis recipe space effectively mitigates misguided searches toward unfavorable rewarding trajectories, particularly when encountering sufficiently novel designs. These core concepts, substan- tiated by empirical results, underscore the potential of ABC-RL in generating high-quality synthesis recipes, thereby streamlining modern complex chip design processes for enhanced efficiency.
Reproducibility Statement For reproducibility, we provide detailed information regarding method- ologies, architectures, and settings in Section 3.1

---

Published as a conference paper at ICLR 2024
REFERENCES
Luca Amarú, Eeerre-m Gaillardon, and Giovanni De Micheli. The epfi combinational benchmark suite. In Proceedings of the 24th International Workshop on Logic & Synthesis (IWLS), number CONF, 2015.
Luca Amarú, Patrick Vuillod, Jiong Luo, and Janet Olson. Logic optimization and synthesis: Trends and directions in industry. Design, Automation Test in Europe Conference Exhibition (DATE), 2017, pp. 1303-1305. IEEE, 2017.
Marcin Andrychowicz, Anton Raichuk, Piotr Stańczyk, Manu Orsini, Sertan Girgin, Raphael Marinier, Léonard Hussenot, Matthieu Geist, Olivier Pictquin, Marcin Michalski, et al. What matters in on-policy reinforcement learning? large-scale empirical study. arXiv preprint arXiv:2006.05990, 2020.
Yunsheng Bai, Derek Xu, Yizhou Sun, and Wei Wang. Glsearch: Maximum common subgraph detection via learning search. In International Conference on Machine Learning, pp. 588-598. PMLR, 2021.
Robert Brayton and Alan Mishchenko. ABC: An Academic Industrial-Strength Verification Tool. In Tayssir Touili, Byron Cook, and Paul Jackson (eds.), Computer Aided Verification, pp. 24-40. 2010.
Robert K Brayton, Gary D Hachtel, Curt McMullen, and Alberto Sangiovanni- Vincentelen Logic minimization algorithms for VLSI synthesis, volume 2. Springer Science & Business Media, 1984.
anngiovaami-iiceetellii
Animesh Chowdhury, Jitendra Bhandari, Luca Collini, Ramesh Karri, Benjamin Tan, and Siddharth Garg. CORVERTS: Contrastively learning structurally invariant netlist representations. In 2023 ACM/IEEE 5th Workshop on Machine Learning for CAD (MLCAD), pp. 1-6. IEEE, 2023.
Animesh Basak Chowdhury, Benjamin Tan, Ramesh Karri, and Siddharth Garg. OpenABC-D: A large-scale dataset for machine learning guided integrated circuit synthesis. arXiv preprint arXiv:2110. 1292, 2021.
Animesh Basak Chowdhury, Benjamin Tan, Ryan Carey, Tushit Jain, Ramesh Karri, and Siddharth Garg. Bulls-eye: Active few-shot learning guided synthesi.. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 2022.
Jacob Devlin, Ming-Wai Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: DeXXiv:18100. 1810.04805 2018.
Anirudh Goyal, Abram Friesen, Andrea Banino, Theophane Weber, Nan Rosemary Ke, Adria Puig- domenech Badia, Arthur Guez, Mehdi Mirza, Peter C Humphreys, Ksenia Konyushova, et al. Retrieval- augmenned reinforcement learning. In International Conference on Machine Learning, pp. 7740-7765. PMLR, 2022.
Winston Haaswijk, Edo Collins, Benoit Seguin, Mathias Soeken, Frédéric Kaplan, Sabine Süsstrunk, and Giovanni De Micheli. Deep learning for logic optimization algorithms. In International Symposium on Circuits and Systems (ISCAS), pp. 1-4, 2018
He He, Hal Daume III, and Jason M Eisner. Learning search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
AbdeIrahman Hosny, Soheil Hashemi, Mohamed Shalan, and Sherief Reda. DRiLLS: Deep rein- forcement learning for logic synthesis. In Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 581-586, 2020.
Peter Humphreys, Arthur Guez, Olivier Tieleman, Laurent Sifre, Théophane Weber, and Timothy Lillicrap. Large-scale retrieval for reinforcement learning. Advances in Neural Information Processing Systems, 35:20092-20104, 2022.
10

---

Published as a conference paper at ICLR 2024
Thomas N Kipf and Max Welling. Semi- Semi-suueeeiied classification with graph convolutional networks. arXiv preprint arXiv:1609 1609.029777 2016.
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In Machine Learning: ECML 2006: 17th European Conference Machine Learning Berlin, Germany, September 18-22. 2006 Proceedings 17, pp. 282-293. Springer, 2006.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Can q-learning with graph networks learn generalizable branching heuristic for solver? Advances in Neural Information Processing Systems, 33:9608-9621, 2020.
Yao Lai, Yao Mu, and Ping Luo. Maskplace: Fast chip placement via reinforced visual representation learning. Advances Neural Information Processing Systems, 45:24019-22400, 2022.
Yao Lai, Jinxin Liu, Zhentao Tang. Bin Wang, Jianye Hao, and Ping Luo. Chipformer: Transferable chip placement via offline decision transformer. arXiv preprint arXiv:2306. /4744, 2023.
Min Li, Sadaf Khan, Zhengyuan Shi, Naixing Wang, Huang Yu, and Qiang Xu. Deepgate: Learning neural representations logic gates. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pp. 667-672, 2022.
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. A graph placement methodology for fast chip design. Nature, 594(7862):207-213 2021.
Alan Mishchenko, Satrajit Chatterjee, and Robert Brayton. DAG-aware aig rewriting: A fresh look combinational logic synthesis. In Design Automation Conference (DAC), pp. 532-535, 2006.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 5 51807540):599-533 2015.
Walter Lau Neto, Max Austin, Scott Temple. Luca Amaru, Xifan Tang, and perre-Emmanuee Gaillardon. LSOracle: a logic synthesis framework driven by artificial intelligence: Invited paper. In International Conference on Computer-Aided Design (ICCAD), pp. 1-6, 2019.
Walter Lau Neto, Yingjie Li, Pierre-Emmanuel Gaillardon, and Cunxi Yu. Flowtune: End-to- end automatic logic optimization exploration via domain-specific multi-armed bandit. IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 2022.
Heinz Riener, Eleonora Testa, Winston Haaswijk, Alan Mishchenko, Luca Amarù, Giovanni De Micheli, and Mathias Soeken. Scalable generic logic synthesis: One approach to rule them all. In Proceedings of the 56th Annual Design Automation Conference 2019, pp. 1-6, 2019.
Frederik Schmitt, Christopher Hahn, Markus N Rabe, and Bernd Finkbeiner. Neural circuit synthesis from specification patterns. Advances in Neural Information Processing Systems, 34:15408-15444
2021.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-609, 2020.
Zhengyuan Shi, Hongyang Pan, Sadaf Khan, Min Li, Yi Liu, Junhua Huang. Hui-Ling Zhen, Mingxuan Yuan, Zhufei Chu, and Qiang Xu. Deepgate2: Functionality-awan circuit representation learning. arXiv preprint arXiv:2305. 16373, 2023.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwiessrr, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484488) 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint 1rXiv:1712.01815, 2017.
11

---

Published as a conference paper at ICLR 2024
Shailja Thakur, Baleegh Ahmad, Hammond Pearce, Benjamin Tan, Brendan Dolan- Gavitt, Ramesh Karri, and Siddharth Garg. Verigen: A large language model for verilog code generation. arXiv preprint XX1v:2338.00008 2023.
Shobha Vasudevan, Wenjie Joe Jiang, David Bieber, Rishabh Singh, C Richard Ho, Charles Sut- ton, et al. Learning semantic representations to verify hardware designs, Advances in Neural Information Processing Systems, 34:23491-23504, 2021.
Ziyi Wang, Chen Bai, Zhuolun He, Guangliang Zhang, Qiang Xu, Tsung- Yi Ho, Bei Yu, and Yu Huang. Functionality matters in netlist representation learning. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pp. 61-66, 2022.
Zhihao Xing and Shikui Tu. A graph neural network assisted monte carlo tree search approach to traveling salesman problem. IEEE Access, 1.100848-108444 2020.
Saeyang Yang. Logic synthesis and optimization benchmarks user guide: version 3.0. Citeseer, 1991.
Wenlong Yang, Lingli Wang, and Alan Mishchenko. Lazy man's logic synthesis. In Proceedings of the International Conference Computer-Aided Design, pp. 597-604, 2012.
Zhihao Yang, Dong Li, Yingxueff Zhang, Zhanguang Zhang, Guojie Song, Jianye Hao, al. Versatile multi-stage graph neural network for circuit representation. Advances in Neural Information Processing Systems, 35:20313 203244 2022.
Emre Yolcu and Barnabás Póczos. Learning local search heuristics for boolean satisfiability. Advances in Neural Information Processing Systems, 32, 2019.
Cunxi Yu. Flowtune: Practical multi-armed bandits in boolean optimization. In International
Conference On Computer Aided Design (ICCAD), pp. 1-9, 2020.
Cunxi Yu, Houping Xiao, and Giovanni De Micheli. Developing synthesis flows without human knowledge. In Design Automation Conference (DAC), pp- 1-6, 2018.
Keren Zhu, Mingjie Liu, Hao Chen, Zheng Zhao, and David Z. Pan. Exploring logic optimizations with reinforcement learning and graph convolutional network. In Workshop on Machine Learning for CAD (MLCAD). pp. 145-150, 2020.
12

---

Published as a conference paper at ICLR 2024
A
APPENDIX
A.1
LOGIC SYNTHESIS
Logic synthesis transforms hardware design in register transfer level (RTL) to Boolean gate-level network, optimizes the number of gates/depth, and then maps it to standard cells in a technology library Brayton et al. (1984). Well-known representations of Boolean networks include sum-of- product form, product-of-sum, Binary decision diagrams, and AIGs which are a widely accepted format using only AND (nodes) and NOT gates (dotted edges). Several logic minimization heuristics (discussed in Section A.2)) have been developed to perform optimization on AIG graphs because of its compact circuit representation and directed acyclic graph (DAG)-based structuring. These heuristics are applied sequentially ("synthesis recipe") to perform one-pass logic optimization reducing the number of nodes and depth of AIG. The optimized network then mapped using cells from technology library to finally report area, delay and power consumption.
A.2 LOGIC MINIMIZATION HEURISTICS
We now describe optimization heuristics provided by industrial strength academic tool ABC Brayton & Mishchenko (2010):
Balance (b) optimizes AIG depth by applying associative and commutative logic function tree- balancing transformations to optimize for delay.
Rewrite (rw, rw -z) directed acyclic graph (DAG)-aware logic rewriting technique that performs template pattern matching on sub-trees and encodes them with equivalent logic functions.
Refactor (rf, rf -z) performs aggressive changes the netlist without caring about logic sharing. It iteratively examines all nodes in the AIG, lists out the maximum fan-out-free cones, and replaces them with equivalent functions when it improves the cost (c.g., reduces the number nodes).
4. Re-substitution (rs, -Z) creates new nodes in the circuit representing intermediate functionalities using existing nodes; and remove redundant nodes. Re-substitution improves logic sharing.
The zero-cost (-z) variants of these transformation heuristics perform structural changes to the netlist without reducing nodes or depth of AIG. However, previous empirical results show circuit transformations help future passes of other logic minimization heuristics reduce the nodes/depth and achieve the minimization objective.
A.3 MONTE CARLO TREE SEARCH
We discuss in detail the MCTS algorithm. During selection, search tree is built from the current state by following a search policy, with the aim of identifying promising states for exploration.
where QMeTs(s, (s, denotes estimated Q value (discussed next) obtained after taking action from state during the k iteration of MCTS simulation. U represents upper confidence tree (UCT) exploration factor of MCTS search.
log (Eo Nk (MCTs(s,a)
U U = cUCT =uccss
(5)
N
N (M (s, a) denotes the visit count of the resulting state after taking action a from state 8. CUCT denotes constant exploration factor Kocsis & Szepesvári (2006).
The selection phase repeats until a leaf node is reached in the search tree. A leaf node in MCTS tree denotes either child nodes have been ereated it terminal state of the environment. Once a leaf node is reached the expansion phase begins where an action is picked randomly and its roll value is returned or R(sL) is returned for the terminal state sy. Next, back propagation happens where all parent nodes Qu (x, a) values are updated according to the following equation.
Ny. Niter (
Σ
RMCTS( a) a)Nhhrr(sss)))
(6)
13

---

Published as a conference paper at ICLR 2024
A.4 ABC-RL AGENT PRE- TREETININING PROCESS
As discussed in Section 2.3 we pre-train an agent using available past data to help with choosing
which logic minimization heuristic to add to the synthesis recipe. The process is shown as Algorithm
Algorithm ABC-RL: Policy agent pre-training
procedure TRAINING())
2:
Replay buffer (RB) <- Φ, Dtrain {AIG1, AIG2. AIG,). num hamm__ecoss,,, Recipe
Length=L, AIG embedding network: A, Recipe embedding network: R, Agent policy me = U (Uniform distribution), MCTS iterations K, Action space A
3:
for AIG; E Drrain do
4:
+- 0, depth 0
5:
5- A(AGG)) + R(r)
6:
while depth do
7:
TMCTS = . MS,
8:
a wrgmazgeeTTMCTSSSSccc
9:
r - + 0. A(AIG)) R(r)
RB < RB a, (SCTS
11:
s', depth + depth +1
12:
for epochs N do
13:
A a o C(MMMTTS
B NETWORK ARCHITECTURE
B. AIG NETWORK ARCHITECTURE
AIG encoding in ABC: An AIG graph is a directed acyclic graph representing the circuit's boolean functionality. We read the same AIG format introduced in Mishchenko et al. (2006) and commonly used in literature: nodes in the AIG represent AND gates, Primary Inputs (Pis) or Primary Outputs (POs). On the other hand, NOT gates are represented by edges: dashed edges represent NOT gates (i.e., the output of the edge is logical negation of its input) and solid edges represent simple wire whose output equals its input.
Starting with graph G (V, E) that has vertices V and edges E, the GCN aggregates feature information of node with its neighbors' node information. The output is then normalized using Bat chthhnomm and passed through non-linear LeakyReTO activation function. This process is repeated for layers to obtain information for each node based on information from its neighbours up to distance of k-hops. A graph-level READOUT operation produces graph-level embedding. Formally:
GCN-based AIG embedding:
h VN(u)= X (N() bb), E [1..K]
h (W
Σ (EaLN(()
hG READOUT (VV
Here, the embedding for node u, generated by the t layer of the GCN, is represented by hitt The parameters We and by are trainable, and is non-linear ReLU activation function. N(-) denotes the I-hop neighbors of a node. The READOUT function combines the activations from the 4thh layer of all nodes produce the final output by performing pooling operation.
Each node the AIG read from ABC translated a node in our GCN, For the initial embeddings, ho. We use two-dimensional vector to encode node-level features: (1) node type (AND, PI, PO) and global
and (2) number of negated fan-in edges Chowdhury et (2021 2022). we choose average and max pooling concatenated the READOUT operation.
Architectural choice of GNN: We articulate our rationale for utilizing a simple Graph Convolutional Network (GCN) architecture to encode AIGs for the generation of synthesis recipes aimed at optimizing the area-delay product. We elucidate why this approach is effective and support our argument with experiment that validates its efficacy:
14

---

Published as a conference paper at ICLR 2024
Working principle of logic synthesis transformations: Logic synthesis transformations ABC (and in general commercial logic synthesis tools) including rewrite, refactor and re-substitute performs transformations at local subgraph levels rather than the whole AIG structure. For e.g. rewrite performs a backward pass from primary outputs to primary inputs, perform k-way cut at each AIG node and replace the functionality with optimized implementation available in the truth table library of ABC. Similarly, refactor randomly picks fan-in cone of an intermediate node of AIG and replaces it with different implementation if it reduced the nodes of AIG. Thus, effectiveness of any synthesis transformations do not require deeper GCN layers; capturing neighborhood information upto depth our case worked well to extract features out of AIG which can help predict which transformation next can help reduce area-delay product.
Feature initialization of nodes in AIG: The node in our AIG encompasses feature: i) Type of node (Primary Input, Primary Output and Internal Node) and ii) Number negated fan-ins. Thus, our feature initialization scheme takes care of the functionality even though the structure of AIG are exactly similar and the functionality. Thus, two AIG having exact same structure but edge types are different (dotted edge represent negation and solid edge represent buffer), the initial node features of AIG itself will be vastly different and thus our 3-layer GCNs have been capable enough to distinguish between them and generate different synthesis recipes.
important
Several recent GNN-based architectures Li et al. recently to capture functionality of AlG-based hardware representations. This remains an active exploration direction to further enhance the benefits of ABC-RL. distinguish structurally similar yet substantially varying in functionality space.
2022); Shi et al. (2023) have been proposed
C EXPERIMENTAL DETAILS
C.I REWARD NORMALIZATION
In our work, maximizing QoR entails finding recipe P which minimizing the area-delay product of transformed AIG graph. We consider as baseline recipe an expert-crafted synthesis recipe resyn2 Mishchenko et al. (2006) on top of which we improve our ADP.
ADP(SIG.P)
ADP(S(G, P)) < ADP(S(G,P)) otherwise.
R
re
C.2 BENCHMARK CHARACTERIZATION
We present the characterization of circuits used in our dataset. This data provides a clean picture on size and level variation across all the AIGs.
15

---

Published as a conference paper at ICLR 2024
Name
Inputs
Outputs
Nodes
level
alu2
10
401
40
alu4
10
6
735
42
apex
45
45
2655
27
apex2
39
3
445
29
apex3
54
50
2374
21
apex4
19
3452
21
apex5
117
88
1 1280
21
apex6
135
99
659
apex?
49
37
221
b2
16
17
1814
22
105
C432
36
C499
32
C880
60
26
327
C1355
41
32
504
C1908
31
25
414
32
C2670
233
140
717
21
C3540
50
22
1038
41
C5315
178
123
1773
38
C6288
32
32
2337
120
C7552
207
108
2074
29
frg1
28
126
19
frg2
143
139
1164
i10
257
224
2675
50
17
199
67
904
i8
133
81
3310
19
63
889
16
434
m4
16
760
max 1024
10
1021
max 128
24
536
max512
6
743
19
pair
173
137
1500
24
proml
40
7803
24
prom2
21
3513
22
seq
41
35
2411
29
tahle3
14
14
2183
24
table5
17
15
1987
26
adder
256
129
1020
255
bar
135
128
3336
12
div
128
128
44762
4470
log2
32
32
32060
444
max
512
130
2865
287
multiplier
128
128
27062
274
sin
24
25
5416
225
sqrt
128
64
24618
5058
square
62
128
18484
250
arbiter
256
129
11839
87
ctrl
26
174
cavle
10
11
693
i2c
147
142
1342
20
int2float
11
7
260
16
mem etrl
1204
1231
46836
114
priority
128
8
978
250
router
60
30
257
54
voter
1001
13758
70
Table 5: Benchmark characterization: Primary inputs, outputs, number of nodes and level of AIGs
16

---

Published as a conference paper at ICLR 2024
14
50
12
177.5
125
40
10.0
30
12.5
7.5
2.5
10
5.0
20
40 60
60
100
20
40
60
80
100
20
40
60
100
20
48
60
80
100
Iterations
Iterations
Iterations
Iterations
(a) b9
(b) apex2
(c) proml
(d) i9
20.0
15.0
25
17.5
20.0
20
10.0
17.5
12.5
7.5
10.0
12.5
7.5
2.5
10.0
40
80
100
20
40
60
80
100
20
40
60
80
100
Iterations
Iterationn
Iber Perations
(e) m4
(f) pair
(g) max 1024
(h) c7552
Figure Area-delay product reduction (in %) compared to resyn2 MCNC circuits.
GREEN:
PA+Pred, Chowdhury et al. (2022). BLUE: MCTS al. (202). RED: ABC-RL
D RESULTS
D.1 PERFORMANCE OF ABC-RL AGAINST PRIOR WORKS AND BASELINE MCTS+LEARNING
D.1.1 MCNC BENCHMARKS
Figure plots the ADP reductions over search iterations for MCTS, SA+Pred, and ABC-RL. In m4, ABC-RL's 's agent explores paths with higher rewards whereas standard MCTS continues scarching without further improvement. A similar trend is observed for proml demonstrating that a pre-trained agent helps bias search towards better parts of the search space. SA+Pred. Chowdhury et al. (2022) also leverages past history, but is unable to compete (on average) with MCTS and ABC-RL. in part because SA typically underperforms MCTS tree-based search spaces. Also from Figure that ABC-RL in most cases achieves higher ADP reductions earlier than competing methods (excepl pair). This results in significant geo. mean run-time speedups of 2.5x at iso- Mo-QQRR compared to standard MCTS on MCNC benchmarks.
D.1.2 EPFL ARITHMETIC BENCHMARKS
Figure 8 illustrates the performance of ABC-RL in comparison to state-of-the-art methods: Pure MCTS Neto et al. (2022) and SA+Prediction Chowdhury et al. (2022). In contrast to the scenario where MCTS+Bascline underperforms pure MCTS (as shown in here observe that ABC- RL. effectively addresses this issue, resulting in superior ADP reduction. Remarkably, ABC-RL achieved geometric mean 5.8x iso-QoR speed-up compared to MCTS across the EPFL arithmetic benchmarks.
16
25
35
50
40
20
30
10
15
20
20
10
MCTS
15-
SA-Pred
20
40
60
8D
100
20
60
100
Iterations
Iterations
Iterations
Iterations
(a) bar
(b) div
(c) square
(d) sqrt
Figure Arca-delay product reduction (in %6) compared resyn2 EPFL arithmetic benchmarks, GREEN:
SA+Pred. Chowdhury et al. 2002), BLUE: MCTS Neto et al. (2022) RED: ABC-RL
17

---

Published as a conference paper at ICLR 2024
D.1.3
EPFL RANDOM CONTROL BENCHMARKS
20
30
35
28
116-
30
26
Redurtion
14
12
1.
20
15
10
15
22
20
SA-Pred Pred.
10
16
ABC-AL
20
60
80
100
20
40
60
100
20
60
100
Iterations
Iterations
Iterations
(a) cavle
(b) mem_etri
(c) router
(d) voter
Figure 9: Area-delay product reduction (in %) compared to resyn2 on EPFL random control benchmarks. On cavle and router, ABC-RL perform better than MCTS where baseline MCTS+Leaming under-perform. GREEN: PA+Pred, Chowdhury el al. (2022), BLUE: MCTS et al. (2022), RED: ABC-RL.
D.2 PERFORMANCE OF BANCCMMRR-SPECIIEE ABC-RL AGENTS
out of 12 MCNC benchmarks, ABC-RL guided by the MCNC agent demonstrated improved performance compared to the benchmark-wide agent. This suggests that the syper-parameters (6t, and T') derived from the validation dataset led to optimized a values for MCNC benchmarks. However, the performance of the MCNC agent was comparatively lower EPFL arithmetic and random control benchmarks.
ABC-RL+MCNC agent:
ABC-RL+ARITH agent: Our EPFL arith agent resulted in better ADP reduction compared to benchmark- wide agent only on A4(sqrt). This indicate that benchmark- agent is able to learn from diverse of benchmarks resulting in better ADP reduction. On MCNC benchmarks, observe that ARITH agent performed the best amongst all on C6(m4) and C10 (c7552) because these are arithmetic circuits.
Our RC agent performance on EPFL random control benchmarks are not that great compared benchmark-wel agent. This is primarily because of the fact that EPFL random control benchmarks have hardware designs performing unique functionality and hence learning from history doesn't help much. But, ABC-RL ensures that performance don't 't detoriate compared pure MCTS.
ABC-RL+RE agent:
D.3 PERFORMANCE OF ABC-RL VERSUS FINE-TUNING (MCTS+L+FT)
MCNC Benchmarks: Fig. we depict the performance comparison among MCTS+finetune agent, ABC-RL, and pure MCTS. Remarkably, ABC-RL outperforms MCTS+finetune 11 out of 12 benchmarks, approaching MCTS+finetune's performance on b9. A detailed analysis of circuits where MCTS+finetune performs worse than pure MCTS (19, m4, pair, c880, max1 4 and c7552) reveals that these belong to out MCNC designs where MCTS+lcarning performs suboptimally compared to pure MCTS. This observation underscores the fact that although finetuning contributes to a better geometric mean over MCTS+leamiig (23.3% over 20.7%), it still falls short. benchmarks, alu4 and apex4, MCTS+MMMntttt
on 6 out of 8 benchmarks. For the remaining performs comparably to pure MCTS for alu4 and slightly better for apex4. Thus, ABC-RL emerges as more suitable choice for scenarios where fine-tuning resource-intensive. yet we seek versatile agent capable of appropriately guiding the search away from unfavorable trajectories.
EPFL Benchmarks: In Fig. [ and 12] we present the performance comparison with MCTS+finetune Notably, for designs bar and div, MCTS+finctune achieved equivalent ADP as ABC-RL, main- taining the same iso so-QoR speed-up compared to MCTS. These designs exhibited strong perfor- mance with baseline MCTS+Learning, thus aligning with the expectation of favorable results with MCTS+finetune. On square, MCTS+finetune nearly matched the ADP reduction achieved by pure MCTS. This suggests that fine-tuning contributes to policy improvement from the pre-trained agent, resulting in enhanced performance compared to baseline MCTS+Leaming, In the case of sqrt, MCTS+finetune approached the performance of ABC-RL. Our fine-tuning experiments affirm its ability to correct the model policy, although it require more samples to converge towards ABC-RL performance.
18

---

Published as a conference paper at ICLR 2024
17.5
20.0 0-
20
18
17.5
14
5 15.0
12.5
16
14
10.0
12.5
10
7.5
5.0
10
12
2.5
6
ABC-AL
NCTS
MCTS-finctune
20
40
60
80
100
40
50
80
100
20
40
60
80
100
20
40
60
80
100
lteration
Iterations
Iterations
Iterations
(a) alu4
(b) apex I
(c) apex2
(d) apex4
14
55
Reduction (96)
22
20
12
10
40
45
50
20
35
16
20
40
60
100
20
40
60
80
100
20
40
60
80
100
40
60
80
100
Iterations
Iterations
lterationn
Iterationn
(e) b9
(f) c880
(g) proml
(h) i9
20-
16
72.5
25
Reduction
10
20.0
20
20
15.0
15
12.5
10
7.5
60
20
60
80
100
20
40
60
80
100
80
100
Iterations
Iterations
Iterations
(i) m4
(i) pair
(k) max I 1024
(I) c7552
Figure 10: Arca-delay product reduction (in %) compared to resyn2 MCNC benchmarks. YELLOW:
MCTS+Finetune, BLUE: MCTS Neto 2022). RED: ABC-RL
16
35
50
22.5
30
12
20.0
17.5
25
30
8
15.0
20
20
10.0
MCTS -finctuee
MCTS
10
ABC-RL
20
40
60
80
100
20
60
60
100
Iterations
Iterations
Iterations
Iterations
(a) bar
(b) div
(c) square
(d) squt
Figure 11: Arca-delay product reduction (in %) compared to resyn2 EPFL arithmetic benchmarks. YELLOW: MCTS+Finetune, BLUE: MCTS Neto et (2022). RED: ABC-RL
40
30
35
08
25
28
26
10
20
15
10
20
15
24
22
Minttufnnetuee
MCTS
20
ABC-RL
20
40
60
80
100
20
40
80
100
Iterations
Iterations
Iterations
Iterations
(a) cavle
(b) mem_mmmmmmm ctrl
(c) router
(d) voter
Figure 12: Area-delay product reduction (in %) compared resyn2 EPFL random control benchmarks.
YELLOW: MCTS+FT, BLUE: MCTS NetS et al. (2022). RED: ABC-RI.
19

---

Published as a conference paper at ICLR 2024
D.4 ABC-RL: SIMILARITY SCORE COMPUTATION AND NEAREST NEIGHBOUR RETRIEVAL
Next, we report nearest neighbor retrieval performance of ABC-RL which is a key mechanism in setting a tune pre-trained agent's recommendation during MCTS search. We report similarity score which is the cosine distance between test AIG and nearest neighbour retrieved via similarity. We also report the training circuit which the test AIG is closest we set T = 100 and 9εh 0.007.
Based on our validation dataset,
Benchmark
Designs
Similarity Score
Nearest ncighbour
alu4
0.000
alu2
apex
0.001
apex3
apex2
0.002
alu2
apex4
0.000
prom2
c7552
0.006
max512
i9
0.003
prom2
MCNC
m4
0.001
max512
proml
0.002
prom2
b9
0.005
c2670
c880
0.006
frgl
pair
0.010
m3
max 1024
0.023
alu2
bar
0.002
prom2
div
0.001
log2
EPFL arith
square
0.012
alu2
sqrt
0.002
multiplier
cavlc
0.007
alu2
mem_cti
0.001
prom2
EPFL random control
router
0.025
adder
voter
0.006
m3
Table Similarity score (x10- nearest neighbour retrieved using ABC-RL test designs. Nearest neighbour denotes the training design closest to test-time design
D.5 ABC-RL: ARCHITECTURAL CHOICES FOR RECIPE ENCODER
ABC-RL uses BERT-based recipe encoder to extract two meaningful information: 1) Contextual relationship between current synthesis transformations and previous ones and 2) The synthesis transformations which needs more attention compared others depending its position. For e.g. rewrite operation at the start of a synthesis recipe tend to optimize more number of nodes in AIG compared its position later in the recipe Yu 2020);; Neto al. (0022). Similarly, transformations like balance are intended towards reducing delay of the design wheras transformations like rewrite, refactor, resub are intended towards area optimization. Thus, selective attention and placement of their positions with respect to other synthesis transformations needs to be learned which makes BERT an ideal choice to encode synthesis recipe. As part of additional ablation study, we encode our synthesis recipe with LSTT network with input sequence length (I. 10) and apply zero-padding for recipe length less than L.
Table 7: Area-delay reduction (in 96), ABC-RL- BERT is ABC-RL RL trained with naive synthesis encoder instead of BERT. MCTS FT indicate MCTS+L.caming with online fine-tuning.
ADP reduction (in %)
Recipe
encuder
MCNC
EPFL arith
EPFL random
C1
C2
C3
C4
C5
C6
C8
C9
CI0
CII
C12
A2
A4
RI
R2
R3
Naive
17.0
16.5
14.
13,1
446
16.9
10.0
23.5
16.3
18.8
10.6
19.0
36.9
51.7
9.9
20.0
15.5
23,0
28.0
26.9
21.2
LSTM-based
19.5
17.8
13.3
44.
17.8
10.3
23,5
20.1
19.6
36.9
10.9
22.4
16.8
24.3
32.3
28.7
22.6
BERT-based
19.9 19.6
16.8
15.0
46.9
19.1
12.1
24.3
21.3
21.1
13.
21.6
36.9
56.2
14.0
23.8
19.8
30,2
38.9
30.0
25.3
20

---

Published as a conference paper at ICLR 2024
D.6 RUNTIME ANALYSIS OF ABC-RL VERSUS SOTA
We now present wall-time comparison of ABC-RL versus SOTA methods on test designs for 100 iterations. We note that for all online search schemes, the runtime is dominated by that the number of online synthesis runs (typically 9.5 seconds per run) as opposed to inference cost of the deep network (e.g. 11 milli-seconds for ABC-RL) Thus, as observed in the table below, ABC-RL runtime is within 1.5% of MCTS and SA+Pred. Table g presents wall-time comparison of ABC-RL versus existing SOTA methods for 100 iterations. Overall, ABC-RL run time overhead over MCTS and SA+Pred. (over 100 iterations) has geometric mean of 1.51% % and 2.09%, respectively. In terms of wall-time, ABC-RL achieves 3.75x geo. mean iso-QoR speed-up.
Runtime (in seconds)
ABC-RL overhead (in %)
Iso-QoR speed-up MCTS wall-time
Designs
MCTS
SA+Pred.
ABC-RL
w.r.t. MCTS w.r.t. SA+Pred.
alu4
35.6
35.3
36.0
1.12
1.98
1.89x
apex
105.6
105.1
107.0
1.33
1.81
5.82x
apex2
20.2
20.1
20.5
1.49
1.99
1.80x
apex4
195.6
193.7
199.6
2.04
3.05
1.58x
c7552
91.4
91.2
93.2
1.97
2.19
1.16x
i9
40.2
40.3
41.2
2.49
2.23
1,30x
m4
37.1
37.3
37.9
1.89
1.41
3.11x
proml
201.6
200.3
205.7
2.03
2.70
4.04x
b9
16.9
16.8
17.3
2.37
2.98
2.11x
c880
16.8
16.6
17.5
2.38
2.99
1.20x
pair
110.3
110.0
112.0
1.54
1.73
0.90x
max 1024
82.6
82.0
84.9
2.78
3.50
1.77x
bar
192.4
191.2
196.5
2.13
2.77
3.59x
div
655,4
652.1
668.9
2.06
2.58
8,82x
square
398.6
395.0
403.1
1.12
2.05
4.17x
sqrt
448.5
444.2
455.5
1.56
2.54
8.21x
cavle
56.4
56.1
57.2
1.42
1.96
4.95x
mem_etrl
953.7
950.3
966.5
1.34
1.70
6.33x
router
44.2
43.9
44.8
1.36
2.05
3.08x
voter
312.5
311.0
317.9
1.73
2.22
5.57x
Geomean
1.51
2.09
3.75x
Table 8: Wall-time overhead of ABC-RL over SOTA methods 100 iterations (Budget: 100 synthesis runs).
We report iso no-Q wall-time speed-up with respect to baseline MCTS Neto et al. 2022).
D.7 ABC-RL PERFORMANCE ON TRAINING AND VALIDATION DESIGNS
Next, we present ABC-RL performance on training and validation circuits and compare with baseline MCTS. For training circuits, ABC-RL sets 0 indicating the search with augmented with full recommendation from pre-trained agent. For validation circuits, ABC-RL sets a and performs search with tuned recommendation from tre-trained agent.
21

---

Published as a conference paper at ICLR 2024
ADP reduction (in %)
Designs
MCTS
ABC-RL
alu2
21.2
22.3
apex3
12.9
12.9
apex5
32.50
32.5
apex6
10.00
10.7
apex7
0.80
1.7
20.75
22.1
c1355
34.80
35.4
c1908
14.05
15,9
c2670
7.50
10.7
c3540
20.30
22.8
c432
31.00
31.8
c499
12.80
12.8
c6288
0.28
0.6
frg
25.80
25.8
frg2
46.20
47.1
i10
28.25
31.2
17
37.50
37.7
i8
40.00
47.3
m3
20.10
25.0
max128
24.10
31.8
max512
14.00
16.8
prom2
18.10
19.8
seq
17.10
20.9
table3
15.95
16.1
table5
23.40
25.5
Geomean 15.39
17.84
Table 9: Arca-delay reduction compared resyn2 on MCNC training and validation circuits. We compare results of MCTS and ABC-RL approach.
ADP reduction %)
ADP reduction (in %)
Designs
Designs
MCTS
ABC-RL
MCTS
ABC-RL
adder
18.63
18.63
arbiter
0.03
0.03
log2
9.09
11.51
ctrl
27.58
30.85
37.50
45.86
i2c
13.45
15.65
multiplier
9.90
12.68
int2float
8.10
8.1
sin
14.50
15.96
priority
77.53
77.5
Geomean
15.55
18.18
Geomean 5.87
6.19
Table 10: Area-delay reduction resyn2 EPFL arithmetic (left) and random control (right) training and validation benchmarks using MCTS and ABC-RL
22


Reviews:
[{"review_id": "LS2H9Lwt1Q", "reviewer": "Reviewer_Pwwd", "summary": "This work introduces, ABC-RL, an MCTS+Learning algorithm to optimize the transformation recipes in logic synthesis to minimize the area delay product (ADP).  It employs GCN for AIG features and a transformer for applied transformations. It introduces a hyperparameter to adjust recommendations from pre-trained agents during the search. The hyperparameter is determined by similarity computed from GNN features learned during training. The key observation it leverages from hardware designs is that they contain both familiar and entirely new components. The empirical results show ABC-RL improves synthesized circuit Quality-of-Result (QoR) by up to 24.8% over SOTA methods and provides an average runtime speed-up of 1.6× compared to baseline MCTS.", "questions": "1. How is it compared to non-learning-based recipes? Is there an O3 flag for logic synthesis? \n2. How does its wall clock time (not iterations) compare to other algorithms such as MCTS and SA+Pred?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The policy network architecture for recipe encoding and AIG embedding is reasonably selected.\n2. The novel introduction of a similarity-score-based hyperparameter effectively enhances ABC-RL convergence, as observed in the results.\n3. The study provides a comprehensive evaluation, comparing various search algorithms for logic synthesis recipe optimization, including MCTS, online RL, and simulated annealing. It also includes comparisons with MCTS+Learning with fine-tuning.", "weaknesses": "1. It would be beneficial to provide an estimate of the number of gates in each benchmark circuit. One concern with this approach is whether GCN-based AIG embeddings can effectively scale to real-world circuit designs.\n2. With the integration of GNN + transformer features. It is likely that the compute complexity and runtime of each search iteration would be higher than the baseline MCTS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CtAotUn5rd", "reviewer": "Reviewer_3ENJ", "summary": "This paper presents ABC-RL, a retrieval-guided RL approach to generate an optimized synthesis recipe for logic synthesis. ABC-RL tunes a weight that adeptly adjusts recommendations from pre-trained agents during testing. Given a circuit with high similarity to the circuits in the training dataset, ABC-RL assigns high weight to the policy by the RL agent. Otherwise, ABC-RL tends to rely more on the default searching strategy.", "questions": "Please refer to the weakness part.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThis paper introduces a retrieval-guided RL agent to search for an optimized synthesis recipe for logic synthesis. ABC-RL selectively leverages the knowledge obtained during training based on the similarity between training and testing samples. This approach can address the issue of RL performance decrease caused by different data distributions. \n\n2.\tThe authors claim that ABC-RL can achieve up to 24.8% QoR improvement and reduce runtime up to 9x.", "weaknesses": "1.\tABC-RL calculates the cosine similarity between the embeddings of training and testing samples to determine the similarity score. Therefore, the quality of AIG embeddings is the key to the entire methodology. Unfortunately, the authors do not explore this issue and simply use a 3-layer GCN to do it. It's hard to believe such an approach could work properly. A circuit graph is a lot more complicated than a plain graph, not only it's directed, but more importantly, it has unique functions associated with it. Two AIGs could be very similar in terms of structure but differ significantly in terms of functionalities. Consequently, they may require different synthesis recipes, isn't it?\n\n2.\tThe experiments are conducted with a very small dataset, which only includes 23 netlists for training. This is not convincing. The proposed agent should have seen sufficient circuit designs to come up with a good RL strategy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QBna1vIOAd", "reviewer": "Reviewer_qBwB", "summary": "Summary:\n This papers proposes ABC-RL method to smoothly change the impact of learned policy in the search objective based on the graph similarity. Similar designs to training examples will have more bias from learned policy, while novel circuit will use more search. Compared to prior method, the propose one outperforms in various designs in terms of area-delay product.", "questions": "Basically, it is listed in the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Strength: \n\n1.\tThe proposed method is based on good observation that the benchmark has a large diversity, and the learned policy sometimes is not helpful for novel circuits.\n\n2.\tThe proposed method smoothly controls the importance of learned policy using GNN-based graph embedding similarity scores. The variable heuristic synthesis solution from the learned policy is encoded with transformer blocks for better performance.\n\n3.\tIt also runs fast with runtime benefits.", "weaknesses": "Weakness:\n\n1.\tThe overall framework basically does test-time augmentation. It assumes pre-trained policy is not generalizable to novel circuits, and by comparing the test example with the training example, it dynamically selects among two search strategies, but in a smooth way. The circuit similarity is a performance proxy for pretrained agent and MCTS method, and use that proxy to predict the weights to ensemble two models. The novelty, in this sense, is limited. Is it possible to combine more synthesis strategies based on a more general performance predictor at test time?\n\n2.\tThe usage of BERT is not well justified. There are other simpler methods to encode variable-length sequences, e.g., RNN. The attention model is also data-hungry during training. Why BERT is the most suitable encoder?\n\n3.\tThe assumption that learned policy cannot generalize to diverse benchmarks is not well supported. If there is generalizable knowledge in circuit representation and synthesis strategies, it should try to improve the generalization of the learned policy by using more data/better algorithms. If this problem in nature is not generalizable or learnable, then it is not necessary to use an RL agent to learn the synthesis strategy at the beginning. The proposed method does not fundamentally explain or solve the learnability of circuit synthesis problems, but rather uses two model ensembles to just cover some in-distribution data with learned model and out-of-distribution examples by search.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U6r8NQ4aGi", "reviewer": "Reviewer_yxFf", "summary": "This paper proposes a new logical synthesis optimization sequence method ABC-RL based on MCTS and pertained policy. Unlike previous works, ABC-RL can compute the similarity of the new circuit with previous circuits, thus determining how much experience will be used. Experiments show that ABC-RL achieves SOTA optimization results in most circuits.", "questions": "1. Could you compare ABC-RL and DRiLLS methods?\n\n2. As weakness 2, could you give each circuit’s nest neighbor circuit and similarity factor?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The idea that the degree of retrieval is determined by the similarity function is interesting, and it shows the advanced performance in experiments.\n\n2. The experiments are extensive.\n\n3. The paper is well-organized and easy to read.", "weaknesses": "1. Some other ML method baselines are not included. For example, the DRiLLS [1] results are not included in the paper, but it is an important method recently.\n\n2. The retrieval performance is not well reported. For example, it should give us examples of each circuit’s nearest neighbor circuit and similarity factor. \n\n3. ChiPFormer [2]  is an RL placement method with a pretrained policy and should be included in related work.\n\n[1] Hosny, Abdelrahman, et al. \"DRiLLS: Deep reinforcement learning for logic synthesis.\" 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). IEEE, 2020.\n\n[2] Lai, Yao, et al. \"ChiPFormer: Transferable Chip Placement via Offline Decision Transformer.\" (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EJuPfl3vaD", "reviewer": "Reviewer_pgL7", "summary": "The authors proposed a new method for finding optimal synthesis recipes for unseen netlists. They proposed three methods, one based on MCTS and a trained policy on training netlist (MCTS+L) and the other, and more superior, is using MCTS and a trained policy with a variable to control the reliance on the trained policy or the online MCTS search (ABC-RL). The variable \\alpha is determined based on a nearest neighbor search to determine if the netlist is close to the training netlists or not. The authors split the dataset of netlists into train, validation, and test sets and used the train to train the policy and used the validation set to set the hyperparameter that controls \\alpha. The experimental results show that the ABC-RL can outperform the other methods and SOTA in most of the test netlists and can achieve the best goe-mean performance.", "questions": "- It would be great if the authors can also provide the results for the rest of the benchmark netlists to ensure that the similar performance gains hold up for the training and validation sets.\n- In Section 2.4, in definition of \\sigma_{\\delta_{th}, T}(z), replace \\teta with \\delta_{th}.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Extensive experimental results.\n  - The authors provided comparisons with multiple baseline including Online-RL, Simulated Annealing, MCTS, and MCTS+L and MCTS+L+FT.\n  - The study on training the policy on specific benchmarks was helpful showing the effect of \\alpha and closeness of netlist to the training dataset.\n  - They perform an ablation study on the architecture of the policy to determine the impact of the transformer architecture on the performance.\n- The authors motivated the need for a variable that can control the effect of policy vs MCTS very well by an example in the Introduction Section.\n- The paper is well written and organized and can be followed easily by non-experts. \n- The related literature has been sufficiently reviewed and cited.", "weaknesses": "- The idea of using \\alpha was interesting and novel to the best of my knowledge, however it is a simple and small contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)