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:

list(Slice)

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:

str

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:
  • sink (tuple(int,int)) – (x, y)

  • heuristic_source (tuple(int,int)) – (x, y) An element from sources which is used as a guiding heuristic for the A* algorithm.

  • sources (set(tuple(int,int))) – set([(x, y), …])

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:

list(tuple(int,tuple(int,int)))

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:

RoutingTree

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:
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:

list(ApplicationEdgePartition)

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.

Parameters:

vertices (list(MachineVertex)) – The vertices to target

Returns:

A dict of (x, y) to target (cores, links)

Return type:

dict(tuple(int, int), tuple(set(int), set(int)))

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:
  • traffic (dict(tuple(int,int), int)) – A dictionary of (x, y): count of routes

  • vector (tuple(int, int, int)) – (x, y, z) The vector which the path should cover.

  • start (tuple(int, int)) –

    (x, y) The coordinates from which the path should start.

    Note

    This is a 2D coordinate.

Returns:

min route

Return type:

list(tuple(int,tuple(int, int)))

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.

Parameters:
  • vector (tuple(int,int,int)) – (x, y, z) The vector which the path should cover.

  • start (tuple(int,int)) –

    (x, y) The coordinates from which the path should start.

    Note

    This is a 2D coordinate.

Returns:

min route

Return type:

list(tuple(int,tuple(int, int)))

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.

Parameters:
  • source (tuple(int,int)) – The source x, y coordinates

  • dest (tuple(int,int)) – The destination x, y coordinates

  • machine (Machine) – The machine on which to route

Return type:

RoutingTree

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.

Parameters:

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:

bool

pacman.utilities.algorithm_utilities.routing_algorithm_utilities.route_to_endpoint(vertex: AbstractVirtual) int[source]
Parameters:

vertex (MachineVertex) –

Return type:

int

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:
  • dm_vector (list(tuple(int,int))) – A vector made up of a list of (dimension, magnitude), where dimensions are x=0, y=1, z=diagonal=2

  • start (tuple(int,int)) – The x, y coordinates of the start

Returns:

A list of (link_id, (target_x, target_y)) of nodes on a route

Return type:

list(tuple(int,tuple(int, int)))

pacman.utilities.algorithm_utilities.routing_algorithm_utilities.vertex_chip(vertex: MachineVertex) Chip[source]
Parameters:

vertex (MachineVertex) –

Return type:

Chip

pacman.utilities.algorithm_utilities.routing_algorithm_utilities.vertex_xy(vertex: MachineVertex) Tuple[int, int][source]
Parameters:

vertex (MachineVertex) –

Return type:

tuple(int,int)

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.

Parameters:

chip (tuple(int,int)) – The chip the route is currently passing through.

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 sets to store children. This was changed to lists 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))

property chip: Tuple[int, int]

The chip the route is currently passing through.

Return type:

tuple(int,int)

property is_leaf: bool
property label: str | None
remove_child(child: Tuple[int, RoutingTree | MachineVertex])[source]
Parameters:

child (tuple(int, RoutingTree or MachineVertex)) –

traverse() Iterable[Tuple[int | None, Tuple[int, int], Set[int]]][source]

Traverse the tree yielding the direction taken to a node, the coordinates of that node and the directions leading from the Node.

Returns:

A sequence of (direction, (x, y), set(route)) describing the route taken. At each step, we have the direction taken to reach a Node in the tree, the (x, y) coordinate of that Node and routes leading to children of the Node.

Return type:

iterable(tuple(int, tuple(int,int), set(int)))

Module contents