Research map / Architectures and efficiency / RNNs and normalization
Scalable and Effective Arithmetic Tree Generation for Adder and Multiplier Designs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Casts adder and multiplier design as single-player tree generation games, using MCTS for prefix trees and PPO for compressor trees to find lower-delay, smaller-area arithmetic circuits.
Problem
Designing fast and small adders and multipliers is hard because the design space of prefix and compressor trees is huge, and prior human, optimization, and learning-based methods get stuck in local optima or ignore joint optimization of components.
Approach
Model prefix-tree editing as a single-player game (AddGame) solved with an MCTS agent, and compressor-tree construction as a game (MultGame) solved with a PPO agent, co-optimized in alternating rounds, plus a two-level fast/full synthesis retrieval and a faster synthesis flow.
Key results
- Adder designs reduce delay and area by up to 26% and 30% versus PrefixRL, and discover a 128-bit adder with 10 levels and size 244.
- Multipliers with PPO+MCTS improve speed by up to 49% and reduce area by up to 45% compared with RL-MUL.
- Discovered 45nm multipliers transfer to the 7nm ASAP7 library without modification.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Co-design the compressor tree with an optimized prefix tree instead of optimizing only the compressor tree (ablation) | Multiplier design · 8/16/32/64-bit multipliers, Min Delay | delay: 0.5180 -> 0.4905; 0.7392 -> 0.7138; 0.9960 -> 0.9685; 1.2424 -> 1.2401 | Helped |
| Co-design the compressor tree with an optimized prefix tree instead of optimizing only the compressor tree (ablation) | Multiplier design · 8/16/32/64-bit multipliers, Trade-off | delay: 0.6558 -> 0.6420; 1.0135 -> 0.9487; 1.3856 -> 1.3262; 1.7941 -> 1.7038 | Helped |
| Use PPO+MCTS co-design instead of PPO compressor-tree-only optimization (ablation) | Multiplier design · 8/16/32/64-bit multipliers, Trade-off | area: 377 -> 384; 1568 -> 1566; 6581 -> 6469; 26088 -> 26087 | Mixed |
| Apply the proposed multiplier co-design method rather than RL-MUL | Multiplier design · Multipliers | delay: up to 33% | Helped |
| Apply the proposed multiplier co-design method rather than RL-MUL | Multiplier design · Multipliers | area: 45% | Helped |
| Use MCTS to search prefix adder trees instead of PrefixRL | Adder design · Adders | delay: up to 26% | Helped |
| Use MCTS to search prefix adder trees instead of PrefixRL | Adder design · Adders | area: up to 30% | Helped |
| Use the two-level retrieval strategy instead of raw PrefixRL retrieval (ablation) | PrefixRL adder search · Adder delay and area | design quality | Helped |
| Use the improved multiplier synthesis flow instead of the raw flow (ablation) | Multiplier reward computation · Multiplier synthesis | speedup: 10x | Helped |
Surprising findings
- Adding cells does not improve theoretical adder metrics, so pruning restricts modifications to deletions in theoretical optimization.
- PPO optimizing only the compressor tree (PPO) achieves second-best results, and some fast-flow results are comparable to the default Yosys multiplier in area.
Limitations
- Fast synthesis flow omits routing and gives only about 95% delay accuracy.
- Multiplier search time grows substantially at 64 bits (about 28 hours).
Experimental setup
Benchmarks: Nangate45 ASAP7
Metrics: delay area level size
Baselines: PrefixRL RL-MUL Sklansky adder Brent-Kung adder Kogge-Stone adder Wallace multiplier GOMIL SA Default Yosys multiplier
Builds on: PrefixRL RL-MUL Proximal Policy Optimization Monte Carlo Tree Search UCT
Closest papers by meaning
- A Hierarchical Adaptive Multi-Task Reinforcement Learning Framework for Multiplier Circuit Design (ICML 2024 · similarity 0.83)
- GPU-Accelerated Synthesis of Mixed-Boolean Arithmetic: Beyond Caching (NeurIPS 2026 · similarity 0.82)
- Reinforcement Learning within Tree Search for Fast Macro Placement (ICML 2024 · similarity 0.82)
- QiMeng-GEMM: Automatically Generating High-Performance Matrix Multiplication Code by Exploiting Large Language Models (AAAI 2025 · similarity 0.82)
- Retrieval-Guided Reinforcement Learning for Boolean Circuit Minimization (ICLR 2024 · similarity 0.81)
- Transformers Can Do Arithmetic with the Right Embeddings (NeurIPS 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.