Today a "bus" is N independent sequential A* searches that are softly attracted to a shared centerline. Nothing assigns each member a lane, and nothing ever computes the permutation between the two ends of the bus. The result is that members grab lanes greedily in routing order and the last members have to cross their own siblings — which, at fab-floor clearance inside a BGA courtyard, they cannot.
This issue proposes treating a bus as one object: plan a spine, assign slots from terminal order, emit members as pitch offsets of the spine, and use the longest increasing subsequence of the end-to-end permutation to decide exactly which members must change layer.
Evidence: the failures are stragglers, not scattered congestion
From the mez_rx run (the board from #614, now added to the corpus as set28/mez_rx — 8 layers, 236 routable nets, 400-ball 0.8mm-pitch FPGA). Final: 91.1% complete, 21 nets short, against a corpus median of 100%.
Grouping the 21 failures by net family:
| group |
lost |
size |
failed members |
G* (LED matrix) |
3 |
24 |
G15, G3, G7 |
SDR_A* |
1 |
12 |
SDR_A9 |
RGMII_RXD* |
1 |
4 |
RGMII_RXD0 |
PORT2_T* |
1 |
8 |
PORT2_T0- |
R* |
1 |
24 |
R22 |
7 of 21 failures are the last one-to-three members of a group whose siblings all routed. (Of the rest, 5 are U1 power-rail escape remainders — a pour/comb problem, explicitly out of scope here — and the remainder are genuine singletons.)
"23 of 24 routed and the 24th can't get through" is a very specific signature. It is not congestion in general; it is a member being forced to cross the siblings that already took its lane. The router reports these as no rippable blockers found, which is true and completely uninformative.
What the current implementation does, and where it stops short
Four concrete gaps:
1. The permutation is never computed. bus_detection._order_nets_by_position() sorts members by source position only — it picks the axis with the larger spread and sorts by it. The target order is never derived and never compared against the source order. BusGroup.clique_endpoint records which end formed the clique, and the other end is simply not modelled. So the single fact that determines a bus's whole strategy — do the two ends agree on order? — is not available anywhere in the code.
2. Slots are never assigned. bus_detection.get_bus_routing_order() returns a middle-outward routing order. Order is not slot: each member still discovers its own lane through A*, so lane assignment is whatever falls out of greedy search. --ordering mps has the same limitation at the whole-board level — MPS decides when a net routes, not where it sits.
3. The corridor geometry is computed and then thrown away. bus_corridor.py already does the hard part: it probe-routes the representative at a ladder of inflated widths (the wide-power-net track_margin mechanism, so k sibling-rooms per side are reserved on the shared obstacle map) and scores length + (k_max - k) * room * ROOM_WEIGHT. Then it feeds the winning path in as attraction_path and nothing else. We already know where the ribbon should go — we just decline to put copper there.
4. Corridor capacity is capped below real bus widths. MAX_RUNG = 3, so k_max = min(ceil((N-1)/2), 3) — room for roughly 7 tracks, regardless of N. G* is 24 members and SDR_A* is 12. For any bus wider than ~7, the probe reserves too little space by construction, so even the attraction hint points down a corridor that was never sized for the group.
Worth noting: CORRIDOR_VIA_COST_MULT = 4.0 exists with the comment "the human routes a bus as a river on ONE layer". The instinct is already in the codebase; this issue is about following it through to geometry.
Proposal: emit ribbons
1. Group model
Extend BusGroup with the missing half of the topology: order_a and order_b (member order projected onto the axis perpendicular to travel, at each end), the permutation π mapping slot-at-A to slot-at-B, and its inversion count. inversions == 0 means a clean river.
2. Spine
Reuse the existing probe, with MAX_RUNG raised (or removed) so k tracks the real member count instead of saturating at 3. Keep the probe's via-cost multiplier — a layer-coherent centerline is exactly what a ribbon needs.
3. Slots from terminal order
Slot i = rank in order_a. This is the step that does not exist today, and it is most of the fix: once lanes are pre-assigned, no member can take a lane that a later member needs.
4. The LIS rule (the key idea)
Two members i < j in end-A order must cross each other iff π(i) > π(j). Therefore the maximum subset routable as a clean single-layer river is the Longest Increasing Subsequence of π, and the members not in the LIS — exactly N - |LIS| of them — each need one layer hop to get across.
This is O(N log N), exact, and it directly predicts a bus's via count before any copper is placed. It is also precisely what a human does with a twisted bus: most lines run straight through on one layer, and a few dive to cross. Compare against #296's measurement of 2.57 vias/member for us vs 1.24 for the human — that gap is the cost of discovering the permutation one net at a time instead of solving it once.
Where the crossings happen should be chosen by available room along the spine, not by routing order. Today it is implicitly the latter, which is why the untangling lands in the least roomy place — the BGA courtyard.
5. Emit by offset
Each member = the spine offset by (slot - center) * pitch, with pitch = track_width + clearance (net-class aware, and .kicad_dru-aware per #498). Octolinear offsetting is well-defined here: offset each segment along its normal and miter at the 45°/90° corners, so the output stays in the existing geometry vocabulary. Inner and outer members differ in length at corners; the existing length-matching pass runs afterwards and can absorb that for matched buses.
6. Fans at the ends
Short, local routes from the ribbon end to each pad. Because slot order equals terminal order by construction, the fans do not cross each other — which is the whole point of doing the assignment up front.
7. Fallback ladder
Full river → partial river (the largest subset that fits) → slot-pinned sequential (today's attraction, but with lanes pre-assigned) → today's free attraction → plain sequential. Every rung is cheap to fall back from, and failure is detected before copper is committed rather than 20 members later.
Why this is Python-only
No Rust change is required: the probe already exists, LIS / slot assignment / polyline offsetting are pure Python geometry, and emission goes through kicad_writer / pcb_modification. Per the repo's Rust-change policy that matters — a crate bump and per-platform binary redistribution is a much heavier lift than this needs. Rust only enters if we later want a genuine multi-net simultaneous search, which this proposal is designed to avoid.
Measurement
Evaluation plan
Establish the baseline first — we effectively do not have one. --bus appears in 2 of 399 recorded corpus runs, and was not passed on the mez_rx run above. So the existing machinery is almost entirely unexercised, and the first step is simply to re-run mez_rx with --bus on.
That is also the cheapest possible falsification of this issue: if attraction alone recovers those 7 stragglers, the diagnosis is wrong and we have spent one route step finding out. The prediction is that it recovers few or none, because attraction cannot assign slots.
Then env-gated A/B: mez_rx (G* 24, SDR_A* 12, RGMII_RXD* 4), the thrash boards (glasgow, ulx3s, icepi_zero), and the BGA escapes (orangecrab, lpddr4) where a mis-sized reservation could strangle a mandatory escape — the #584 softcap lesson applies.
Relationship to #589
Complementary, and this should land first. #589's rough pass predicts paths per net; a 24-member bus becomes 24 nearly-identical predictions piled into one demand bin, which overstates contention in the corridor and understates it everywhere else. Ribbons turn a bus into one rough path with a known width — a much better demand primitive for the global planner. Bus-as-object makes #589 better rather than competing with it.
Out of scope for v1
- Multi-drop / comb buses (address lines to several DRAMs): not a two-cluster topology, and the strict filter's parallel-travel rule likely already excludes them.
- Pin swapping to reduce inversions — that is a schematic change.
- Power-rail escape remainders (5 of
mez_rx's 21 failures). Those want copper area, not traces; keeping them out of the measurement avoids contaminating the bus signal.
Refs: #589 (global planning — this is its natural precursor), #296 (vias/member vs human, and the corridor-probe prior art), #584 (composition values + A/B harness), #587 / #588 (symptom-side fields this attacks the cause of), #614 (source of the board), #452 (direction preference).
Today a "bus" is N independent sequential A* searches that are softly attracted to a shared centerline. Nothing assigns each member a lane, and nothing ever computes the permutation between the two ends of the bus. The result is that members grab lanes greedily in routing order and the last members have to cross their own siblings — which, at fab-floor clearance inside a BGA courtyard, they cannot.
This issue proposes treating a bus as one object: plan a spine, assign slots from terminal order, emit members as pitch offsets of the spine, and use the longest increasing subsequence of the end-to-end permutation to decide exactly which members must change layer.
Evidence: the failures are stragglers, not scattered congestion
From the
mez_rxrun (the board from #614, now added to the corpus asset28/mez_rx— 8 layers, 236 routable nets, 400-ball 0.8mm-pitch FPGA). Final: 91.1% complete, 21 nets short, against a corpus median of 100%.Grouping the 21 failures by net family:
G*(LED matrix)SDR_A*RGMII_RXD*PORT2_T*R*7 of 21 failures are the last one-to-three members of a group whose siblings all routed. (Of the rest, 5 are U1 power-rail escape remainders — a pour/comb problem, explicitly out of scope here — and the remainder are genuine singletons.)
"23 of 24 routed and the 24th can't get through" is a very specific signature. It is not congestion in general; it is a member being forced to cross the siblings that already took its lane. The router reports these as
no rippable blockers found, which is true and completely uninformative.What the current implementation does, and where it stops short
Four concrete gaps:
1. The permutation is never computed.
bus_detection._order_nets_by_position()sorts members by source position only — it picks the axis with the larger spread and sorts by it. The target order is never derived and never compared against the source order.BusGroup.clique_endpointrecords which end formed the clique, and the other end is simply not modelled. So the single fact that determines a bus's whole strategy — do the two ends agree on order? — is not available anywhere in the code.2. Slots are never assigned.
bus_detection.get_bus_routing_order()returns a middle-outward routing order. Order is not slot: each member still discovers its own lane through A*, so lane assignment is whatever falls out of greedy search.--ordering mpshas the same limitation at the whole-board level — MPS decides when a net routes, not where it sits.3. The corridor geometry is computed and then thrown away.
bus_corridor.pyalready does the hard part: it probe-routes the representative at a ladder of inflated widths (the wide-power-nettrack_marginmechanism, so k sibling-rooms per side are reserved on the shared obstacle map) and scoreslength + (k_max - k) * room * ROOM_WEIGHT. Then it feeds the winning path in asattraction_pathand nothing else. We already know where the ribbon should go — we just decline to put copper there.4. Corridor capacity is capped below real bus widths.
MAX_RUNG = 3, sok_max = min(ceil((N-1)/2), 3)— room for roughly 7 tracks, regardless of N.G*is 24 members andSDR_A*is 12. For any bus wider than ~7, the probe reserves too little space by construction, so even the attraction hint points down a corridor that was never sized for the group.Worth noting:
CORRIDOR_VIA_COST_MULT = 4.0exists with the comment "the human routes a bus as a river on ONE layer". The instinct is already in the codebase; this issue is about following it through to geometry.Proposal: emit ribbons
1. Group model
Extend
BusGroupwith the missing half of the topology:order_aandorder_b(member order projected onto the axis perpendicular to travel, at each end), the permutationπmapping slot-at-A to slot-at-B, and its inversion count.inversions == 0means a clean river.2. Spine
Reuse the existing probe, with
MAX_RUNGraised (or removed) soktracks the real member count instead of saturating at 3. Keep the probe's via-cost multiplier — a layer-coherent centerline is exactly what a ribbon needs.3. Slots from terminal order
Slot
i= rank inorder_a. This is the step that does not exist today, and it is most of the fix: once lanes are pre-assigned, no member can take a lane that a later member needs.4. The LIS rule (the key idea)
Two members
i < jin end-A order must cross each other iffπ(i) > π(j). Therefore the maximum subset routable as a clean single-layer river is the Longest Increasing Subsequence of π, and the members not in the LIS — exactlyN - |LIS|of them — each need one layer hop to get across.This is O(N log N), exact, and it directly predicts a bus's via count before any copper is placed. It is also precisely what a human does with a twisted bus: most lines run straight through on one layer, and a few dive to cross. Compare against #296's measurement of 2.57 vias/member for us vs 1.24 for the human — that gap is the cost of discovering the permutation one net at a time instead of solving it once.
Where the crossings happen should be chosen by available room along the spine, not by routing order. Today it is implicitly the latter, which is why the untangling lands in the least roomy place — the BGA courtyard.
5. Emit by offset
Each member = the spine offset by
(slot - center) * pitch, withpitch = track_width + clearance(net-class aware, and.kicad_dru-aware per #498). Octolinear offsetting is well-defined here: offset each segment along its normal and miter at the 45°/90° corners, so the output stays in the existing geometry vocabulary. Inner and outer members differ in length at corners; the existing length-matching pass runs afterwards and can absorb that for matched buses.6. Fans at the ends
Short, local routes from the ribbon end to each pad. Because slot order equals terminal order by construction, the fans do not cross each other — which is the whole point of doing the assignment up front.
7. Fallback ladder
Full river → partial river (the largest subset that fits) → slot-pinned sequential (today's attraction, but with lanes pre-assigned) → today's free attraction → plain sequential. Every rung is cheap to fall back from, and failure is detected before copper is committed rather than 20 members later.
Why this is Python-only
No Rust change is required: the probe already exists, LIS / slot assignment / polyline offsetting are pure Python geometry, and emission goes through
kicad_writer/pcb_modification. Per the repo's Rust-change policy that matters — a crate bump and per-platform binary redistribution is a much heavier lift than this needs. Rust only enters if we later want a genuine multi-net simultaneous search, which this proposal is designed to avoid.Measurement
Evaluation plan
Establish the baseline first — we effectively do not have one.
--busappears in 2 of 399 recorded corpus runs, and was not passed on themez_rxrun above. So the existing machinery is almost entirely unexercised, and the first step is simply to re-runmez_rxwith--buson.That is also the cheapest possible falsification of this issue: if attraction alone recovers those 7 stragglers, the diagnosis is wrong and we have spent one route step finding out. The prediction is that it recovers few or none, because attraction cannot assign slots.
Then env-gated A/B:
mez_rx(G*24,SDR_A*12,RGMII_RXD*4), the thrash boards (glasgow, ulx3s, icepi_zero), and the BGA escapes (orangecrab, lpddr4) where a mis-sized reservation could strangle a mandatory escape — the #584 softcap lesson applies.Relationship to #589
Complementary, and this should land first. #589's rough pass predicts paths per net; a 24-member bus becomes 24 nearly-identical predictions piled into one demand bin, which overstates contention in the corridor and understates it everywhere else. Ribbons turn a bus into one rough path with a known width — a much better demand primitive for the global planner. Bus-as-object makes #589 better rather than competing with it.
Out of scope for v1
mez_rx's 21 failures). Those want copper area, not traces; keeping them out of the measurement avoids contaminating the bus signal.Refs: #589 (global planning — this is its natural precursor), #296 (vias/member vs human, and the corridor-probe prior art), #584 (composition values + A/B harness), #587 / #588 (symptom-side fields this attacks the cause of), #614 (source of the board), #452 (direction preference).