Compare commits
3
Commits
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
f1d0f8df70 | ||
|
|
c44ff272ae | ||
|
|
05f31fc828 |
+2
-2
@@ -24,9 +24,11 @@ off. Exits non-zero if any run crashed or timed out.
|
|||||||
from __future__ import annotations
|
from __future__ import annotations
|
||||||
|
|
||||||
import argparse
|
import argparse
|
||||||
|
from concurrent.futures import ThreadPoolExecutor, as_completed
|
||||||
import json
|
import json
|
||||||
import math
|
import math
|
||||||
import os
|
import os
|
||||||
|
from pathlib import Path
|
||||||
import re
|
import re
|
||||||
import shlex
|
import shlex
|
||||||
import subprocess
|
import subprocess
|
||||||
@@ -34,8 +36,6 @@ import sys
|
|||||||
import tempfile
|
import tempfile
|
||||||
import threading
|
import threading
|
||||||
import time
|
import time
|
||||||
from concurrent.futures import ThreadPoolExecutor, as_completed
|
|
||||||
from pathlib import Path
|
|
||||||
|
|
||||||
NOT_ROUTED = re.compile(r"freeroute: (\d+) connection\(s\) not routed")
|
NOT_ROUTED = re.compile(r"freeroute: (\d+) connection\(s\) not routed")
|
||||||
TO_ZONE = re.compile(r"freeroute: (\d+) more connection\(s\) left to a zone fill")
|
TO_ZONE = re.compile(r"freeroute: (\d+) more connection\(s\) left to a zone fill")
|
||||||
|
|||||||
@@ -0,0 +1,253 @@
|
|||||||
|
"""Why did each connection fail? Sort the failures of one exact-engine run.
|
||||||
|
|
||||||
|
uv run python bench/diagnose.py board.dsn --edge-clearance 0.5 [--json out.json]
|
||||||
|
|
||||||
|
Every connection the exact engine leaves unrouted lands in one bucket:
|
||||||
|
|
||||||
|
rejected the grid routed it, the exact geometry check refused its copper
|
||||||
|
alone it cannot be routed even on a board with no other routes: the
|
||||||
|
pads, keepouts or the grid itself are the limit, not congestion
|
||||||
|
walled-in in the routed board one of its pins has no way out: a flood from
|
||||||
|
the pin's end cells through free cells stops short (pin access)
|
||||||
|
congestion both pins can get out, but no free path joins them
|
||||||
|
|
||||||
|
The board state is the one the result came from (the best pass), rebuilt by
|
||||||
|
replaying that pass's paths. Diagnostic only: it reaches into the router.
|
||||||
|
"""
|
||||||
|
|
||||||
|
from __future__ import annotations
|
||||||
|
|
||||||
|
import argparse
|
||||||
|
from collections import Counter
|
||||||
|
import json
|
||||||
|
from pathlib import Path
|
||||||
|
import sys
|
||||||
|
|
||||||
|
from freeroute.board import build_board
|
||||||
|
from freeroute.board.search_tree import ShapeSearchTree
|
||||||
|
from freeroute.dsn import parse_dsn
|
||||||
|
from freeroute.route import grid_router
|
||||||
|
from freeroute.route.exact_router import route_board_exact
|
||||||
|
from freeroute.route.grid_router import GridRouter, _ends_of
|
||||||
|
from freeroute.route.pipeline import (
|
||||||
|
_mm_to_board,
|
||||||
|
_rule_clearance_dsn,
|
||||||
|
_rule_width_dsn,
|
||||||
|
_via_half_board,
|
||||||
|
)
|
||||||
|
|
||||||
|
# a pin whose free neighbourhood holds fewer nodes than this is walled in
|
||||||
|
FLOOD_LIMIT = 200
|
||||||
|
|
||||||
|
|
||||||
|
def _capture_router():
|
||||||
|
"""Patch GridRouter so the instance route_board_exact builds, and the paths
|
||||||
|
of its best pass, can be read back afterwards."""
|
||||||
|
seen: dict = {}
|
||||||
|
original_commit = GridRouter._commit
|
||||||
|
original_snapshot = GridRouter._snapshot
|
||||||
|
|
||||||
|
def commit(self, conn, path):
|
||||||
|
original_commit(self, conn, path)
|
||||||
|
self._diag_paths[conn.index] = (list(path), conn.a_end, conn.b_end)
|
||||||
|
|
||||||
|
def snapshot(self, conns):
|
||||||
|
self._diag_best = {c.index: self._diag_paths[c.index] for c in conns if c.routed}
|
||||||
|
seen["router"] = self
|
||||||
|
return original_snapshot(self, conns)
|
||||||
|
|
||||||
|
def init(self, *args, **kwargs):
|
||||||
|
original_init(self, *args, **kwargs)
|
||||||
|
self._diag_paths = {}
|
||||||
|
self._diag_best = {}
|
||||||
|
seen["kwargs"] = kwargs
|
||||||
|
seen["args"] = args
|
||||||
|
|
||||||
|
original_init = GridRouter.__init__
|
||||||
|
GridRouter.__init__ = init
|
||||||
|
GridRouter._commit = commit
|
||||||
|
GridRouter._snapshot = snapshot
|
||||||
|
return seen
|
||||||
|
|
||||||
|
|
||||||
|
def _capture_conflicts() -> list:
|
||||||
|
"""Record each exact-check refusal: the copper box, its kind, and the
|
||||||
|
shape it came too close to. The check stops at a connection's first
|
||||||
|
conflict, so refusals and rejected connections line up in order."""
|
||||||
|
log: list = []
|
||||||
|
original = ShapeSearchTree.clearance_conflict
|
||||||
|
|
||||||
|
def conflict(self, box, net_no, layer, clearance, kind="wire"):
|
||||||
|
hit = original(self, box, net_no, layer, clearance, kind)
|
||||||
|
if hit:
|
||||||
|
expanded = box.offset(clearance)
|
||||||
|
other = next(
|
||||||
|
(s for s in self.overlapping(expanded)
|
||||||
|
if s.net_no != net_no and s.on_layer(layer)
|
||||||
|
and (s.blocks == "all" or s.blocks == kind + "s")),
|
||||||
|
None,
|
||||||
|
)
|
||||||
|
log.append((net_no, kind, layer, box, clearance, other))
|
||||||
|
return hit
|
||||||
|
|
||||||
|
ShapeSearchTree.clearance_conflict = conflict
|
||||||
|
return log
|
||||||
|
|
||||||
|
|
||||||
|
def _gap(a, b) -> int:
|
||||||
|
dx = max(b.ll.x - a.ur.x, a.ll.x - b.ur.x, 0)
|
||||||
|
dy = max(b.ll.y - a.ur.y, a.ll.y - b.ur.y, 0)
|
||||||
|
return max(dx, dy)
|
||||||
|
|
||||||
|
|
||||||
|
def _fresh(seen) -> GridRouter:
|
||||||
|
router = grid_router.GridRouter(*seen["args"], **seen["kwargs"])
|
||||||
|
router._conns = router._build_connections()
|
||||||
|
return router
|
||||||
|
|
||||||
|
|
||||||
|
def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
|
||||||
|
"""How many nodes a pin can reach through free cells (up to FLOOD_LIMIT),
|
||||||
|
and which other nets' copper bounds the region."""
|
||||||
|
walls: Counter = Counter()
|
||||||
|
# the search starts on every end node unconditionally (it may leave one
|
||||||
|
# inside a wire keepout by a via), so the flood does too
|
||||||
|
start = list(router._end_nodes(pin, net_no, conns))
|
||||||
|
seen = set(start)
|
||||||
|
frontier = list(start)
|
||||||
|
while frontier and len(seen) < FLOOD_LIMIT:
|
||||||
|
x, y, layer = frontier.pop()
|
||||||
|
steps = [(x + dx, y + dy, layer) for dx, dy in router._neighbours]
|
||||||
|
if router._via_placeable((x, y), net_no, conns):
|
||||||
|
steps += [(x, y, other) for other in router.layers if other != layer]
|
||||||
|
elif len(seen) == 1:
|
||||||
|
# the pin's own exit is a via that other copper leaves no room for
|
||||||
|
via_nodes = [(*c, lay) for c in router._via_cells((x, y)) for lay in router.layers]
|
||||||
|
for owner in router._crossed_owners(via_nodes, net_no, conns):
|
||||||
|
walls[conns[owner].net_no] += 1
|
||||||
|
for n in steps:
|
||||||
|
if n in seen or not (0 <= n[0] < router.cols and 0 <= n[1] < router.rows):
|
||||||
|
continue
|
||||||
|
if router._enter_cost(n[:2], n[2], net_no, False, conns) is None:
|
||||||
|
# trace, via footprint or clearance halo, as rip-up sees them
|
||||||
|
owners = router._crossed_owners([n], net_no, conns)
|
||||||
|
for owner in owners:
|
||||||
|
walls[conns[owner].net_no] += 1
|
||||||
|
if not owners:
|
||||||
|
walls[0] += 1 # a pad or keepout
|
||||||
|
continue
|
||||||
|
seen.add(n)
|
||||||
|
frontier.append(n)
|
||||||
|
return len(seen), walls
|
||||||
|
|
||||||
|
|
||||||
|
def diagnose(
|
||||||
|
dsn_text: str, edge_clearance_mm: float | None, resolution: int = 2, shove: bool = False,
|
||||||
|
access_cost: float = 0.0,
|
||||||
|
) -> dict:
|
||||||
|
dsn = parse_dsn(dsn_text)
|
||||||
|
names = {i + 1: n.name for i, n in enumerate(dsn.nets)}
|
||||||
|
scale = max(dsn.resolution.value, 1)
|
||||||
|
seen = _capture_router()
|
||||||
|
conflicts = _capture_conflicts()
|
||||||
|
exact = route_board_exact(
|
||||||
|
build_board(dsn),
|
||||||
|
trace_width=round(_rule_width_dsn(dsn) * scale),
|
||||||
|
clearance=round(_rule_clearance_dsn(dsn) * scale),
|
||||||
|
via_half=_via_half_board(dsn, scale),
|
||||||
|
edge_clearance=_mm_to_board(dsn, scale, edge_clearance_mm),
|
||||||
|
resolution=resolution,
|
||||||
|
shove=shove,
|
||||||
|
access_cost=access_cost,
|
||||||
|
)
|
||||||
|
routed = seen["router"]
|
||||||
|
best = routed._diag_best
|
||||||
|
grid_failed = {(c.net_no, *_ends_of(c)) for c in routed._conns if c.index not in best}
|
||||||
|
|
||||||
|
# the board as the best pass left it
|
||||||
|
state = _fresh(seen)
|
||||||
|
conns = state._conns
|
||||||
|
for idx, (path, a_end, b_end) in best.items():
|
||||||
|
conns[idx].a_end, conns[idx].b_end = a_end, b_end
|
||||||
|
state._commit(conns[idx], path)
|
||||||
|
empty = _fresh(seen)
|
||||||
|
# refusals in the order the check made them, one per rejected connection
|
||||||
|
per_net: dict[int, list] = {}
|
||||||
|
for net_no, kind, layer, box, clearance, other in conflicts:
|
||||||
|
if other is None:
|
||||||
|
what = "?"
|
||||||
|
elif other.net_no == -1:
|
||||||
|
what = "keepout"
|
||||||
|
else:
|
||||||
|
what = ("trace/via of " if other.routed else "pad of ") + names.get(other.net_no, "?")
|
||||||
|
short = (clearance - _gap(box, other.tile)) / scale / 1000 if other is not None else 0
|
||||||
|
per_net.setdefault(net_no, []).append(
|
||||||
|
{"copper": kind, "layer": layer, "against": what, "short_mm": round(short, 4)}
|
||||||
|
)
|
||||||
|
by_key = {(c.net_no, *_ends_of(c)): c for c in conns}
|
||||||
|
|
||||||
|
rows = []
|
||||||
|
for failure in exact.result.failed:
|
||||||
|
net_no, a, b = failure[0], failure[1], failure[2]
|
||||||
|
zone = failure[3] if len(failure) > 3 else ""
|
||||||
|
if zone:
|
||||||
|
continue # left to a zone fill, not a failure
|
||||||
|
key = (net_no, a, b)
|
||||||
|
row = {"net": names.get(net_no, str(net_no)), "a": a, "b": b}
|
||||||
|
conn = by_key.get(key)
|
||||||
|
if key not in grid_failed:
|
||||||
|
row["kind"] = "rejected"
|
||||||
|
if per_net.get(net_no):
|
||||||
|
row["conflict"] = per_net[net_no].pop(0)
|
||||||
|
elif conn is None:
|
||||||
|
row["kind"] = "unknown"
|
||||||
|
elif empty._search(empty._conns[conn.index], allow_ripup=False, conns=empty._conns) is None:
|
||||||
|
row["kind"] = "alone"
|
||||||
|
else:
|
||||||
|
walled = []
|
||||||
|
for end, group in ((a, conn.a_group), (b, conn.b_group)):
|
||||||
|
for pin in group[0][:1]: # a group's first pin is its route end
|
||||||
|
reach, walls = _flood(state, pin, net_no, conns)
|
||||||
|
if reach < FLOOD_LIMIT:
|
||||||
|
walled.append({
|
||||||
|
"pin": end, "reach": reach,
|
||||||
|
"walls": [names.get(n, "pads/keepouts") for n, _ in walls.most_common(4)],
|
||||||
|
})
|
||||||
|
row["kind"] = "walled-in" if walled else "congestion"
|
||||||
|
if walled:
|
||||||
|
row["walled"] = walled
|
||||||
|
rows.append(row)
|
||||||
|
return {"failures": rows, "counts": dict(Counter(r["kind"] for r in rows))}
|
||||||
|
|
||||||
|
|
||||||
|
def main(argv: list[str] | None = None) -> int:
|
||||||
|
ap = argparse.ArgumentParser(description=__doc__.split("\n\n")[0])
|
||||||
|
ap.add_argument("dsn", type=Path)
|
||||||
|
ap.add_argument("--edge-clearance", type=float, metavar="MM")
|
||||||
|
ap.add_argument("--grid-resolution", type=int, default=2, metavar="K")
|
||||||
|
ap.add_argument("--shove", action="store_true", help="as mckicad routes")
|
||||||
|
ap.add_argument("--access-cost", type=float, default=0.0)
|
||||||
|
ap.add_argument("--json", type=Path, help="also write the full table here")
|
||||||
|
args = ap.parse_args(argv)
|
||||||
|
|
||||||
|
report = diagnose(args.dsn.read_text(), args.edge_clearance, args.grid_resolution, args.shove,
|
||||||
|
args.access_cost)
|
||||||
|
for row in report["failures"]:
|
||||||
|
extra = ""
|
||||||
|
for w in row.get("walled", []):
|
||||||
|
extra += f" [{w['pin']} reaches {w['reach']} cells, walled by {', '.join(w['walls'])}]"
|
||||||
|
if "conflict" in row:
|
||||||
|
c = row["conflict"]
|
||||||
|
extra += (f" [{c['copper']} on layer {c['layer']} {c['short_mm']} mm too close"
|
||||||
|
f" to {c['against']}]")
|
||||||
|
print(f"{row['kind']:11} {row['net']}: {row['a']} to {row['b']}{extra}")
|
||||||
|
total = sum(report["counts"].values())
|
||||||
|
print(f"\n{total} failed: " + ", ".join(f"{k} {v}" for k, v in sorted(report["counts"].items())),
|
||||||
|
file=sys.stderr)
|
||||||
|
if args.json:
|
||||||
|
args.json.write_text(json.dumps(report, indent=1))
|
||||||
|
return 0
|
||||||
|
|
||||||
|
|
||||||
|
if __name__ == "__main__":
|
||||||
|
raise SystemExit(main())
|
||||||
+13
-2
@@ -30,8 +30,8 @@ from freeroute.ses import write_ses
|
|||||||
#: which optional flags each engine actually implements. Anything not listed for
|
#: which optional flags each engine actually implements. Anything not listed for
|
||||||
#: an engine is rejected by :func:`_validate` rather than quietly ignored.
|
#: an engine is rejected by :func:`_validate` rather than quietly ignored.
|
||||||
ENGINE_OPTIONS: dict[str, frozenset[str]] = {
|
ENGINE_OPTIONS: dict[str, frozenset[str]] = {
|
||||||
"grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote"}),
|
"grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access"}),
|
||||||
"exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote"}),
|
"exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access"}),
|
||||||
"room": frozenset({"shove", "pack"}),
|
"room": frozenset({"shove", "pack"}),
|
||||||
}
|
}
|
||||||
|
|
||||||
@@ -45,6 +45,7 @@ _FLAG_NAMES = {
|
|||||||
"seed": "--seed",
|
"seed": "--seed",
|
||||||
"orders": "--orders",
|
"orders": "--orders",
|
||||||
"promote": "--promote-failures",
|
"promote": "--promote-failures",
|
||||||
|
"access": "--access-cost",
|
||||||
}
|
}
|
||||||
|
|
||||||
|
|
||||||
@@ -158,6 +159,13 @@ def build_parser() -> argparse.ArgumentParser:
|
|||||||
help="grid and exact engines: up to R rounds, each routing the connections that "
|
help="grid and exact engines: up to R rounds, each routing the connections that "
|
||||||
"failed so far first; keeps the best round",
|
"failed so far first; keeps the best round",
|
||||||
)
|
)
|
||||||
|
parser.add_argument(
|
||||||
|
"--access-cost",
|
||||||
|
type=float,
|
||||||
|
metavar="C",
|
||||||
|
help="grid and exact engines: extra cost for a route to pass where it would close "
|
||||||
|
"another pin's way out while that pin still has connections to route (default 0: off)",
|
||||||
|
)
|
||||||
parser.add_argument(
|
parser.add_argument(
|
||||||
"--jobs",
|
"--jobs",
|
||||||
type=int,
|
type=int,
|
||||||
@@ -186,6 +194,7 @@ def main(argv: list[str] | None = None) -> int:
|
|||||||
("seed", args.seed is not None),
|
("seed", args.seed is not None),
|
||||||
("orders", args.orders is not None),
|
("orders", args.orders is not None),
|
||||||
("promote", args.promote_failures is not None),
|
("promote", args.promote_failures is not None),
|
||||||
|
("access", args.access_cost is not None),
|
||||||
)
|
)
|
||||||
if asked
|
if asked
|
||||||
]
|
]
|
||||||
@@ -219,6 +228,7 @@ def main(argv: list[str] | None = None) -> int:
|
|||||||
"edge_clearance_mm": args.edge_clearance,
|
"edge_clearance_mm": args.edge_clearance,
|
||||||
"resolution": 2 if args.grid_resolution is None else args.grid_resolution,
|
"resolution": 2 if args.grid_resolution is None else args.grid_resolution,
|
||||||
"heuristic_weight": args.heuristic_weight,
|
"heuristic_weight": args.heuristic_weight,
|
||||||
|
"access_cost": args.access_cost or 0.0,
|
||||||
}
|
}
|
||||||
elif args.engine == "grid":
|
elif args.engine == "grid":
|
||||||
options = {
|
options = {
|
||||||
@@ -227,6 +237,7 @@ def main(argv: list[str] | None = None) -> int:
|
|||||||
"max_passes": max_passes,
|
"max_passes": max_passes,
|
||||||
"edge_clearance_mm": args.edge_clearance,
|
"edge_clearance_mm": args.edge_clearance,
|
||||||
"resolution": 1 if args.grid_resolution is None else args.grid_resolution,
|
"resolution": 1 if args.grid_resolution is None else args.grid_resolution,
|
||||||
|
"access_cost": args.access_cost or 0.0,
|
||||||
}
|
}
|
||||||
if args.engine == "room":
|
if args.engine == "room":
|
||||||
result = build_rooms_routing_result(
|
result = build_rooms_routing_result(
|
||||||
|
|||||||
@@ -96,6 +96,7 @@ def route_board_exact(
|
|||||||
heuristic_weight: float = 1.0,
|
heuristic_weight: float = 1.0,
|
||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
|
access_cost: float = 0.0,
|
||||||
) -> ExactRouteResult:
|
) -> ExactRouteResult:
|
||||||
"""Route ``board`` orthogonally and verify the result with exact geometry.
|
"""Route ``board`` orthogonally and verify the result with exact geometry.
|
||||||
|
|
||||||
@@ -126,6 +127,7 @@ def route_board_exact(
|
|||||||
heuristic_weight=heuristic_weight,
|
heuristic_weight=heuristic_weight,
|
||||||
seed=seed,
|
seed=seed,
|
||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
|
access_cost=access_cost,
|
||||||
)
|
)
|
||||||
edge = 0 if edge_clearance is None else edge_clearance
|
edge = 0 if edge_clearance is None else edge_clearance
|
||||||
outline = board.outline
|
outline = board.outline
|
||||||
|
|||||||
@@ -157,8 +157,16 @@ class GridRouter:
|
|||||||
heuristic_weight: float = 1.0,
|
heuristic_weight: float = 1.0,
|
||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
|
access_cost: float = 0.0,
|
||||||
) -> None:
|
) -> None:
|
||||||
self.board = board
|
self.board = board
|
||||||
|
# Pin access: while a pin still has connections to route, the cells
|
||||||
|
# its route would leave by (its end cells, the via it may need there,
|
||||||
|
# and the clearance around both) cost other nets this much extra, so
|
||||||
|
# they route round a fine-pitch pin's way out instead of sealing it.
|
||||||
|
self.access_cost = max(float(access_cost), 0.0)
|
||||||
|
self._doorways: dict[Node, list[tuple[int, int]]] = {}
|
||||||
|
self._pending: dict[int, int] = {}
|
||||||
# None keeps the deterministic order; a seed shuffles which connection
|
# None keeps the deterministic order; a seed shuffles which connection
|
||||||
# routes first, to measure how much a result owes to the order
|
# routes first, to measure how much a result owes to the order
|
||||||
self.seed = seed
|
self.seed = seed
|
||||||
@@ -289,6 +297,8 @@ class GridRouter:
|
|||||||
margin = self.clearance + self.half_width
|
margin = self.clearance + self.half_width
|
||||||
outline = self.board.outline
|
outline = self.board.outline
|
||||||
self._via_edge_block: set[Cell] = set()
|
self._via_edge_block: set[Cell] = set()
|
||||||
|
# wire keepouts as boxes, to check a pin stub the way the exact engine will
|
||||||
|
self._keepout_boxes: dict[int, list[IntBox]] = {}
|
||||||
if outline is not None:
|
if outline is not None:
|
||||||
# cells too close to the real outline (rounded corners included):
|
# cells too close to the real outline (rounded corners included):
|
||||||
# for a trace on every layer, and separately for a via's wider copper
|
# for a trace on every layer, and separately for a via's wider copper
|
||||||
@@ -325,6 +335,8 @@ class GridRouter:
|
|||||||
if box.is_empty():
|
if box.is_empty():
|
||||||
continue
|
continue
|
||||||
# the same distance the exact engine verifies against
|
# the same distance the exact engine verifies against
|
||||||
|
if item.blocks_wires:
|
||||||
|
self._keepout_boxes.setdefault(item.layer, []).append(box)
|
||||||
for cell in self._cells_in_box(box, margin):
|
for cell in self._cells_in_box(box, margin):
|
||||||
if item.blocks_wires:
|
if item.blocks_wires:
|
||||||
self._keepout.add((*cell, item.layer))
|
self._keepout.add((*cell, item.layer))
|
||||||
@@ -474,12 +486,16 @@ class GridRouter:
|
|||||||
enter = self._enter_cost(cell, cl, net_no, allow_ripup, conns)
|
enter = self._enter_cost(cell, cl, net_no, allow_ripup, conns)
|
||||||
if enter is None:
|
if enter is None:
|
||||||
continue
|
continue
|
||||||
|
if self._doorways:
|
||||||
|
enter += self._access(nxt, net_no)
|
||||||
step = 1.0 if dx == 0 or dy == 0 else math.sqrt(2)
|
step = 1.0 if dx == 0 or dy == 0 else math.sqrt(2)
|
||||||
self._relax(
|
self._relax(
|
||||||
current, nxt, base + step + enter, goal_cell, g_score, came_from, open_heap
|
current, nxt, base + step + enter, goal_cell, g_score, came_from, open_heap
|
||||||
)
|
)
|
||||||
if len(self.layers) > 1:
|
if len(self.layers) > 1:
|
||||||
g_via = base + self.via_cost
|
g_via = base + self.via_cost
|
||||||
|
if self._doorways:
|
||||||
|
g_via += self._access(current, net_no)
|
||||||
for layer in self.layers:
|
for layer in self.layers:
|
||||||
if layer == cl:
|
if layer == cl:
|
||||||
continue
|
continue
|
||||||
@@ -513,6 +529,18 @@ class GridRouter:
|
|||||||
]
|
]
|
||||||
|
|
||||||
def _stub_clear(self, pin: Pin, cell: Cell, layer: int, net_no: int, conns) -> bool:
|
def _stub_clear(self, pin: Pin, cell: Cell, layer: int, net_no: int, conns) -> bool:
|
||||||
|
keepouts = self._keepout_boxes.get(layer)
|
||||||
|
if keepouts:
|
||||||
|
# the stub is off the grid, so check it exactly, as the exact
|
||||||
|
# engine will: its copper grown by clearance must miss every keepout
|
||||||
|
from freeroute.geometry.polyline import Polyline, PolylineShape
|
||||||
|
|
||||||
|
end = self._cell_center(cell)
|
||||||
|
if end != pin.location:
|
||||||
|
for tile in PolylineShape(Polyline([pin.location, end]), self.half_width).tiles():
|
||||||
|
grown = tile.offset(self.clearance)
|
||||||
|
if any(k.overlaps(grown) for k in keepouts):
|
||||||
|
return False
|
||||||
for c in self._stub_cells(pin.location, cell):
|
for c in self._stub_cells(pin.location, cell):
|
||||||
owner = self._cell_owner.get((*c, layer))
|
owner = self._cell_owner.get((*c, layer))
|
||||||
if owner is not None and conns[owner].net_no != net_no:
|
if owner is not None and conns[owner].net_no != net_no:
|
||||||
@@ -765,8 +793,19 @@ class GridRouter:
|
|||||||
if node not in self._cell_owner:
|
if node not in self._cell_owner:
|
||||||
self._cell_owner[node] = conn.index
|
self._cell_owner[node] = conn.index
|
||||||
conn.trace_cells.append((c, layer))
|
conn.trace_cells.append((c, layer))
|
||||||
|
# A pin inside a wire keepout can only leave by a via. Its stub to the
|
||||||
|
# cell centre would be track inside the keepout, so the via goes on
|
||||||
|
# the pin itself (a via in its own pad) and the stub is left out.
|
||||||
|
in_pad: dict[int, IntPoint] = {}
|
||||||
|
if len(wire_segs) > 1:
|
||||||
|
for idx, pin in ((0, conn.a_end), (len(wire_segs) - 1, conn.b_end)):
|
||||||
|
layer, cells = wire_segs[idx]
|
||||||
|
if isinstance(pin, Pin) and len(cells) == 1 and (*cells[0], layer) in self._keepout:
|
||||||
|
in_pad[idx] = pin.location
|
||||||
conn.wires = []
|
conn.wires = []
|
||||||
for idx, (layer, cells) in enumerate(wire_segs):
|
for idx, (layer, cells) in enumerate(wire_segs):
|
||||||
|
if idx in in_pad:
|
||||||
|
continue
|
||||||
points = [self._cell_center(c) for c in cells]
|
points = [self._cell_center(c) for c in cells]
|
||||||
if idx == 0 and isinstance(conn.a_end, Pin):
|
if idx == 0 and isinstance(conn.a_end, Pin):
|
||||||
points.insert(0, conn.a_end.location)
|
points.insert(0, conn.a_end.location)
|
||||||
@@ -776,7 +815,11 @@ class GridRouter:
|
|||||||
if len(points) >= 2:
|
if len(points) >= 2:
|
||||||
conn.wires.append((layer, points))
|
conn.wires.append((layer, points))
|
||||||
conn.vias = [self._cell_center(c) for c in conn.via_cells]
|
conn.vias = [self._cell_center(c) for c in conn.via_cells]
|
||||||
|
for idx, location in in_pad.items():
|
||||||
|
# via k joins wire segments k and k + 1
|
||||||
|
conn.vias[0 if idx == 0 else idx - 1] = location
|
||||||
conn.routed = True
|
conn.routed = True
|
||||||
|
self._settle(conn, -1)
|
||||||
|
|
||||||
def _rip(self, conn: _Connection) -> None:
|
def _rip(self, conn: _Connection) -> None:
|
||||||
for cell, layer in conn.trace_cells:
|
for cell, layer in conn.trace_cells:
|
||||||
@@ -799,6 +842,7 @@ class GridRouter:
|
|||||||
conn.vias = []
|
conn.vias = []
|
||||||
conn.routed = False
|
conn.routed = False
|
||||||
conn.rip_count += 1
|
conn.rip_count += 1
|
||||||
|
self._settle(conn, +1)
|
||||||
|
|
||||||
def _crossed_owners(self, path: list[Node], net_no: int, conns: list[_Connection]) -> set[int]:
|
def _crossed_owners(self, path: list[Node], net_no: int, conns: list[_Connection]) -> set[int]:
|
||||||
owners: set[int] = set()
|
owners: set[int] = set()
|
||||||
@@ -814,6 +858,50 @@ class GridRouter:
|
|||||||
owners.add(i)
|
owners.add(i)
|
||||||
return owners
|
return owners
|
||||||
|
|
||||||
|
# --- pin access ---------------------------------------------------------
|
||||||
|
|
||||||
|
@staticmethod
|
||||||
|
def _group_pins(conn: _Connection):
|
||||||
|
return [*conn.a_group[0], *conn.b_group[0]]
|
||||||
|
|
||||||
|
def _build_doorways(self, conns: list[_Connection]) -> None:
|
||||||
|
"""Map every cell that would close a pin's way out to that pin."""
|
||||||
|
spread = [(0, 0), *self._halo_offsets]
|
||||||
|
done: set[int] = set()
|
||||||
|
for conn in conns:
|
||||||
|
for pin in self._group_pins(conn):
|
||||||
|
self._pending[id(pin)] = self._pending.get(id(pin), 0) + 1
|
||||||
|
if id(pin) in done:
|
||||||
|
continue
|
||||||
|
done.add(id(pin))
|
||||||
|
claim = (id(pin), conn.net_no)
|
||||||
|
exits: set[Node] = set()
|
||||||
|
for x, y, layer in self._end_nodes(pin, conn.net_no, conns):
|
||||||
|
exits.add((x, y, layer))
|
||||||
|
for c in self._via_cells((x, y)):
|
||||||
|
exits.update((*c, other) for other in self.layers)
|
||||||
|
cells: set[Node] = set()
|
||||||
|
for x, y, layer in exits:
|
||||||
|
for dx, dy in spread:
|
||||||
|
if 0 <= x + dx < self.cols and 0 <= y + dy < self.rows:
|
||||||
|
cells.add((x + dx, y + dy, layer))
|
||||||
|
for node in cells:
|
||||||
|
self._doorways.setdefault(node, []).append(claim)
|
||||||
|
|
||||||
|
def _settle(self, conn: _Connection, delta: int) -> None:
|
||||||
|
if not self._pending:
|
||||||
|
return
|
||||||
|
for pin in self._group_pins(conn):
|
||||||
|
if id(pin) in self._pending:
|
||||||
|
self._pending[id(pin)] += delta
|
||||||
|
|
||||||
|
def _access(self, node: Node, net_no: int) -> float:
|
||||||
|
"""Extra cost for ``net_no`` to use a cell another pin still needs."""
|
||||||
|
for pin_id, owner_net in self._doorways.get(node, ()):
|
||||||
|
if owner_net != net_no and self._pending.get(pin_id, 0) > 0:
|
||||||
|
return self.access_cost
|
||||||
|
return 0.0
|
||||||
|
|
||||||
# --- passes -------------------------------------------------------------
|
# --- passes -------------------------------------------------------------
|
||||||
|
|
||||||
def route(self) -> RouteResult:
|
def route(self) -> RouteResult:
|
||||||
@@ -822,6 +910,8 @@ class GridRouter:
|
|||||||
self._conns = conns
|
self._conns = conns
|
||||||
if not conns:
|
if not conns:
|
||||||
return RouteResult(self.half_width)
|
return RouteResult(self.half_width)
|
||||||
|
if self.access_cost:
|
||||||
|
self._build_doorways(conns)
|
||||||
|
|
||||||
passes = self.max_passes if self.rip_up else 1
|
passes = self.max_passes if self.rip_up else 1
|
||||||
best_count = -1
|
best_count = -1
|
||||||
@@ -1067,6 +1157,7 @@ def route_board(
|
|||||||
heuristic_weight: float = 1.0,
|
heuristic_weight: float = 1.0,
|
||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
|
access_cost: float = 0.0,
|
||||||
) -> RouteResult:
|
) -> RouteResult:
|
||||||
"""Convenience wrapper: build a :class:`GridRouter` and route the board."""
|
"""Convenience wrapper: build a :class:`GridRouter` and route the board."""
|
||||||
router = GridRouter(
|
router = GridRouter(
|
||||||
@@ -1084,5 +1175,6 @@ def route_board(
|
|||||||
heuristic_weight=heuristic_weight,
|
heuristic_weight=heuristic_weight,
|
||||||
seed=seed,
|
seed=seed,
|
||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
|
access_cost=access_cost,
|
||||||
)
|
)
|
||||||
return router.route()
|
return router.route()
|
||||||
|
|||||||
@@ -82,6 +82,7 @@ def route_dsn_board(
|
|||||||
max_passes: int = 10,
|
max_passes: int = 10,
|
||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
|
access_cost: float = 0.0,
|
||||||
) -> tuple[RouteResult, int, list[str]]:
|
) -> tuple[RouteResult, int, list[str]]:
|
||||||
"""Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
|
"""Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
|
||||||
and the layer names. ``layers`` restricts routing to those signal-layer
|
and the layer names. ``layers`` restricts routing to those signal-layer
|
||||||
@@ -104,6 +105,7 @@ def route_dsn_board(
|
|||||||
max_passes=max_passes,
|
max_passes=max_passes,
|
||||||
seed=seed,
|
seed=seed,
|
||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
|
access_cost=access_cost,
|
||||||
)
|
)
|
||||||
return result, scale, [layer.name for layer in dsn.layers]
|
return result, scale, [layer.name for layer in dsn.layers]
|
||||||
|
|
||||||
@@ -146,12 +148,14 @@ def build_routing_result(
|
|||||||
edge_clearance_mm: float | None = None,
|
edge_clearance_mm: float | None = None,
|
||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
|
access_cost: float = 0.0,
|
||||||
) -> RoutingResult:
|
) -> RoutingResult:
|
||||||
"""Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
|
"""Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
|
||||||
route, scale, layer_names = route_dsn_board(
|
route, scale, layer_names = route_dsn_board(
|
||||||
dsn, layers=layers, rip_up=rip_up, max_passes=max_passes,
|
dsn, layers=layers, rip_up=rip_up, max_passes=max_passes,
|
||||||
edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
|
edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
|
||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
|
access_cost=access_cost,
|
||||||
)
|
)
|
||||||
return _to_routing_result(route, dsn, scale, layer_names)
|
return _to_routing_result(route, dsn, scale, layer_names)
|
||||||
|
|
||||||
@@ -169,6 +173,7 @@ def route_dsn_board_exact(
|
|||||||
diagonal: bool = False,
|
diagonal: bool = False,
|
||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
|
access_cost: float = 0.0,
|
||||||
) -> tuple[ExactRouteResult, int, list[str]]:
|
) -> tuple[ExactRouteResult, int, list[str]]:
|
||||||
"""Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
|
"""Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
|
||||||
DRC-verified) track; return the exact result, the scale, and layer names.
|
DRC-verified) track; return the exact result, the scale, and layer names.
|
||||||
@@ -195,6 +200,7 @@ def route_dsn_board_exact(
|
|||||||
diagonal=diagonal,
|
diagonal=diagonal,
|
||||||
seed=seed,
|
seed=seed,
|
||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
|
access_cost=access_cost,
|
||||||
)
|
)
|
||||||
return exact, scale, [layer.name for layer in dsn.layers]
|
return exact, scale, [layer.name for layer in dsn.layers]
|
||||||
|
|
||||||
@@ -212,6 +218,7 @@ def build_exact_routing_result(
|
|||||||
edge_clearance_mm: float | None = None,
|
edge_clearance_mm: float | None = None,
|
||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
|
access_cost: float = 0.0,
|
||||||
) -> RoutingResult:
|
) -> RoutingResult:
|
||||||
"""Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
|
"""Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
|
||||||
exact, scale, layer_names = route_dsn_board_exact(
|
exact, scale, layer_names = route_dsn_board_exact(
|
||||||
@@ -226,6 +233,7 @@ def build_exact_routing_result(
|
|||||||
heuristic_weight=heuristic_weight,
|
heuristic_weight=heuristic_weight,
|
||||||
seed=seed,
|
seed=seed,
|
||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
|
access_cost=access_cost,
|
||||||
)
|
)
|
||||||
return _to_routing_result(exact.result, dsn, scale, layer_names)
|
return _to_routing_result(exact.result, dsn, scale, layer_names)
|
||||||
|
|
||||||
|
|||||||
@@ -157,6 +157,7 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
|
|||||||
"seed": ["--seed", "3"],
|
"seed": ["--seed", "3"],
|
||||||
"orders": ["--orders", "2"],
|
"orders": ["--orders", "2"],
|
||||||
"promote": ["--promote-failures", "2"],
|
"promote": ["--promote-failures", "2"],
|
||||||
|
"access": ["--access-cost", "5"],
|
||||||
}
|
}
|
||||||
for engine, options in ENGINE_OPTIONS.items():
|
for engine, options in ENGINE_OPTIONS.items():
|
||||||
for option in options:
|
for option in options:
|
||||||
|
|||||||
Reference in New Issue
Block a user