Scalable and Effective Arithmetic Tree Generation for Adder and Multiplier Designs

Thank you so much for your positive comments.

Weakness 1 [Innovation]

• Circuit design is a broad field encompassing various tasks. Our work focuses on arithmetic unit design (adders and multipliers), which differs significantly from graph placement in search space and evaluation metrics. Graph placement involves optimizing the positions of circuit modules with graph structures, while arithmetic unit design deals with the structures of prefix and compressor trees, resulting in vastly different combinatorial space and optimization criteria.

• Moreover, our approach includes several innovations:

  • When designing adders, we use the MCTS framework to balance exploring new design possibilities and refining existing ones, ensuring a comprehensive and efficient search across the design space.
  • For the compressor tree search in MultGame, the search performance is enhanced by redefining actions and states, and building the design from scratch, providing greater search flexibility.
  • The optimization process is also optimized by two-level retrieval and pruning strategies, enabling the efficient scaling of the design's bit-width (128-bit adder and 64-bit multiplier).
  • Our co-design framework allows simultaneous optimization of prefix and compressor trees, further enhancing the performance of designed multipliers.

Question 1 [Difference with PrefixRL]

Both our approach and PrefixRL [17] apply an RL framework to circuit design. However, our method incorporates several critical enhancements that we would like to clarify:

• Advancement in the RL (state, action, and reward) formulation:
  • State: In PrefixRL, prefix trees are represented using a binary matrix, which is solely applicable to the prefix tree structure. In contrast, our model does not directly represent the prefix tree structure. Instead, each node, representing a prefix tree, is evaluated by $W(s)$, a scoring function designed to effectively balance exploration and exploitation.
  • Action: PrefixRL’s actions include adding and deleting cells. However, adding cells does not improve the theoretical metrics (level/size) of the adder it represents. Therefore, we have strategically omitted actions that add cells when optimizing these metrics. This refinement significantly boosts search efficiency, especially in the case of a 128-bit adder, by focusing on actions that directly contribute to performance improvement.
  • Reward: The reward in PrefixRL is calculated based on the performance improvement at each step. Our method, however, utilizes the performance value of the final node reached during the simulation phase of MCTS. This shift reduces the computational overhead from multiple time-consuming simulations and provides a more direct assessment of performance outcomes.
• Advancement in Task Setting and Method Design:
  • Task Setting: PrefixRL only addresses adder design, whereas we work on adder and multiplier designs.
  • Method Design: We have introduced a novel framework for the co-optimization of the multiplier’s compress tree and prefix tree. This integrated approach significantly enhances the overall effectiveness of multiplier design.

Question 2 [Extend to Exponentiation Operation]

Exponentiation operations, whether employing the naive method or the method of exponentiation by squaring, involve numerous multiplication operations. Thus, our existing multiplier design approach is inherently well-suited to optimize these procedures. By harnessing the repeated multiplication principle intrinsic to both naive and binary exponentiation techniques, we can extend our RL framework, initially developed for multipliers, to enhance the design and efficiency of exponentiation units. This extension also allows us to further improve our model to accommodate the iterative nature of exponentiation, ensuring that our optimization effectively addresses the distinctive characteristics and performance demands of these hardware modules.

Question 3 [Need for Designing Game]

We understand your concern regarding the need to design the "game" for our work. Indeed, the majority of problems solved using RL necessitate the explicit definition of states, actions, and rewards, much like designing a game. The benefit of this approach is that a well-defined structure can significantly enhance the agent's ability to optimize the target efficiently and effectively.

Regarding the work "Eureka", we fully agree that it represents an excellent contribution to the field. We will discuss Eureka in our revised paper and consider applying its reward design methodologies to arithmetic unit design in our future work. We believe that leveraging Eureka's approach can further improve our algorithm's efficiency and performance.

Thank you very much for your positive comments.

Weakness 1 [Focus on Adders and Multipliers]

• While our current results focus on adders and multipliers, these operations are among the most time-consuming on GPUs, making their optimization highly significant.

• We would like to clarify that our work can also be extended to other arithmetic modules. Taking exponentiation as an example, exponentiation operations require multiple multiplication operations. By leveraging the underlying principle of repeated multiplication in exponentiation, we can apply our RL framework, initially designed for optimizing adders and multipliers, to enhance the design and efficiency of exponentiation units. This extension would involve tuning our model to accommodate the iterative nature of exponentiation, ensuring that the optimization captures the unique characteristics and performance requirements of these hardware modules.

Weakness 2 [Scalability]

We understand your concern regarding the scalability of our methods to larger bit widths. Currently, most computer systems predominantly use integer widths within the 128-bit range (with 64-bit multipliers producing 128-bit results), covering most practical applications. Moreover, we have employed pruning and two-level retrieval techniques to effectively explore and discover superior 128-bit prefix adder structures. Additionally, through optimized synthesis, we have scaled our multiplier designs from 16-bit to 64-bit, demonstrating significant improvements over the RL-MUL approach. Thus, our approach addresses current practical requirements and showcases the potential for scalability and enhanced performance through advanced optimization techniques.

Minors

Thank you for pointing out. We will correct them in the revised version.

Question 1 [Details about the synthesis]

We have provided detailed information on the timing aspects of the design flow in the appendix of our paper. Specifically, Fig. 12 and Fig. 13 contain comprehensive script codes that outline our approach to both logical and physical synthesis. For Fig. 12, we have maintained consistency with the RL-MUL methodology, while for Fig. 13, we utilized the default physical synthesis flow parameters provided by OpenROAD. These figures should provide the detailed information you have requested regarding the timing aspects and the specific parameters used in OpenROAD.

Question 2 [Extension to Other Hardware Units]

Our method can also be extended to exponentiation units. See Weakness 1.

Thank you very much for your positive comments.

Weakness 1 [Add Detailed Introduction in Main Text]

Thank you for the suggestion. In our revised paper, we will include the introduction of the states and actions for both AddGame and MultGame, and the tree representations in the Appendix, to the main text.

Weakness 2 [Technology Used in Fig. 6]

The Fig. 6 results are based on Nangate45 PDK (45 nm). We will add this information to the caption of Fig. 6 in our revised version.

Question 1 [Benefits of Building from Scratch]

Building from scratch theoretically allows for the exploration of a broader range of compressor tree structures. All compressor trees can be viewed as being composed of basic compressor units, and building from scratch begins with adding these fundamental compressors. This approach grants greater freedom compared to modifying an existing compressor tree. This is because modifying existing compressor trees limits the exploration of new structures due to constraints such as the number of iterations.

Additionally, the number of compressors in a compressor tree is finite, which means the steps in our building-from-scratch method are also limited. Consequently, optimization performance can be maintained within an acceptable range. As shown in Table 8, the optimization time remains within a reasonable timeframe. This demonstrates that building from scratch offers more design flexibility while maintaining performance.

Question 2 [Objective in Table 7]

The designs in Table 7 are obtained by performing trade-off optimization with open-source tools and then directly testing these optimized circuits with commercial tools. The increase in area can be attributed to the differences between the open-source and commercial tools used. Due to variations in their synthesis methodologies, the results from open-source tools might not achieve optimal performance when used with commercial tools. However, our approach still demonstrates significant advantages in terms of delay. We will clarify this in the new version of our paper.

Question 3 [Accuracy Definition in Table 9]

As we introduced in the two-level retrieval, we defined a fast flow and a full flow. The fast flow is quick but may not be accurate without routing, whereas the full flow takes longer but provides precise delay and area outputs. We assume that the delay and area predicted by the fast flow are $d'$ and $a'$, respectively, while the delay and area achieved from the full flow are $d$ and $a$. The accuracy reported in Table 9 is defined as $\frac{d'}{d}$ and $\frac{a'}{a}$. Experimental results show that the fast flow tends to slightly underestimate delay, while its area predictions are completely accurate.

Thank you very much for your positive feedback.

Weakness 1 [PDK Selection]

Although the 45nm and 7nm PDKs employed in our study are open-source and academically oriented, they are designed to closely mimic corresponding industry nodes and are widely used for benchmarking purposes within the academic community. This ensures complete reproducibility of our results, which is a critical aspect of rigorous scientific research. For example, both PrefixRL and RL-MUL utilize the open-source Nangate45 PDK. In contrast, commercial-grade industry PDKs are proprietary and restrict the sharing of detailed process information. While we acknowledge the importance of validating our approach with industry PDKs in future work to confirm its practicality in real-world applications, open-source PDKs provide a robust foundation for demonstrating our methodology's feasibility and effectiveness within this paper's scope.

Weakness 2 [Grammatical Error]

A good catch. We will correct this in our revised version.

Question 1 [Usage of Industry PDK]

The PDKs used in our study are designed to mimic corresponding industry nodes and are widely adopted for benchmarking purposes. They help enhance reproducibility, while industry PDKs, being proprietary, may present some challenges with reproducibility.

Question 2 [Applicability to Real Industry PDKs]

Our proposed method can be directly applied to real industry PDKs. The only requirement is to modify the library files corresponding to the parameters during synthesis.

Question 3 [Design Number Variability]

Traditional designs like Brent-Kung and Sklansky adders have fixed prefix structures, resulting in a single, consistent design each time they are implemented. In contrast, RL methods explore a wide design space during a single execution, generating various tree structures and diverse design outcomes. This flexibility allows RL methods to produce multiple designs within one optimization process.

Thank you so much for your constructive comments.

Weakness 1 [Application in Modern LLM]

• We appreciate this observation regarding the diminishing improvements of our PPO-based method as the bit width decreases. Indeed, the paper highlights the significance of multipliers and adders for large models, which traditionally have used higher bit widths. However, it is essential to note that while modern AI models often utilize 16 bits or even lower for efficiency, the computational demands and precision requirements can vary significantly depending on the application and deployment scenario. Recent studies [1] have shown that the performance of LLAMA 3 significantly degrades with low-bit quantization. This indicates that our method for high-bit precision has substantial potential for improving the computational speed of future large models and high-performance computing tasks.

• In addition to theoretical improvements, we are actively collaborating with industry partners to validate and refine our approach in real-world scenarios, ensuring that our method remains relevant and effective for contemporary AI applications, irrespective of their bit-width requirements.

[1] How Good Are Low-bit Quantized LLAMA3 Models? An Empirical Study

Weakness 2 [About Floating-Point Data]

• Thank you for raising the concern regarding the performance of our method on floating-point v.s. integer data types. It is important to clarify that at the fundamental level, the arithmetic operations of addition and multiplication share core similarities between floating-point and integer data types. For example, in floating-point multiplication, the exponents are added (integer addition), and the significands are multiplied (integer multiplication). This indicates that the core computational workload lies in integer arithmetic. Thus, while our current evaluation is on integer data types, the principles and optimizations easily apply to floating-point arithmetic.

• Although our initial evaluations focused on integer operations due to their straightforward implementation and common usage in specific applications, the core optimizations are inherently applicable to floating-point arithmetic as well. Future work will explicitly focus on floating-point evaluations to demonstrate this applicability and to fine-tune our method for any floating-point-specific optimizations that may be required.

Weakness 3 [Significance in Addition and Multiplication. Extension to Other Arithmetic Units]

• While our current results focus on adders and multipliers, these operations are among the most time-consuming on GPUs, making their optimization highly significant.

• We would like to clarify that our work can also be extended to other arithmetic modules. Taking exponentiation as an example, exponentiation operations require multiple multiplication operations. By leveraging the underlying principle of repeated multiplication in exponentiation, we can apply our RL framework, initially designed for optimizing adders and multipliers, to enhance the design and efficiency of exponentiation units. This extension would involve tuning our model to accommodate the iterative nature of exponentiation, ensuring that the optimization captures the unique characteristics and performance requirements of these hardware modules.

Thank you very much for your constructive feedback.

Weakness 1 [Distinction and Improvement over PrefixRL [17]]

Both our approach and PrefixRL [17] apply an RL framework to circuit design. However, our method incorporates several critical enhancements that we would like to clarify:

• Advancement in the RL (state, action, and reward) formulation:
  • State: In PrefixRL, prefix trees are represented using a binary matrix, which is solely applicable to the prefix tree structure. In contrast, our model does not directly represent the prefix tree structure. Instead, each node, representing a prefix tree, is evaluated by $W(s)$, a scoring function designed to effectively balance exploration and exploitation.
  • Action: PrefixRL’s actions include adding and deleting cells. However, adding cells does not improve the theoretical metrics (level/size) of the adder it represents. Therefore, we have strategically omitted actions that add cells when optimizing these metrics. This refinement significantly boosts search efficiency, especially in the case of a 128-bit adder, by focusing on actions that directly contribute to performance improvement.
  • Reward: The reward in PrefixRL is calculated based on the performance improvement at each step. Our method, however, utilizes the performance value of the final node reached during the simulation phase of MCTS. This shift reduces the computational overhead from multiple time-consuming simulations and provides a more direct assessment of performance outcomes.
• Advancement in Implementation:
  • Two-level Retrieval: We use the fast synthesis flow to retrieve potential designs, and then use full synthesis flow to get the final performance results, improving the efficiency.
• Advancement in Task Setting and Method Design:
  • Task Setting: PrefixRL only addresses adder design, whereas we work on adder and multiplier designs.
  • Method Design: We have introduced a novel framework for the co-optimization of the multiplier’s compress tree and prefix tree. This integrated approach significantly enhances the overall effectiveness of multiplier design.

Weakness 2 [Data Points]

See the response in Question 3.

Question 1 [State Representation]

Specific representation of adder and multiplier:

• Adder: We represent the prefix tree structure based on the score $W(s)$ at the nodes of the search tree, eliminating the need to explicitly design a matrix representation model in PrefixRL [17] and making it more generalizable.
• Multiplier: We select high-level meta-features, such as the maximum estimated delay value of bits, different from the matrix representation in counterparts (e.g. RL-MUL). Utilizing these higher-level features enhances the model's ability to learn the construction of multipliers with detailed information, thereby improving design outcomes.

Difference with PrefixRL [17]:

Please refer to our response in [Weakness 1] for the advantages of our approach over PrefixRL.

Question 2 [Did the obtained design go through an equivalence-checking process to ensure the functionality correctness?]

Sure, we did it. Specifically, we used corresponding testbenches for the generated Verilog code, which includes hundreds of sets of addition or multiplication operations. By observing the outputs, we verified the correctness of the computations.

Question 3 [Sklansky v.s. Koggle-Stone]

We agree with the reviewer that, in general, the Kogge-Stone adder generally has lower latency than the Sklansky adder due to its highly parallel, low fanout, and balanced prefix computation structure. As observed in our paper (Figure 6, middle subfigure), the Kogge-Stone adder exhibits lower latency compared to the Sklansky adder.

However, in some specific experimental conditions, the Sklansky adder can also exhibit lower latency, as observed in our experiments (Figure 6, left subfigure) and also reported in the literature [1, 2, 3, 4]. The specific reasons for this observation are the following:

• Impact by the Interconnection Complexity: In real-world implementations, the Kogge-Stone adder's structure results in very complex interconnections. Typically, with abundant hardware resources, this interconnection complexity can be effectively managed. However, when actual hardware resources are limited, this complexity can lead to significant wiring congestion and increased actual delay. In contrast, the Sklansky adder, with its reduced interconnection, offers simpler wiring. This simplicity decreases the likelihood of congestion and potentially enhances overall performance under resource limitations.

• Impact by Synthesis Tools: Delay is influenced not only by the differences in the prefix tree structures (in Kogge-Stone and Sklansky adders) but also by the subsequent synthesis processes. Typically, the high fan-out in the Sklansky adder tends to increase its delay. However, modern synthesis tools (e.g., Yosys, OpenROAD) are equipped with advanced optimization techniques that can effectively manage high fan-out by balancing the load, buffering critical paths, and optimizing the placement of logic elements. These tools can significantly reduce the adverse impact of high fan-out on delay, ensuring that the Sklansky adder performs efficiently.

To further validate our experimental results, we also consulted an expert in adder design, who believes that it is entirely acceptable for the Sklansky adder to have a slightly lower delay than the Kogge-Stone adder after physical synthesis.

[1] Performance comparison among various parallel prefix adder topologies

[2] PrefixRL: Optimization of parallel prefix circuits using deep reinforcement learning

[3] Implementation of 64 Bit Arithmetic Adders

[4] An Efficient Design and Performance Analysis of Novel 8 Bit Modified Wallace Multiplier Using Sklansky Adder in Comparison with Kogge-Stone Adder (KSA)