PaperlayerView exact revision on arXiv

Source-linked AI summary

FABO: Agent-Guided Discovery of Joint Breakpoint Optimization for Timing-Driven Routing Trees

Shang Liu, Wenji Fang, Jing Wang, Hongxin Kong, Yao Lu, Zhiyao Xie

arXiv:2608.30268v1cs.AR

TL;DR

The paper asks whether language-model-guided search can discover a constructive routing algorithm that improves SALT’s wirelength under per-sink stretch constraints. It develops a checked multi-agent search framework that leads to FABO, which jointly selects shared breakpoints across root-to-sink paths. Across 1.29 million nets, FABO lowers average FLUTE-normalized wirelength at every tested tolerance, with peak reductions of 0.83% overall and 2.66% for nets with at least 30 pins.

  • Problem

    The paper asks whether a new constructive algorithm can reduce wirelength beyond SALT while preserving the same per-sink normalized-stretch constraint.

  • Method

    The paper combines parallel language-model exploration with independent checking and develops FABO, which represents legal breakpoints as intervals and jointly selects shared breakpoints.

  • Results

    FABO reduces average FLUTE-normalized wirelength at every setting across 1.29 million nets, with peak reductions of 0.83% overall and 2.66% for nets with at least 30 pins.

  • Takeaways & Limitations

    The results show that coordinating breakpoint choices across paths sharing root-side wire improves wirelength under per-sink stretch budgets, especially for higher-fanout nets.

  • Takeaways & Limitations

    FABO’s candidate ranking, connector construction, support-tree choice, and postprocessing remain heuristics, with complete-tree evaluation as the acceptance rule.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper asks whether language-model-guided search can improve SALT’s wirelength under per-sink stretch constraints, and introduces a checked multi-agent framework that discovers FABO. FABO jointly optimizes shared breakpoints, preserving sink budgets while reducing wirelength across the evaluated benchmark.

  • Motivation: Routing-tree topology affects wirelength, congestion, capacitance, and delay because root-to-sink paths may share or duplicate physical wire.High-fanout nets are especially sensitive because one root-side segment can serve many sinks.
  • Problem and gap: SALT is the state-of-the-art constructive method for minimizing wirelength subject to a hard normalized-stretch bound for every sink.The formulation applies before detailed resistance, capacitance, or sign-off timing is available.
  • Approach: The framework uses parallel hypothesis generation and independent checking across hypotheses, specifications, implementations, and evaluation outputs.Eight Hypothesis Agents explore alternatives, while a Critic and three Programmer–Verifier chains check them before evidence is reused.
  • Discovered bottleneck: SALT repairs one sink path at a time and never jointly selects breakpoints for paths sharing root-side wire, potentially splitting them early and duplicating wire.The missed joint decision becomes more important as fanout increases.
  • FABO: FABO changes the decision unit from individual sinks to groups of paths sharing root-side wire, selecting shared points from overlapping feasible breakpoint intervals.This preserves every sink’s path budget while making group-level wirelength savings explicit.
  • Results: Across 1.29 million ICCAD15 nets and 20 SALT tolerances, FABO reduces average FLUTE-normalized wirelength at every setting, peaking at 0.83% overall and 2.66% for nets with at least 30 pins.FABO-FAST identifies and optimizes most substantially improvable nets at 1.3× SALT’s runtime.

II. PROBLEM FORMULATION

The paper formulates rectilinear shallow-light routing as constructing a rooted Steiner tree that minimizes wirelength while bounding each root-to-sink path’s normalized detour. Stretch tolerance controls the trade-off between shortest paths and lower-wirelength topologies.

  • Problem definition: The input is a root pin and sink set on the Manhattan plane, and feasible solutions are rooted rectilinear Steiner trees spanning all pins.Steiner points may be introduced while pin coordinates remain fixed.
  • Path constraint: Shallowness is the largest normalized root-to-sink tree-path length relative to the corresponding Manhattan distance.The tree-path distance is measured along the unique route from the root to each sink.
  • Objective and metric: Wirelength is the exact geometric-union length of the tree, with coincident segments counted once, and is reported normalized to the corresponding FLUTE tree.This normalization compares each routing tree against the same net’s FLUTE construction.
  • Reported metrics: The normalized-delay metric γ(T) is reported experimentally but is not an optimization constraint.The optimization is governed by path-stretch budgets and wirelength.
  • Stretch schedule: Stretch tolerance ϵ specifies the allowed multiplicative detour beyond a Manhattan-shortest path through a per-sink path budget.At ϵ = 0, every root-to-sink path must be Manhattan-shortest; increasing ϵ relaxes the constraint toward minimum-wirelength trees.

III. AGENT-GUIDED ALGORITHM-DISCOVERY FRAMEWORK

The framework addresses serial search’s path dependence and error propagation by generating alternatives in parallel and independently checking each stage. Verified implementations and valid complete trees supply the evidence used in later search rounds.

  • Motivation: A serial agent can remain on one reasoning trajectory and propagate errors across hypothesis, specification, implementation, verification, and evaluation stages.This can cause later iterations to refine one construction rather than explore fundamentally different structures.
  • Generation and criticism: Eight isolated Hypothesis Agents propose structural mechanisms from shared verified evidence, and a Critic converts the strongest directions into three specifications.Isolation is intended to produce several search directions rather than repeated refinements of one draft.
  • Search-round state: The SSOT records verified conclusions and links them to code and evaluation artifacts for use in the next search round.The workflow also uses a Web Search Agent to retrieve mathematical tools for unresolved structural questions.
  • Implementation verification: Three Programmer–Verifier chains implement and independently check the specifications in parallel.The framework separates implementation checking from algorithmic evidence.
  • Evaluation and evidence: A fixed Evaluator checks complete routing trees, verifies every root-to-sink path budget, and measures exact wirelength before results enter the SSOT.This establishes code-spec conformance, output validity, and objective improvement as separate checks.

B. How Results Update the Next Round

The search process converts failed candidate results into a focus on shared root-side structure, then operationalizes that focus through FABO’s flow-level breakpoint representation. FABO evaluates sharing and budget feasibility jointly before accepting a complete tree.

  • Evidence classification: The framework classifies runs as implementation failures, construction failures, or verified negative results, and compares algorithms only on valid-tree evaluator measurements.The SSOT stores each result label with code, build, output, metric, and verification artifacts.
  • Updating the search: Two candidate families produced no gain on targeted nets, shifting the next search round from local attachment changes to shared root-side structure.The resulting formulation led to flow-level breakpoint optimization.
  • Flow-aware objective: FABO treats each root-to-sink path as a flow and counts an edge’s length once regardless of how many flows use it.Wirelength therefore reflects total path length minus sharing.
  • Breakpoint intervals: For each over-budget flow, FABO represents legal breakpoint positions as a contiguous interval where a new shortest root connection remains within the sink’s path budget.The breakpoint keeps the suffix to the sink and replaces the abandoned root-side prefix.
  • Joint sharing: A shared breakpoint in overlapping intervals can reroute multiple flows, but an old trunk is released only after all flows using it have left.This all-or-nothing accounting makes support-wire savings flow-aware.
  • Algorithm pipeline: FABO computes intervals, selects shared breakpoint covers, ranks deeper candidates by released support wire, and accepts only complete trees that satisfy every budget and improve the incumbent.The running example contrasts SALT’s private repair with FABO’s boundary selection, joint rewiring, and final validation.

A. From Sink-Local Repair to Shared Breakpoints

SALT repairs violating sink paths independently, which can leave shared root-side wire split around one sink. FABO instead moves the shared trunk jointly while preserving all per-sink budgets, reducing wirelength in the recorded example.

  • SALT’s sink-local repair: SALT repairs each violating sink by connecting its breakpoint to the root through new shortest wire.The repair keeps the breakpoint-to-sink support wire and is followed by fixed postprocessing.
  • FABO’s shared repair: 10.85%: FABO reduces wirelength from 1,042,970 to 929,794 under the same budgets.The example uses superblue18 net 323 with eight pins and ϵ = 0.1125.
  • SALT’s sink-local repair: SALT’s final tree has wirelength 1,042,970 at maximum stretch α = 1.000.Postprocessing rebuilds the trunk straight down t2’s column.
  • FABO’s shared repair: FABO rewires all seven flows onto a trunk closer to the other sinks, spending t2’s permitted detour without lengthening other paths.The coordinated move saves more wire through sharing than the additional path length it introduces.

B. Feasible Breakpoint Intervals

FABO models each sink’s budget-feasible breakpoint choices as a contiguous suffix interval on its support path. It then covers these intervals with shared breakpoint choices, starting from a minimum feasible cover.

  • Feasible breakpoint intervals: A breakpoint x is feasible for sink t when ϕt(x) = dM(r, x) + st(x) ≤ Bt.This criterion is safe because coincident wire merges can only shorten the realized tree path.
  • Feasible breakpoint intervals: Each sink’s feasible breakpoints form one nonempty suffix interval It = T 0[ft, t].If the whole support path is feasible, ft = r; an interior boundary can be inserted without changing geometry or wirelength.
  • Examples: Figure 6 compares FLUTE support, SALT before and after postprocessing, and FABO across eight high-degree examples.Edge colors encode the number of root-to-sink paths sharing each edge, and each row reports FABO’s reduction relative to final SALT.
  • Shared breakpoint selection: A shared breakpoint can serve every flow whose interval contains it, allowing those flows to share root-side wire before separating.FABO assigns each sink the deepest selected point in its interval and preserves the suffix afterward.
  • Shared breakpoint selection: FABO initializes a feasible breakpoint set greedily by processing proper intervals in nonincreasing support depth and adding uncovered boundaries.The root is then added to cover remaining intervals.
  • Shared breakpoint selection: The greedy boundaries form a minimum-size set intersecting every interval with ft ≠ r.This minimum cover is only a guaranteed-feasible starting point, not necessarily the wirelength optimum.

D. Flow-Aware Refinement

FABO refines breakpoint sets by evaluating how candidate moves release shared support wire. Its gain is computed per physical edge so shared edges are not counted multiple times.

  • Candidate refinement: FABO proposes one deeper feasible breakpoint at a time and reassigns every sink using the deepest-point rule.The proposal is evaluated under the resulting complete reassignment.
  • Edge-level accounting: FABO measures a proposal by the support wire it frees rather than by summing shortened suffixes across flows.Summing flow reductions would count shared edges repeatedly.
  • Edge-level accounting: An edge is released exactly when every flow that used it leaves under the proposal.The edge-user and leaving-flow sets provide the exact release condition.
  • Edge-level accounting: The gain G(a) sums the lengths of retained support edges whose user sets are fully covered by leaving flows.Here ℓ(e) denotes the length of support edge e.
  • Example: In the recorded example, FABO moves all seven flows to a new spine, releasing the entire old trunk, whereas SALT releases only 126,540 of 804,065 support wire.The edge-level gain ranks candidates; complete-tree evaluation decides acceptance.

E. Complete-Tree Construction and Acceptance

FABO realizes selected breakpoints with a rectilinear connector, grafts retained suffixes into a rooted tree, and evaluates complete valid candidates. Feasibility is preserved when each assigned breakpoint is budget-feasible and the connector satisfies the required bound.

  • Complete-tree construction: FABO builds a rectilinear connector spanning the root and selected breakpoints at their Manhattan distances from the root.Retained suffixes are grafted under their breakpoints and redundant Steiner nodes are removed.
  • Feasibility: If every sink receives a feasible breakpoint and realization preserves suffixes in a valid tree, the realized tree satisfies every budget.The realized root-to-sink path is no longer than the connector path followed by the retained suffix.
  • Realization and postprocessing: FULLREALIZE and FASTREALIZE construct connectors differently, but both satisfy the connector bound and are rechecked by the evaluator.The better valid raw or postprocessed form is returned.
  • Acceptance: Acceptance requires a connected, acyclic rooted tree containing every pin, satisfying every budget, and minimizing exact wirelength among valid trees.Maximum stretch α breaks a wirelength tie.
  • Acceptance: FABO’s Figure 5 acceptance moves the other six flows onto the resulting spine and deletes the old trunk after budget validation.The selection, construction, and consolidation roles are shown as separate steps.

F. FABO Candidate Search

FABO uses a two-stage search that first constructs a valid tree from feasible breakpoint intervals, then refines it with bounded, flow-aware proposals accepted only when they improve the realized tree.

  • Two-stage search: Stage one computes feasible breakpoint intervals, builds a minimum cover, realizes it, and produces a valid tree.Theorem 2 guarantees the stage-one budgets, and the evaluator confirms them.
  • Two-stage search: Each refinement round fast-realizes and validates leading proposals, committing only a valid proposal that improves the current scan tree.The search stops when no valid proposal improves the current tree.
  • Two-stage search: Stage two forms a bounded pool of deeper breakpoints and ranks proposals with a fixed score dominated by flow-aware gain.The score also rewards reassigned-flow depth and discounts proposals far from selected points.

G. Guarantees and Scope

FABO’s guarantees cover feasible construction and evaluator-based acceptance, while its search components remain heuristic; experiments compare it with SALT on a released ICCAD15 benchmark across tolerances and fanout ranges.

  • Guarantees: FABO’s evaluator rejects incomplete or budget-violating trees, and incumbent updates accept only valid candidates improving (WL, α) under ≺lex.The validated stage-one tree initializes the incumbent, ensuring the returned tree is no worse than that baseline.
  • Scope: The minimum cover minimizes only the number of initial non-root breakpoints and does not guarantee minimum final wirelength.Candidate ranking, connector construction, support-tree choice, and postprocessing remain heuristic; complete-tree evaluation is the acceptance rule.
  • Empirical scope: FABO dominates SALT across all 20 stretch tolerances in full-benchmark means, with reductions also reported by pin-count range.Figure 7 compares full-benchmark means and wirelength reductions across tolerances, including fanout-stratified results.
  • Empirical scope: FABO dominates SALT in every pin-count range, with a wider gap at higher fanout.Figure 8 averages shallowness α and normalized wirelength β for each method, tolerance, and labeled pin-count range.
  • Benchmark scope: The released ICCAD15 benchmark contains 1,294,541 nets with at least three pins from eight designs and excludes 2-pin nets.The benchmark differs from counts reported in the SALT paper, but both methods use the same released files and evaluator.
  • Metrics: At fixed ϵ, FABO and SALT satisfy the same per-sink path limit, while β measures total tree wirelength normalized by FLUTE wirelength.Lower mean wirelength therefore compares routing cost under the same feasibility constraint.

B. FABO Dominates SALT at Every Constraint

FABO outperforms SALT across all 20 stretch-tolerance settings, with larger wirelength gains on high-fanout and low-sharing nets. FABO-FAST recovers most high-gain opportunities under a 1.3× SALT runtime budget.

  • FABO has lower mean FLUTE-normalized wirelength than postprocessed SALT at all 20 stretch-tolerance settings.The largest full-benchmark reduction is 0.83% at ϵ = 0.1125, where means are 1.0312 for SALT and 1.0227 for FABO.
  • FABO dominates SALT at every operating point without increasing mean path stretch or delay.FABO reaches β < 1.001 at α = 1.2062 versus SALT at α = 1.2298, and at γ = 1.5235 versus 1.5340 on the delay frontier.
  • FABO’s maximum wirelength reduction grows with fanout, reaching 2.66% for nets with at least 30 pins.The corresponding maxima are 0.31% for 3–9 pins, 1.70% for 10–19, and 2.15% for 20–29 pins.
  • FABO retains more shared root-connected trunk wire than SALT across every shown ϵ and ρ pair.At ϵ = 0.1125 and ρ = 50%, the mean shared-trunk fraction is 49.38% for FABO versus 48.74% for SALT.
  • FABO-FAST uses SALT on every net, predicts expected FABO gain, and runs FABO selectively until the runtime budget is reached.Unselected nets retain their SALT trees, while selected nets keep the shorter feasible result.
  • FABO-FAST recovers 99.0%–100% of nets with at least 25% gain at b = 1.3.Recovery declines for smaller-gain groups, reaching 21.0%–45.3% for the 5%–10% group.

VI. CONCLUSION

An agent-guided framework combining parallel exploration with independent checking discovered a limitation in SALT’s sink-by-sink repair. This led to FABO, which improves wirelength across the benchmark, while FABO-FAST makes high-gain improvements practical within 1.3× SALT’s runtime.

  • The framework combines parallel language-model exploration with independent checking to discover and validate routing-tree algorithms.
  • SALT’s sink-by-sink repair cannot coordinate breakpoints across paths sharing root-side wire, causing premature splitting and duplicated wire.
  • FABO represents feasible breakpoint choices as intervals and jointly selects shared breakpoints while preserving every sink’s stretch budget.
  • FABO reduces average FLUTE-normalized wirelength at every setting, with peak reductions of 0.83% overall and 2.66% for nets with at least 30 pins.
  • FABO-FAST identifies and optimizes most high-gain nets within 1.3× SALT’s runtime.
Loading 2608.30268v1…