Structure & Discovery / NeurIPS Workshop 2022

The Circuit Board a Routing Algorithm Knows It Can Solve

ReSPack builds synthetic wiring problems around feasible routes, then tests how often existing solvers can rediscover a route as rules get tighter.

ReSPack: A Large-Scale Rectilinear Steiner Tree Packing Data Generator and Benchmark

Kanghoon Lee, Youngjoon Park, Han-Seul Jeong, Sunghoon Hong, Deunsol Yoon, Sungryull Sohn, Minu Kim, Hanbum Ko, Moontae Lee, Honglak Lee, Kyunghoon Kim, Euihyuk Kim, Seonggeon Cho, Jaesang Min, Woohyung Lim

Overview

On a circuit board, every group of related pins needs a path, and routing one group may block the next. A routing algorithm can fail because its search strategy got stuck or because the board cannot be routed at all. ReSPack takes away that ambiguity in a synthetic benchmark by constructing a valid routing when it creates each instance.

Key Findings

A wire can find the right pin and still ruin the board

Imagine routing a circuit board one connection at a time. A short first route can cut off a path another pin group will need. Moving to a second layer may help, until a keep-out region or spacing rule makes that route impossible too. A useful benchmark needs cases that expose these conflicts and a way to tell that each case has a valid solution. ReSPack starts from that last requirement and generates both the problem and a feasible route.

Figure 1 places a routing example from a printed circuit board alongside an instance generated by ReSPack.
Figure 1 places a routing example from a printed circuit board alongside an instance generated by ReSPack.

Draw a feasible route, then hand over the pins

Each group of pins needs a tree that follows a rectangular grid. Intermediate grid points let several routes within a group share branches. The tree edges SiS_i span the terminals in group ii. Writing V(Si)V(S_i) for the vertices used by a tree, the benchmark minimizes total wire length while enforcing that the different nets use disjoint vertices.

min⁡S1,…,SK ∑i=1K∑e∈SiC(e),∑i=1K1{v∈V(Si)}≤1(v∈V).\min_{S_1,\ldots,S_K}\ \sum_{i=1}^K\sum_{e\in S_i}C(e), \qquad \sum_{i=1}^K\mathbf 1\{v\in V(S_i)\}\leq 1\quad(v\in V).

The benchmark sets C(e)=1C(e)=1 for every edge. ReSPack builds the trees sequentially, sampling how many terminals to use and drawing candidates from the largest connected component that remains available. Each tree must pass the constraint checks before it is saved. The released challenge contains the terminal groups. The routes built along the way supply feasible references. Problem definition and generator, Sections 2–3

The three drawings in Figure 2 show why independently connecting each pin group can give an infeasible packing.
The three drawings in Figure 2 show why independently connecting each pin group can give an infeasible packing.

The layout is only the first rule

The generator can reserve areas where wires cannot run, enforce spacing between different wires, and cap the path length between any two terminals in the same tree. A keep-out region and spacing rule reduce the grid available to later trees. The generator tests length after constructing a tree. These checks make it possible to vary the difficulty of the rules without losing the assurance that a released case has a feasible reference.

Figure 3 shows a prohibited area, a spacing requirement, and a modified route that satisfies the wire-length constraint.
Figure 3 shows a prohibited area, a spacing requirement, and a modified route that satisfies the wire-length constraint.

The fixed benchmark has two layers and eight grid sizes, from 8 × 8 to 1,024 × 1,024. It offers 100 instances per grid size and constraint setting. A solver faces three sets of rules at each size. It can solve the basic packing problem, work around prohibited areas, or meet all three constraints together.

Selected grid sizeTreesMean terminals with all three rulesReference edge density with all three rules
8 × 8410.816.6%
32 × 321664.111.5%
256 × 256128512.19.7%
1,024 × 1,0245122,603.410.7%

The density in Table 1 is the fraction of grid edges used by the generator's reference solution. At the largest scale, the solver still has to route more than 2,600 terminals on average. Benchmark sizes, Table 1

Ask how often a solver finishes and how short its routes are

The authors test an exact mixed-integer solver, sequential heuristics, and methods that account for congestion. On the two-layer 32 × 32 benchmark, Table 2 reports the following mean success rates.

MethodBasic packingAll three additional rules
Sequential-159.0%2.6%
PathFinder-1100.0%0.8%
RankingCost-MT100.0%8.0%

Success asks whether the solver found a valid route. For successful solutions, the reported percentage cost gap is

Gap(%)=100(CsolverCreference−1).\mathrm{Gap}(\%)=100\left(\frac{C_{\mathrm{solver}}}{C_{\mathrm{reference}}}-1\right).

The reference is the route created by the generator. A negative gap means a shorter route than that reference. The exact solver is omitted from the combined-constraint experiments because the formulation would require substantial changes. The tested methods ran out of attempts or time without finding any feasible solutions on the extra-large cases, even though the generator supplied valid routes. Evaluation results, Table 2 and Section 4.3

Questions & Answers

The opening answers are simulated author responses based on the paper.

Q: Why can the baseline beat the supplied route?

A: The generated route proves feasibility. It comes from a heuristic and can be longer than a route found later.

Q: What does the largest grid tell us?

A: The benchmark includes grids up to 1024 × 1024 with two layers. The paper omits extra-large results because its baselines failed to find feasible solutions at that scale.

Q: Can a solver with cheaper routes be the worse choice overall?

A: Yes. Route cost is only observable for the boards the solver actually completes. In the 32 × 32 experiments, PathFinder-1 goes from full success to under 1% when the added constraints apply. SCIP is omitted in the setting with all three constraints, so the supplied feasible route is a cost reference there. Cost, feasibility, and runtime together show how much routing work the solver gets done.

Future Ideas

Train a router to spot the order that causes a dead end

Use ReSPack to generate layouts where a small change in net order separates a routable attempt from a failed one. Train a model to choose a net to reroute based on the layout after a congestion deadlock. Build a deterministic checker for all spacing and path-length constraints. Compare against PathFinder and the learned net-ordering baseline at equal runtime on held-out generator configurations and separately on real design layouts. Measure complete valid routings, wire length, and time spent rerouting.

Include RankingCost-MT, which already learns a net ordering, as a comparison. A held-out set of actual layouts can test whether the learned rerouting rule transfers beyond the generator.

Sources