37 lines
2.5 KiB
Markdown
37 lines
2.5 KiB
Markdown
|
# Geometric Representation and Data Structures
|
||
|
|
|
||
|
|
This document defines the core data structures for representing the routing problem.
|
||
|
|
|
||
|
|
## 1. Port Definitions (Connectivity)
|
||
|
|
Routing requests are defined as a mapping of source ports to destination ports.
|
||
|
|
|
||
|
|
* **Port Structure:** `(x, y, orientation)`
|
||
|
|
* `x, y`: Coordinates snapped to **1nm** grid.
|
||
|
|
* `orientation`: Strictly $\{0, 90, 180, 270\}$ degrees.
|
||
|
|
* **Netlist:** A dictionary or list of tuples: `{(start_port): (end_port)}`. Each entry represents a single-layer path that must be routed.
|
||
|
|
* **Heterogeneous Widths:** The router supports different widths $W_i$ per net. Dilation for a specific net $i$ is calculated as $(W_i + C)/2$ to maintain the global clearance $C$.
|
||
|
|
|
||
|
|
## 2. Component Library (Move Generator)
|
||
|
|
The router uses a discrete set of components to expand states in the A* search.
|
||
|
|
|
||
|
|
### 2.1. Straight Waveguides
|
||
|
|
* **A* Expansion:** Generates "Straight" moves of varying lengths (e.g., $1\mu m, 5\mu m, 25\mu m$).
|
||
|
|
* **Snap-to-Target:** If the destination port $T$ is directly ahead and the current state's orientation matches $T$'s entry orientation, a special move is generated to close the gap exactly.
|
||
|
|
|
||
|
|
### 2.2. Fixed 90° Bends (PDK Cells)
|
||
|
|
* **Parameters:** `radius`, `width`.
|
||
|
|
* **A* Expansion:** A discrete move that changes orientation by $\pm 90^\circ$ and shifts the coordinate by the radius.
|
||
|
|
* **Grid Alignment:** If the bend radius $R$ is not a multiple of the search grid (default $1\mu m$), the resulting state is **snapped to the nearest grid point**, and a warning is issued to the user.
|
||
|
|
|
||
|
|
### 2.3. Parametric S-Bends (Compact)
|
||
|
|
* **Parameters:** `radius`, `width`.
|
||
|
|
* **A* Expansion:** Used ONLY for lateral offsets $O < 2R$.
|
||
|
|
* **Large Offsets ($O \ge 2R$):** The router does not use a single S-bend move for large offsets. Instead, the A* search naturally finds the optimal path by combining two 90° bends and a straight segment. This ensures maximum flexibility in obstacle avoidance for large shifts.
|
||
|
|
|
||
|
|
## 3. Obstacle Representation
|
||
|
|
Obstacles are provided as raw polygons on a single layer.
|
||
|
|
|
||
|
|
* **Pre-processing:** All input polygons are inserted into an **R-Tree**.
|
||
|
|
* **Buffer/Dilation:** Obstacles are pre-dilated by $(W_{max} + Clearance)/2$ for initial pruning, but final collision tests use the net-specific width $W_i$.
|
||
|
|
* **No Multi-layer:** The router assumes all obstacles and paths share the same plane.
|
||
|
|
* **Safety Zone:** Ignore collisions within **2nm** of start and end ports for robustness.
|