Scalable and Effective Arithmetic Tree Generation for Adder and Multiplier Designs
Authors: Yao Lai
Jinxin Liu
David Z. Pan
Ping Luo
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Reinforcement Learning
Computer Arithmetic
Electronic Design Automation
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: Employing RL methods for arithmetic tree generation yields superior designs for adders and multipliers.

Abstract: Across a wide range of hardware scenarios, the computational efficiency and physical size of the arithmetic units significantly influence the speed and footprint of the overall hardware system. Nevertheless, the effectiveness of prior arithmetic design techniques proves inadequate, as they do not sufficiently optimize speed and area, resulting in increased latency and larger module size. To boost computing performance, this work focuses on the two most common and fundamental arithmetic modules, adders and multipliers. We cast the design tasks as single-player tree generation games, leveraging reinforcement learning techniques to optimize their arithmetic tree structures. This tree generation formulation allows us to efficiently navigate the vast search space and discover superior arithmetic designs that improve computational efficiency and hardware size within just a few hours. Our proposed method, **ArithTreeRL**, achieves significant improvements for both adders and multipliers. For adders, our approach discovers designs of 128-bit adders that achieve Pareto optimality in theoretical metrics. Compared with PrefixRL, it reduces delay and size by up to 26% and 30%, respectively. For multipliers, compared to RL-MUL, our method enhances speed and reduces size by as much as 49% and 45%. Additionally, ArithTreeRL's flexibility and scalability enable seamless integration into 7nm technology. We believe our work will offer valuable insights into hardware design, further accelerating speed and reducing size through the refined search space and our tree generation methodologies.

Scalable and Effective Arithmetic Tree Generation for Adder and Multiplier Designs
Yao Lai', Jinxin Liu?, David Z. Pan Ping Luo' 'The University of Hong Kong. 'The University of Texas at Austin, *Zejjang University
Abstract
Across wide range of hardware scenarios, the computational efficiency and phys- ical size of the arithmetic units significantly influence the speed and footprint of the overall hardware system. Nevertheless, the effectiveness of prior arithmetic design techniques proves inadequate, as they do not sufficiently optimize speed and area, resulting in increased latency and larger module size. To boost comput- ing performance, this work focuses the two most common and fundamental arithmetic modules, adders and multipliers. We cast the design tasks as single- player tree generation games, leveraging reinforcement learning techniques optimize their arithmetic tree structures, This tree generation formulation allows to efficiently navigate the vast search space and discover superior arithmetic designs that improve computational efficiency and hardware size within just a few hours. Our proposed method, Arith TreeRL, achieves significant improvements for both adders and multipliers. For adders, our approach discovers designs of 128-bit adders that achieve Pareto optimality in theoretical metries. Compared with PrefixRI., it reduces delay and size by up to 26% and 30%, respectively. For multipliers, compared RL-MUL. our method enhances speed and reduces size by as much as 49% and 45%. Additionally, AreehTreeRL's flexibility and scalability enable seamless integration into 7nm technology. We believe our work will offer valuable insights into hardware design, further accelerating speed and reducing size through the refined search space and our tree generation methodologies. Codes are released at ggiihub.com/liiyol//AAiiii l/Arithmetic Tree
1
Introduction
Since the inception of computers, researchers have striven to boost computing speed and decrease hardware size. High computing speed is essential for wide range of real-world applications, such artificial intelligence [ high-performance computing [2], and high-frequency trading [3], particu- larly for the recent applications of large language models like GPT (4. Concurrently, the demand for smaller hardware has escalated due to the growth of wearable devices and 1oT technology [5].
Hardware specialists have steadily miniaturized CMOS technology O to boost processor speeds and shrink chip sizes. However, as CMOS technology's 's scaling nears its fundamental physical limits [7], further miniaturization poses significant challenges. Therefore, exploring innovative circuit design has emerged as a vital alternative to drive performance enhancement and area reduction. Among the family of arithmetic modules for hardware architectures, adders and multipliers constitute two essential modules, playing a critical role various computational operations. For example, basic addition and multiplication operations compute all convolution and fully connected layers
Corresponding to: Ping Luo @.l.o@cs.hk..kk.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Prefix Tree
Compressor Tree
Lavel
Prefix Tree Design
AddGame
Adder
Co-design
level
20
0L0 05 m940
Compressor
MullGame
high
high
Tree
200
cell 22 binary bits G.,)
binary bit
Design
Multiplier
cell 1 binary bit (G.))
Hall Adderr
Full
P. propagation G, generation
cont
sum
Adder
(a)
(c)
Figure (a) Arith AreeRT, framework. Two agents optimize prefix and compressor trees, respectively, modeling the tasks as AddGame for adders and MultGame for multipliers. (h) Prefix tree. (c) Compressor tree. Different tree structures lead to different qualities of adder and multiplier designs.
of deep learning models. Performance analysis of the ResNet model reveals that the convolution operation, consisting solely of addition and multiplication, constitutes 98.4% of the overall GPU execution time during model inference. Under Amdahl's Law 19. an enhancement of 30% in addition and multiplication operation speeds could result in 29% improvement in inference speed. Intriguingly, this improvement comparable to the speedup typically seen with a generational upgrade in semiconductor process technology [1O 11] Thus, designing more efficient and compact adders and multipliers is crucial for the overall advancement hardware design.
Numerous arithmetic module design methods have been proposed in recent years, These techniques generally fall into one of three main categories: human-based [22 [3,, optimization- baased (14
and learning-base baased [1719]. However, these methods either demand significant hardware expertise or get trapped in local optimal due to the vast design search space for adders and multipliers modules. For human- humen-based methods, hardware experts have crafted variety of arithmetic modules, such as the Sklansky adder [12] and the Wallace multiplier [3]. Nevertheless, designing new structures becomes increasingly challenging for humans input bits increase. Optimization-base
methods, and integer linear programming [16), can enhance the quality of arithmetic designs by exploring wider variety of structures. Despite their potential, the extensive search space poses a challenge, necessitating manually defined assumptions to limit the search scope for feasible computation. For example, Ma et al. (20] assumed the existence of semi-regular structures in adders, which may lead to locally optimal solutions. While learning- -bsed approaches have emerged as promising tool for automating hardware design in recent years [17]- 19), navigating the vast design space to find the optimal solution for arithmetic modules remains formidable challenge. For example, the two primary components of an N-bit multiplier, the compressor tree and the prefix tree, have approximately O(2-1) and O(24N²) design space (17). respectively. Consequently, the search space of a simple 16-bit multiplier is already comparable to that of the Go game (3361) 21 Meanwhile, such bearning-based approaches also fail to consider the joint optimization of different components within arithmetic hardware [17] 18]. thus easily leading to degenerated hardware with undesired performance bottleneck.
like bottom-up enumerate search [14 155
To resolve the above limitations and boost the performance, we formulate the arithmetic adder and multiplier design problems as two single-player tree generation games, AddGame and MultGame, respectively, as shown in Fig. Tb. The key insight is that by reframing the design problems into interactive tree generation games, we harness the power of progressive optimization algorithms, allowing us to explore the intricate design space of arithmetic units dynamically. Starting from an initial prefix tree, the player in AddGame sequentially modifies cells in the prefix tree, in the same spirit as tactical movements in board games. Our MultGame contains two parts, specifically for designing the compressor tree and the prefix tree of multipliers. The compressor tree design involves the player compressing all partial products with different compressors, similar to match game. In contrast, the prefix tree design follows the same rules as the AddGame. Unlike the default design process depicted in Fig. 2p. the tree structures discovered in games are converted into specific Verilog codes [22), as illustrated Fig. P.. We demonstrate that the delay and area of arithmetic modules can be largely decreased by substituting the default designs with our discovered tree structures.

---

WHDlle Miltisterre, Y: V0
matepctancs OF
crcrodile
outpurt [tod]
wote pey 2h, ph. ph PG, PG P7, PR, PP,
22 $E.U.., SELAJAS
youg
Syntheas
your
Logical Syathois
balfaacerr Faoiis_A. FEURA, 27 pretze true
sone 12:03 unstcdaale
AddiCaam
A.MM Mulliplier
Physical Syntheds
Physical Synthasis
Default Structural Trees
Xy M
mocile addrcc, by
aeout [3:2] by (200) get
vone p3.3. a1.. eanigh FL.1 aE33 ME23
21. 12.2,
exstig 22.1 +523 NEP1
eaxigh 22.2 12.1 $2.21
Practica Multiplier Dosiga (delay 351 ps. area 70 usiF)
Practical Muttipller
get natiure
(detay 400
Desiga
undiodala
#asiinn +3.3
a000 78 um))
(a)
(b)
Figure 2: Comparison of design processes. (a) Default design process. The synthesis tool automatically generates a default multiplier when using multiplication commands (xºy) in Verilog HDL code. (b) Enhanced design process in TreeL, ArithTreeRL discovers an optimized multiplier structure and generates specialized Verilog HDL code for this improved structure, reducing delay and area after synthesis.
We propose RreehT (Arithmetic Tree Reinforcement Learning), novel approach that utilizes customized reinforcement learning agents for optimizing arithmetic tree structures. In practical imple- mentation, Arith TreeRL employs two distinet agents tailored to the specific characteristics of prefix and compressor tree optimization. For the prefix tree, appearing in both AddGame and MultGame, we utilize Monte-Carlo Tree Search (MCTS) 23 agent to efficiently explore the large action space while preserving previous exploration experience. For the compressor tree, exclusive to MultGame, we take a Proximal Policy Optimization (PPO) 24 agent due to its superior exploration efficiency. To capture the global design for multiplier designs, we also designed an optimization curriculum as depicted in Fig. I iteratively running MCTS and PPO agents to refine the prefix and compressor trees.
This paper has three main contributions. Firstly, we model the arithmetic module design tasks as kingeeplaaer tree generation games, i..,, AddGame and MultGame, which inherit the well-established RL capabilities for complex decision-making tasks (arithmetic tree optimization). Secondly, we propose a co-designed framework that integrates prefix and compressor tree modules, enabling the discovery of optimal combinations that lead to global optimal multipliers. Thirdly, our experiments reveal that our designed 128-bit Pareto-optimal adders outperform the latest theoretical designs. Also, our designed adders achieved up to 26% and 30% reductions in delay and area compared to PrefixRL [17]. and multipliers offer 33% and 45% improvements over RL-MUL [18] in the same metrics. These designs are ready for direct integration into synthesis tools, offering significant industrial benefits, and are flexible and scalable enough to be seamlessly adopted into 7nm technology.
2 Preliminaries
Adder Design. An -bbit adder can be constructed by cascading N 1-bit adders. However, this approach results in an (NN) delay due to the sequential propagation of the carry signal from the lower bit to the higher bit. To address this issue, prefix adders have been proposed 25 26]. Prefix adders designed based on the principles of addition, with a focus on reusing and parallelizing intermediate signal bits. These signal bits can be divided into two categories: propagation bits p; a, t 6; and generation bits gi a; b, where ag b, E {0, 1), i 21,2,... N represent the addends at the i-th bit, and 'ø' and '." denote the logic XOR and AND operations, respectively (27). These propagation and generation signals can be defined at both the individual bit level and across a range of bits. For an individual bit with index i, they are denoted by P.x = Pt and G = gs. When considering range of bits, this range is treated as an interval identified by a tuple (i.j). Within each such interval, we have a single propagation signal P.y Th Pk and single generation signal Gzy = 9j > Peej IKk where '+' represents the logic OR operation. Note that the computation of Pay and Gv. is influenced solely by the input bits from position to j. The (N + 1) outputs of the adder can be calculated from the signal bits with the initial condition G = 0 by CN+1 IN + PN I and s; p. + G where + is the carry-out bit and 8; is the i-th sum bit.
The prefix adder design aims to optimize a hierarchical tree structure that generates all intervals (1, from the initial intervals (i, i), shown in Fig. lp. Signal bits for two adjacent intervals, (i, k) and
3

---

(k + 1.)), can be merged to form the larger interval (i.j) by the computations P.y = Pak Pk+1:: and G.j = Ges Ps+1g + GR+ig- This merging process generates a prefix tree where each cell represents an (i,j) interval with two signal bits. If an interval results from merging two others, its corresponding cell is the child node in the tree, and the merged intervals are its parent node. For example, the (5, 8) cell is the child node of the (5, 6) and (7, 8) cells because it derived from them. A key advantage of this structure is that cells with no dependencies can be computed in parallel. Different tree structures can result in adders with varying delays and areas. When evaluating the theoretical quality of the prefix adder, We can use level (tree height) and size (number of cells) as theoretical metrics to substitute for practical metries like delay and area.
Multiplier Design. An N-bit multiplier carries out the multiplication of two N-bit multiplicands. which can be regarded as the cumulative addition of N addends, involving total of N2 bits. Each addend represents a partial product with different powers of two weights, illustrated in Fig. 4p. Multipliers can be easily achieved by cascading (N 1) N-bit adders or using a single N-bit adder (N 1) times. However, both result in a large area or high delay. To mitigate this, the N2 bits in the partial products can be added simultaneously by 1-bit adders, which can also be seen bit compression process because the number of bits gradually decreases. The compression process halts when the number of bits for each binary digit is reduced to two or fewer before feeding into a downstream adder, as illustrated in Fig. T.. The process generates a compressor tree, describing compression mechanism that merges N bits into fewer bits by compressors such as half and full addrrs. Introducing an additional carry-in input distinguishes a full adder from a half adder, as shown in Fig. ПT. which affects the latency and area. The difference is crucial when configuring the compressor tree in multipliers to optimize for delays and area requirements. Upon completing the compression, the remaining bits are processed by 2.N-bit prefix adder, designed yield the globally optimal multiplier. In summary, adder and multiplier design tasks can be interpreted as a tree-based structural generation process optimize hardware metrics while maintaining functionality.
3 Our Approach
We use reinforcement learning to solve the tree generation for adder and multiplier designs. The environments are modeled as single-player tree generation games: AddGame for adder design and MultGame for multipliers, as illustrated in Fig. Dp. Considering differences among the games, such as action space, we propose two types of agents: one by MCTS (28 and another by PPO (24).
3.1 AddGame
AddGame is modeled for designing prefix trees in adders and multipliers, as shown in Fig. 3 this game, the player modifies the structures of given initial prefix trees by basic actions to optimize the adders' metrics. The state of the game is denoted as 8, corresponding to the current prefix tree. In our evaluation, each state is assessed on two theoretical metrics, level and size, and two practical metrics, delay and area. The player always chooses one action from two kinds of actions: (1) delete a cell (i, j). (2) add cell ji. which (i,5) is the cell index as shown in Fig, Dp. A cell (i, (i < j) can be deleted if the prefix tree does not have the cell (t, R)) subject to i > " and >> 1, and all deletable cells
marked in red in Fig. 3 and 5 A cell (i.j) can be added if it does not exist in the prefix tree. All positions where cells can be added are marked with 'x'. A legalization operation [17] is always executed after one action to guarantee the feasibility of the prefix tree as Fig. [3] The game aims to maximize the performance score R(s) of the adder s. This score is determined by a weighted combination of delay and area (using level and size when optimizing theoretical metrics).
Given the large action space, the agent for playing AddGame is based on an improved MCTS method, which has demonstrated its effectiveness in numerous game tasks 21 29 30). Starting from the prefix trees in human-desii -eeinnd adders, the MCTS agent continuously cycles through four phases: selection, expansion, simulation, and backpropagation, and gradually builds search tree in this process. Each node in the search tree represents one prefix tree.
In the selection phase, the agent selects the child node with state that has the highest score W(s), continuing until it encounters a node that has not been fully expanded. The scores for evaluating nodes are computed by the Upper Confidence bounds applied to Trees (UCT) 31 keeping the balance between exploration and exploitation. In the search tree, each node with the state 8 stores a visit count N (s) and an action value (ss). The visit count N Nss) records the number of visits to the

---

node The action value (s)) is the weighted sum of the best performance score max R and average performance score R of all its descendant nodes, which can be formalized as:
V(s) = (1-3)
E s'E((s)
R(s))/D(s) + max R(s') (ED())
(1)
performaance scure
performance
where (s) represents all descendant nodes of the node (including itself), i.e., all generated adders by sequence of actions from adder |- gives the number of nodes. R(s')) indicates the performance score of the adder of the state s', which is defined as -Delay a'Area or - -iize. a and are sum weights.
We define the node score W (s)) with the state follows:
(Ps()(s)) N(s)
(())
(+))
(2)
1. Selection Delete cell +
Add cell 3
where P(s) is the parent node of s, (-) is visit count function, and e an adjustable parameter.
Updkile
Soore
In the expansion phase, random action is chosen from the unexplored actions available at the node identified in the selection phase and executed.
Update Score
2. Expansion
Delete cell
expands the search tree by adding new node corresponding to the result after that action. In the simulation phase, a sequence of actions is taken until the performance scores of adders can no longer be improved (in theoretical metrics optimization) the simulation exceeds the maximum steps (in practical metrics optimization). In the backpropagation phase, the last state reached in the simulation phase evaluated get a performance score R(s), which then backpropagated to update the scores of all preceding nodes in the search tree.
delete calls
Update Soore
3. Simulation
by defail policy
4. Backpropagation
R(S) = -Delay a Area
R(s) Size
Figure 3: Method for designing prefix trees with
Pruning. To enhance efficiency, we implement pruning techniques to avoid the exploration of un- necessary sub-trees. When optimizing theoretical metrics, we restrict modifications actions, as adding cells does not improve the design outcome. Furthermore, we impose an upper limit on the level metric to prevent the creation of structures with excessively high complexity. This upper limit, denoted as L., is set for each MCTS search and is gradually relaxed with each search iteration.
MCTS. Four phases the search process are exccuted iteratively, gradually building search tree.
delete cell
Two-level Retrieval. We adopt two-level retrieval strategy to balance synthesis accuracy and computational efficiency. We divide the search into two stages because the full synthesis flow is highly accurate but time-consuming. A faster marginally less simulating accurate synthesis flow employed in the first stage, eliminating the time-intensive steps such as routing. Only the top K adders identified in the first stage undergo full synthesis in the second stage.
3.2 MultGame
MultGame consists two parts for jointly designing compressor and prefix trees in multipliers, as shown in Fig. The part focused the prefix tree design is identical to that in AddGame. Meanwhile, the part focused on the compressor tree design involves continually merging bits in partial products through compression actions, depicted in Fig. 4 This process is similar some match games like '2048' [32] where items are merged in a specific way to achieve high scores.
The compressor tree is built from scratch instead of starting from existing solutions for more design flexibility. The game state 8t at step is represented by vector representing the current compressor tree status. The player chooses one of two actions: (1) using half adder or (2) using full adder to
5

---

Betion digit
(4)
Dut
half sdder
full miler
hall wdleer
Notation
@
estimated deday value
-p)
(r 03
-delay)
muii placedd
(b)
Binary Bit
Notation
partill products
(c) Logic Gate Notation
Half adder (n A, B
deloffy -n was jww. anloyfiad)) dieed)
Full adder B. Cin out Cout:
dilgg promecedd doly,
Figure 4: Designing compressor trees with PPO. Three representations are illustrated. (a) Dot notation. Each dot represents an output bit, with the number inside indicating the estimated delay for selecting adder input bits. The agent's 's actions involve adding full or half adders to compress the bits until cach binary digit contains no more than two bits. The final reward, rr, is defined as the inverse of the delay. encouraging designs with lower delays. (b) Binary bit notation. 0/1 are values of bits for the example multiplication. (c) Logic gate notation. The actual logic gate circuit design for each state.
compress bits at the action digit, which is defined as the lowest digit containing more than two bits, as indicated in Fig. 4h. Half and full adders compress two or three bits in the k-th digit and generate a carry-out bit in the (k + 1)-th digit and a sum bit in the k-th digit. Rough delays for all bits are estimated, assuming one-unit delay for all basic logic gates, shown in the dots of Fig. 4h. To minimize the increase in total delay, the bits with the lowest estimated delays are selected as inputs for the adders. The game terminates step T when all digits have computed through the synthesis tools as the negative of the delay, denoted rr = - delay. Moreover, a half adder, where 1 < S T. This
fewer bits. A reward er is
penalty term -p is also applied to r; if the action 04-1 penalty reflects that a full adder accepts three input bits (two addend bits and a carry-in bit) and produces two output bits sum bit and carry-out bit), effectively reducing the bit count. In contrast, a half adder only processes two addend bits and outputs two bits, thus not contributing to a reduction in bit count. A half adder's lack of bit count reduction can lead more adder modules, increasing the overall module area.
We train RL agent with policy and value networks using the PPO method. Both networks are built by multi-layer perceptions (MLPs) 33 with three layers. The inputs comprise pre-defined features as Table 1. including action digit, max delay, number of half adders, eligible action type, and the estimated delays of bits. The policy and value networks contain (64, 16, 2) and (64,8, 8, 1) neurons in each layer. The last layer of the policy network is connected Softmax activation function [34 for choosing actions.
Table I: State features for policy and value network.
Feature
Size
Description
Action digit
1
Digit for action.
Max delay
Maximum estimated delay value of all bits.
Number of half adders
1
Number of added half adders in action digit.
Mask for action
2
The mask for cnsuring valid action.
Delay of action bits
3 The delays of bits for action.
When training, the objective function can be defined as follows for maximizing the game's cumulative reward:
T
((0) E Er,,
[Gr]
Erawn
Σ Yr.
(3)
k=0

---

where r = (su, 4u. F1, a1....,...0................ -1-1; PT) is trajectory from the game episode, and Te denotes the policy parameterized by 8. GT refers the cumulative discounted reward from step 0 to step T. The discount factor y adjusts the emphasis between immediate and future rewards. When implementing the PPO, the objective function for optimizing the policy network can be formalized as:
L(0) = E. min (rr(0).A,, clip(r.(0),, c, 1, +c).
(4)
where Ed[-] indicates the empirical average over a finite batch of samples, and re(0) denotes the probability ratio =u(as]as)
Touza [Rel Here, Oota is the policy network parameters before the update. A.
G.-V, Vi an estimation of the advantage function at step t, and V2 is the value estimated by the value network. clip(-, e,
1 + e) is the function restricting results to the interval [1 1 + c).
Simultaneouslly, the value network with parameters ø is updated by optimizing the following objective function L( E. Lopoott_L(GGa V.), where smooth_LI() is the smooth L1 loss function 335
Synthesis Acceleration. In RL-MUL [8]] rumning synthesis tools proved to be a bottleneck, especially for scaling to multipliers with higher bit-widths. To address this, our enhancements to the synthesis flow yield a 10x speedup in reward computation without sacrificing accuracy. These modifications facilitate the design of multipliers up to 64-bit, expanding from the 16-bit limit in RL-MUL. Enhancements include activating the fast mode in the logical synthesis script and adopting direct code template-basee generation of Verilog HDL code from search results, moving away from the consumingg EasyMAC (36] tool.
Co-design Framework. As shown in Fig. 1 we developed joint design approach to optimize the multiplier's ' two primary components: the prefix and compressor trees. Our method involves an iterative process where each round involves optimizing the compressor tree with fixed prefix tree and searching for an ideal prefix tree that aligns with the optimized compressor. This alternating optimization continues until the computational iterations conclude.
4 Experiments
We use the logic synthesis tool Yosys 0.27 (37 and the physical synthesis tool OpenROAD 2.0 38 with N5ngate45 [39] and ASAP7 (40) libraries to implement experiments. Both synthesis tools are open-sourced for result reproduction. All experiments are run on one GeForce RTX 3090 GPU and one AMD Ryzen 5950X 16-core CPU. Detailed settings are in Appendix A.3 and A.5 modules have successfully undergone functional verification.
All designed
4.1 Adder Design
Theoretical Evaluation. As illustrated in Fig. П.. prefix tree structures define the technology- independent theoretical metrics of level and size. Empirically, optimizing the level usually presents more challenges than size. Therefore, we set the search objective when optimizing theoretical metrics to find the optimal size for each specified upper bound level L. We begin our search with the Sklansky adder [12), which has theoretical minimum level of log, N. Starting with set at this minimum, we incrementally increase it for each new iteration, using the smallest prefix tree identified in the previous round as the initial state. We limited the number of steps to x 10 for each search iteration. For baselines, the results were obtained directly from the respective original publications. Table 2 shows that our method surpasses the state-of-the-ar designs in (14) Some discovered adder structures are presented in Fig. 5 Despite the exponentially growing search space, our MCTS method can enhance 128-bit adders, surpassing the designs from optimization based methods. Notably, guided by Snir's 's thcoretical lower bound for size at given level [41], we were the first to discover an optimal 128-bit adder with 10 levels and a size of 244.
Practical Evaluation. Practical metrics, including the delay and area of hardware modules, are computed through synthesis tools for evaluation. We run 1000 full syntheses for adders in each method to ensure a fair comparison. Our ArithTreeRL method begins each search from one of three adders: Sklansky [12], Brent-Kung (4), and ripple-carry 44. two-level retrieval strategy
implemented by dividing the search into two stages: (1) 5000 fast syntheses. (2) 500 full syntheses
with the top 500 adders selected from the first stage. Efficiency tests show that one full flow's
computational load equals 10 fast flows. Thus, the proposed strategy achieves the same computational
7

---

Table 2:
Comparisons discovered adders and area, Smaller sizes are preferable.
Input Bit
Level
Theory Size Bound
Sklansky Size
Area Heuristic
+
Best Known Size
[4
Arith TreeRT..
64
6
120
192
169
167
167
64
8
118
120
118
118
64
10
116
116
116
116
128
247
448
375
364
364
128
246
304
276
273
128
245
284
250
248
128
10
244
257
245
244
128-hit adder (level =8 size=273
bit adder (levd =9 9:0-2248
12t adder (level =10 249
20000000 605
Figure 5: Some first discovered prefix trees for 128-bit adders with the smallest sizes.
32-bit adder
64-bit adder
128-bit adder
3.0
1.0
Portunt
1.4
Wediat
3.5-
Aith livel)
Skandby
Sciamly
2.40
Delag (ms))
Kagpo Stans
2.35
0.4
3.10
0.4
325
(pm77))
Figure Comparison adders delay area. Each point represents one adder and line segments connect Pareto-optimal adders. 'PrefixRL (2-level retr.)' is the raw PrefixRL method improved by our two-level retrieval strategy. Sklansky, Brent-Kung and Kogge-Stone refer to human-designed adders. ArithTreeRL can significantly improve the delay and area, particularly for high-bit adders. Furthermore, it can discover adders with minimal delays. Our two-level retrieval strategy can effectively find superior designs.
volume with 1000 full flows. The state-of-the-ar method PrefixRL [7 is implemented with optimal settings. In our results in Fig. 6 each prefix adder is represented by a 2D point based on its delay and area. It shows the significant improvement achieved when our two-level retrieval strategy used in the PrefixRI. method due to efficiency improvements that facilitate exploring expanded sample corpus. Moreover, employing the MCTS method can lead to the discovery of more superior adders because this method effectively navigates through problems with vast state spaces, utilizing information stored during the search process. Overall, our approach can reduce the delay or area of adders by up to 26% and 30%, respectively, compared with PrefixRL, while maintaining the computational amount.
Visualization.
The scores of the first actions after 400 search steps when optimizing the theoretical metrics are visualized as heatmaps in Fig. 7 In selection phase, the action with the highest score is chosen. For example, the first action for the 8-bit adder is to delete the (5. 7) cell with the highest score because this reduces the size of the adder. On the contrary, the action with the lowest score is to add the (4, 7) cell because it augments both size and level.

---

32 adder
PARRIC
16-0it
High
8-bit adder
Mod um
Low
14
64-bit adder
Aerpa PM
Figure 7: Heatmap for first action scores. The actions with the highest and lowest scores marked.
Accuracy of Fast Flow. The time-consuming routing phase is removed in the fast flow of the two-level strategy. To evaluate the impact of this simplification, we tested the simulation accuracy of the fast flow against the full flow. The results in Table indicate that the fast flow can still achieve an utterly accurate area estimation and over 95% accurate delay. Therefore, the fast synthesis flow can help improve efficiency without significantly losing accuracy.
Table 3: Accuracy of fast synthesis flow,
Bits of adders
32
64
128
Delay Acc. (%)
96. 06.11100.86 100.00110.00
1.12 100.00.10.00
95.34.12.60
Area Acc. (%)
100.00110.00
4.2 Multiplier Design
Practical Evaluation. Given the lack of a commonly adopted theoretical metric for multipliers, we practical metrics for evaluation. Our multiplier design utilizes a co-design framework with three iterative search rounds, incorporating 900 steps for the compressor tree and 100 for the prefix tree each round. This yields 3000 steps, consistent with the search steps of other baseline methods in experiments. As shown in Fig. [Jand Appendix Fig. [4] we compared the effectiveness of our method with several baselines, including the human-designer
Wallace multiplier [13], optimization baasd methods including GOMIL [6] and SA [45]. the default multiplier given in the synthesis tool, and the learning-hasse based method RL-MUL. 18]. In our evaluation, we assessed the multipliers' performance by adjusting the expected delay parameter in the synthesis process. Subsequently, the resulting areas of each multiplier different delays depicted
segmented line. Consistent with the RL- MUL [18] assessment approach, each method selects an optimal multiplier for comparison. Results for Wallace (13), GOMIL (16), SA (45), and RL-MUL (18) in 8/16 bits are referenced from the RL-MUL work. RL-MUL method is reproduced and tested in 32/64 bits. The results show that the co- design method, ArithTreeRL, outperforms the synthesis tool's baselines and default multipliers. This is because of the co-design framework, the restructured MultGame, and the improved synthesis flow. It can achieve second-best results even when only optimizing the compressor tree. Compared with the state-of-the-art RI-MUUL method, our method can reduce the delay by up to 33% and the area by 45%. Furthermore, our method can reduce the delay of the default multipliers used in the Yosys tool [37 by up to 16% and the area by 35%. We also report the delays and areas in Table 4 Our method consistently achieves minimal delays for the delay minimization. When optimizing for trade-off (delay 0.00larea), designed by 45mm technology are compatible with the 7nm [40] without any modifications.
approach achieves optimal or comparable results. Also, The multipliers
Efficiency. Due to the time-consuming nature of the full synthesis flow, we developed a synthesis flow that is over 10x faster while maintaining high simulation accuracy for adder design, as discussed in the method. The efficiency is shown in Fig. gh. Additionally, we optimized the logic synthesis and HDL code generation processes in the synthesis flow for multiplier design. According Fig. gb, our improved fast flow can accelerate the process up to 20x.
5 Conclusion
Designing adder and multiplier modules is a fundamental and crucial task in computer science. We first model this task as tree-generation process, conceptualizing it as sequential decision-making

---

Table 4: Numerical comparison of multipliers in delay (ns) and area (um ). (45mm)
Num bits
8-bit
16-bit
32-bit
64-bit
Objective
Method
area
delay
areaa
delay
urea
delay
area
delay
RL-MUL
496
0.7089
2271
1.1330
8767
2.0150
34810
2.6771
PPO w/ raw flow
496
0.6921
2259
1.1277
8788
1.9437
34810
2.6355
Min Delay
Default
535
0.6203
2499
0.8908
10637
1.0745
42128
1.3998
PPO
692
0.5180
2551
0.7392
11329
0.9960
41257
1.2424
39436
RI-MUUL
388
0.7691
1695
1.2666
7033
2.1932
28616
2.889
PPO flow
388
0.7618
1687
1.2268
7036
2.0945
28609
2.8928
Trade-off
Default
367
0.6837
1590
0.9997
6685
1.4170
26871
1.9403
PPO
1.3856
ArechTreeRT
384
0.6420
1566
0.9487
6469
1.3262
26087
1.7038
Methed (raur flowl:
COPEL
ILPUL
Wethed foow::
Delcut
P70 (ou1
Technology
-5em
16-hit multipllrr
32-bit muttipler
6d-bit multiplier
2.70
2.2
3.0
1.4
3.75
2.20
1200
3250
21.0
12:0
2722 2253
27.0
1003
3731 5220 1000 0100 20001 1760
3.30
20200
21000
22000
4.500
33130
Figure 8: Comparison of multipliers. The designs were tested in 45mm and 7nm. Each segmented line represents the performance of one multiplier under different timing constraints. 'Method (our flow)' are methods with our improved flow. The 'Default' multipliers default. 'reeth is our co-design method combining PPO and MCTS, while 'PP (our)" optimizes only the compressor tree. We apply 45nm designs to the 7nm library without modifications, showcasing the transferability.
those generated by the synthesis tool by
Adder design
(b) Multiplier design
full flow fast now (ArithreeRL)
row flow
0.4
now (ArithTreeRL)
Num of bits
11.3
Num
66-
T6.8
0.2
156.77
1.3
25
35
40
20
50
100
120
140
180
Time 155
Time (6)
Figure 9: Design flow time consumption. (average of 1000 runs)
game. Then, we propose reinforcement learning method to solve it, facilitating scalable and efficient search for globally optimal designs. Through extensive experiments, our approach achieves state-of-the-art performance for adders and multipliers in terms of delay and area within the same computational resources. Moreover, we discovered can be applied to more advanced technology processes. This enhancement basic arithmetic modules optimizes hardware performance and size, showing significant potential for boosting computationally intensive fields.
method has demonstrated transfcrability, the designs
Limitations. This paper focuses exclusively on designing and optimizing adder and multiplier modules, which are fundamental components in computational systems. does not explore other basic elements, such as exponentiation or more complex arithmetic units. However, our method is naturally extendable to other arithmetic operations, such as exponentiation. Future research could explore these extensions to unlock further designs across various hardware components.
10

---

Acknowledgments and Disclosure of Funding
We gratefully acknowledge Ronghao Lin of Sun Yat-sen University for his assistance with the introduction video. This paper is partially supported by the National Key R&D Program of China No.2022220161000 and the General Research Fund of Hong Kong No. 17200622 and 17209324.
References
[1] P. Yao, H. Wu, B. Cao, J. Tang. Q. Zhang. W. Zhang, J.J. Yang. and H. Qian, "Fully hardware-impllemened memristor convolutional neural network," Nature, vol. 577, no. 7792, pp. 641-646, 2020.
[2] M. Hasceb and F. Saced, "High performance computing framework for tera-scale database scarch of mass spectrometry data," Nature computational science, vol. no. pp. 550-561,20 2021.
[3] R. Orús, Mugel, and Lizaso, "Quantum computing for finance: Overview and prospects." Reviews in Physics, vol. 4, p. 100028, 2019.
[4] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang. S. Agarwal, K. Slama, A. Ray et al., "Training language models to follow instructions with human feedback," Advances in Neural Information Processing Systems (NeurIPS), vol. 35, pp. 27 730-27 744, 2022.
[5] J. Min, S. Demchyshyn,
Sempionatto, Y. Song, Hailegnaw, C. Xu, Y. Yang, Solomon, C. Putz, L. Lehner et al., "An autonomous wearable biosensor powered by perovskite solar cell," Nature Electronics, pp. 1-12, 2023.
[6] M. T. Bohr and I. A. Young, "Cmos scaling trends and beyond," JEEE Micro, vol. 37, no. 6, pp. 20-29, 2017.
[7] Y. Taur, "Cmos design near the limit of scaling," IBM Journal of Research and Development, vol. 46, no. 2.3, pp. 213-222, 2002.
[8] K. He, Zhang, Ren, and J. Sun, "Deep residual learning for image recognition," " in Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR). IEEE, 2016, pp. 770-778.
[9] D. P. Rodgers, "Improvements in multiprocessor system design." ACM SIGARCH Computer Architecture News, vol. 13, no. 3. pp. 225 231, 1985.
[10] T. Hiramoto, "Five nanometre emos technology," Nature Electronics, vol. 2, no. 12, pp. 537-558, 2019.
[11] S. Salahuddin, K. Ni, and S. Datta, "The era of hyper-scaling in electronics," Nature Electronics, vol. 1, 8. pp. 442-450, 2018.
[12] J. Sklansky, "Conditional-sum addition logic." IEEF Transactions on Flectronic computers, pp. 226-231, 1960.
[13] C. S. Wallace, "A suggestion for a fast multiplier," JEEE Transactions on electronic Computers, pp. 14-17, 1964.
[14] S. Roy, M. Choudhury, R. Puri, and D. Z. Pan, "Towards optimal performance-aree area trade-off in adders by synthesis of parallel prefix structures," in Proceedings of the Annual Design Automation Conference (DAC). ACM/IEEF, 2013, pp. 1-8.
[15] "Twarrs optimal performance-are trade-off in adders by synthesis of parallel prefix structures." " IEEE Transactions on Computer-Aiie Aided Design of Integrated Circuits and Systems (TCAD), vol. 33, no. 10, 1517, 2014.
[16] W. Xiao, W. Qian, and W. Liu, "Gomil: Global optimization of multiplier by integer linear programming," in Design, Automation & Test in Europe Conference & Exhibition (DATE). IEFF, 2021, pp. 374-379.
[17] R. Roy, J. Raiman, N. Kant, Elkin, R. Kirby, M. Siu, Oberman, S. Godil, and B. Catanzaro, "Prefixrl: Optimization of parallel prefix circuits using deep reinforcement leaming," " in Proceedings of the Annual Design Automation Conference (DAC). ACM/IEEE, 2021, pp. 853-858.
[18] D. Zuo, Y. Ouyang, and Y. Ma. "RL-MUL: Multiplier design optimization with deep reinforcement learning." in Proceedings of the Annual Design Automation Conference (DAC). ACM/IEEE, 2023, pp. 1-8.

---

[19] H. Geng. Y. Ma. Q. Xu, J. Miao, S. Roy, and B. Yu, "High-speed adder design space exploration via graph neural processes." " IEEE Transactions on Computer-Aided Design Integrated Circuits and Systems (TCAD), vol. 41, no. 8. pp. 2657-2670, 2021.
[20] Y. Ma. S. Roy, J. Miao, Chen, and B. Yu, "Cross-layer optimization for high speed adders: A pareto driven machine learning approach." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 38, no. 12. pp. 2298-2311,,011
[21] D. Silver, Huang, J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot et al., "Mastering the game of go with deep neural networks and tree search," nature, vol. 529, no. 7587, pp. 484 489, 2016.
[22] S. Palnitkar, Verilog HDL: a guide to digital design and synthesis. vol. 1.
Prentice Hall Professional, 2003,
[23] C. B. Browne, F. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton, "A survey of monte carlo tree search methods," IEEE Transactions on Computational Intelligence and Al in games, vol. 4, no. I, pp. 1 1-43, 2012.
[24] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, "Proximal policy optimization algorithms," arXiv preprint 10X.::/777.063777 2017.
[25] P. M. Kogge and H. S. Stone, "A parallel algorithm for the efficient solution of a general class of recurrence equations," " IEEE Transactions on Computers (TC), vol. 100, no. pp. 786-793, 1973.
[26] R. E. Ladner and M. J. Fischer, "Parallel prefix computation." Journal of the ACM (JACM), vol. 27, no. 4.
pp. 831-838, 1980.
[27] C. H. Roth Jr, L. L. Kinney, and E. B. John, Fundamentals of logic design.
Cengage Learning, 2020.
[28] M. Swiechowski, K. Godlewski, B. Sawicki, and J. Mandziuk, "Monte carlo search: A review of recent modifications and applications," Artificial Intelligence Review, vol. 56, no. 3. pp. 2497-2562, 2023.
[29] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathicu, Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev et al., "Grandmaster level starcraft ii using multi-agent reinforcement learning." " Nature, vol. 575, no. 7782. pp. 350-354, 2019.
[30] A. Fawzi, M. Balog, A. Huang, Hubert, B. Romera-Paredes M. Barekatain, A. Novikov, F, J. R Ruiz, J. Schrittwieser, G. Swirszez et al., "Discovering faster matrix multiplication algorithms with reinforcement learning." Nature, vol. 610, no. 7930, pp. 47-53, 2022. 2022.
[31] L. Koesis and C. Szepesvári, "Bandit based monte-carlo planning," in European conference on machine learning (ECML). Springer, 2006, pp. 282-293.
[32] A. Dedieu and J. Amar, "Deep reinforcement lcarning for 2048," in Conference on Neural Information Processing Systems (NeurIPS), 2017.
[33] F. Murtagh, "Multilayer perceptrons for classification and regression," Neurocomputingg vol. 2, no. 5-6, pp. 183-197, 1991.
[34] C. M. Bishop and N. M. Nasrabadi, Pattern recognition and machine learning. Springer, 2006, vol. 4.
[35] R. Girshick, "Fast r-enn," in Proceedings of the IEEE international conference on computer vision (ICCV). IEEE, 2015, pp. 1440-1448
[36] J. Zhang, Q. Gao, Y. Guo, B. Shi, and G. Luo, "Easymac: design exploration-enabled multiplier- accumulator generator using canonical architectural representation." in Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC) IEEE, 2022, pp. 647-653.
[37] C. Wolf, "Yosys open synthesis suite," 2016.
[38] T. Ajayi and D. Blaauw, "Openroad: Toward self-driving, open-source digital layout implementation tool chain," in Proceedings of Government Microcircuit Applications and Critical Technology Conference, 2019.
[39] I. NanGate, "NanGate FrecPDK45 open cell library," 2008.
[40] L. T. Clark, V. Vashishtha, L. Shifren, A. Gujja, S. Sinha, B. Cline, C. Ramamurthy, and G. Yeric, "ASAP7: A 7-nm FinFET predictive process design kit," Microelectronics Journal vol. 53, 2016.
12

---

[41] M. Snir, "Depth-size trade-off's for parallel prefix computation." Journal of Algorithms, vol. 7, no. 2. pp. 185-201, 1986.
[42] T. Matsunaga and Y. Matsunaga, "Area minimization algorithm for parallel prefix adders under bitwise delay constraints," in Proceedings of the 17th ACM Great Lakes symposium on VLSI, 2007, pp. 435 440.
[43] Brent and Kung. regular layout for parallel adders," " IEEE Transactions on Computers (TC), vol. 100,
no, 3, pp. (60-264, 1982.
[44] P. Behrooz, "Computer arithmetic: Algorithms hardware designs," Oxford University Press, vol. 19,
pp. 512.83-512 585, 2000.
[45] P. Van Laarhoven, E. H. Aarts, P. J. van Laarhoven, and E. H. Aarts, Simulated annealingg 1987.
Springer.
[46] J. K. Ousterhout et al., Tel: An embeddable command language. Computer Science Division, 1989.
University of California, Berkeley,
[47] S. D. Compiler, "Synopsys design compiler," Pages/default. aspx, 2016.
[48] N. H. Weste and D. Harris, CMOS VLSI design: circuits and systems perspective. India, 2015.
Pearson Education
[49] T. Han, D. A. Carlson, and P. Levitan, VLSI DESIGN OF HIGH-SPEED, LOW-AREA ADDITION CIRCUITRY. IEEE, 1987.
[50] Liu, Zhou, Zhu, and C.-K. Cheng, "An algorithmic approach for generic parallel adders," in International Conference on Computer Aided Design (ICCAD). IEEE, 2003, pp. 734-7444
[51] Fishburn, "A depth-decreasing heuristic for combinational logic: or how to convert a ripple-carry adder into a -aory-lookahead adder or anything in-between," in Proceedings of the Annual Design Automation Conference (DAC). ACM/IEEE, 1991, pp. 361-364.
[52] R. Zimmermann, -Nn-iheuiistic optimization and synthesis of varallel-prefis adders," in proc. of IFIP workshop. Citeseer, 1996.
[53] H. Zhu, C.-K. Cheng, and R. Graham, "Constructing zero-deficiency parallel prefix adder of minimum depth," in Proceedings of Asia and South Pacific Design Automation Conference (ASP-DAC), 2005, pp. 083-888.
[54] F. S. Melo, "Convergence of q-learning: simple proof," Institute Of Systems and Robotics, Tech. Rep, pp- 1-4, 2001.
[55] L. Dadda, "Some schemes for parallel multipliers," Alta frequenza, vol. 34, pp. 349-356, 1965.
[56] W. Townsend, E. E. Swartzlander Jr. and A. Abraham, "A comparison of dadda and wallace multiplier delays." in Advanced signal processing algorithms, architectures, and implementations XIII, vol. 5205, SPIE, 2003, pp. 552-560.
[57] D. J. Mankowitz, A. Michi, A. Zhernov, M. Gelmi, M. Selvi, C. Paduraru, E. Leurent, S. Iqbal, J.-B. Lespiau, A. Ahem al., "Faster sorting algorithms discovered using deep reinforcement learning." Nature, vol. 618, no. 7964, pp. 257-263, 2023.
[58] Schrittwieser, Antonoglou, T. Hubert, Simonyan, L. Sifre. S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel el al., "Mastering atari. go, chess and shogi by planning with a learned model." Nature, vol. 588, no. 7839, pp. 604-609, 2020.
[59] Z. Wang, J. Wang, Q. Zhou, B. Li, and H. Li, "Sample-efficient reinforcement learning via conservative model-based actor-critie." in Proceedings of the AAAI Conference Artificial Intelligence (AAAI), vol. 36, 8, 2022, pp. 8612-8620.
[60] M. Hessel, J. Modayil, H. Van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver. "Rainbow: Combining improvements in deep reinforcement learning"" Proceedings of the AAAI conference on artificial intelligence (AAAI), vol. 32, no. 1, 2018.
[61] R. Yang. J. Wang. Z. Geng, M. Ye, Ji, B. Li. and E. Wu, "Learning task-relevant representations for generalization via characteristic functions of reward sequence distributions." in Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining (SIGKDD), 2022, pp. 2242 2252.
13

---

[62] J. Wang, R. Yang. Z. Geng, Z. Shi. M. Ye, Q. Zhou, S. Ji, B. Li, Y. Zhang, and E. Wu. "Generalization in visual reinforcement learning with the reward sequence distribution," arXiv preprint arXiv:230200900. 2023.
[63] Z. Wang, Pan, Q. Zhou, and Wang. "Efficient exploration in resource-resttritted reinforcement learning." in Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), vol. 37, no. 8, 2023, pp. 2029-7
[64] V. Mnih, K. Kavukcuoglu, D. Silver, A, Graves, I. Antonoglon, D. Wierstra, and M. Riedmiller, "Playing atari with deep reinforcement learning," arXiv preprint arXiv:1312.5602 2013.
[65] T. P. Lillicrap. J. Hunt, A. Pritzel, Heess, T. Erez, Y. Tassa, Silver, and D. Wierstra, "Continuous control with deep reinforcement learning," arXiv preprint arXiv:/509002))) 2015.
[66] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, "Policy gradient methods for reinforcement learning with function approximation," Conference on Neural Information Processing Systems (NeurIPS), vol. 12, 1999.
[67] A. Hosny, S. Hashemi, M. Shalan, and S. Reda, "Drills: Deep reinforcement learning for logic synthesis," in 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC) IEEE, 2020, pp. 581-586 586.
[68] K. Zhu, M. Liu, Chen, Z. Zhao, and D. Z. Pan, "Exploring logic optimizations with reinforcement learning and graph convolutional network." in Proceedings of the 2020 ACM/IEEE Workshop on Machine Learning for CAD (MLCAD). 2020, pp. 145-150.
[69] Z. Wang. J. Wang. D. Zuo, J. Yunjie, X. Xia, Y. Ma, H. Jianye, M. Yuan, Y. Zhang, and F. Wu, "A hierarchical adaptive multi-task reinforcement learning framework for multiplier circuit design," in Forty- first International Conference on Machine Learning (ICML), 2024.
[70] Z. Wang, I.. Chen, J. Wang, Y. Bai, Li, X. Li, M. Yuan, H. Jianye, Y. Zhang, and F. Wu, "A circuit domain generalization framework for efficient logic synthesis in chip design." in Forty-first International Conference on Machine Learning (ICML), 2024.
[71] D. Niu, Y. Dong, Z. Jin, C. Z.Zanng Q. Li, and C. Sun, "Ossp-pla: An online stochastic stepping policy for pla reinforcement learning," " IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems (TCAD), 2023.
[72] Z. Jin, H. Pei, Y. Dong, X. Jin, X. Wu, W. W. Xing, a.d Niu, "Accelerating nonlinear circuit simulation with reinforcement learning," in Proceedings of the 59th ACM/IEEE Design Automation Conference (DAC), 2022, pp. 619-624.
[73] A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang. E. Songhori, S. Wang, Y.-. Lec, E. Johnson, O. Pathak. A. Nazi et al., "A graph placement methodology for fast chip design," Nature, vol. 594, no. 7862, pp. 207-212, 2021.
[74] R. Cheng and Yan, "On joint learning for solving placement and routing in chip design," Advances in Neural Information Processing Systems (NeurIPS), vol. 34, pp. 16.08-165513 119,, 2021.
[75] Y. Lai, Y. Mu, and P. Luo, "Maskplace: Fast chip placement via reinforced visual representation learning"" Advances in Neural Information Processing Systems (NeurIPS), vol. 35, pp. 24 24 030, 2022.
[76] Y. Lai, J. Liu, Z. Tang, B. Wang, J. Hao, and Luo, "Chipformer: Transferable chip placement via offline decision transformer," in ICML. PMLR, 2023. pp. 18 346-18364 184..
[77] Y. Shi, K. Xue, L. Song, and C. Qian, "Maero placement by firr-maskk-uidee black-box optimization." " Advances in Neural Information Processing Systems (NeurIPS), 2023.
[78] R. Zhong, J. Ye, 7. Tang, S. Kai, M. Yuan, J. Hao, and J. Yan, "Preroutgnn for timing prediction with order preserving partition: Global circuit pre-training, local delay learning and attentional cell modeling,"" in Proceedings of the AAAI Conference Artificial Intelligence, vol. 38, no. 15, 2024, pp. 17 087-17 095.
[79] Z. Geng, J. Wang, Z. Liu, S. Xu, Z. Tang, M. Yuan, Jianye, Y. Zhang, and F. Wu, "Reinforcement learning within tree search for fast macro placement," in Forty-first International Conference on Machine Learning (JCML), 2024.
[80] Z. Wang, Z. Geng, Z. Tu, J. Wang, Y. Qian. Z. Xu, Z. Liu, S. Xu, Z. Tang, S. Kai et al., "Benchmarking end-to-end performance of bi-based chip placement algorithms," " arXiv preprint arXiv:2407.1 15026, 2024.
14

---

[81] H. Chen, K.-C. Hsu, W. J. Tumee, P.-H. Wei, K. Zhu, D. Z. Pan, and H. Ren. "Reinforcement learning guided detailed routing for custom circuits," in Proceedings of the 2023 International Symposium Physicul Design (ISPD). 2023, pp. 26-34.
[82] T. Qu. Y. Lin, Z. Lu, Y. Su, and Y. Wei, "Asynchronous reinforcement learning framework for net order exploration in detailed routing, in 2021 Design, Automation Test in Europe Conference Exhibition (DATE). JEEE, 2021. pp. 1815-1820.
[83] Du, Wang. Zhong, and Yan, "Hubrouter: Learning global routing via hub generation and pin-hub connection," Advances in Neural Information Processing Systems (NewrIPS), vol. 36, 2024.
[84] S. Beheshti-Shiral A. Vakil, S. Manoj, Savidis, H. Homayoun,
Sasan, reinforced learning solution for clock skew engineering to reduce peak current and ir drop." in Proceedings of the 2021 on Great Lakes Symposium on VLSI, 2021, pp. 181-187.
[85] H. Wang. K. Wang. J. Yang. L. Shen, N. Sun, H.-S. Lee, and Han, "Gen-rl circuit designer: Transferable transistor sizing with graph neural networks and reinforcement learning," in Proceedings of the Annual Design Automation Conference (DAC). ACM/TEEF, 2020, pp. 1-6.
[86] Y.-.. Lu, S. Nath, V. Khandelwal, and S. K. Lim, "RI-sizer: Visi gate sizing for timing optimization using deep reinforeement leamning"" in Proceedings the Annual Design Automation Conference (DAC). ACM/IEEE, 2021, pp. 733- 738.
[87] Z. Shi, M. Li, S. Khan, L. Wang, N. Wang. Y. Huang, and Q Xu, DDeepppi: Test point insertion with deep reinforcement lcarning," in 2022 IEEE International Test Conference (ITC). IEEE, 2022, pp. 194-203.
15

---

Appendix
A
Method Details
A.1 Level Upper Bound
When optimizing adders in theoretical metrics, the search process is stratified based series of incremental level upper bounds, L. The initial bound is set to log2 N and is incrementally raised in subsequent stages. For each new stage, the starting configuration state is the adder design with the minimum size obtained from the previous stage's s search, as illustrated in Fig. T0
soarch
2 search
L=6
N
L=7 size = N
291
190
Figure 10: Level upper bound L for optimizing theoretical metries of adders. The example is for 64-bit adder design. The search is divided into stages, and the level upper bound 7. increases one at time. The initial state for each search is set the best adder found in the last search iteration.
A.2 Two-Level Retrieval
In our two-level retrieval strategy, we implement a fast synthesis flow with minimal loss precision. In the fast flow, we keep all other steps, including logic synthesis, clock tree synthesis, and placement, but remove the most expensive routing step. According to our efficiency test Fig. 9 our fast synthesis flow without the routing step can speed up more than ten times. At the same time, the fast flow can still achieve highly accurate area measurements and 95% accurate delay estimations as detailed in Table 3 Thus, the fast synthesis flow can help search for many adders possible without losing accuracy. At the end of the first stage of two-level retrieval, we use the coordinate (area, delay) the representative points for adders and compute all distances from these points to the Pareto boundary. We sort the distances ascending order and use the K-th distance as the threshold for selecting the adders to the second stage. As shown in Fig, I the K adders with the constitutnnn the top 10% in our efficiency settings-wil
shortest distances to the Pareto be selected for full synthesis execution.
A.3 Synthesis Scripts
The logical and physical synthesis process for Yosys and Open is implemented using the Tel scripting language [46). We provide the complete Tcl scripts used for the logical synthesis in Fig. 12
A.4 Cache, Save, and Recover Design
Our configuration allows the prefix and compressor trees to be easily saved and restored. The prefix tree stored as an upper triangular matrix ANN where cell (i.j) is marked with Aj, it exists: otherwise, A,, = 0 it does not. The compressor tree is represented by variable-length sequence = (ao, 01, 422 .r....,.,11 with each a; E 0, 1. Here, a; represents the addition of a full adder, and 1 signifies the addition of a half adder. In the context of our game modeling, the matrix and the sequence together can completely reconstruct the prefix and compressor trees, respectively. Furthermore, both structures be serialized into strings. These strings are then
16

---

K =8 Selected Unselected
D
Delay
Area
Figure 11: Select adders in two-level retrieval. After the first stage of the two-level retrieval process, each adder is represented by 2D point based on its delay and area. When selecting the top K adders for the second stage, boundary. The K adders with the smallest distances are selected. The threshold distance, denoted as D, is defined by the distance of the K-th adder the Pareto boundary.
them according their distances from these points the Pareto
read -av input.v
aynth -tep main flatten
opt
-censtr ./abe_constr constz -fast -liberty library typical. -D 100 write verilog output.v
set ww..diriinngii. cell BUF X1 load 10.0 [all outputs]
constraint file abc contt
Figure 12: Scripts for logical synthesis.
processed through a hash function to generate fixed-length values that serve as keys in our cache. This cache stores the results of previous syntheses, which helps in avoiding redundant synthesis runs.
A.5 Hyperparameter
Our hyperparameter configuration be found in Table
Table 5: Hyperparameter Configuration
Name
Description
Value
Weight for delay and area in Fig.
0.01 /0/00/00000/00/0
Sum weight in Eq.
0.01
Sum weight in Eq.
10v/
Penalty value for using half adders
0.1
Discount factor in Eq.
0,8
Gradient clip norm in Eq.
0.2
Batch size PPO
64
Replay huffer size for PPO learning rate
6
0.001
0.01 for designing multipliers, 0 (ripple-carry adder initial state) and 0.001 (others) for designing adders, where unit of delay is ns, and the unit of area is pm?.

---

A.6 Input Selection in Compressor Tree
In the compressor tree design, both half and full adders are utilized. When assigning input bits to a full or half adder, we prioritize the bits with minimal estimated delays. For instance, consider the where we are selecting inputs for action ag, and the available input bits have delays {0, O, O, O, 1]. In this situation, the three bits with delay of would be chosen inputs for full adder to minimize the overall delay. The rationale behind this that adders introduce additional delays, and our objective is minimize the maximum delay across all bits. A more nuanced strategy is employed when inputs are fed into full adder: the bit with the highest delay out of the three is connected to the carry input. For example, given input bits with delays {0, 0, 1). the bit with delay of would be connected to the carry input of the full adder. This strategy is adopted because the delay from the carry input to the output bits involves only two logic gates, which is faster than the three logic gates' delay from the addend inputs to the outputs.
A.7 Strategy for Searching Multipliers
In the search process, each multiplier is tested two boundary expected delay parameters (50 and 2 x 10%). The average delay and area are then calculated from the results obtained at these two boundary conditions. The performance score for each multiplier is the weighted sum of the average delay and area. The multiplier with the highest score is selected for final evaluation.
A.8 Module Functionality Verification
Each module undergoes rigorous testing protocol comprising 100 addition or multiplication op- erations to ensure the correctness and reliability of its functionality. For specific test bench details, please refer to our code.
B Supplementary Results
B.1 Adder Design
In addition to Fig. 5 we present some novel designs of the 128-bit adder discovered by our method in Fig. 13 which achieve minimal sizes under the given levels.
As illustrated Fig. 6 we concurrently present the timeline for optimizing key performance metrics in the design of the adder. Our approach ensures sustained efficiency throughout the design process. The primary bottleneck remains the simulation phase.
Table Time cost for Adder Design (hours).
Method
32-bit
64 bit
128-bit
PrefixRL
1.74
4.36
11.62
PrefixRL (two-level retrieval)
1.88
3.79
8.05
ArithTrecRL
1.71
3.68
7.34
B.2 Multiplier Design
The design results of the 8-bit multiplier are reported Fig. 14
B.3 Correlation between Metrics
We investigated the correlation between theoretical and practical metrics to demonstrate the signifi- cance of optimizing theoretical metrics. For 64-bit and 128-bit adders, we sampled 6, 000 instances to assess their theoretical and practical metrics. Our results show a high correlation between two groups of metrics: level with delay and size with area, illustrated Fig. [5] Thus, structures with lower levels and smaller sizes are more likely to result in adders with lower delays and smaller areas.
18

---

128b7, adder, lovel Fize 273
Figure 13: Additional examples of 128-bit adders. More structures of the 128-bit adder first discovered by our method are shown.
multiplier
Vill
0.8
COML
R.VIL
APO con
0.7
Cour flwwd
Delay (ns)
PRO Artitheatt
Technologs:
Area (um²)
Figure 14: Comparison of 8-bit multipliers
64-0n adder deley
66 bit adder area-size
128 adder delay-level level
128-bit bit adder area size
1400
3160
1253
2000
600
100
34.0
Lanvel
Figure 15:
Correlation of theoretical and practical metrics. The fitted lines indicate strong correlations in delay-level and area-size. The data are derived from 6k adders for each.
B.4 Commercial Synthesis Tool Results
In addition to our tests on open-source tools, we also utilized a commercial synthesis tool, Synopsys Design Compiler 2020 47). to demonstrate the generalizability of our approach. presents the results of the multipliers designed by this tool. We did not incorporate timing constraints when testing the delay of the critical path. The technology library used was the Nangate 45nm library [39]. The speed of our designed multiplier still holds a significant advantage, illustrating our design approach's 's broad applicability and substantial potential.
B.5 Design Time
The overall design time is reported in Table 8 and the duration is within an acceptable range for the design process.
19

---

Table 7: Results of commercial synthesis tool. All designs are the best-discovered multipliers with the OpenROAD tool. Corresponding Verilog codes are imput into the Synopsis Design Compiler for synthesis.
Bits in multiplier
8 bit
16 bit
32 bit
64 bit
Method
area (pom)))
delay (ra)
delay (ns)
(Jam²))
delay (18)
(pm)))
delay (rt)
Default
314.1
1.30
1288.5
2.60
5203.2
4.88
20844.3
9.29
RL-MUL
313.9
1.47
1373.6
2.98
5757.3
5.86
23563.6
11.73
416.6
1734.9
3.19
7331.5
29545.7
11.92
ArithTrecLL
465.5
1.20
1866.8
1.76
7555.5
2.34
30134.1
3.17
Table 8: Total design time.
Module
Adder
Multiplier
Bits
32
64
128
Time (h)
1.71
3.68
7.34
0.82
2.26
4.04
27.92
20

---

C Related Work
C.1 Computer Arithmetic
In the quest for high performance and low cost, computer arithmetic design plays crucial role in computer hardware, one of the most fundamental fields in computer science [44]. Issues for study include number representation, arithmetic operations, and real arithmetic. The addition is the most common arithmetic operation and serves as basic unit for many other operations, making it the most studied module. The most basic adder structure is the ripple carry adder, which propagates the carry bit from low to high bits. Due to its serial structure, both the delay and size are ((N) ) for an N-bit addition. The carry look-ahead adder has been proposed to improve the delay by computing the carries for each digit simultancously through an expanded formula. It can achieve Oloog N) delay and ONN log N) size. However, due to the long internal delay of higher-valency gates used in the look-ahead adder 48 various prefix adders have been developed, including the Brent- Brent-Kung (43) Sklansky [2]. Kogge-Stone [25], and Han-Carlson adders [49]. Most of these designs are variations of prefix adders. Although the minimal delay complexity is still Olog N), these adders can often have lower delays than the carry look-ahead adder because they use faster two-input logic gates [48] Additionally, different prefix adders can strike a balance between delay and area, making them more suitable for actual hardware design.
Despite extensive research, human- engineered prefix adders encounter challenges in realizing Pareto- optimal designs. Notably, the dimensions of the Sklansky adder can be further minimized whilst maintaining its operational level, as indicated by Roy et al. [14] Consequently. a plethora of opriizz methodologies have been put forward 42
53 The heuristic algorithm proposed by Roy and colleagues [14] employs bottom-up enumeration tactic, commencing with binary adder and iteratively escalating the bit count inductively based on extant structures. To reconcile the disparity between theoretical and empirical metrics, Ma et al. 220] developed a training regimen for a predictive model to estimate actual metrics from theoretical ones. This model utilizes a Pareto active learning approach to selectively scrutinize adders, which exhibit latent high- perforreff metrics, for empirical validation via synthesis tools. Additionally, Geng et al. [19] have embraced graph neural networks to enhance the precision of the predictive model. However, these methodologies necessitate the pre-selection of a finite set of adders for prediction purposes, representing merely a fraction of the comprehensive feasible space and potentially overlooking superior adder configurations. The foray of reinforcement learning into the domain of adder design was pioneered by Roy et al. integrating novel approach to address design challenges. Nevertheless, the employed Q- network methodology (54) lacks exploration capabilities when applied to expansive problem domains. Moreover, it mandates complete synthesis for each adder design, a prohibitively time-intensive process when attempting to sample a vast array of adder configurations, thereby yielding suboptimal solutions.
In analog to adder design, foundational research on multipliers has also been rooted in manual methodologies. An -biit multiplication fundamentally involves generating N partial products by deploying N AND gates, which correspond to each pair of bits to be multiplied [48] Subsequently, these partial products
accumulated to yield 2N result. The most straightforward strategy employs N successive accumulation operations over N clock cycles, utilizing a serial approach that requires solely one adder and one register. Nevertheless, this method incurs delay of O(N log N) with the employment of logarithmic delay adder 44), indicating a super-linear increase relative to the bit count. To elevate computational efficiency, one may adopt compressor tree structure to compress the partial products concurrently using full and half adders, finalizing the computation with a single 2/- adder. Given that the compressor tree's 's height roughly Olog N). the delay of the multiplier can be refined to Ollog N + log (2N)) = Ollog N). Although Wallace (13) and Dadda trees [55] the predominant compressor trees share a theoretical logarithmic delay, empirical delays vary [6 underscoring the impact of the specific tree structure on multiplier performance. Xiao et al. 16 translated the design of these trees into an integer linear problem, addressed via a combinatorial solver, yet they did not include practical metrics in their model. Zuo et al. [18] pioneered the use of reinforcement learning to refine the multiplier design. Their approach, which modifies the Wallace tree structure rather than constructing anew, narrows the state space due to the finite action sequence length. Moreover, the synthesis process remains laborious, presenting challenges in optimizing multipliers exceeding 16 bits. Furthermore, the technique has not considered the joint optimization of
21

---

the compressor and prefix trees within the multiplier, which poses barrier to identifying globally optimal design.
C.2 Reinforcement Learning
Reinforcement Learning (RL) has surpassed human performance in many domains, including the ancient game of Go 22 the complex strategy game StarCraft [29], optimizing sorting algorithms [57]. and improving matrix multiplication techniques [30. At its heart, RL involves training agents to make series of decisions to achieve a goal, learning from interactions with their environment by trial and error to maximize reward over time. There are two primary categories of RL methods: model- based and model-free free. In model-based RL, agents use an explicit model of the environment to inform their decisions [58 59 Tools like Monte Carlo Tree Search (MCTS) (28), which simulate various future paths to aid decision-making, are often integrated with these methods. This combination has proven particularly potent for tasks requiring a long sequence of decisions. Conversely, model-free RL methods [60H63], such as DQN (64), DDPG [65], and policy gradient approaches [66], operate without explicit model of the environment. A prominent example of model-free RL is Proximal Policy Optimization (PPO) 24. This algorithm iteratively refines the agent's s policy, optimizing a surrogate objective function to balance the need for stable policy updates with the desire for efficient exploration. This leads to high sample efficiency and reduced training times. Choosing the right RL method is crucial, as different tasks may require different approaches. By aligning the strengths of specific RL techniques with the demands of the task at hand, agents can navigate complex decision spaces with remarkable effectiveness.
Recent advancements have shown that reinforcement learning is powerful tool every hardware design phase, because circuit design and testing are fundamentally combinatorial optimization problems. These tasks aim to navigate a vast solution space for the most efficient configuration. Notable examples of prior achievements include logic synthesis [67/770, circuit simulation [71 72)
chip placement [73/80), chip routing [8TH83], clock tree synthesis [84] circuit gate sizing [85] 86).
and hardware testing (87), among others. As such, reinforcement learning's 's widespread success in various Electronic Design Automation (EDA) tasks highlights its remarkable capabilities and adaptability tool for hardware design optimization.
D Societal Impact
The advancements presented in this study have significant implications for various sectors reliant on high-po perforerffrm computing and artificial intelligence. By optimizing the design of adders and multipliers, we can enhance the efficiency and reduce the physical footprint of hardware systems, leading more powerful and compact devices. This can result in faster processing speeds and lower energy consumption, contributing to more sustainable technology practices. However, the societal impact extends beyond just technical improvements. As these optimized designs become more prevalent, they could reduce costs in producing advanced computational hardware, making high-peeformance computing more accessible democratization of technology could spur innovation and accelerate advancements in fields such as medicine, environmental science, and education. Nonetheless, the potential for job displacement in traditional hardware design roles should be considered. and efforts should be made to retrain and upskill workers to adapt to these technological advancements.
wider range of industries and researchers. This
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope?
Answer: [Yes]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include theoretical results.
23

---

All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
24

---

Please see the NeurIPS code and data submission guidelines (https://nips.co http://iidee/ooeeuuuiusisssss///
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //nips https/ccccpclccgccceeeeeeee hta.biiicguiddeesddeeuutbiiiii sww.aiisssiooooiioyo..oo.. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma emror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
25

---

If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp/////nerrpps.ccppcpple/eee/
Answer: [Yes]
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
26

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwppppaittcoooe thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of derived asset (if has changed) should be provided. this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
27

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
28


Reviews:
[{"review_id": "OGHkNqd2GJ", "reviewer": "Reviewer_RWUd", "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.", "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])?\n2. Did the obtained design go through an equivalence-checking process to ensure the functionality correctness? If so, the details should be provided. \n3. 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.", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "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. \n2. Some additional data points in the results might not look reasonable. See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive feedback.\n\n**Weakness 1 [Distinction and Improvement over PrefixRL [17]]**\n\nBoth 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:\n- **Advancement in the RL (state, action, and reward) formulation:**\n    - **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.\n    - **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.\n    - **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.\n- **Advancement in Implementation:**\n   - **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.\n- **Advancement in Task Setting and Method Design:**\n    - **Task Setting**: PrefixRL only addresses adder design, whereas we work on adder and multiplier designs.\n    - **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.\n\n**Weakness 2 [Data Points]**\n\nSee the response in Question 3.\n\n**Question 1 [State Representation]**\n\n**Specific representation of adder and multiplier:**\n- **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.\n- **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.\n\n**Difference with PrefixRL [17]:** \n\nPlease refer to our response in [Weakness 1] for the advantages of our approach over PrefixRL.\n\n**Question 2 [Did the obtained design go through an equivalence-checking process to ensure the functionality correctness?]**\n\nSure, 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. \n\n**Question 3 [Sklansky v.s. Koggle-Stone]**\n\nWe 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.\n\nHowever, 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:\n\n- **Impact by the Interconnection Complexity**: In real-world implementations, the Kogge-Stone adder's structure results in very complex interconnections. \nTypically, 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.\n\n- **Impact by Synthesis Tools**: \nDelay 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.\nTypically, 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.\n\nTo 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. \n\n\n[1] Performance comparison among various parallel prefix adder topologies\n\n[2] PrefixRL: Optimization of parallel prefix circuits using deep reinforcement learning\n\n[3] Implementation of 64 Bit Arithmetic Adders\n\n[4] An Efficient Design and Performance Analysis of Novel 8 Bit Modified Wallace Multiplier Using Sklansky Adder in Comparison with Kogge-Stone Adder (KSA)", "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": "eTu3sGYJsI", "reviewer": "Reviewer_2F2a", "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.", "questions": "Please refer to the weakness.", "limitations": "Authors have adequately addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is in good writing style. Figures are well plotted.\n- The use of reinforcement learning and tree generation games for Adder and Multiplier generation is novel and interesting. \n- 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.\n- 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.\n- 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. \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your constructive comments.\n\n**Weakness 1 [Application in Modern LLM]**\n\n- 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.\n\n- 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.\n\n[1] How Good Are Low-bit Quantized LLAMA3 Models? An Empirical Study \n\n**Weakness 2 [About Floating-Point Data]**\n\n- 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.\n\n- 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.\n\n**Weakness 3 [Significance in Addition and Multiplication. Extension to Other Arithmetic Units]**\n\n- While our current results focus on adders and multipliers, these operations are among the most time-consuming on GPUs, making their optimization highly significant. \n\n- 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.", "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": "bQ5b1gIxlW", "reviewer": "Reviewer_9vo2", "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.", "questions": "1.\tWhy the authors do not test on real industry PDKs?\n2.\tDoes the proposed method have any limitations when applied to real industry PDKs?\n3.\tIn 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?", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper is well-written and logically sound. \n2.\tThe paper explores the application of RL methods to arithmetic circuit design, presenting a unique intersection of interest for RL community and AI chip development. \n3.\tThe 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.\n4.\tThe 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.\n5.\tExperiments 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.\n\nA minor grammatical correction is needed on line 114, where “it derived” should be revised to “it is derived.”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback.\n\n**Weakness 1 [PDK Selection]**\n\nAlthough 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.\n\n**Weakness 2 [Grammatical Error]**\n\nA good catch. We will correct this in our revised version.\n\n**Question 1 [Usage of Industry PDK]**\n\nThe 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.\n\n**Question 2 [Applicability to Real Industry PDKs]**\n\nOur 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.\n\n**Question 3 [Design Number Variability]**\n\nTraditional 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.", "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": "Pn17NHYKR6", "reviewer": "Reviewer_9Uwn", "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.", "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?\n2. Is the objective of Table 7 to minimize delay? Can you present a result with a trade-off objective?\n3. Please provide the definition of accuracy mentioned in Appendix B.6.", "limitations": "Limitations and societal impacts are discussed in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n2. Main concerns are addressed which include the performance of designed adders and multipliers and the time cost of the searching process.\n3. 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.\n2. Some details are missing. For example, it is unclear whether the results shown in Figure 6 are synthesized using Nangate45 technology.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive comments.\n\n**Weakness 1 [Add Detailed Introduction in Main Text]**\n\nThank 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.\n\n**Weakness 2 [Technology Used in Fig. 6]**\n\nThe 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.\n\n**Question 1 [Benefits of Building from Scratch]**\n\nBuilding 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.\n\nAdditionally, 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.\n\n**Question 2 [Objective in Table 7]**\n\nThe 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.\n\n**Question 3 [Accuracy Definition in Table 9]**\n\nAs 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.", "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": "D4G50msb4s", "reviewer": "Reviewer_xS4r", "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.", "questions": "1. Could you provide detailed information on the design flow? Moreover, how are the floorplan and placement parameters set in OpenROAD?\n\n1. Could you elaborate on how your method might be extended or adapted to optimize other hardware units?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Originality:**\n\n1. 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.\n\n1. The introduction of tree-generation games and the application of RL techniques to optimize arithmetic module designs are novel and innovative.\n\n**Quality:**\n\n1. Based on the experimental results, this paper has discovered several optimal 128-bit adder architectures, a noteworthy achievement given the vast search space explored.\n\n1. The experiments are thorough, validated across different technology nodes and using both open-source and commercial tools, confirming the method's effectiveness.\n\n**Clarity:**\n\n1. The paper is well-organized, featuring a clear introduction, detailed methodology, and systematic presentation of results. This structure facilitates understanding the complex concepts introduced.\n\n1. The introduction video is a nice touch and helps in understanding the proposed method.\n\n**Significance:**\n\n1. The authors have made the research open-source and documented most of the experimental details comprehensively, which significantly enhances the reproducibility of the results.\n\n1. 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.\n\n1. 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.\n\nMinors:\n1. I suggest the authors consistently use either the abbreviation 'RL' or the full term 'reinforcement learning' throughout the paper.\n\n1. In Equation 3, $\\sum_{i=0}^{n}$ should be $\\sum_{i=1}^{N}$.\n\n1. Lines 226-227: '... from step 0 to step T' should be '... from step 1 to step T'.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive comments.\n\n**Weakness 1 [Focus on Adders and Multipliers]**\n- While our current results focus on adders and multipliers, these operations are among the most time-consuming on GPUs, making their optimization highly significant. \n\n- 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.\n\n\n**Weakness 2 [Scalability]**\n\nWe 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.\n\n\n**Minors**\n\nThank you for pointing out. We will correct them in the revised version.\n\n**Question 1 [Details about the synthesis]**\n\nWe 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.\n\n**Question 2 [Extension to Other Hardware Units]**\n\nOur method can also be extended to exponentiation units. See Weakness 1.", "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": "FgKmiKet5H", "reviewer": "Reviewer_LxHh", "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.", "questions": "A few question and notes are listed below:\n\nIt 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?\n\nHow one would extend to other arithmetic operations, such as exponentiation?\nSeems 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: \nMa, Yecheng Jason, et al. \"Eureka: Human-level reward design via coding large language models.\" arXiv preprint arXiv:2310.12931 (2023).", "limitations": "The authors adequately addressed the limitations and, if applicable, potential negative societal impact of their work", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strengths of the paper are listed below:\nThe paper introduces an innovative method for designing arithmetic modules that outperforms traditional human design techniques. \n\nThe 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:\n\nthe paper innovation limited to application of RL and Tree Search to a circuit design problem, which are studied in other previous work such as: \nMirhoseini, Azalia, et al. \"A graph placement methodology for fast chip design.\" Nature 594.7862 (2021): 207-212.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your positive comments.\n\n**Weakness 1 [Innovation]**\n\n- 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.\n\n- Moreover, our approach includes several innovations: \n    - 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. \n    - 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. \n    - 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).\n    - Our co-design framework allows simultaneous optimization of prefix and compressor trees, further enhancing the performance of designed multipliers. \n\n**Question 1 [Difference with PrefixRL]**\n\nBoth 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:\n\n- **Advancement in the RL (state, action, and reward) formulation:**\n    - **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.\n    - **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.\n    - **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.\n- **Advancement in Task Setting and Method Design:**\n    - **Task Setting**: PrefixRL only addresses adder design, whereas we work on adder and multiplier designs.\n    - **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.\n\n\n\n**Question 2 [Extend to Exponentiation Operation]**\n\nExponentiation 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.\n\n**Question 3 [Need for Designing Game]**\n\nWe 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.\n\nRegarding 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.", "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:

Meta-review: This submission models Adder and Multiplier design as a single player tree generation problem for RL agents. AddGame supports the prefix tree generation for Adder/Multiplier design and utilizes the Monte Carlo Tree Search RL agent to find the optimal adder. MultGame supports compressor tree generation for Multiplier design and utilizes Proximal Policy Optimization solver to find the optimal multiplier. Optimal adder/multiplier configs are selected based on the delay/area tradeoff each design config. The authors use a synthesis tool, optimized for runtime (skip routing step w/o impact to area/delay estimate), to generate the delay/area metrics using N7 tech PDK. The experiments section compares Adder/Multiplier designs generated by AddGame/MultGame against previous state-of-the-art Adder/Multipliers generated by Manually/via Default Synthesis Recipe/Other Learning based techniques. The comparison data shows superior area/delay designs generated by AddGame/MultGame for a range of bit sizes (8-64 bit Mult, 32-128 bit Add). These results have tremendous practical application as Adder/Multipliers are the primary compute blocks used for computationally intensive benchmarks, AIML and otherwise. 

During the discussion phase reviewers asked several clarification questions related to the RL agent setup, the Synthesis/PnR tool settings, tech node selection and potential applicability of the proposed techniques to HW modules other than Adder/Multipliers. The authors have done a great job of adding detailed responses to all such questions. 

Reviewer RWUd, raised a great question regarding specific datapoints in Figure 6, left chart, showing Sklansky adder with lower delay than Kogge-stone adder. The reviewers provide a convincing explanation of this datapoint highlighting the limitations of HW resources (routing/wire congestion) as the cause of this non-intuitive datapoint. 

The paper is well organized, and the figures and the text explain all key concepts well. I recommend this paper be accepted for NeurIPS.

Edit: Updated my recommendation to spotlight (prev Oral) post discussion with SAC.
Decision: Accept (spotlight)