66 lines
4.2 KiB
Markdown
66 lines
4.2 KiB
Markdown
|
# Routing Search Specification
|
||
|
|
|
||
|
|
This document details the Hybrid State-Lattice A* implementation and the "PathFinder" (Negotiated Congestion) algorithm for multi-net routing.
|
||
|
|
|
||
|
|
## 1. Hybrid State-Lattice A* Search
|
||
|
|
The core router operates on states $S = (x, y, \theta)$, where $\theta \in \{0, 90, 180, 270\}$.
|
||
|
|
|
||
|
|
### 1.1. State Representation & Snapping
|
||
|
|
To ensure search stability and hash-map performance:
|
||
|
|
* **Intermediate Ports:** Every state expanded by A* is snapped to a search grid.
|
||
|
|
* **Search Grid:** Default snap is **1000nm (1µm)**.
|
||
|
|
* **Final Alignment:** The "Snap-to-Target" logic bridges the gap from the coarse search grid to the final **1nm** port coordinates.
|
||
|
|
* **Max Design Size:** Guidelines for memory/performance assume up to **20mm x 20mm** routing area.
|
||
|
|
|
||
|
|
### 1.2. Move Expansion Logic
|
||
|
|
From state $S_n$, the following moves are evaluated:
|
||
|
|
1. **Tiered Straight Steps:** Expand by a set of distances $L \in \{1\mu m, 5\mu m, 25\mu m\}$.
|
||
|
|
2. **Snap-to-Target:** A "last-inch" look-ahead move. If the target $T$ is within a **Capture Radius (Default: 10µm)** and a straight segment or single bend can reach it, a special move is generated to close the gap exactly at 1nm resolution.
|
||
|
|
3. **90° Bend:** Try clockwise/counter-clockwise turns using fixed PDK cells.
|
||
|
|
4. **Small-Offset S-Bend:**
|
||
|
|
* **Only for $O < 2R$:** Parametric S-bend (two tangent arcs).
|
||
|
|
* **$O \ge 2R$:** Search naturally finds these by combining 90° bends and straight segments.
|
||
|
|
|
||
|
|
### 1.3. Cost Function $f(n) = g(n) + h(n)$
|
||
|
|
The search uses a flexible, component-based cost model.
|
||
|
|
|
||
|
|
* **$g(n)$ (Actual Cost):** $\sum \text{ComponentCost}_i + \text{ProximityCost} + \text{CongestionCost}$
|
||
|
|
* **Straight Segment:** $L \times C_{unit\_length}$.
|
||
|
|
* **90° Bend:** $10 \times (\text{Manhattan distance between ports})$.
|
||
|
|
* **S-Bend:** $f(O, R)$.
|
||
|
|
* **Proximity Cost:** $k/d^2$ penalty (strict checks use R-Tree).
|
||
|
|
* **Congestion Cost:** $P \times (\text{Overlaps in Path R-Tree})$.
|
||
|
|
* **$h(n)$ (Heuristic):**
|
||
|
|
* Manhattan distance $L_1$ to the target.
|
||
|
|
* Orientation Penalty: High cost if the state's orientation doesn't match the target's entry orientation.
|
||
|
|
* **Greedy Weighting:** The A* search uses a weighted heuristic (e.g., $1.1 \times h(n)$) to prioritize search speed over strict path optimality.
|
||
|
|
* **Danger Map Heuristic:** Fast lookups from the **1µm** pre-computed proximity grid.
|
||
|
|
|
||
|
|
## 2. Multi-Net "PathFinder" Strategy (Negotiated Congestion)
|
||
|
|
1. **Iteration:** Identify "Congestion Areas" using Path R-Tree intersections.
|
||
|
|
2. **Inflation:** Increase penalty multiplier $P$ for congested areas.
|
||
|
|
3. **Repeat:** Continue until no overlaps exist or the max iteration count is reached (Default: **20 iterations**).
|
||
|
|
|
||
|
|
### 2.1. Convergence & Result Policy
|
||
|
|
* **Least Bad Attempt:** If no 100% collision-free solution is found, return the result with the lowest total cost (including overlaps).
|
||
|
|
* **Explicit Reporting:** Results MUST include a `RoutingResult` object containing:
|
||
|
|
* `path_geometry`: The actual polygon sequence.
|
||
|
|
* `is_valid`: Boolean (True only if no collisions).
|
||
|
|
* `collisions`: A count or list of detected overlap points/polygons.
|
||
|
|
* **Visualization:** Overlapping regions are highlighted (e.g., in red) in the heatmaps.
|
||
|
|
|
||
|
|
## 3. Search Limits & Scaling
|
||
|
|
* **Node Limit:** A* search is capped at **50,000 nodes** per net per iteration.
|
||
|
|
* **Dynamic Timeout:** Session-level timeout based on problem size:
|
||
|
|
* `Timeout = max(2s, 0.05s * num_nets * num_iterations)`.
|
||
|
|
* *Example:* A 100-net problem over 20 iterations times out at **100 seconds**.
|
||
|
|
|
||
|
|
## 4. Determinism
|
||
|
|
All search and rip-up operations are strictly deterministic.
|
||
|
|
* **Seed:** A user-provided `seed` (int) MUST be used to initialize any random number generators (e.g., if used for tie-breaking or initial net ordering).
|
||
|
|
* **Tie-Breaking:** If two nodes have the same $f(n)$, a consistent tie-breaking rule (e.g., based on node insertion order or state hash) must be used.
|
||
|
|
|
||
|
|
## 5. Optimizations
|
||
|
|
* **A* Pruning:** Head toward the target and prune suboptimal orientations.
|
||
|
|
* **Safety Zones:** Ignore collisions within **2nm** of start/end ports.
|
||
|
|
* **Spatial Indexing:** R-Tree queries are limited to the bounding box of the current move.
|