PaperlayerView exact revision on arXiv

Source-linked AI summary

Whole-Route Planning of a Memory Bus Between Two BGAs: An Exact Model of Crossings and Layer Changes, Negotiated to DRC-Clean Copper

Andrew Haas

arXiv:2610.35601v1cs.AR

TL;DR

Bus routing between processor and DRAM BGAs remains largely manual, while prior algorithms optimize proxies such as crossings or layer counts. This paper plans crossings, their order, and layer changes jointly, then negotiates the plan into audited copper. It completes the evaluated bus ladders and reports fewer vias and less copper than the human layouts.

  • Problem

    Bus routing between processor and DRAM BGAs remains largely manual, and published methods optimize proxies such as crossing or layer counts rather than demonstrating clean copper and comparison with designer via counts.

    Source: §I · p. 1

  • Method

    An exact constraint-programming model jointly chooses crossing positions and order and lane layer changes, then geometry placement, cuts, snapping, and router-rule audits negotiate the plan toward copper.

    Source: §I · p. 1

  • Results

    Every rung of both evaluated ladders routes all nets connected and DRC-clean with no more vias and less copper than the human layouts; the router also completes 45 Zynq-board nets with 70 vias versus the designer’s 105.

    Source: B. Against the human · p. 7, §IX · p. 10

  • Takeaways & Limitations

    The whole-route approach can carry a planned bus into production-router-clean copper, including a complete real DDR3 bus and 43 nets of another bus.

    Source: §IX · p. 10

    The route does not match lengths, and optimality is relative to the model and fixed ends; the escape-end search uses an estimate that is exact only in parts.

    Source: §VIII · p. 9

Abstract

from arXiv · show

Routing the bus between a processor and its DRAM remains largely manual in printed circuit board (PCB) design, and published algorithms optimize proxies such as crossing or layer counts. We present a router that plans every lane of a two-layer BGA-to-BGA bus before any copper is laid, and carries the plan to design-rule-clean copper. Its core is an exact constraint-programming model that chooses, for all lanes at once, where each necessary crossing occurs, in what order -- by a rule over every triple of lanes -- and where each lane changes layer, with via room; for the ends it is given, it proves its plan optimal within the model. The model reads naturally as physics: worldlines, frustrated Ising spins and contact forces. A linear program places the lanes in millimeters; the constraints it must violate return to the model as cuts, and audit findings as negotiated congestion prices, until the plan passes an audit against the production router's rules or lays clean. The escapes are chosen by an estimate of the same objective, and differential pairs carry their polarity, with an automatic via crossover where the ends disagree. On an Allwinner H3 and a Zynq-7020, each to a DDR3 device, the router completes every rung of two ladders, of up to 51 nets on the H3 (its whole bus) and 43 on the Zynq, connected and DRC-clean, never with more vias than the human designer (80 against 88 and 62 against 100 at the top rungs) and always with less copper, where the toolkit's production router leaves nets open on four of the ten rungs and Freerouting completes none. On the Zynq board itself it completes 45 of the bus's nets with 70 vias to the designer's 105. On generated buses of three, four and six routing layers every run completes, and every one with a known optimum attains it.

I. INTRODUCTION

The paper addresses the gap between staged bus-planning proxies and a complete, physically realizable route. It jointly plans crossings and layer changes, then negotiates the plan with board geometry and router-rule audits.

I. INTRODUCTION

  • The router jointly chooses all crossing positions and their order, plus every lane’s layer changes, and proves optimality for the ends it is given.Its triple rule admits exactly the crossing orders realizable by a wiring diagram of the lane permutation.Source: §I · p. 1
  • It carries plans into board geometry through an elastic linear program, cuts, grid snapping, and audits against production-router rules in a negotiation loop.Audit findings also feed back to the choice of escapes.Source: §I · p. 1
  • Differential pairs are planned as single lanes with end-specific polarity, with an automatic via crossover when their end polarities disagree.Source: §I · p. 1

II. RELATED WORK

  • Earlier via-minimization work assigns layers to a given topology or routed layout; it does not jointly place and order crossings with layer choices and via room.Source: §II · p. 2
  • Prior bus and escape-routing work includes joint escape selection, bus planning, exact escape models, and flows that finish layouts, but most work stops at a plan and uses private cases.Lin et al. carried simultaneous escape routing through gridless area routing to finish commercial boards that a commercial router could not.Source: §II · p. 2
  • The model uses convex orders of permutation crossings and reports no known model applying that structure to jointly minimize vias with crossing positions and via room.Its physics interpretation maps lanes to worldlines, crossings to scattering events, layer changes to domain walls, and linear-program dual variables to contact forces.Source: §I · p. 1, §II · p. 2

III. THE PROBLEM AND THE FRAME

The problem is to route bus lanes between two BGAs through a constrained two-layer region, where fixed end escapes determine the crossing topology. The frame and route coordinate represent each lane’s path so crossings and layer changes can be planned along the whole route.

A. Setting

  • A bench contains source and destination BGAs, bus nets, and fixed obstacles, with each net leaving at a source tooth and arriving at a destination berth.The described benches have two signal layers, F and B, and each end has a layer.Source: A. Setting · p. 2
  • The planned clearance is 0.105 mm, with 0.127 mm lanes, 0.25 mm vias, and a 0.252 mm minimum lane pitch on a 0.025 mm grid.The benches’ clearance is 0.1 mm; planning and routing use 5 µm above it.Source: A. Setting · p. 2
  • The objective counts planned layer-change vias and adds penalties for a net carrying more than two vias; the final route must be connected and DRC-clean.The ends supply stub vias, while a differential pair’s layer change counts once despite laying two barrels.Source: A. Setting · p. 2

B. The frame and the route coordinate

  • The frame is derived from the board by orienting the source west of the destination, growing their pad boxes, and running a trunk between them.Lanes use destination rings or source lead-ins to join the trunk on their respective sides.Source: B. The frame and the route coordinate · p. 2
  • Cuts on the arrays’ far faces unroll destination berths and source teeth into berth order φ and launch order λ.The destination cut lies in the widest berth gap; the source cut is chosen to minimize crossings.Source: B. The frame and the route coordinate · p. 2
  • Each lane’s path is represented by one route coordinate u, so lanes at the same coordinate stand across the bus and a crossing has one shared position.The coordinate is discretized on a 0.0504 mm grid.Source: B. The frame and the route coordinate · p. 3
  • Every inverted pair crosses exactly once, while pairs not inverted do not cross; the crossing order records the braid and layers determine over-and-under behavior.In Fig. 2, berth order (3, 1, 4, 2) requires the three inverted pairs to cross, with the triple rule ordering t23 before t13.Source: B. The frame and the route coordinate · p. 3, Figure 2 · p. 3

C. Two bounds

The section gives a lower bound on vias from the lane permutation and an exact per-lane count once partner layers and crossing order are fixed. The example illustrates both the bound and the whole-route model’s simultaneous crossing and layer choices.

Two bounds

  • 2(K − LIS(π)) vias is a lower bound when every lane starts and ends on F and routes within the frame.Lanes that never change layer form an increasing subsequence; every other lane must leave F and return, requiring at least two vias.Source: C. Two bounds · p. 3
  • For a lane with both ends on F, the fewest layer changes equal twice the number of maximal consecutive runs of F-layer crossing partners.Each such run requires one change into B and one out; choosing all lanes’ layers and crossing order together remains the central difficulty.Source: C. Two bounds · p. 3

IV. THE WHOLE-ROUTE SOLVE

The whole-route CP-SAT model jointly chooses crossing positions and order, plus each lane’s layer changes, before routing. Its triple rule characterizes realizable crossing orders, while via-room constraints and cuts help carry the plan toward a feasible layout.

IV. THE WHOLE-ROUTE SOLVE

  • The CP-SAT model chooses every crossing and layer change for all lanes together, with crossing positions constrained to route-specific windows.Crossing windows account for entries, the front-of-source band, and where lanes leave the trunk or reach a landing or ring.Source: §IV · p. 3
  • The triple rule admits exactly the crossing orders realizable by a wiring diagram of the lanes’ permutation.For each triple of mutually crossing lanes, the crossings occur in one of two orders; the model’s Boolean selects between them.Source: §IV · pp. 3–4
  • Each lane has up to three ordered layer changes, with via-room spacing and end-layer parity constraining their positions.Changes must also stay out of specified bands and end regions; neighboring changes are staggered to preserve via clearance.Source: §IV · p. 4
  • Layer is modeled as an Ising spin, crossings impose opposite layers, and each layer change is a domain wall counted by the objective.Frustrated cycles of must-differ constraints force vias; the solve also chooses the order of crossing events.Source: §IV · p. 4
  • Built-in clearance cuts and soft-cut penalties constrain where layer changes may occur and contribute to the plan’s objective.The objective also penalizes vias beyond two per net, but this is a price rather than a hard cap.Source: §IV · p. 4
  • The proof is optimality in whole vias for fixed ends under the model’s assumptions, including one crossing per inverted pair and at most three changes per lane.Positions lie on grid G and built-in and loop cuts are heuristic; the board’s via count also depends on the chosen ends.Source: §IV · p. 4

V. CHOOSING THE ENDS

The ends determine the braid, so the router searches for escape assignments using an estimate of the route objective. It then reranks promising assignments with an exact ordering model, although the end selection itself is not proved optimal.

V. CHOOSING THE ENDS

  • Escape assignments are searched using estimated via cost, trunk congestion, crossings, and audit feedback.The search changes one tooth or berth at a time and iterates from seeded random kicks.Source: §V · pp. 4–5
  • For candidate ends, via estimates use exact per-layer covers for same-layer conflicts and a minimum cut for wrong-layer partners.Conflicts between lanes whose ends differ are resolved greedily.Source: §V · p. 5
  • The best candidates are reranked with a lighter exact model, but the local search and work limits mean the chosen ends are not proved best.Offering street berths trades a few vias for fewer crossings and a quicker solve.Source: §V · p. 5

VI. FROM PLAN TO COPPER

The plan is converted to copper through staged geometry, snapping, and audits against the production router’s rules. Each stage preserves clearance margin for the following stage before the production router lays the plan.

VI. FROM PLAN TO COPPER

  • Geometry and polish place the lanes in millimeters while keeping a grid step more room than the later snap and audit.An audit gates the smooth plan before snapping.Source: §VI · p. 5
  • The snap lays pairs on the router’s grid, then polish fits singles around them before a second snap lays the singles.Each step is audited.Source: §VI · p. 5
  • A final audit with a lint of the router’s shape rules gates the snapped plan before the production router lays it.Source: §VI · p. 5

A. Geometry

A linear program places lanes and vias in board geometry while honoring spacing, room, and boundary constraints. A second pass handles non-convex island-side choices combinatorially, and violated constraints feed cuts back to the solve.

A. Geometry

  • The linear program places lane offsets at columns every 0.1 mm along the trunk and both rings, with ends pinned and selected nearby columns held parallel to the spine.It constrains same-layer pitch, via room, board and pad boundaries, and slope changes.Source: A. Geometry · p. 5
  • The first pass minimizes added length, bends, and a hinge penalty for neighboring lanes closer than the comfortable pitch 2p.Tangent cuts underestimate length, so slopes below 13° cost nothing in this approximation.Source: A. Geometry · p. 5
  • A second pass assigns each lane a side of every island before solving, preserving convexity while accounting for slope-corrected pitch.If a lane cannot be held on its chosen side, the resulting island or via constraint becomes a cut for the solve.Source: A. Geometry · p. 5
  • Dual values act as contact forces that identify binding rules, while paid elastic-constraint slack and static, via, or dive constraints can return as cuts.The two-pass program’s dual is passed to HiGHS through SciPy.Source: A. Geometry · p. 5

B. Polish and snap

The polish adjusts the smooth lane geometry to satisfy the audit’s board-coordinate rules, then the snap converts the plan to router-grid paths while reserving room for later lanes.

B. Polish and snap

  • The polish uses small vertex moves in trust boxes of ±0.05 mm, adding nearby audit rules as elastic constraints and pushing any lane or via found inside a pad out of its island.It straightens audit-flagged folds and notches between rounds and keeps the best state reached, rather than simply the last one.Source: B. Polish and snap · pp. 5–6
  • Fig. 4 depicts the geometry LP as lanes under string tension, with pad-box and pitch constraints carrying the dual forces where they bind.The pad box pushes the lowest lane upward at the bend, while pitch struts pass the load up the stack; nonbinding rules carry no force.Source: Figure 4 · p. 6
  • The snap lays pairs first and holds them while singles are polished and snapped; up to two sweeps then retry every lane against the others’ copper.Its A* search is confined to a strip 2p either side of each smooth lane, with vias within 2p of the plan.Source: B. Polish and snap · p. 6

C. Differential pairs

Differential pairs retain their polarity through planning and routing, while audits gate each route stage and return failures to a negotiation loop that revises the plan, geometry, or chosen ends.

C. Differential pairs

  • A differential pair is modeled as one two-slot lane; when its end hands disagree, the solve requires a layer change and the snap lays a via crossover at the first dive.The crossover staggers both barrels on one side of the pair, with its footprint known before placement.Source: C. Differential pairs · p. 6

D. Audit and route

  • The audit gates the smooth and snapped plans against router rules, and the production router then lays pairs and singles in confined bands; a passing audit does not guarantee that every lane will be laid.Independent checks grade connectivity and DRC on the written board.Source: D. Audit and route · p. 6

E. The negotiation loop

  • Audit shortfalls return as history prices, while geometry and snap failures return as cuts; repeated end findings are priced to guide the next fanout choice.If no plan satisfies the hard cuts, they become soft costs; the loop stops at a passing gate, its round limit, or an end finding.Source: E. The negotiation loop · p. 6, Figure 5 · p. 7
  • The loop searches topological sectors: the solve proposes a sector, convex geometry relaxes within it, and yielding constraints identify sectors to leave.A failed loop is still laid, but its cuts are not proved valid, so optimality applies only to the model it ends with.Source: E. The negotiation loop · pp. 6–7

VII. RESULTS

The evaluation grades routed boards for connectivity, DRC, vias, and copper across two DDR3 bus ladders, comparing the proposed route with human and automated routers. The proposed route completes every ladder rung cleanly and uses fewer vias and less copper than the human designs.

A. Benches and grading

  • The H3 bench has 51 bus nets, including three differential pairs, and the Zynq ladder covers rungs up to 43 nets; boards are graded independently for connectivity, 0.1 mm-clearance DRC, vias, and copper.The two designs use different layer settings: the H3 designer routed on two layers, while the Zynq designer used outer layers only.Source: A. Benches and grading · p. 7

B. Against the human

  • Every rung of both ladders is connected and DRC-clean, with no more vias and less copper than the human; only H3 K28 and K35 require more than the first fanout round.The ladders reach 51 nets on H3 and 43 on Zynq.Source: B. Against the human · p. 7
  • 80 vias versus the human’s 88 on H3 K51, and 62 versus 100 on Zynq K43.The copper difference partly reflects the human route’s length matching.Source: B. Against the human · p. 7

C. Against other routers

  • The production chain completes six of ten rungs and leaves one to four nets open on the others, while Freerouting completes none; both use more copper than the proposed route on every rung.The production chain uses 2.0 to 4.7 times the proposed route’s vias; Freerouting can use fewer vias on connected nets while leaving nets open.Source: C. Against other routers · p. 7

D. On the board itself

The evaluation includes a Zynq DDR3 bus routed on its own board and generated buses tested on two or more routing layers. The route completes the graded on-board nets and achieves every known optimum in the multi-layer generated cases.

D. On the board itself

  • On the Zynq board, all 45 graded nets complete in the first round with 70 vias versus the human’s 105 and less copper; the production chain leaves one net open and two clearance violations.The route handles 46 nets between the arrays but refuses the clock pair and column-address strobe; the reset stub is excluded from grading.Source: D. On the board itself · p. 7, Table I · p. 8, Figure 7 · p. 9

E. Synthetic buses

  • On two-layer synthetic buses, 23 runs complete; of 16 with graded optima, 10 match exactly and two complete above optimum, while six leave nets open because layer changes lack room.The generated set contains 29 buses of 4 to 16 nets with varied crossing patterns.Source: E. Synthetic buses · pp. 8–9

F. More routing layers

  • Across 87 runs on three-, four-, and six-layer generated buses, every run completes connected and DRC-clean, and all 48 with known optima attain them.More layers provide room for layer changes but do not lower the channels’ optima.Source: F. More routing layers · p. 9

G. Cost

The router completes real DDR3 bus routes with fewer vias and less copper than the designers, and its first solves are proved optimal for their chosen ends. The paper also identifies runtime costs and scope limits, including the lack of length matching.

G. Cost

  • H3 K51 took 290 s overall; its geometry LP used 150 s, about half the runtime at the top of both ladders.The full H3 K51 breakdown also includes 42 s for fanout, 32 s for the solve, 19 s for polishes, 27 s for snaps, 11 s for audits and lint, and 6 s to lay the plan.Source: G. Cost · p. 9
  • Every rung’s first solve was proved optimal; the top H3 solve handled 313 crossings and 2 744 triples in 30 s, and the board solve handled 229 crossings and 1 922 triples in 46 s.Every other rung’s first solve was proved optimal in 7 s or less.Source: G. Cost · p. 9

VIII. LIMITATIONS AND FUTURE WORK

  • The route does not match lengths; multilayer evaluation covers generated buses only, and the study uses two boards with design constants developed on them.Optimality is relative to the model and fixed ends; the model also limits each inverted pair to one crossing, each lane to at most three layer changes, and positions to grid G.Source: §VIII · p. 9

IX. CONCLUSION

  • The router fully automatically routed one real DDR3 bus whole and 43 nets of another, plus 45 nets on the second board, with fewer vias and less copper than their designers.Source: §IX · p. 10
  • The physics framing connects triple-order consistency to worldlines, vias to spin frustration, and LP dual forces to rules holding lanes in place or yielding.Source: §IX · p. 10
Loading 2610.35601v1…