physdes.router namespace

Submodules

physdes.router.global_router module

Global Router for VLSI Physical Design.

This module provides a global router that offers multiple strategies for routing between a source and multiple terminals. The global router is a key component in the VLSI physical design flow, responsible for finding paths for interconnects while considering various constraints such as wirelength and timing.

The GlobalRouter class implements several routing algorithms, each tailored for different optimization goals:

• route_simple(): A basic approach that connects terminals directly to the nearest point in the routing tree.

• route_with_steiners(): A more advanced technique that inserts Steiner points to minimize wirelength.

• route_with_constraints(): A performance-driven strategy that considers both wirelength and timing constraints.

This modular design allows users to choose the most appropriate routing strategy for their specific needs, providing a flexible and powerful tool for global routing tasks.

class physdes.router.global_router.GlobalRouter(source_position, terminal_positions, keepouts=None)

Bases: object

A global router for routing between a source and multiple terminals.

__init__(source_position, terminal_positions, keepouts=None)

Initializes the GlobalRouter.

Parameters:

• source_position (Point) – The starting point for the routing.

• terminal_positions (List[Point]) – A list of terminal points to be routed to.

• keepouts (List[Point] | None) – A list of rectangular regions to avoid during routing.

Examples

>>> from physdes.point import Point
>>> source = Point(0, 0)
>>> terminals = [Point(10, 0), Point(1, 0), Point(5, 0)]
>>> router = GlobalRouter(source, terminals)
>>> router.terminal_positions
[Point(1, 0), Point(5, 0), Point(10, 0)]
>>> source = Point(Point(0, 0), 0)
>>> terminals = [Point(Point(10, 1), 0), Point(Point(1, 2), 0), Point(Point(5, 0), 0)]
>>> router = GlobalRouter(source, terminals)
>>> router.terminal_positions
[Point(Point(1, 2), 0), Point(Point(5, 0), 0), Point(Point(10, 1), 0)]
>>> from physdes.interval import Interval
>>> keepouts = [Point(Interval(2, 4), Interval(2, 4))]
>>> router = GlobalRouter(source, terminals, keepouts)
>>> router.keepouts
[Point(Interval(2, 4), Interval(2, 4))]

route_simple()

Performs a simple routing by connecting terminals directly to the nearest node in the tree.

Examples

>>> from physdes.point import Point
>>> source = Point(0, 0)
>>> terminals = [Point(1, 1), Point(2, 2)]
>>> router = GlobalRouter(source, terminals)
>>> router.route_simple()
>>> router.tree.calculate_total_wirelength()
4
>>> source = Point(Point(0, 0), 0)
>>> terminals = [Point(Point(1, 1), 1), Point(Point(2, 0), 2)]
>>> router = GlobalRouter(source, terminals)
>>> router.route_simple()
>>> router.tree.calculate_total_wirelength()
6

route_with_constraints(alpha=1.0)

Performance-driven routing by inserting Steiner points to reduce wire length.

Examples

>>> from physdes.point import Point
>>> source = Point(0, 0)
>>> terminals = [Point(1, 1), Point(2, 2)]
>>> router = GlobalRouter(source, terminals)
>>> router.route_with_constraints()
>>> router.tree.calculate_total_wirelength()
4
>>> source = Point(Point(0, 0), 0)
>>> terminals = [Point(Point(1, 1), 1), Point(Point(2, 0), 2)]
>>> router = GlobalRouter(source, terminals)
>>> router.route_with_constraints()
>>> router.tree.calculate_total_wirelength()
5

route_with_steiners()

Performs wirelength-driven routing by inserting Steiner points to reduce wire length.

Examples

>>> from physdes.point import Point
>>> source = Point(0, 0)
>>> terminals = [Point(1, 1), Point(2, 2)]
>>> router = GlobalRouter(source, terminals)
>>> router.route_with_steiners()
>>> router.tree.calculate_total_wirelength()
4
>>> source = Point(Point(0, 0), 0)
>>> terminals = [Point(Point(1, 1), 1), Point(Point(2, 0), 2)]
>>> router = GlobalRouter(source, terminals)
>>> router.route_with_steiners()
>>> router.tree.calculate_total_wirelength()
5

source_position

The starting point for the routing.

terminal_positions

A list of terminal points to be routed to, sorted by distance from the source.

tree

The routing tree, which is built up as the routing progresses.

worst_wirelength

The wirelength of the longest connection from the source to a terminal.

physdes.router.routing_tree module

class physdes.router.routing_tree.GlobalRoutingTree(source_position)

Bases: object

Global routing tree that supports Steiner node and terminal node insertion.

__init__(source_position)

Initializes the GlobalRoutingTree.

Parameters:

source_position (Point[Any, Any]) – The starting point for the routing.

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(1, 1))
>>> tree.source.pt
Point(1, 1)
>>> tree3d = GlobalRoutingTree(Point(Point(1, 1), 1))
>>> tree3d.source.pt
Point(Point(1, 1), 1)

calculate_total_wirelength()

Calculate total wirelength of the routing tree.

Returns:

The total wirelength.

Return type:

int

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> s1 = tree.insert_steiner_node(Point(1, 1))
>>> t1 = tree.insert_terminal_node(Point(2, 2), s1)
>>> tree.calculate_total_wirelength()
4
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> s1 = tree3d.insert_steiner_node(Point(Point(1, 1), 1))
>>> t1 = tree3d.insert_terminal_node(Point(Point(2, 2), 2), s1)
>>> tree3d.calculate_total_wirelength()
6

calculate_worst_wirelength()

Calculate the worst wirelength of the routing tree.

Returns:

The worst wirelength.

Return type:

int

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> s1 = tree.insert_steiner_node(Point(1, 1))
>>> t1 = tree.insert_terminal_node(Point(2, 2), s1)
>>> tree.calculate_worst_wirelength()
4
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> s1 = tree3d.insert_steiner_node(Point(Point(1, 1), 1))
>>> t1 = tree3d.insert_terminal_node(Point(Point(2, 2), 2), s1)
>>> tree3d.calculate_worst_wirelength()
6

find_path_to_source(node_id)

Find the path from a node back to the source.

Parameters:

node_id (str) – The ID of the node to find the path from.

Returns:

A list of nodes representing the path from the source to the given node.

Return type:

List[RoutingNode]

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> s1 = tree.insert_steiner_node(Point(1, 1))
>>> t1 = tree.insert_terminal_node(Point(2, 2), s1)
>>> path = tree.find_path_to_source(t1)
>>> len(path)
3
>>> path[0].id
'source'
>>> path[1].id
'steiner_1'
>>> path[2].id
'terminal_1'
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> s1 = tree3d.insert_steiner_node(Point(Point(1, 1), 1))
>>> t1 = tree3d.insert_terminal_node(Point(Point(2, 2), 2), s1)
>>> path = tree3d.find_path_to_source(t1)
>>> len(path)
3
>>> path[0].id
'source'
>>> path[1].id
'steiner_1'
>>> path[2].id
'terminal_1'

get_all_steiner_nodes()

Get all Steiner nodes in the tree.

Returns:

A list of all Steiner nodes.

Return type:

List[RoutingNode]

Examples

>>> tree = GlobalRoutingTree(Point(0, 0))
>>> s1 = tree.insert_steiner_node(Point(1, 1))
>>> s2 = tree.insert_steiner_node(Point(2, 2))
>>> steiners = tree.get_all_steiner_nodes()
>>> len(steiners)
2
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> s1 = tree3d.insert_steiner_node(Point(Point(1, 1), 1))
>>> s2 = tree3d.insert_steiner_node(Point(Point(2, 2), 2))
>>> steiners = tree3d.get_all_steiner_nodes()
>>> len(steiners)
2

get_all_terminals()

Get all terminal nodes in the tree.

Returns:

A list of all terminal nodes.

Return type:

List[RoutingNode]

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> t1 = tree.insert_terminal_node(Point(1, 1))
>>> t2 = tree.insert_terminal_node(Point(2, 2))
>>> terminals = tree.get_all_terminals()
>>> len(terminals)
2
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> t1 = tree3d.insert_terminal_node(Point(Point(1, 1), 1))
>>> t2 = tree3d.insert_terminal_node(Point(Point(2, 2), 2))
>>> terminals = tree3d.get_all_terminals()
>>> len(terminals)
2

get_tree_structure(node=None, level=0)

Get a string representation of the tree structure.

This method returns a hierarchical text representation of the routing tree, showing the parent-child relationships between nodes with indentation.

Parameters:

• node (Optional[RoutingNode]) – The starting node for the tree traversal. If None, starts from source.

• level (int) – The current indentation level (used for recursion).

Returns:

A string representation of the tree structure.

Return type:

str

insert_node_on_branch(new_node_type, point, branch_start_id, branch_end_id)

Insert a new node on an existing branch between two nodes.

Parameters:

• new_node_type (NodeType) – The type of the new node (NodeType.STEINER or NodeType.TERMINAL).

• x – The x-coordinate of the new node.

• y – The y-coordinate of the new node.

• branch_start_id (str) – The ID of the starting node of the branch.

• branch_end_id (str) – The ID of the ending node of the branch.

Returns:

The ID of the new node.

Return type:

str

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> s1 = tree.insert_steiner_node(Point(1, 1))
>>> t1 = tree.insert_terminal_node(Point(2, 2), s1)
>>> new_id = tree.insert_node_on_branch(NodeType.STEINER, Point(1, 2), s1, t1)
>>> new_id
'steiner_2'
>>> tree.nodes[new_id].parent.id == s1
True
>>> tree.nodes[t1].parent.id == new_id
True
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> s1 = tree3d.insert_steiner_node(Point(Point(1, 1), 1))
>>> t1 = tree3d.insert_terminal_node(Point(Point(2, 2), 2), s1)
>>> new_id = tree3d.insert_node_on_branch(NodeType.STEINER, Point(Point(1, 2), 2), s1, t1)
>>> new_id
'steiner_2'
>>> tree3d.nodes[new_id].parent.id == s1
True
>>> tree3d.nodes[t1].parent.id == new_id
True

insert_steiner_node(pt, parent_id=None)

Insert a new Steiner node into the routing tree.

Parameters:

• x – The x-coordinate of the new node.

• y – The y-coordinate of the new node.

• parent_id (str | None) – The ID of the parent node. If None, connect to the source.

Returns:

The ID of the new Steiner node.

Return type:

str

Examples

>>> tree = GlobalRoutingTree(Point(0, 0))
>>> steiner_id = tree.insert_steiner_node(Point(1, 1))
>>> steiner_id
'steiner_1'
>>> tree.nodes[steiner_id].parent == tree.source
True
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> steiner_id = tree3d.insert_steiner_node(Point(Point(1, 1), 1))
>>> steiner_id
'steiner_1'
>>> tree3d.nodes[steiner_id].parent == tree3d.source
True

insert_terminal_node(point, parent_id=None)

Insert a new terminal (sink) node into the routing tree.

Parameters:

• pt – The position of the new node.

• parent_id (str | None) – The ID of the parent node. If None, find the nearest node.

Returns:

The ID of the new terminal node.

Return type:

str

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> terminal_id = tree.insert_terminal_node(Point(1, 1))
>>> terminal_id
'terminal_1'
>>> tree.nodes[terminal_id].parent == tree.source
True
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> terminal_id = tree3d.insert_terminal_node(Point(Point(1, 1), 1))
>>> terminal_id
'terminal_1'
>>> tree3d.nodes[terminal_id].parent == tree3d.source
True

insert_terminal_with_constraints(point, allowed_wirelength, keepouts=None)

Inserts a terminal node with wirelength constraints, adding a Steiner point if it reduces wire length.

Parameters:

• pt – The position of the terminal to insert.

• allowed_wirelength (int) – The maximum allowed wirelength from the source.

• keepouts (List[Point[Interval[int], Interval[int]]] | None) – A list of rectangular regions to avoid.

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> tree.insert_terminal_with_constraints(Point(2, 2), 10)
>>> tree.calculate_total_wirelength()
4
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> tree3d.insert_terminal_with_constraints(Point(Point(2, 2), 2), 10)
>>> tree3d.calculate_total_wirelength()
6
>>> from physdes.interval import Interval
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> _ = tree.insert_terminal_node(Point(10, 0))
>>> keepouts = [Point(Interval(4, 6), Interval(-1, 1))]
>>> tree.insert_terminal_with_constraints(Point(5, 5), 100, keepouts)
>>> tree.calculate_total_wirelength()
20

insert_terminal_with_steiner(point, keepouts=None)

Inserts a terminal node, adding a Steiner point if it reduces wire length.

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> tree.insert_terminal_with_steiner(Point(2, 2))
>>> tree.calculate_total_wirelength()
4
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> tree3d.insert_terminal_with_steiner(Point(Point(2, 2), 2))
>>> tree3d.calculate_total_wirelength()
6
>>> from physdes.interval import Interval
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> _ = tree.insert_terminal_node(Point(10, 0))
>>> keepouts = [Point(Interval(4, 6), Interval(-1, 1))]
>>> tree.insert_terminal_with_steiner(Point(5, 5), keepouts)
>>> tree.calculate_total_wirelength()
20

optimize_steiner_points()

Simple optimization to remove unnecessary Steiner points.

Examples

>>> from physdes.point import Point
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> s1 = tree.insert_steiner_node(Point(1, 1))
>>> t1 = tree.insert_terminal_node(Point(2, 2), s1)
>>> tree.optimize_steiner_points()
>>> len(tree.get_all_steiner_nodes())
0
>>> tree3d = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> s1 = tree3d.insert_steiner_node(Point(Point(1, 1), 1))
>>> t1 = tree3d.insert_terminal_node(Point(Point(2, 2), 2), s1)
>>> tree3d.optimize_steiner_points()
>>> len(tree3d.get_all_steiner_nodes())
0

visualize_tree()

Simple ASCII visualization of the routing tree.

visualize_tree3d()

Simple ASCII visualization of the routing tree3d.

class physdes.router.routing_tree.NodeType(value)

Bases: Enum

Enum representing different types of routing nodes.

SOURCE = 3

STEINER = 1

TERMINAL = 2

classmethod __contains__(member)

Return True if member is a member of this enum raises TypeError if member is not an enum member

note: in 3.12 TypeError will no longer be raised, and True will also be returned if member is the value of a member in this enum

classmethod __getitem__(name)

Return the member matching name.

classmethod __iter__()

Return members in definition order.

classmethod __len__()

Return the number of members (no aliases)

class physdes.router.routing_tree.RoutingNode(node_id, node_type, position)

Bases: object

Represents a node in the global routing tree.

__init__(node_id, node_type, position)

Initialize a routing node.

Parameters:

• node_id (str) – Unique identifier for the node.

• node_type (NodeType) – Type of the node (SOURCE, STEINER, or TERMINAL).

• position (Point) – Position of the node in 2D or 3D space.

add_child(child_node)

Add a child node to this node.

Examples

>>> parent = RoutingNode("p1", NodeType.STEINER, Point(0, 0))
>>> child = RoutingNode("c1", NodeType.TERMINAL, Point(0, 0))
>>> parent.add_child(child)
>>> len(parent.children)
1
>>> child.parent == parent
True
>>> parent = RoutingNode("p1", NodeType.STEINER, Point(Point(0, 0), 0))
>>> child = RoutingNode("c1", NodeType.TERMINAL, Point(Point(0, 0), 0))
>>> parent.add_child(child)
>>> len(parent.children)
1
>>> child.parent == parent
True

children: List[RoutingNode]

get_position()

Get the position of the node.

Returns:

A Point object.

Return type:

Point[int, int]

Examples

>>> from physdes.point import Point
>>> node = RoutingNode("n1", NodeType.TERMINAL, Point(10, 20))
>>> node.get_position()
Point(10, 20)
>>> node = RoutingNode("n1", NodeType.TERMINAL, Point(Point(10, 20), 20))
>>> node.get_position()
Point(Point(10, 20), 20)

manhattan_distance(other_node)

Calculate Manhattan distance to another node.

Parameters:

other_node (RoutingNode) – The other node to calculate the distance to.

Returns:

The Manhattan distance.

Return type:

int

Examples

>>> from physdes.point import Point
>>> node1 = RoutingNode("n1", NodeType.TERMINAL, Point(0, 0))
>>> node2 = RoutingNode("n2", NodeType.TERMINAL, Point(3, 4))
>>> node1.manhattan_distance(node2)
7
>>> node1 = RoutingNode("n1", NodeType.TERMINAL, Point(Point(0, 0), 0))
>>> node2 = RoutingNode("n2", NodeType.TERMINAL, Point(Point(3, 4), 4))
>>> node1.manhattan_distance(node2)
11

parent: RoutingNode | None

remove_child(child_node)

Remove a child node.

Examples

>>> parent = RoutingNode("p1", NodeType.STEINER, Point(0, 0))
>>> child = RoutingNode("c1", NodeType.TERMINAL, Point(0, 0))
>>> parent.add_child(child)
>>> parent.remove_child(child)
>>> len(parent.children)
0
>>> child.parent is None
True
>>> parent = RoutingNode("p1", NodeType.STEINER, Point(Point(0, 0), 0))
>>> child = RoutingNode("c1", NodeType.TERMINAL, Point(Point(0, 0), 0))
>>> parent.add_child(child)
>>> parent.remove_child(child)
>>> len(parent.children)
0
>>> child.parent is None
True

physdes.router.routing_visualizer module

physdes.router.routing_visualizer.save_routing_tree3d_svg(tree3d, keepouts=None, scale_z=100, filename='routing_tree3d.svg', width=800, height=600)

Save the routing tree3d visualization as an SVG file.

Parameters:

• tree3d (GlobalRoutingTree) – GlobalRoutingTree instance

• filename (str) – Output filename

• width (int) – SVG canvas width

• height (int) – SVG canvas height

physdes.router.routing_visualizer.save_routing_tree_svg(tree, keepouts=None, filename='routing_tree.svg', width=800, height=600)

Save the routing tree visualization as an SVG file.

Parameters:

• tree (GlobalRoutingTree) – GlobalRoutingTree instance

• filename (str) – Output filename

• width (int) – SVG canvas width

• height (int) – SVG canvas height

physdes.router.routing_visualizer.visualize_routing_tree3d_svg(tree3d, keepouts=None, scale_z=100, width=800, height=600, margin=50)

Visualize a GlobalRoutingTree in SVG format.

Parameters:

• tree3d (GlobalRoutingTree) – GlobalRoutingTree instance to visualize

• width (int) – SVG canvas width

• height (int) – SVG canvas height

• margin (int) – Margin around the drawing area

Returns:

SVG string representation

Return type:

str

Examples

>>> from physdes.point import Point
>>> from physdes.router.routing_tree import GlobalRoutingTree
>>> tree = GlobalRoutingTree(Point(Point(0, 0), 0))
>>> s1 = tree.insert_steiner_node(Point(Point(1, 0), 1))
>>> t1 = tree.insert_terminal_node(Point(Point(2, 0), 2), s1)
>>> svg = visualize_routing_tree3d_svg(tree, width=200, height=200)
>>> '<circle cx="50.0" cy="50.0"' in svg
True
>>> '<circle cx="100.0" cy="100.0"' in svg
True
>>> '<circle cx="150.0" cy="150.0"' in svg
True

physdes.router.routing_visualizer.visualize_routing_tree_svg(tree, keepouts=None, width=800, height=600, margin=50)

Visualize a GlobalRoutingTree in SVG format.

Parameters:

• tree (GlobalRoutingTree) – GlobalRoutingTree instance to visualize

• width (int) – SVG canvas width

• height (int) – SVG canvas height

• margin (int) – Margin around the drawing area

Returns:

SVG string representation

Return type:

str

Examples

>>> from physdes.point import Point
>>> from physdes.router.routing_tree import GlobalRoutingTree
>>> tree = GlobalRoutingTree(Point(0, 0))
>>> s1 = tree.insert_steiner_node(Point(1, 1))
>>> t1 = tree.insert_terminal_node(Point(2, 2), s1)
>>> svg = visualize_routing_tree_svg(tree, width=200, height=200)
>>> '<circle cx="50.0" cy="50.0"' in svg
True
>>> '<circle cx="100.0" cy="100.0"' in svg
True
>>> '<circle cx="150.0" cy="150.0"' in svg
True