🧭 Global Router with Keepouts and 3D Extension

VLSI Physical Design Automation

📋 Agenda

1. Introduction - What is Global Routing? 🎯
2. Core Architecture - GlobalRouter & RoutingTree 🏗️
3. Routing Strategies - Simple, Steiner, Constraints ⚡
4. Keepouts - Avoiding Obstacles 🚧
5. 3D Extension - Multi-layer Routing 📦
6. Visualization - SVG Output Examples 🖼️
7. Code Demo - Live Examples 💻
8. Summary & Future Work 🔮

🎯 What is Global Routing?

Global routing determines the general path of each net through the chip, while detailed routing refines the exact wire positions.

graph TD
    A[Net List] --> B[Global Routing]
    B --> C[Routing Regions]
    C --> D[Detailed Routing]
    D --> E[Final Layout]

    style A fill:#e1f5fe
    style B fill:#b3e5fc
    style C fill:#81d4fa
    style D fill:#4fc3f7
    style E fill:#29b6f6

Key Objectives:

• ✅ Minimize total wirelength
• ✅ Satisfy timing constraints
  
• ✅ Avoid routing obstacles (keepouts)
• ✅ Enable multi-layer (3D) routing

🏗️ Core Architecture

GlobalRouter Class

┌─────────────────────────────────────────────┐
│              GlobalRouter                    │
├─────────────────────────────────────────────┤
│  - source_position: Point      (start)       │
│  - terminal_positions: List[Point] (sinks)  │
│  - keepouts: List[Point] (obstacles)        │
│  - tree: GlobalRoutingTree (result)         │
│  - worst_wirelength: int (constraint)       │
└─────────────────────────────────────────────┘

Key Methods:

🌳 Routing Tree Structure

class GlobalRoutingTree:
    """
    Global routing tree that supports 
    Steiner node and terminal node insertion.
    """
    
    # Node Types:
    # - SOURCE: Starting point
    # - STEINER: Intermediate optimization points
    # - TERMINAL: End points (sinks)

Tree Visualization:

                    +--.----------o (terminal)
                    |   `.
                    |     `.      (steiner)
                    |       `.
                    o---------`---+ (source)

         +--<---o
         |
         *-------->---o
         |
  o--->--+

⚡ Routing Strategy 1: Simple

route_simple() - Direct Connection

Connects each terminal directly to the nearest node in the existing tree.

def route_simple(self) -> None:
    for t in self.terminal_positions:
        self.tree.insert_terminal_node(t)

Visual Example:

graph LR
    S[Source<br/>📍] --> T1[Terminal 1]
    S --> T2[Terminal 2]
    S --> T3[Terminal 3]

    style S fill:#ff9800
    style T1 fill:#4caf50
    style T2 fill:#4caf50
    style T3 fill:#4caf50

Pros/Cons:

• ✅ Fast (O(n))
• ❌ Suboptimal wirelength

🌿 Routing Strategy 2: Steiner Points

route_with_steiners() - Wirelength Optimization

Inserts Steiner points to reduce total wirelength by creating shared paths.

def route_with_steiners(self) -> None:
    for t in self.terminal_positions:
        self.tree.insert_terminal_with_steiner(t, self.keepouts)

The Steiner Problem:

Given n terminals, find minimum spanning tree.

Minimize: ∑_i, jw_ij ⋅ x_ij

Where x_ij = 1 if edge (i, j) is in the tree.

Visual:

graph TD
    S[Source] --> SP[Steiner Point]
    SP --> T1[Terminal 1]
    SP --> T2[Terminal 2]

    style S fill:#ff9800
    style SP fill:#9c27b0
    style T1 fill:#4caf50
    style T2 fill:#4caf50

⏱️ Routing Strategy 3: Constraints

route_with_constraints() - Performance-Driven

Balances wirelength with timing constraints using α parameter.

def route_with_constraints(self, alpha: float = 1.0) -> None:
    allowed_wirelength = round(self.worst_wirelength * alpha)
    for t in self.terminal_positions:
        self.tree.insert_terminal_with_constraints(
            t, allowed_wirelength, self.keepouts
        )

Constraint Equation:

allowed_length = α × worst_wirelength

Where α ∈ [0.5, 2.0] typically.

When to Use:

🚧 Keepouts Implementation

What are Keepouts?

Keepouts are rectangular regions that the router must avoid - like pre-routed wires, macros, or IP blocks.

# Define keepouts as intervals
keepouts = [
    Point(Interval(1600, 1900), Interval(1000, 1500)),
    Point(Interval(500, 800), Interval(600, 900)),
]

Visual Representation:

rectangle
    title Keepout Regions
    direction LR
    A[Routing Area]
    B{Keepout 1}
    C{Keepout 2}
    D[Free to Route]

    A --> B
    A --> C
    A --> D

Blocking Detection:

# From routing_tree.py
for keepout in keepouts:
    if (keepout.contains(nearest_pt) or 
        keepout.blocks(path1) or 
        keepout.blocks(path2) or 
        keepout.blocks(path3)):
        block = True

🔍 Keepout Path Avoidance Algorithm

_find_insertion_point() Method

def _find_insertion_point(
    point: Point,
    keepouts: Optional[List[Point]] = None,
    allowed_wirelength: Optional[int] = None,
) -> Tuple[Optional[RoutingNode], RoutingNode]:

Algorithm Flow:

flowchart TD
    A[Start] --> B{Traverse Tree}
    B --> C[Calculate Path to Point]
    C --> D{Keepouts Block?}
    D -->|Yes| E[Skip This Branch]
    D -->|No| F{Distance < Min?}
    F -->|Yes| G[Update Nearest]
    F -->|No| H[Continue]
    G --> I{Allowed Wirelength?}
    I -->|Yes| J[Check Constraint]
    J -->|Pass| K[Select as Candidate]
    I -->|No| K
    H --> B
    K --> L[Return Parent & Nearest]

    style A fill:#ff9800
    style K fill:#4caf50

📦 3D Extension

Multi-Layer Routing

The router supports 3D coordinates - useful for multi-layer chips (e.g., 2D + metal layers).

2D vs 3D Point:

# 2D Point
p2d = Point(100, 200)

# 3D Point (x, y, z) where z = layer
p3d = Point(Point(100, 200), 3)  # Layer 3

Visual:

graph LR
    subgraph "2D View"
        A[x, y]
    end
    subgraph "3D View"
        B[x, y, z]
    end

    A -->|"extend"| B

    style A fill:#e3f2fd
    style B fill:#bbdefb

Distance Calculation:

• 2D: d = |x₁ − x₂|+|y₁ − y₂| (Manhattan)
• 3D: d = |x₁ − x₂|+|y₁ − y₂|+|z₁ − z₂|

📊 3D Wirelength Comparison

Example from Code:

>>> tree2d = GlobalRoutingTree(Point(0, 0))
>>> tree2d.insert_steiner_node(Point(2, 2))
>>> tree2d.calculate_total_wirelength()
4

>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> tree3d.insert_steiner_node(Point(Point(2, 2), 2))
>>> tree3d.calculate_total_wirelength()
6  # 2 + 2 + 2 (includes z-layer cost)

🖼️ Visualization Examples - 2D

1. Routing with Steiner Points

Optimal wirelength using Steiner points

🖼️ With Constraints

2. Routing with Timing Constraints

Performance-driven routing with timing budget

🖼️ With Keepouts

3. Routing with Obstacles

Routes detour around gray keepout regions

🖼️ Steiner + Keepouts

4. Optimal Routing with Obstacles

Combines Steiner optimization with keepout avoidance

🖼️ 3D Routing Examples

5. 3D Routing with Steiner Points

6. 3D with Constraints & Keepouts

💻 Code Demo

Basic Usage

from physdes.point import Point
from physdes.router.global_router import GlobalRouter

# Define source and terminals
source = Point(0, 0)
terminals = [Point(10, 0), Point(5, 5), Point(8, 3)]

# Create router
router = GlobalRouter(source, terminals)

# Choose strategy
router.route_simple()          # Fast, direct
# or
router.route_with_steiners()   # Optimal wirelength
# or
router.route_with_constraints(1.0)  # With timing budget

With Keepouts

from physdes.interval import Interval

# Define keepout regions
keepouts = [
    Point(Interval(4, 6), Interval(-1, 1)),  # Block in middle
]

router = GlobalRouter(source, terminals, keepouts)
router.route_with_steiners()

# Calculate total wirelength
total_wl = router.tree.calculate_total_wirelength()
print(f"Total wirelength: {total_wl}")

With 3D Coordinates

# 3D routing (e.g., 2-metal layer design)
source_3d = Point(Point(0, 0), 0)      # Layer 0
terminals_3d = [
    Point(Point(10, 1), 1),  # Layer 1
    Point(Point(5, 2), 2),   # Layer 2
]

router_3d = GlobalRouter(source_3d, terminals_3d)
router_3d.route_with_steiners()

Visualization

from physdes.router.routing_visualizer import (
    save_routing_tree_svg,
    visualize_routing_tree_svg
)

# Generate SVG string
svg = visualize_routing_tree_svg(
    router.tree, 
    keepouts, 
    width=1000, 
    height=1000
)
print(svg)

# Save to file
save_routing_tree_svg(
    router.tree, 
    keepouts,
    filename="my_route.svg"
)

📈 Algorithm Complexity

Where: - n = number of terminals - m = nodes in tree - k = number of keepouts

🔬 Key Data Structures

Point Class (Generic)

class Point(T1, T2):
    """Supports both 2D and 3D coordinates"""
    
    xcoord: T1  # int or Interval
    ycoord: T2  # int or Interval

RoutingNode

class RoutingNode:
    id: str
    type: NodeType  # SOURCE, STEINER, TERMINAL
    pt: Point
    children: List[RoutingNode]
    parent: Optional[RoutingNode]
    path_length: int  # for constraint checking

🎯 Key Algorithms

1. Nearest Node Search

def _find_nearest_node(self, point: Point) -> RoutingNode:
    """Find node with minimum Manhattan distance"""
    nearest = self.source
    min_distance = self.source.manhattan_distance(target)
    
    for node in self.nodes.values():
        dist = node.manhattan_distance(target)
        if dist < min_distance:
            nearest = node
    return nearest

2. Steiner Point Insertion

def insert_terminal_with_steiner(self, point, keepouts=None):
    parent, nearest = self._find_insertion_point(point, keepouts)
    
    if parent is None:
        nearest.add_child(terminal)
    else:
        # Insert Steiner point on the branch
        nearest_pt = possible_path.nearest_to(point)
        steiner = RoutingNode(..., nearest_pt)
        # Reconnect: parent -> steiner -> nearest + terminal

🧪 Testing

Run Tests

# All tests
pytest

# Specific test
pytest tests/test_global_router_with_keepouts.py -v

# With coverage
pytest --cov physdes --cov-report term-missing

Test Coverage:

📊 Output Examples - Global Router

2D Routing Results

Image	Description
	Routing with Steiner points
	Routing with timing constraints
	Routing with keepout obstacles
	Steiner points + keepouts

3D Routing Results

Image	Description
	3D routing with Steiner points
	3D with constraints & keepouts

🔄 Flow Diagram

flowchart TB
    subgraph Input
        A[Source Point] --> R[GlobalRouter]
        B[Terminals] --> R
        C[Keepouts] --> R
    end

    R --> D{route_simple}
    R --> E{route_with_steiners}
    R --> F{route_with_constraints}

    D --> G[Direct Connection]
    E --> H[Find Optimal Branch]
    F --> I[Check Wirelength Budget]

    G --> J[GlobalRoutingTree]
    H --> J
    I --> J

    J --> K[Calculate Wirelength]
    K --> L[Visualize SVG]

    style R fill:#ff9800
    style J fill:#4caf50
    style L fill:#2196f3

💡 Design Patterns Used

1. Strategy Pattern

Different routing algorithms as interchangeable strategies.

# GlobalRouter supports multiple strategies
router.route_simple()           # Strategy A
router.route_with_steiners()    # Strategy B  
router.route_with_constraints() # Strategy C

2. Composite Pattern

Routing tree as hierarchical structure.

graph TD
    Source --> Steiner1
    Source --> Steiner2
    Steiner1 --> Terminal1
    Steiner1 --> Terminal2
    Steiner2 --> Terminal3

    style Source fill:#ff9800
    style Steiner1 fill:#9c27b0
    style Steiner2 fill:#9c27b0
    style Terminal1 fill:#4caf50
    style Terminal2 fill:#4caf50
    style Terminal3 fill:#4caf50

🔧 Extensions & Future Work

Potential Enhancements

Related Projects

• physdes-cpp - C++ implementation
• physdes-rs - Rust implementation

📚 References

Papers

• VLSI Physical Design: A comprehensive textbook on global routing algorithms
• Steiner Tree Problem: NP-hard optimization in VLSI routing

Code References

• src/physdes/router/global_router.py - Main router
• src/physdes/router/routing_tree.py - Tree data structure
• src/physdes/router/routing_visualizer.py - SVG generation

Documentation

# Generate docs
sphinx-build -b html docs/ docs/_build/html

# View at http://localhost:8000

✅ Summary

What We Covered:

1. GlobalRouter class with 3 routing strategies
2. Keepouts for obstacle avoidance
3. 3D extension for multi-layer chips
4. Visualization via SVG output
5. Code examples and test cases

Key Takeaways:

• ✅ Steiner points reduce wirelength significantly
• ✅ Keepouts enable routing around obstacles
• ✅ 3D coordinates support modern multi-layer designs
• ✅ Modular design allows easy extension

🏁 Q&A

Questions?

Contact

• GitHub: luk036/physdes-py
• Documentation: physdes-py.readthedocs.io

📎 Appendix: Mathematical Formulas

Manhattan Distance

d₂((x₁, y₁), (x₂, y₂)) = |x₁ − x₂|+|y₁ − y₂|

3D Manhattan Distance

d₃((x₁, y₁, z₁), (x₂, y₂, z₂)) = |x₁ − x₂|+|y₁ − y₂|+|z₁ − z₂|

Wirelength Budget

budget = α × max_i(dist(source, terminal_i))

📎 Appendix: Point Class API

Creation

# 2D
p = Point(100, 200)

# 2D with intervals (for keepouts)
p = Point(Interval(10, 20), Interval(30, 40))

# 3D
p3d = Point(Point(100, 200), 3)  # (x,y), layer

Methods

📎 Appendix: File Structure

physdes-py/
├── src/physdes/
│   ├── router/
│   │   ├── global_router.py      # Main router ⭐
│   │   ├── routing_tree.py       # Tree structure ⭐
│   │   └── routing_visualizer.py # SVG output
│   ├── point.py                  # Point/Interval classes
│   ├── interval.py               # Interval arithmetic
│   └── cts/
│       └── dme_algorithm.py       # Clock tree synthesis
├── tests/
│   ├── test_global_router*.py    # Router tests
│   └── test_routing_tree*.py     # Tree tests
├── outputs/                       # Generated SVGs
│   ├── example_route*.svg
│   └── *clock_tree*.svg
└── README.md

Appendix: Mermaid Diagram Styles

Color Legend

graph TD
    A[Source/Start] --> B[Process]
    B --> C[Output]
    B --> D[Alternative]

    style A fill:#ff9800,color:#000
    style B fill:#2196f3,color:#fff
    style C fill:#4caf50,color:#000
    style D fill:#f44336,color:#fff

🎬 End of Presentation

Thank you! 🎉

physdes-py - VLSI Physical Design Python Library