Source code for pacman.operations.router_algorithms.ner_route

# Copyright (c) 2017-2019 The University of Manchester
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
"""Neighbour Exploring Routing (NER) algorithm from J. Navaridas et al.

Algorithm refrence: J. Navaridas et al. SpiNNaker: Enhanced multicast routing,
Parallel Computing (2014).

`http://dx.doi.org/10.1016/j.parco.2015.01.002`

Based on
https://github.com/project-rig/rig/blob/master/rig/place_and_route/route/ner.py
https://github.com/project-rig/rig/blob/master/rig/geometry.py
https://github.com/project-rig/rig/blob/master/rig/place_and_route/route/utils.py
"""

import heapq
import itertools
import functools

from collections import deque, defaultdict

from spinn_utilities.progress_bar import ProgressBar
from pacman.exceptions import MachineHasDisconnectedSubRegion
from pacman.model.graphs import (
    AbstractFPGA, AbstractVirtual, AbstractSpiNNakerLink)
from pacman.model.routing_table_by_partition import (
    MulticastRoutingTableByPartition, MulticastRoutingTableByPartitionEntry)
from .routing_tree import RoutingTree


def _convert_a_route(
        routing_tables, partition, incoming_processor, incoming_link,
        partition_route):
    """
    Converts the algorithm specific partition_route back to standard spinnaker
    and ands it to the routing_tables.

    :param MulticastRoutingTableByPartition routing_tables:
        spinnaker format routing tables
    :param AbstractSingleSourcePartition partition: \
        Partition this route applies to
    :param int or None incoming_processor: processor this link came from
    :param int or None incoming_link: link this link came from
    :param RoutingTree partition_route: algorithm specific format of the route
    """
    x, y = partition_route.chip

    next_hops = list()
    processor_ids = list()
    link_ids = list()
    for (route, next_hop) in partition_route.children:
        if route is not None:
            next_incoming_link = None
            if route >= 6:
                # The route was offset as first 6 are the links
                processor_ids.append(route - 6)
            else:
                link_ids.append(route)
                next_incoming_link = (route + 3) % 6
            if isinstance(next_hop, RoutingTree):
                next_hops.append((next_hop, next_incoming_link))

    entry = MulticastRoutingTableByPartitionEntry(
        link_ids, processor_ids, incoming_processor, incoming_link)
    routing_tables.add_path_entry(entry, x, y, partition)

    for next_hop, next_incoming_link in next_hops:
        _convert_a_route(
            routing_tables, partition, None, next_incoming_link, next_hop)


def _ner_net(src, destinations, machine, vector_to_nodes):
    """ Produce a shortest path tree for a given net using NER.

    This is the kernel of the NER algorithm.

    :param tuple(int,int) source:
        The coordinate (x, y) of the source vertex.
    :param iterable(tuple(int,int)) destinations:
        The coordinates of destination vertices.
    :param ~spinn_machine.Machine machine:
        machine for which routes are being generated
    :param vector_to_nodes: ??????????
    :return:
        A RoutingTree is produced rooted at the source and visiting all
        destinations but which does not contain any vertices etc. For
        convenience, a dictionary mapping from destination (x, y) coordinates
        to the associated RoutingTree is provided to allow the caller to insert
        these items.
    :rtype: tuple(RoutingTree, dict(tuple(int,int),RoutingTree))
    """
    radius = 20
    # Map from (x, y) to RoutingTree objects
    route = {src: RoutingTree(src)}

    # Handle each destination, sorted by distance from the source, closest
    # first.
    sorted_dest = sorted(
        destinations, key=(lambda dest: machine.get_vector_length(src, dest)))
    for destination in sorted_dest:
        # We shall attempt to find our nearest neighbouring placed node.
        neighbour = None

        # Try to find a nearby (within radius hops) node in the routing tree
        # that we can route to (falling back on just routing to the source).
        #
        # This implementation scans the list of all route nodes created so far
        # and finds the closest node which is < radius hops
        # (falling back on the origin if no node is closer than radius hops).

        neighbour = None
        neighbour_distance = None
        for candidate_neighbour in route:
            distance = machine.get_vector_length(
                candidate_neighbour, destination)
            if distance <= radius and (
                    neighbour is None or distance < neighbour_distance):
                neighbour = candidate_neighbour
                neighbour_distance = distance

        # Fall back on routing directly to the source if no nodes within radius
        # hops of the destination was found.
        if neighbour is None:
            neighbour = src

        # Find the shortest vector from the neighbour to this destination
        vector = machine.get_vector(neighbour, destination)

        # The route may inadvertently pass through an
        # already connected node. If the route is allowed to pass through that
        # node it would create a cycle in the route which would be VeryBad(TM).
        # As a result, we work backward through the route and truncate it at
        # the first point where the route intersects with a connected node.
        nodes = vector_to_nodes(vector, neighbour, machine)
        i = len(nodes)
        for direction, (x, y) in reversed(nodes):
            i -= 1
            if (x, y) in route:
                # We've just bumped into a node which is already part of the
                # route, this becomes our new neighbour and we truncate the LDF
                # route. (Note ldf list is truncated just after the current
                # position since it gives (direction, destination) pairs).
                neighbour = (x, y)
                nodes = nodes[i + 1:]
                break

        # Take the longest dimension first route.
        last_node = route[neighbour]
        for direction, (x, y) in nodes:
            this_node = RoutingTree((x, y))
            route[(x, y)] = this_node

            last_node.append_child((direction, this_node))
            last_node = this_node

    return route[src], route


def _is_linked(source, target, direction, machine):
    """
    :param tuple(int,int) source:
    :param tuple(int,int) target:
    :param int direction:
    :param ~spinn_machine.Machine machine:
    :rtype: bool
    """
    s_chip = machine.get_chip_at(source[0], source[1])
    if s_chip is None:
        return False
    link = s_chip.router.get_link(direction)
    if link is None:
        return False
    if link.destination_x != target[0]:
        return False
    if link.destination_y != target[1]:
        return False
    return True


def _copy_and_disconnect_tree(root, machine):
    """
    Copy a RoutingTree (containing nothing but RoutingTrees), disconnecting
    nodes which are not connected in the machine.

    Note that if a dead chip is part of the input RoutingTree, no corresponding
    node will be included in the copy. The assumption behind this is that the
    only reason a tree would visit a dead chip is because a route passed
    through the chip and wasn't actually destined to arrive at that chip. This
    situation is impossible to confirm since the input routing trees have not
    yet been populated with vertices. The caller is responsible for being
    sensible.

    :param RoutingTree root:
        The root of the RoutingTree that contains nothing but RoutingTrees
        (i.e. no children which are vertices or links).
    :param ~spinn_machine.Machine machine:
        The machine in which the routes exist
    :return: (root, lookup, broken_links)
        Where:
        * `root` is the new root of the tree
          :py:class:`~.RoutingTree`
        * `lookup` is a dict {(x, y):
          :py:class:`~.RoutingTree`, ...}
        * `broken_links` is a set ([(parent, child), ...]) containing all
          disconnected parent and child (x, y) pairs due to broken links.
    :rtype: tuple(RoutingTree, dict(tuple(int,int),RoutingTree),
        set(tuple(tuple(int,int),tuple(int,int))))
    """
    new_root = None

    # Lookup for copied routing tree {(x, y): RoutingTree, ...}
    new_lookup = {}

    # List of missing connections in the copied routing tree [(new_parent,
    # new_child), ...]
    broken_links = set()

    # A queue [(new_parent, direction, old_node), ...]
    to_visit = deque([(None, None, root)])
    while to_visit:
        new_parent, direction, old_node = to_visit.popleft()

        if machine.is_chip_at(old_node.chip[0], old_node.chip[1]):
            # Create a copy of the node
            new_node = RoutingTree(old_node.chip)
            new_lookup[new_node.chip] = new_node
        else:
            # This chip is dead, move all its children into the parent node
            assert new_parent is not None, \
                "Net cannot be sourced from a dead chip."
            new_node = new_parent

        if new_parent is None:
            # This is the root node
            new_root = new_node
        else:
            if new_node is not new_parent:
                # If this node is not dead, check connectivity to parent
                # node (no reason to check connectivity between a dead node
                # and its parent).
                if _is_linked(
                        new_parent.chip, new_node.chip, direction, machine):
                    # Is connected via working link
                    new_parent.append_child((direction, new_node))
                else:
                    # Link to parent is dead (or original parent was dead and
                    # the new parent is not adjacent)
                    broken_links.add((new_parent.chip, new_node.chip))

        # Copy children
        for child_direction, child in old_node.children:
            to_visit.append((new_node, child_direction, child))

    return new_root, new_lookup, broken_links


def _a_star(sink, heuristic_source, sources, machine):
    """ Use A* to find a path from any of the sources to the sink.

    Note that 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.

    :param tuple(int,int) sink: (x, y)
    :param tuple(int,int) heuristic_source: (x, y)
        An element from `sources` which is used as a guiding heuristic for the
        A* algorithm.
    :param set(tuple(int,int)) sources: set([(x, y), ...])
    :param ~spinn_machine.Machine machine:
    :return: [(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.
    :rtype: list(tuple(int,tuple(int,int)))
    """
    # Select the heuristic function to use for distances
    heuristic = (lambda the_node: machine.get_vector_length(
        the_node, heuristic_source))

    # A dictionary {node: (direction, previous_node}. An entry indicates that
    # 1) the node has been visited and 2) which node we hopped from (and the
    # direction used) to reach previous_node.  This may be None if the node is
    # the sink.
    visited = {sink: None}

    # The node which the tree will be reconnected to
    selected_source = None

    # A heap (accessed via heapq) of (distance, (x, y)) where distance is the
    # distance between (x, y) and heuristic_source and (x, y) is a node to
    # explore.
    to_visit = [(heuristic(sink), sink)]
    while to_visit:
        _, node = heapq.heappop(to_visit)

        # Terminate if we've found the destination
        if node in sources:
            selected_source = node
            break

        # Try all neighbouring locations.
        for neighbour_link in range(6):  # Router.MAX_LINKS_PER_ROUTER
            # Note: link identifiers arefrom the perspective of the neighbour,
            # not the current node!
            neighbour = machine.xy_over_link(
                #                  Same as Router.opposite
                node[0], node[1], (neighbour_link + 3) % 6)

            # Skip links which are broken
            if not machine.is_link_at(
                    neighbour[0], neighbour[1], neighbour_link):
                continue

            # Skip neighbours who have already been visited
            if neighbour in visited:
                continue

            # Explore all other neighbours
            visited[neighbour] = (neighbour_link, node)
            heapq.heappush(to_visit, (heuristic(neighbour), neighbour))

    # Fail of no paths exist
    if selected_source is None:
        raise MachineHasDisconnectedSubRegion(
            "Could not find path from {} to {}".format(
                sink, heuristic_source))

    # Reconstruct the discovered path, starting from the source we found and
    # working back until the sink.
    path = [(visited[selected_source][0], selected_source)]
    while visited[path[-1][1]][1] != sink:
        node = visited[path[-1][1]][1]
        direction = visited[node][0]
        path.append((direction, node))

    return path


def _route_has_dead_links(root, machine):
    """ Quickly determine if a route uses any dead links.

    :param RoutingTree root:
        The root of the RoutingTree which contains nothing but RoutingTrees
        (i.e. no vertices and links).
    :param ~spinn_machine.Machine machine:
        The machine in which the routes exist.
    :return: True if the route uses any dead/missing links, False otherwise.
    :rtype: bool
    """
    for _, (x, y), routes in root.traverse():
        chip = machine.get_chip_at(x, y)
        for route in routes:
            if chip is None:
                return True
            if not chip.router.is_link(route):
                return True
    return False


def _avoid_dead_links(root, machine):
    """ 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).

    :param RoutingTree root:
        The root of the RoutingTree which contains nothing but RoutingTrees
        (i.e. no vertices and links).
    :param ~spinn_machine.Machine machine:
        The machine in which the routes exist.
    :return:
        A new RoutingTree is produced rooted as before. A dictionary mapping
        from (x, y) to the associated RoutingTree is provided for convenience
    :rtype: tuple(RoutingTree,dict(tuple(int,int),RoutingTree))
    """
    # Make a copy of the RoutingTree with all broken parts disconnected
    root, lookup, broken_links = _copy_and_disconnect_tree(root, machine)

    # For each disconnected subtree, use A* to connect the tree to *any* other
    # disconnected subtree. Note that this process will eventually result in
    # all disconnected subtrees being connected, the result is a fully
    # connected tree.
    for parent, child in broken_links:
        child_chips = set(c.chip for c in lookup[child])

        # Try to reconnect broken links to any other part of the tree
        # (excluding this broken subtree itself since that would create a
        # cycle).
        path = _a_star(child, parent,
                       set(lookup).difference(child_chips),
                       machine)
        # Add new RoutingTree nodes to reconnect the child to the tree.
        last_node = lookup[path[0][1]]
        last_direction = path[0][0]
        for direction, (x, y) in path[1:]:
            if (x, y) not in child_chips:
                # This path segment traverses new ground so we must create a
                # new RoutingTree for the segment.
                new_node = RoutingTree((x, y))
                # A* will not traverse anything but chips in this tree so this
                # assert is meerly a sanity check that this occurred correctly.
                assert (x, y) not in lookup, "Cycle created."
                lookup[(x, y)] = new_node
            else:
                # This path segment overlaps part of the disconnected tree
                # (A* doesn't know where the disconnected tree is and thus
                # doesn't avoid it). To prevent cycles being introduced, this
                # overlapped node is severed from its parent and merged as part
                # of the A* path.
                new_node = lookup[(x, y)]

                # Find the node's current parent and disconnect it.
                for node in lookup[child]:  # pragma: no branch
                    dn = [(d, n) for d, n in node.children if n == new_node]
                    assert len(dn) <= 1
                    if dn:
                        node.remove_child(dn[0])
                        # A node can only have one parent so we can stop now.
                        break
            last_node.append_child((last_direction, new_node))
            last_node = new_node
            last_direction = direction
        last_node.append_child((last_direction, lookup[child]))

    return root, lookup


def _do_route(source_vertex, post_vertexes, machine, placements,
              vector_to_nodes):
    """ Routing algorithm based on Neighbour Exploring Routing (NER).

    Algorithm refrence: J. Navaridas et al. SpiNNaker: Enhanced multicast
    routing, Parallel Computing (2014).
    http://dx.doi.org/10.1016/j.parco.2015.01.002

    This algorithm attempts to use NER to generate routing trees for all nets
    and routes around broken links using A* graph search. If the system is
    fully connected, this algorithm will always succeed though no consideration
    of congestion or routing-table usage is attempted.

    :param MachineVertex source_vertex:
    :param iterable(MachineVertex) post_vertexes:
    :param ~spinn_machine.Machine machine:
    :param Placements placements:
    :param vector_to_nodes:
    :return:
    :rtype: RoutingTree
    """
    source_xy = _vertex_xy(source_vertex, placements, machine)
    destinations = set(_vertex_xy(post_vertex, placements, machine)
                       for post_vertex in post_vertexes)
    # Generate routing tree (assuming a perfect machine)
    root, lookup = _ner_net(source_xy, destinations, machine, vector_to_nodes)

    # Fix routes to avoid dead chips/links
    if _route_has_dead_links(root, machine):
        root, lookup = _avoid_dead_links(root, machine)

    # Add the sinks in the net to the RoutingTree
    for post_vertex in post_vertexes:
        tree_node = lookup[_vertex_xy(post_vertex, placements, machine)]
        if isinstance(post_vertex, AbstractVirtual):
            # Sinks with route-to-endpoint constraints must be routed
            # in the according directions.
            route = _route_to_endpoint(post_vertex, machine)
            tree_node.append_child((route, post_vertex))
        else:
            core = placements.get_placement_of_vertex(post_vertex).p
            if core is not None:
                #  Offset the core by 6 as first 6 are the links
                tree_node.append_child((core + 6, post_vertex))
            else:
                # Sinks without that resource are simply included without
                # an associated route
                tree_node.append_child((None, post_vertex))

    return root


def _vertex_xy(vertex, placements, machine):
    """
    :param MachineVertex vertex:
    :param Placements placements:
    :param ~spinn_machine.Machine machine:
    :rtype: tuple(int,int)
    """
    if not isinstance(vertex, AbstractVirtual):
        placement = placements.get_placement_of_vertex(vertex)
        return placement.x, placement.y
    link_data = None
    if isinstance(vertex, AbstractFPGA):
        link_data = machine.get_fpga_link_with_id(
            vertex.fpga_id, vertex.fpga_link_id, vertex.board_address)
    elif isinstance(vertex, AbstractSpiNNakerLink):
        link_data = machine.get_spinnaker_link_with_id(
            vertex.spinnaker_link_id, vertex.board_address)
    return link_data.connected_chip_x, link_data.connected_chip_y


def _route_to_endpoint(vertex, machine):
    """
    :param MachineVertex vertex:
    :param ~spinn_machine.Machine machine:
    :rtype: int
    """
    if isinstance(vertex, AbstractFPGA):
        link_data = machine.get_fpga_link_with_id(
            vertex.fpga_id, vertex.fpga_link_id, vertex.board_address)
    else:
        link_data = machine.get_spinnaker_link_with_id(
            vertex.spinnaker_link_id, vertex.board_address)
    return link_data.connected_link


def _least_busy_dimension_first(traffic, vector, start, machine):
    """ List the (x, y) steps on a route that goes through the least busy\
        routes first.

    :param traffic: A dictionary of (x, y): count of routes
    :param vector: (x, y, z)
        The vector which the path should cover.
    :param start: (x, y)
        The coordinates from which the path should start (note this is a 2D
        coordinate).
    :param machine:the spinn machine.
    :return: min route
    """

    # Go through and find the sum of traffic depending on the route taken
    min_sum = 0
    min_route = None
    for order in itertools.permutations([0, 1, 2]):
        dm_vector = [(i, vector[i]) for i in order]
        route = _get_route(dm_vector, start, machine)
        sum_traffic = sum(traffic[x, y] for _, (x, y) in route)
        if min_route is None or min_sum > sum_traffic:
            min_sum = sum_traffic
            min_route = route

    for _, (x, y) in min_route:
        traffic[x, y] += 1

    return min_route


def _longest_dimension_first(vector, start, machine):
    """
    List the (x, y) steps on a longest-dimension first route.

    :param tuple(int,int,int) vector: (x, y, z)
        The vector which the path should cover.
    :param tuple(int,int) start: (x, y)
        The coordinates from which the path should start (note this is a 2D
        coordinate).
    :param ~spinn_machine.Machine machine:
    :return:
    :rtype: list(tuple(int,int))
    """
    return _get_route(
        sorted(enumerate(vector), key=(lambda x: abs(x[1])), reverse=True),
        start, machine)


def _get_route(dm_vector, start, machine):
    x, y = start

    out = []

    for dimension, magnitude in dm_vector:
        if magnitude == 0:
            continue

        if dimension == 0:  # x
            if magnitude > 0:
                # Move East (0) magnitude times
                for _ in range(magnitude):
                    x, y = machine.xy_over_link(x, y, 0)
                    out.append((0, (x, y)))
            else:
                # Move West (3) -magnitude times
                for _ in range(magnitude, 0):
                    x, y = machine.xy_over_link(x, y, 3)
                    out.append((3, (x, y)))
        elif dimension == 1:  # y
            if magnitude > 0:
                # Move North (2) magnitude times
                for _ in range(magnitude):
                    x, y = machine.xy_over_link(x, y, 2)
                    out.append((2, (x, y)))
            else:
                # Move South (5) -magnitude times
                for _ in range(magnitude, 0):
                    x, y = machine.xy_over_link(x, y, 5)
                    out.append((5, (x, y)))
        else:  # z
            if magnitude > 0:
                # Move SouthWest (4) magnitude times
                for _ in range(magnitude):
                    x, y = machine.xy_over_link(x, y, 4)
                    out.append((4, (x, y)))
            else:
                # Move NorthEast (1) -magnitude times
                for _ in range(magnitude, 0):
                    x, y = machine.xy_over_link(x, y, 1)
                    out.append((1, (x, y)))
    return out


def _ner_route(machine_graph, machine, placements, vector_to_nodes):
    """ Performs routing using rig algorithm

    :param MachineGraph machine_graph:
    :param ~spinn_machine.Machine machine:
    :param Placements placements:
    :return:
    :rtype: MulticastRoutingTableByPartition
    """
    routing_tables = MulticastRoutingTableByPartition()

    progress_bar = ProgressBar(len(machine_graph.vertices), "Routing")

    for source_vertex in progress_bar.over(machine_graph.vertices):
        # handle the vertex edges
        for partition in machine_graph.\
                get_multicast_edge_partitions_starting_at_vertex(
                    source_vertex):
            post_vertexes = list(
                e.post_vertex for e in partition.edges)
            routing_tree = _do_route(
                source_vertex, post_vertexes, machine, placements,
                vector_to_nodes)
            incoming_processor = placements.get_placement_of_vertex(
                partition.pre_vertex).p
            _convert_a_route(
                routing_tables, partition, incoming_processor, None,
                routing_tree)

    progress_bar.end()

    return routing_tables


[docs]class NerRoute(object): """ Performs routing using rig algorithm """ __slots__ = []
[docs] def __call__(self, machine_graph, machine, placements): """ basic ner router :param MachineGraph machine_graph: the machine graph :param ~spinn_machine.Machine machine: spinnaker machine :param Placements placements: the placements :return: a routing table by partition :rtype: MulticastRoutingTableByPartition """ return _ner_route( machine_graph, machine, placements, _longest_dimension_first)
[docs]class NerRouteTrafficAware(object): """ Performs routing with traffic awareness """ __slots__ = []
[docs] def __call__(self, machine_graph, machine, placements): """ traffic-aware ner router :param MachineGraph machine_graph: the machine graph :param ~spinn_machine.Machine machine: spinnaker machine :param Placements placements: the placements :return: a routing table by partition :rtype: MulticastRoutingTableByPartition """ traffic = defaultdict(lambda: 0) return _ner_route( machine_graph, machine, placements, functools.partial(_least_busy_dimension_first, traffic))