Retrieval-Guided Reinforcement Learning for Boolean Circuit Minimization

We thank the reviewer for their detailed and insightful feedback. We address the questions raised:

Q1) 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.

Response:

Thank you for your recommendation. To provide a comprehensive overview, we applied ABC-RL to both training and validation netlists, and the performance improvements are detailed in Appendix D7 (Table 9 and 10). On MCNC circuits, ABC-RL achieved a geometric mean ADP reduction of 17.84%, surpassing MCTS, which resulted in a 15.39% reduction. For EPFL arithmetic circuits, ABC-RL demonstrated an 18.18% geometric mean reduction compared to MCTS, which yielded a 15.55% ADP reduction. Finally, on EPFL random control circuits, the geometric mean ADP reduction was 6.19% and 5.87% for ABC-RL and MCTS, respectively.

Q2) In Section 2.4, in the definition of $\sigma_{\delta_{th}, T}(z)$, replace $\theta$ with $\delta_{th}$.

Response:

Thanks for pointing out this oversight. We have replaced $\theta$ with $\delta_{th}$ in our updated manuscript.

We thank the reviewer for their insightful feedback and address the concerns raised:

Q1) 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.

Response:

Thank you for the excellent suggestion. In the updated draft, we have cited and evaluated against DRiLLS as well, and reported results in Table 2. DRiLLS is competitive with Online-RL (both have a 16.1% ADP reduction), but has less ADP reduction compared to our proposed ABC-RL (25.3%).

Q2) The retrieval performance is not well reported. For example, it should give us examples of each circuit’s nearest neighbor circuit and similarity factor.

Response:

Thank you for the suggestion. This is actually informative data and we have included it in Appendix D.4 (Table 6). Several interesting observations can be drawn: first, note that the closest circuits in the training set are often semantically similar (alu2 for alu4, apex3 for apex1, sqrt for multiplier), suggesting that the learned embeddings are capturing netlist structure/function. Second, netlists for which we found MCTS+L to underperform MCTS alone, for example, square and cavlc have relatively high cosine distances of 0.012 and 0.007, respectively, relative to the $\delta_{th}=0.007$ in Equation 4.

Q3) ChiPFormer [2] is an RL placement method with a pretrained policy and should be included in related work.

Response:

Thank you for pointing out this recent work regarding pre-training offline agents for chip placement problems. We have included the citation in our related work section.

[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.

[2] Lai, Yao, et al. "ChiPFormer: Transferable Chip Placement via Offline Decision Transformer." (2023).

Q3) The 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.

Response:

We thank the reviewer for raising this point. We would like to emphasize that ABC-RL never defaults to a pure search solution, but instead chooses the right mix of learning and search on a per-benchmark basis. Emprically, across our test circuits, ABC-RL never sets $\alpha=1$, i.e., never fully turns off the learned agent, thus ensuring that the learned policy is constantly helping, albeit by different amounts. This is evidenced by the fact that ABC-RL outperforms pure MCTS search on all circuits except on one (for which both results are the same). Therefore, in each of these instances, the learned agent is actually generalizing to test inputs and helping to boost performance over the pure search agent, but by different amounts. In sum, our claim is not that learning does not help (in fact, on average even MCTS+L is better than MCTS), but that the amount of learning should be judiciously selected using our proposed scheme.

Finally, one can imagine a test circuit that is so novel that ABC+RL sets $\alpha=1$ in which case we would default to search. However, in our view, such an “out-of-distribution” (OOD) circuit by itself would not mean that learning is not useful, given that OOD inputs are routinely encountered across a range of ML applications. Nevertheless, we note that ABC-RL itself does not label test circuits explicitly as either in-distribution or OOD.

We thank the reviewer for appreciating our motivational observation that in practice benchmarks have large diversity and learned policy sometimes do not help for entirely novel circuits. The method also smoothly controls the recommendation from pre-trained agents while performing MCTS for synthesis recipe generation yielding runtime benefits. We address the reviewers' concerns below.

Q1) The 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 pre-trained agent and MCTS method, and uses 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?

Response:

We thank the reviewer for the question. With regards to novelty, as far as we are aware, adaptively mixing learning and search using an based on retrieval-guided cosine similarity is a new idea in literature that empirically outperforms several state-of-art methods, while a simpler solution without the judicious choice of how much learning to use (MCTS+L) does not. As such, our contributions include the algorithm to weight the pre-trained and pure search agents, how to set its hyper-parameters, and other policy network architecture contributions that are not in prior work and are key to the performance of our method.

The reviewer makes an interesting point about ensembling other synthesis strategies. We agree that it might be possible to train a test time predictor that selects within this broader class of strategies, for example, SA+Pred etc. This would be an interesting avenue for future work. We do want to highlight one key point here: our pre-trained and MCTS search agents are not ensembles in the traditional sense: in fact, the pre-trained agent is trained to emulate MCTS search (as in alphaGO etc.), thus providing it a performance boost. As such, one could imagine pre-trained agents used to emulate other online search methods like simulated annealing, thus giving these methods a boost as well. Finally, these learning-augmented-search methods could be ensembled in the more traditional sense.

Q2) The 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?

Response:

Thank you for the suggestion; a comparison with an RNN (or LSTM) encoder is a good idea. To test this idea, we replaced our BERT-based encoder with an LSTM encoder and retrained our model. Our detailed results in Appendix D.5. We find that our BERT-based encoder outperforms the LSTM-based encoder. Specifically, ABC-RL using an LSTM recipe encoder achieves 22.6% geo-mean ADP reduction compared to 25.3% using the existing BERT-based recipe encoder. The table is reproduced below for your convenience.

We thank the reviewer for appreciating ABC-tuning strategy to adjust recommendations from pre-trained agents during test time and address the issue of learned policies sometimes underperforming pure search. We address the reviewer’s primary concerns below.

Q1) Quality of AIG embeddings: The reviewer is concerned about usage of 3-layer GCN network to encode AIG graphs which are directed and represent functionality. Thus, two AIG’s with the same structure can differ in functionality and hence require different synthesis recipes. However, our 3-layer GCN may fail to distinguish between such similar AIG structure but different functionality.

Response:

Thank you for the question. We note that unlike CNNs, GNN/GCN architectures tend to be shallower because deeper networks suffer from a well-studied “over-smoothing” [1,2] effect; i.e., as GCN depth increases each node’s features depend on all other nodes, resulting in an ``averaging” effect that causes all nodes to have similar embeddings. Therefore, GNNs often achieve optimal classification performance when networks are shallow, and many widely used GNNs/GCNs architectures are no deeper than 4 layers [2,3,4]. Prior work on ML for logic synthesis, for instance, the Online-RL approach (Zhu et al. 2020), and SA+Pred. (Chowdhury et al., 2022) methods we compare against also use GCNs with up to 4 layers. Mirhoseini et al, (2021) use only a 2-layer GCN in their RL agent for chip placement. As such, we would like to emphasize that our GCN architecture depth is consistent with common practice in the graph learning literature.

[1] Li, Qimai et al. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

[2] Wu, Xinyi, et al. "A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks." in International Conference on Learning Representations (ICLR) 2022.

[3] Errica, F., ert al. A Fair Comparison of Graph Neural Networks for Graph Classification. in International Conference on Learning Representations (ICLR) 2020.

[4] Wu, Zonghan et al. A comprehensive survey on graph neural networks. in IEEE transactions on neural networks and learning systems 32.1 (2020): 4-24.

Q2) The 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.

Response:

We note that although we use 23 netlists for training, the actual number of data samples that our agent is trained on is much larger, i.e., about 11,500 different states that are generated during the episodes of training. In each episode, 230 new graphs are generated using most promising synthesis recipes using MCTS, and since we train for 50 episodes, that yields our final tally of 11,500.

Recent work in RL for hardware optimization have similar number of training examples: 20 netlists in [4] and 12 in [5]. In part, the limitation stems from the size of publicly available datasets. In our paper, we have tried to address this issue by combining both commonly used public datasets for logic synthesis, MCNC (1991) and EPFL benchmarks (2015), yielding our eventual tally of 23 training netlists.

[4] Mirhoseini, Azalia, et al. "A graph placement methodology for fast chip design." Nature 2021

[5] Lai, Yao, et al. "Chipformer: Transferable chip placement via offline decision transformer." International Conference on Machine Learning 2023

We acknowledge the reviewer's diligence in pointing out that our rebuttal response may not have comprehensively addressed his inquiries. We address the concerns below:

Q1) Regarding the AIG embedding, the problem is not about the number of layers in the GCN. Circuits are directed graphs with built-in functionalities. Using a simple GCN for AIG embedding, both the structural information and the functional information suffer from great loss. Consequently, it is likely that two vastly different circuits generate similar GCN embedding with this work and hence use similar synthesis recipes, but they shouldn't.

Response:

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 an experiment that validates its efficacy:

• Working principle of logic synthesis transformations: Logic synthesis transformations of ABC (and in general commercial logic synthesis tools) including rewrite, refactor and re-substitute performs transformations at a 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 a fan-in cone of an intermediate node of AIG and replaces it with a 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 3 in 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 two important feature: i) Type of node (Primary Input, Primary Output and Internal Node) and ii) Number of 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.

To illustrate this point further, we conduct a concise experiment involving a test circuit, 'div.' In this experiment, we generate additional AIGs by randomly flipping the edges of the AIG structure, thereby creating structural variants with distinct functionalities. For example, when we mention '10%,' it signifies that 10% of the edge types in the AIG were flipped. We employ the equivalence check feature of the ABC tool to ascertain whether these newly generated AIGs are structurally identical but functionally divergent. Additionally, we present the similarity score (cosine distance) of these AIGs with respect to the original circuit and the achieved Area-Delay Product (ADP) reduction obtained through Monte Carlo Tree Search (MCTS) and ABC-RL.

Our results highlight that the feature extracted by our 3-layer GCN architecture is able to capture functional differences having same skeleton AIG structure resulting in different similarity scores and ABC-RL performs better than MCTS.

Q2) Indeed, we don't have lots of publicly available datasets that are readily applicable to this work. On the one hand, the authors should discuss its implications, i.e., what kind of circuits may benefit from this solution. On the other hand, the authors can extract more circuits from OpenCore or GitHub projects to make the work more convincing. I understand this would involve lots of work, but the authors should at least test a few circuits that are outside of the benchmark dataset to demonstrate the generalization capability of the proposed solution.

Response:

We appreciate the reviewer's understanding that extracting the circuits from Opencore or Github projects and training our framework require considerable more time to demonstrate further effectiveness (Our training time on 23 circuits with parallelized implementation takes around 9 days). However, to the best possible extent we provide results on 9 circuits extracted out of Opencore with our ABC-RL model trained on 23 circuits. We report area-delay reduction (in %) obtained by ABC-RL and compare it with MCTS:

We also want to highlight the fact that: in hardware domain the distribution study of circuits in terms of functionality and structure is still an open problem to explore. For the kind of circuits that can benefit well from ABC-RL (i.e. circuits on which ABC-RL function well and generalize), we observe our cosine distance capture this notion well during test time.

Also asked by reviewer yxFf, we presented this data in Appendix D.4 (Table 6). Several interesting observations we have drawn from it: first, note that the closest circuits in the training set are often semantically similar (alu2 for alu4, apex3 for apex1, sqrt for multiplier), suggesting that the learned embeddings are capturing netlist structure/function. Second, netlists for which we found MCTS+L to underperform MCTS alone, for example, square and cavlc have relatively high cosine distances of 0.012 and 0.007, respectively, relative to the $\delta_{th}=0.007$ in Equation 4.

We thank the reviewer for their insightful feedback and address the concerns raised:

Q1) 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.

Response:

Thank you for the suggestion. We provide detailed characterization in Appendix C.2 listing all the circuits from MCNC and EPFL benchmarks about primary inputs and outputs, number of nodes and level of AIG graphs. The benchmarks circuits range from 400-46,000 nodes. In terms of applicability to real-world designs, we note that logic synthesis is often performed hierarchically because Verilog code itself is written in a modular fashion and because of the large runtimes of flattened synthesis. As such, our results (and indeed those in the logic synthesis literature that all make use of IWLS/EPFL) can be viewed as synthesis runs on leaf and intermediate nodes of a hierarchical flow.

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. How does its wall clock time (not iterations) compare to other algorithms such as MCTS and SA+Pred?

Response:

This is an excellent point. We note that over iterations of MCTS, SA+Pred or ABC-RL search it is the actual synthesis of logic circuits using sample recipes that dominates the runtime, leaving GNN inference as a relatively negligible component to wall-clock time. Therefore, the overhead of ABC-RL over MCTS in terms of wall-clock time is only 1.5% (geo. mean) as shown in Appendix D.6 (Table 8). Our wall-clock speed-up over MCTS at iso-QoR is 3.75x.

Q3) How is it compared to non-learning-based recipes? Is there an O3 flag for logic synthesis?

Response:

The publicly known non-learned recipe for the ABC synthesis tool is resyn2 which is heuristically tailored to optimize for area-delay-product (ADP), our QoR metric. As such it can be viewed as akin to an -O3 flag for C/C++. For this reason, all our reported results in ADP improvements are on top of (i.e., relative to) the resyn2 recipe. Over time, experienced EDA engineers might develop their own intuitions as to which recipes work best for different circuits, but we are not aware of any formal documentation to this effect.