Scalable and Effective Arithmetic Tree Generation for Adder and Multiplier Designs

Summary

This paper presents a new method for designing arithmetic modules by modeling tasks as single-player tree generation games, using reinforcement learning techniques. This approach combines prefix and compressor tree modules to find optimal multipliers. Experiments show that the developed 128-bit adders and multipliers outperform the latest designs, significantly reducing delay and size. The method enhances computational efficiency and hardware size within hours and integrates seamlessly into advanced technology, offering valuable insights for future hardware design.

Strengths

The strengths of the paper are listed below: The paper introduces an innovative method for designing arithmetic modules that outperforms traditional human design techniques. The paper is well-presented, offering a clear explanation of its methodology. It improves results against other method PrefixRL

Weaknesses

The weaknesses of the paper are listed below: the paper innovation limited to application of RL and Tree Search to a circuit design problem, which are studied in other previous work such as: Mirhoseini, Azalia, et al. "A graph placement methodology for fast chip design." Nature 594.7862 (2021): 207-212.

Questions

A few question and notes are listed below: It seems the main additions of this work are two-level Retrieval and MCTS compared to PrefixRL. Are there other inovation that distingush this work vs PrefixRL? How one would extend to other arithmetic operations, such as exponentiation? Seems a weakness to the method is that one needs to design the "game" for addition operators. Maybe There are work that design envs that author could try: Ma, Yecheng Jason, et al. "Eureka: Human-level reward design via coding large language models." arXiv preprint arXiv:2310.12931 (2023).

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors adequately addressed the limitations and, if applicable, potential negative societal impact of their work

Summary

The paper introduces a novel approach to optimizing arithmetic module designs, particularly adders and multipliers. By modeling design tasks as single-player tree generation games and employing RL techniques (MCTS and PPO), the authors effectively explore the design space to uncover superior structures. Their method significantly enhances computational efficiency and reduces hardware size, outperforming existing techniques in both aspects. This work demonstrates the effective application of RL in hardware design, presenting an innovative tree-generation strategy for improved design optimization.

Strengths

**Originality:** 1. Few competing works address adder-multiplier co-design automation using RL or machine learning techniques. This paper stands out as an interesting and pioneering effort in optimizing such designs with RL. 1. The introduction of tree-generation games and the application of RL techniques to optimize arithmetic module designs are novel and innovative. **Quality:** 1. Based on the experimental results, this paper has discovered several optimal 128-bit adder architectures, a noteworthy achievement given the vast search space explored. 1. The experiments are thorough, validated across different technology nodes and using both open-source and commercial tools, confirming the method's effectiveness. **Clarity:** 1. The paper is well-organized, featuring a clear introduction, detailed methodology, and systematic presentation of results. This structure facilitates understanding the complex concepts introduced. 1. The introduction video is a nice touch and helps in understanding the proposed method. **Significance:** 1. The authors have made the research open-source and documented most of the experimental details comprehensively, which significantly enhances the reproducibility of the results. 1. The improvements of the proposed method over existing techniques in terms of delay and area are significant and demonstrate the potential of the proposed approach in optimizing hardware design.

Weaknesses

1. This study primarily focuses on optimizing adders and multipliers, with limited exploration of other modules within the hardware system. 1. While the proposed methods demonstrate notable improvements for 128-bit adders and 64-bit multipliers, their scalability to even larger bit widths needs further investigation. Minors: 1. I suggest the authors consistently use either the abbreviation 'RL' or the full term 'reinforcement learning' throughout the paper. 1. In Equation 3, $\sum_{i=0}^{n}$ should be $\sum_{i=1}^{N}$. 1. Lines 226-227: '... from step 0 to step T' should be '... from step 1 to step T'.

Questions

1. Could you provide detailed information on the design flow? Moreover, how are the floorplan and placement parameters set in OpenROAD? 1. Could you elaborate on how your method might be extended or adapted to optimize other hardware units?

Rating

8

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

N/A

Summary

This paper discusses the application of reinforcement learning to optimize the design of arithmetic circuits, specifically adders, and multipliers. Two single-player tree generation games, AddGame and MultGame, are designed to formulate adder and multiplier design problems. AddGame re-designs the search method, following a similar state space and action space as PrefixRL. MultGame optimizes the compressor tree from scratch instead of starting from existing solutions. Results show they outperform PrefixRL and RL-MUL.

Strengths

1. The paper re-designs the search techniques for adders and multipliers. Experimental results demonstrate the effectiveness of the proposed methods. The findings are significant for hardware design. 2. Main concerns are addressed which include the performance of designed adders and multipliers and the time cost of the searching process. 3. The writing is clear and well-structured.

Weaknesses

1. The paper would benefit from a more detailed introduction of the states and actions for both AddGame and MultGame in the main part. It was confusing to understand how a compressor tree is represented until I referred to Appendix A.4. 2. Some details are missing. For example, it is unclear whether the results shown in Figure 6 are synthesized using Nangate45 technology.

Questions

1. The paper states, “The compressor tree is built from scratch instead of starting from existing solutions for more design flexibility.” Does building from scratch indeed offer more design flexibility while maintaining performance? 2. Is the objective of Table 7 to minimize delay? Can you present a result with a trade-off objective? 3. Please provide the definition of accuracy mentioned in Appendix B.6.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations and societal impacts are discussed in the paper.

Summary

This paper aims to leverage reinforcement learning (RL) techniques for automatic arithmetic circuit design. The authors propose to cast the design tasks as single-player tree generation games, and leverage reinforcement learning techniques to optimize these arithmetic tree structures. For adder circuits, the proposed approach discovers designs of 128-bit adders that achieve Pareto optimality in theoretical metrics. Moreover, the proposed approach significantly outperforms previous state-of-the-art RL-based approaches for adders and multipliers design.

Strengths

1. The paper is well-written and logically sound. 2. The paper explores the application of RL methods to arithmetic circuit design, presenting a unique intersection of interest for RL community and AI chip development. 3. The authors introduce a novel approach by modeling arithmetic module design tasks as single-player tree generation games, namely AddGame and MultGame, leveraging the well-established RL capabilities for complex decision-making tasks. 4. The method exhibits high flexibility and scalability, making it applicable to both 7nm technology and higher-bit units. These characteristics are crucial for practical hardware design and industrial applications. 5. Experiments show that the proposed approach discovers designs of 128-bit adders that achieve Pareto optimality in theoretical metrics, which is an impressive result.

Weaknesses

The paper employs 45nm and 7nm PDKs. They are open-source and academically oriented, but not commercial-grade industry PDKs. This choice might introduce variations in the designs when transitioning from theoretical models to real-world industrial applications. Thus, the authors are encouraged to test their approach on real industry PDKs to validate the practicality in future work. A minor grammatical correction is needed on line 114, where “it derived” should be revised to “it is derived.”

Questions

1. Why the authors do not test on real industry PDKs? 2. Does the proposed method have any limitations when applied to real industry PDKs? 3. In Fig. 6, why do various RL approaches produce a range of designs, whereas traditional designs like BK and Sklansky adders result in only a single design?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N.A.

Summary

This paper presents a reinforcement-learning-based approach to optimizing arithmetic units, specifically adders and multipliers, to enhance computational efficiency and reduce area consumption. The key idea is to frame the design as tree generation games. The evaluation shows that the proposed method can generate 128-bit adders with up to 26% reduced delay and 30% smaller size, and multipliers achieving up to 49% faster speeds and 45% size reductions compared to existing techniques.

Strengths

- The paper is in good writing style. Figures are well plotted. - The use of reinforcement learning and tree generation games for Adder and Multiplier generation is novel and interesting. - The evaluation setup is clear and the comparison between different methods is comprehensive. The trade-off between the area and delay of the resulted ALU designs is well demonstrated. - The reported enhancements in speed and size for adders and multipliers with large bit width are substantial.

Weaknesses

- The improvement of PPO-based method becomes smaller as the bit width becomes lower. The paper claims that multipliers and adders are more important for large models in AI applications. However, the modern large models are typically running with 16 bits or even lower bit width. The applicability of the proposed method in modern applications remain questionable. - The evaluation is mostly performed on integer data types. It is unclear how proposed method works on the adders and multipliers of floating-point data type. - While the results are promising, the specific modeling seems to only work for adders and multipliers. The generalization of the proposed approach on other basic arithmetic units are unclear.

Questions

Please refer to the weakness.

Rating

5

Confidence

2

Soundness

2

Presentation

3

Contribution

2

Limitations

Authors have adequately addressed the limitations.

Summary

A reinforcement learning-based method is proposed to design adders and multipliers within a framework of single-player tree generation games, named AddGame and MultGame. The method leads to the discovery of superior designs for 128-bit adders and multipliers, achieving significant improvements in delay and size compared to previous methods.

Strengths

1. The results look quite promising, especially on large designs.

Weaknesses

1. The novelty is limited, as the RL environment (state, action, reward) is pretty much similar to previous work [17], and MCTS is also not something new in a game-playing problem. 2. Some additional data points in the results might not look reasonable. See questions below.

Questions

1. What's the specific representation of adder and multiplier in the proposed method? Is it similar to previous works (e.g., a matrix in [17])? 2. Did the obtained design go through an equivalence-checking process to ensure the functionality correctness? If so, the details should be provided. 3. Figure 6 presents that the proposed method achieves promising results. However, it is observed that the Sklansky adder achieves even better delay than the Kogge-stone, which looks questionable and degrades the convincingness of the experiment flow.

Rating

5

Confidence

5

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes.

rebuttal acknowledgment

thank you for clarifications and addressing the questions

rebuttal acknowledgment

Thanks for the clarification. Most of the concerns are addressed. A few more comments: 1. If the logic equivalence checking is performed, please add the description in future versions. 2. Regarding the clarification on Kogge-stone vs. Sklansky, if it is due to interconnection, the authors may inspect the final layout and/or tool settings to verify. The score is raised accordingly.

Thank you for the update

We are very grateful for your positive comments once again. We also truly appreciate the time and effort you have put into reviewing our work.