FABO: Agent-Guided Discovery of Joint Breakpoint Optimization for Timing-Driven Routing Trees
2026-08-31 • Hardware Architecture
Hardware Architecture
AI summaryⓘ
The authors study a problem in designing routing trees that connect many points with minimal wire length while keeping the paths efficient. They investigate whether using language-model-guided search can lead to better algorithms than the current best one, called SALT. Their approach finds a key weakness in SALT: it fixes routes one at a time instead of considering shared parts together, which can cause extra wire usage. Based on this insight, the authors develop a new method called FABO that improves wire sharing and reduces wire length across many test cases while keeping runtimes reasonable.
routing treewirelengthpath stretchmulti-pin netSALT algorithmlanguage-model-guided searchbreakpoint optimizationFLUTEICCAD15 benchmarkcongestion
Authors
Shang Liu, Wenji Fang, Jing Wang, Hongxin Kong, Yao Lu, Zhiyao Xie
Abstract
The topology of a routing tree determines how a multi-pin net branches and shares physical wire, directly affecting wirelength, congestion, capacitance, and delay. We study a central early-stage routing problem: minimizing wirelength while bounding the root-to-sink path stretch for every sink. SALT is the state-of-the-art constructive algorithm for this problem. We ask whether language-model-guided search can discover a constructive algorithm that improves on SALT. To make this search reliable, we develop an agent framework that combines parallel exploration with independent checking. Applied to SALT, the framework discovers a structural limitation: SALT repairs one sink path at a time and therefore never jointly decides where paths sharing root-side wire should split. This sink-local choice can split the paths too early and duplicate wire. This discovery leads to Flow-Aware Breakpoint Optimization (FABO), which jointly optimizes breakpoints across root-to-sink paths that share wire while preserving every sink's stretch budget. Across 1.29 million ICCAD15 nets and SALT's 20-point stretch-tolerance schedule, FABO reduces average FLUTE-normalized wirelength at every setting, with peak same reductions of 0.83% overall and 2.66% for nets with at least 30 pins. With 1.3x SALT's runtime, FABO-FAST identifies and optimizes most nets for which FABO provides a substantial wirelength reduction. Code is available at https://github.com/DevinShang/routing-FABO.