pacman.utilities.algorithm_utilities package¶
Submodules¶
pacman.utilities.algorithm_utilities.partition_algorithm_utilities module¶
A collection of methods which support partitioning algorithms.
- pacman.utilities.algorithm_utilities.partition_algorithm_utilities.get_multidimensional_slices(app_vertex: ApplicationVertex) List[Slice] [source]¶
Get the multi-dimensional slices of an application vertex such that each is sized to the maximum atoms per dimension per core except the last, which might be smaller in one or more dimensions.
- Parameters:
app_vertex (ApplicationVertex) – The vertex to get the slices of
- Returns:
The slices
- Return type:
- pacman.utilities.algorithm_utilities.partition_algorithm_utilities.get_single_dimension_slices(app_vertex: ApplicationVertex) List[Slice] [source]¶
- Get the single dimension slices of an application vertex
such that each is sized to the maximum atoms per dimension per core except the last which might be smaller in one or more dimensions
- Parameters:
app_vertex (ApplicationVertex) – The vertex to get the slices of
pacman.utilities.algorithm_utilities.routes_format module¶
- pacman.utilities.algorithm_utilities.routes_format.format_route(entry: MulticastRoutingEntry) str [source]¶
How to render a single routing entry.
- Parameters:
entry (MulticastRoutingEntry) –
- Return type:
pacman.utilities.algorithm_utilities.routing_algorithm_utilities module¶
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.a_star(sink: Tuple[int, int], heuristic_source: Tuple[int, int], sources: Set[Tuple[int, int]]) List[Tuple[int, Tuple[int, int]]] [source]¶
Use A* to find a path from any of the sources to the sink.
Note
The heuristic means that the search will proceed towards heuristic_source without any concern for any other sources. This means that the algorithm may miss a very close neighbour in order to pursue its goal of reaching heuristic_source. This is not considered a problem since 1) the heuristic source will typically be in the direction of the rest of the tree and near by and often the closest entity 2) it prevents us accidentally forming loops in the rest of the tree since we’ll stop as soon as we touch any part of it.
- Parameters:
- Returns:
[(int, (x, y)), …] A path starting with a coordinate in sources and terminating at connected neighbour of sink (i.e. the path does not include sink). The direction given is the link down which to proceed from the given (x, y) to arrive at the next point in the path.
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.avoid_dead_links(root: RoutingTree) RoutingTree [source]¶
Modify a RoutingTree to route-around dead links in a Machine.
Uses A* to reconnect disconnected branches of the tree (due to dead links in the machine).
- Parameters:
root (RoutingTree) – The root of the RoutingTree which contains nothing but RoutingTrees (i.e. no vertices and links).
- Returns:
A new RoutingTree is produced rooted as before.
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.convert_a_route(routing_tables: MulticastRoutingTableByPartition, source_vertex: AbstractVertex, partition_id: str, incoming_processor: int | None, incoming_link: int | None, route_tree: RoutingTree, targets_by_chip: Dict[Tuple[int, int], Tuple[Set[int], Set[int]]])[source]¶
Converts the algorithm specific partition_route back to standard SpiNNaker and adds it to the routing_tables.
- Parameters:
routing_tables (MulticastRoutingTableByPartition) – SpiNNaker-format routing tables
partition (AbstractSingleSourcePartition) – Partition this route applies to
incoming_processor (int or None) – processor this link came from
incoming_link (int or None) – link this link came from
route_tree (RoutingTree) – algorithm specific format of the route
targets_by_chip (dict((int,int),(list(int),list(int)))) – Target cores and links of things on the route that are final end points
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.get_app_partitions() List[ApplicationEdgePartition] [source]¶
Find all application partitions.
Note
Where a vertex splitter indicates that it has internal partitions but is not the source of an external partition, a “fake” empty application partition is added. This allows the calling algorithm to loop over the returned list and look at the set of edges and internal partitions to get a complete picture of all targets for each source machine vertex at once.
- Returns:
list of partitions
Note
Where there are only internal multicast partitions, the partition will have no edges. Caller should use vertex.splitter.get_internal_multicast_partitions for details.
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.get_targets_by_chip(vertices: Iterable[MachineVertex]) Dict[Tuple[int, int], Tuple[Set[int], Set[int]]] [source]¶
Get the target links and cores on the relevant chips.
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.least_busy_dimension_first(traffic: Dict[Tuple[int, int], int], vector: Tuple[int, int, int], start: Tuple[int, int]) List[Tuple[int, Tuple[int, int]]] [source]¶
List the (x, y) steps on a route that goes through the least busy routes first.
- Parameters:
- Returns:
min route
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.longest_dimension_first(vector: Tuple[int, int, int], start: Tuple[int, int]) List[Tuple[int, Tuple[int, int]]] [source]¶
List the (x, y) steps on a longest-dimension first route.
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.most_direct_route(source: Tuple[int, int], dest: Tuple[int, int], machine: Machine) RoutingTree [source]¶
Find the most direct route from source to target on the machine.
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.nodes_to_trees(nodes: List[Tuple[int, Tuple[int, int]]], start: Tuple[int, int], route: Dict[Tuple[int, int], RoutingTree])[source]¶
Convert a list of nodes into routing trees, adding them to existing routes.
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.route_has_dead_links(root: RoutingTree) bool [source]¶
Quickly determine if a route uses any dead links.
- Parameters:
root (RoutingTree) – The root of the RoutingTree which contains nothing but RoutingTrees (i.e. no vertices and links).
- Returns:
True if the route uses any dead/missing links, False otherwise.
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.route_to_endpoint(vertex: AbstractVirtual) int [source]¶
- Parameters:
vertex (MachineVertex) –
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.vector_to_nodes(dm_vector: List[Tuple[int, int]], start: Tuple[int, int]) List[Tuple[int, Tuple[int, int]]] [source]¶
Convert a vector to a set of nodes.
- Parameters:
- Returns:
A list of (link_id, (target_x, target_y)) of nodes on a route
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.vertex_chip(vertex: MachineVertex) Chip [source]¶
- Parameters:
vertex (MachineVertex) –
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.vertex_xy(vertex: MachineVertex) Tuple[int, int] [source]¶
- Parameters:
vertex (MachineVertex) –
- Return type:
- pacman.utilities.algorithm_utilities.routing_algorithm_utilities.vertex_xy_and_route(vertex: MachineVertex) Tuple[Tuple[int, int], Tuple[MachineVertex, int | None, int | None]] [source]¶
Get the non-virtual chip coordinates, the vertex, and processor or link to follow to get to the vertex.
- Parameters:
vertex (MachineVertex) –
- Returns:
the (x,y) coordinates of the target vertex mapped to a tuple of the vertex, core and link. One of core or link is provided the other is None
- Return type:
tuple(tuple(int, int), tuple(MachineVertex, int, None)) or tuple(tuple(int, int), tuple(MachineVertex, None, int))
pacman.utilities.algorithm_utilities.routing_tree module¶
An explicit representation of a routing tree in a machine.
This representation of a route explicitly describes a tree-structure and the complete path taken by a route. This is used during place and route in preference to a set of RoutingTableEntry tuples since it is more easily verified and more accurately represents the problem at hand.
Based on https://github.com/project-rig/rig/blob/master/rig/place_and_route/routing_tree.py
- class pacman.utilities.algorithm_utilities.routing_tree.RoutingTree(chip: Tuple[int, int], label: str | None = None)[source]¶
Bases:
object
Explicitly defines a multicast route through a SpiNNaker machine.
Each instance represents a single hop in a route and recursively refers to following steps.
- append_child(child: Tuple[int, RoutingTree | MachineVertex])[source]¶
- Parameters:
child (tuple(int, RoutingTree or MachineVertex)) –
- property children: Iterable[Tuple[int, RoutingTree | MachineVertex]]¶
A
iterable
of the next steps in the route represented by a (route, object) tuple.Note
Up until Rig 1.5.1, this structure used
set
s to store children. This was changed tolist
s since sets incur a large memory overhead and in practice the set-like behaviour of the list of children is not useful.The object indicates the intended destination of this step in the route. It may be one of:
RoutingTree
representing the continuation of the routing tree after following a given link.A vertex (i.e. some other Python object) when the route terminates at the supplied vertex.
Note
The direction may be None and so additional logic may be required to determine what core to target to reach the vertex.
- Return type:
iterable(tuple(int, RoutingTree or MachineVertex))
- remove_child(child: Tuple[int, RoutingTree | MachineVertex])[source]¶
- Parameters:
child (tuple(int, RoutingTree or MachineVertex)) –