Models

Net

Net Module

class models.net.Net(net_id, net_name, num_of_pins, net_pins_coordinates)

Net class represents a wire that connects two or more pins

set_hpwl() → int

Set the value of HPWL (Half-Perimeter Wirelength)

Returns:

int: HPWL (Half-Perimeter Wirelength)

Node

Node Module

class models.node.Node(prev: Node, coordinates: Tuple[int, int])

Node class represents a pin in a net

Path

Path Module

class models.path.Path(end_node: Node)

Path class represents the full path of a net

Grid

Grid Module

class models.grid.Grid(grid_size: Tuple[int, int], capacity: Tuple[int, int])

A grid of cells, that represents a layout

is_overflow(path: Path) → bool

Determines if overflow exists for a path

Args:

path (Path): layout path

Returns:

bool: layout has overflow

update_congestion(path: Path, increment: bool)

Update congestion level for the path

Args:

path (Path): path increment (bool): congestion is incremented, else decremented

get_edge_cost(edge_id: int) → float

Get the cost of the edge. This cost function ensures that edges with high congestion have higher costs, which guides the search algorithm towards less congested paths and helps find a solution more quickly.

Args:

edge_id (int): Edge ID

Returns:

float: cost of the edge

get_edge_id(coordinate: Tuple[int, int], direction: int) → int

Get ID of the edge

Args:

coordinate (Tuple[int, int]): coordinate of the node direction (int): direction

Returns:

int: Edge ID

get_node_id(coordinate: Tuple[int, int]) → int

Get ID of the node

Args:

coordinate (Tuple[int, int]): the coordinate of the node

Returns:

int: the ID of the node

coordinate_is_in_bound(next_coordinate: Tuple[int, int]) → bool

Determine if given coordinate is within layout bounds

Args:

next_coordinate (Tuple[int, int]): coordinate of next node

Returns:

bool: coordinate of next node is legal or not

Global Router

Global Router Module

class models.global_router.GlobalRouter(algorithm: int, seed: int)

Global Router class, handles the logic of the global router

dump_result(output_file_path: str) → None

Dumps the route result into an output file

Args:

output_file_path (str): path of the output file

rip_up_and_reroute() → Tuple[int, int]

rip up and reroute

Returns:

Tuple[int, int]: overflow and wirelength

get_next_coordinate(current_node_coordinate: Tuple[int, int], direction: int) → Tuple[int, int]

Get next coordinate for the path, given the current node

Args:

current_node_coordinate (Tuple[int, int]): coordinate of current node direction (int): direction to next node’s coordinate

Returns:

Tuple[int, int]: next node’s coordinate

connect_net_breadth_first_search(net: Net) → None

Route a two-pin net with Breadth-First Search

This will only create L-shaped paths for all nets. This is a terrible algorithm as it doesn’t take congestion into account and might create a lot of overflow.

Args:

net (Net): two-pin net

connect_net_best_first_search_heapq(net: Net) → None

Route a two-pin net with Best-First Search

The priority queue (binary heap) stores the nodes to be expanded in ascending order of their congestion heuristic cost. At each step, the algorithm chooses the node with the lowest cost and expands it by considering all of its neighbors.

Args:

net (Net): two-pin net

update_overflow_wirelength() → None

Update overflow and wirelength for the layout

route() → None

main global routing logic

generate_congestion_output(output_file_name: str) → None

Generate the congestion data for the output

Args:

output_file_name (str): name of the output file

parse_input(input_file_path: str) → Dict

Parse the netlist input file

Args:

input_file_path (str): path of the netlist input file

Returns:

Dict: dictionary of the netlist