Routing memory bus lanes with exact crossing and layer planning
Whole-Route Planning of a Memory Bus Between Two BGAs: An Exact Model of Crossings and Layer Changes, Negotiated to DRC-Clean Copper
Hardware Architecture
Summary
Routing the connections between a processor and its memory on a circuit board is usually done mostly by hand and is quite complex. The authors developed a planning tool that figures out the exact best paths for all the memory bus lines across two layers before any physical manufacturing, including where wires cross and switch layers. Their method uses math models inspired by physics and works by adjusting the design until it meets strict manufacturing rules. Tests on real chips show it matches or beats skilled human designers and existing tools, delivering cleaner, complete connections.
What this means in practice
- •For pcb designers: Automatically generate optimal routing plans for memory buses between BGAs that meet strict manufacturing rules before copper layers are applied.
- •For electronics manufacturing engineers: Audit and adjust PCB routing to pass production design rule checks with fewer vias and less copper than typical manual or automated approaches.
Authors
Andrew Haas
Abstract
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.