Source code for pacman.operations.placer_algorithms.spreader_placer

# 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/>.

from collections import defaultdict
import functools
import math
import sys
from spinn_utilities.progress_bar import ProgressBar
from pacman.model.placements import Placement, Placements
from pacman.operations.placer_algorithms import OneToOnePlacer
from pacman.utilities.algorithm_utilities.placer_algorithm_utilities import (
    create_vertices_groups, get_same_chip_vertex_groups,
    create_requirement_collections)
from pacman.utilities.utility_objs import ResourceTracker
from pacman.model.constraints.placer_constraints import (
    SameChipAsConstraint, ChipAndCoreConstraint)


[docs]class SpreaderPlacer(OneToOnePlacer): """ Places vertices on as many chips as available with a effort to\ reduce the number of packets being received by the router in total. :param MachineGraph machine_graph: the machine graph :param ~spinn_machine.Machine machine: the SpiNNaker machine :param AbstractMachinePartitionNKeysMap n_keys_map: the n keys from partition map :param int plan_n_timesteps: number of timesteps to plan for :return: placements. :rtype: Placements """ # number of cycles over the machine graph ( # 1. same chip, # 2. 1 to 1, # 3. sort left overs # 4 left overs) ITERATIONS = 4 # distinct steps ( # 1. check constraints, # 2. same chip sets, # 3. 1 to 1 sets, # 4. chip and core) STEPS = 4
[docs] def __call__(self, machine_graph, machine, n_keys_map, plan_n_timesteps): """ :param MachineGraph machine_graph: the machine graph :param ~spinn_machine.Machine machine: the SpiNNaker machine :param AbstractMachinePartitionNKeysMap n_keys_map: the n keys from partition map :param int plan_n_timesteps: number of timesteps to plan for :return: placements. :rtype: Placements """ # create progress bar progress_bar = ProgressBar( (machine_graph.n_vertices * self.ITERATIONS) + self.STEPS, "Placing graph vertices via spreading over an entire machine") # check that the algorithm can handle the constraints self._check_constraints( machine_graph.vertices, additional_placement_constraints={SameChipAsConstraint}) progress_bar.update() # get same chip groups same_chip_vertex_groups = get_same_chip_vertex_groups(machine_graph) progress_bar.update() # get chip and core placed verts hard_chip_constraints = self._locate_hard_placement_verts( machine_graph) progress_bar.update() # get one to one groups one_to_one_groups = create_vertices_groups( machine_graph.vertices, functools.partial( self._find_one_to_one_vertices, graph=machine_graph)) progress_bar.update() # sort chips so that they are radial from a given point and other # init data structs chips_in_order = self._determine_chip_list(machine) resource_tracker = ResourceTracker( machine, plan_n_timesteps, chips=chips_in_order) placements = Placements() placed_vertices = set() cost_per_chip = defaultdict(int) progress_bar.update() # allocate hard ones for hard_vertex in hard_chip_constraints: (x, y, p, _, _) = resource_tracker.allocate_constrained_resources( hard_vertex.resources_required, hard_vertex.constraints) placements.add_placement(Placement(hard_vertex, x, y, p)) placed_vertices.add(hard_vertex) cost_per_chip[x, y] += self._get_cost( hard_vertex, machine_graph, n_keys_map) # place groups of verts that need the same chip on the same chip, self._place_same_chip_verts( same_chip_vertex_groups, chips_in_order, placements, progress_bar, resource_tracker, placed_vertices, cost_per_chip, machine_graph, n_keys_map) # place 1 group per chip if possible on same chip as any already # placed verts. if not then radially from it. self._place_one_to_one_verts( one_to_one_groups, chips_in_order, placements, progress_bar, resource_tracker, placed_vertices, cost_per_chip, machine_graph, n_keys_map, machine) # place vertices which don't have annoying placement constraints. # spread them over the chips so that they have minimal impact on the # overall incoming packet cost per router. self._place_left_over_verts( machine_graph, chips_in_order, placements, progress_bar, resource_tracker, placed_vertices, cost_per_chip, n_keys_map) progress_bar.end() # return the built placements return placements
def _sort_left_over_verts_based_on_incoming_packets( self, machine_graph, placed_vertices, n_keys_map): """ sort left overs verts so that the ones with the most costly verts are at the front of the list :param MachineGraph machine_graph: machine graph :param set(MachineVertex) placed_vertices: the verts already placed :param AbstractMachinePartitionNKeysMap n_keys_map: map between partition to n keys. :return: new list of verts to process. :rtype: list(MachineVertex) """ vert_list = list() incoming_size_map = defaultdict(list) for vertex in machine_graph.vertices: if vertex not in placed_vertices: incoming_size = self._get_cost( vertex, machine_graph, n_keys_map) incoming_size_map[incoming_size].append(vertex) sorted_keys = sorted(incoming_size_map.keys(), reverse=True) for key in sorted_keys: vert_list.extend(incoming_size_map[key]) return vert_list @staticmethod def _sort_chips_based_off_incoming_cost(chips, cost_per_chip): """ sorts chips out so that the chip in front has least incoming cost. :param list(tuple(int,int)) chips: iterable of chips to sort :param cost_per_chip: the map of (x,y) and cost. :type cost_per_chip: dict(tuple(int, int), int) :return: iterable of chips in a sorted fashion. :rtype: list(tuple(int,int)) """ data = sorted(chips, key=lambda chip: cost_per_chip[chip[0], chip[1]]) return data @staticmethod def _get_cost(vertex, machine_graph, n_keys_map): """ gets how many packets are to be processed by a given vertex. :param MachineVertex vertex: the vertex the get the cost of :param MachineGraph machine_graph: the machine graph :param AbstractMachinePartitionNKeysMap n_keys_map: the map of outgoing partition and n keys down it. :return: total keys to come into this vertex. :rtype: int """ # NOTE we going to assume as a worst case scenario that every key is # sent every time step. but this is obviously not valid often # handle incoming total_incoming_keys = 0 for incoming_partition in \ machine_graph.get_multicast_edge_partitions_ending_at_vertex( vertex): total_incoming_keys += n_keys_map.n_keys_for_partition( incoming_partition) # handle outgoing out_going_partitions = \ machine_graph.get_multicast_edge_partitions_starting_at_vertex( vertex) for partition in out_going_partitions: total_incoming_keys += \ n_keys_map.n_keys_for_partition(partition) return total_incoming_keys @staticmethod def _locate_hard_placement_verts(machine_graph): """ locates the verts with hard constraints :param MachineGraph machine_graph: the machine graph :return: list of verts to just place where they demand it :rtype: list(MachineVertex) """ hard_verts = list() for vertex in machine_graph.vertices: for constraint in vertex.constraints: if isinstance(constraint, ChipAndCoreConstraint): hard_verts.append(vertex) return hard_verts def _place_same_chip_verts( self, same_chip_vertex_groups, chips_in_order, placements, progress_bar, resource_tracker, placed_vertices, cost_per_chip, machine_graph, n_keys_map): """ places verts which have to be on the same chip on minimum chip. :param same_chip_vertex_groups: groups of verts which want to be on the same chip. :type same_chip_vertex_groups: dict(MachineVertex, set(MachineVertex)) :param chips_in_order: chips in radial order from mid machine :type chips_in_order: iterable(tuple(int,int)) :param Placements placements: placements holder :param ~spinn_utilities.progress_bar.ProgressBar progress_bar: progress bar :param ResourceTracker resource_tracker: resource tracker :param set(MachineVertex) placed_vertices: vertices which have already been placed :param cost_per_chip: map between (x,y) and the cost of packets :type cost_per_chip: dict(tuple(int, int), int) :param MachineGraph machine_graph: :param AbstractMachinePartitionNKeysMap n_keys_map: :rtype: None """ for vertex in same_chip_vertex_groups.keys(): if len(same_chip_vertex_groups[vertex]) != 1: if vertex not in placed_vertices: to_do_as_group = list() for other_vert in same_chip_vertex_groups[vertex]: if other_vert not in placed_vertices: to_do_as_group.extend( create_requirement_collections( [other_vert], machine_graph)) # allocate as a group to sorted chips so that ones with # least incoming packets are considered first results = \ resource_tracker.allocate_constrained_group_resources( to_do_as_group, chips=chips_in_order) # create placements and add cost to the chip for (x, y, p, _, _), placed_vertex in zip( results, same_chip_vertex_groups[vertex]): placements.add_placement( Placement(placed_vertex, x, y, p)) placed_vertices.add(placed_vertex) cost_per_chip[x, y] += self._get_cost( placed_vertex, machine_graph, n_keys_map) # resort the chips, as no idea where in the list the resource # tracker selected chips_in_order = self._sort_chips_based_off_incoming_cost( chips_in_order, cost_per_chip) # update progress bar to cover one cycle of all the verts in the graph progress_bar.update(len(machine_graph.vertices)) def _place_one_to_one_verts( self, one_to_one_groups, chips_in_order, placements, progress_bar, resource_tracker, placed_vertices, cost_per_chip, machine_graph, n_keys_map, machine): """ place 1 to 1 groups on the same chip if possible. else radially\ from it :param one_to_one_groups: the 1 to 1 groups :type one_to_one_groups: iterable(iterable(MachineVertex)) :param chips_in_order: chips in sorted order of lowest cost :type chips_in_order: iterable(tuple(int,int)) :param Placements placements: placements holder :param ~spinn_utilities.progress_bar.ProgressBar progress_bar: the progress bar :param ResourceTracker resource_tracker: the resource tracker :param set(MachineVertex) placed_vertices: the verts already placed :param cost_per_chip: map of (x,y) and the incoming packet cost :type cost_per_chip: dict(tuple(int, int), int) :param MachineGraph machine_graph: machine graph :param AbstractMachinePartitionNKeysMap n_keys_map: map between outgoing partition and n keys down it :param ~spinn_machine.Machine machine: the SpiNNMachine instance. """ # go through each 1 to 1 group separately for group in one_to_one_groups: # find which cores have already been allocated or not unallocated = list() allocated = list() for one_to_one_vertex in group: if one_to_one_vertex not in placed_vertices: unallocated.append(one_to_one_vertex) else: allocated.append(one_to_one_vertex) # if allocated, then locate which chip to start search at chips = chips_in_order if len(allocated) != 0: x = None y = None all_matched = True # determine if the placed ones are all in the same chip. else # it doesnt matter. for vertex in allocated: placement = placements.get_placement_of_vertex(vertex) if x is None and y is None: x = placement.x y = placement.y else: if x != placement.x or y != placement.y: all_matched = False # order chips so that shared chip is first, and the rest are # nearby it in order. or if not all same, just least first if all_matched: chips = list(self._generate_radial_chips( machine, resource_tracker=None, start_chip_x=x, start_chip_y=y)) # allocate verts. for one_to_one_vertex in unallocated: (x, y, p, _, _) = \ resource_tracker.allocate_constrained_resources( one_to_one_vertex.resources_required, one_to_one_vertex.constraints, chips=chips) # add to placed tracker placed_vertices.add(one_to_one_vertex) # make placement placements.add_placement(Placement( vertex=one_to_one_vertex, x=x, y=y, p=p)) # update cost cost_per_chip[x, y] += self._get_cost( one_to_one_vertex, machine_graph, n_keys_map) # sort chips for the next group cycle chips_in_order = self._sort_chips_based_off_incoming_cost( chips, cost_per_chip) # update progress bar to cover one cycle of all the verts in the graph progress_bar.update(len(machine_graph.vertices)) def _place_left_over_verts( self, machine_graph, chips_in_order, placements, progress_bar, resource_tracker, placed_vertices, cost_per_chip, n_keys_map): """ places left over vertices in locations with least costs. :param MachineGraph machine_graph: machine graph :param chips_in_order: chips in sorted order :type chips_in_order: iterable(tuple(int,int)) :param Placements placements: placements :param ~spinn_utilities.progress_bar.ProgressBar progress_bar: progress bar :param ResourceTracker resource_tracker: resource tracker :param set(MachineVertex) placed_vertices: the verts which already been placed :param cost_per_chip: map between (x,y) and the total packets going through it currently. :type cost_per_chip: dict(tuple(int, int), int) :param AbstractMachinePartitionNKeysMap n_keys_map: map between outgoing partition and n keys down it. """ # locate whatever verts are left sorted_verts = self._sort_left_over_verts_based_on_incoming_packets( machine_graph, placed_vertices, n_keys_map) for vertex in sorted_verts: (x, y, p, _, _) = resource_tracker.allocate_constrained_resources( vertex.resources_required, vertex.constraints, chips=chips_in_order) placements.add_placement(Placement(vertex=vertex, x=x, y=y, p=p)) cost_per_chip[x, y] += self._get_cost( vertex, machine_graph, n_keys_map) # sort chips for the next group cycle chips_in_order = self._sort_chips_based_off_incoming_cost( chips_in_order, cost_per_chip) progress_bar.update(len(machine_graph.vertices)) def _determine_chip_list(self, machine): """ determines the radial list from a deduced middle of the machine :param ~spinn_machine.Machine machine: the machine to find a middle from :return: a list of chips radially from a deduced middle :rtype: list(tuple(int,int)) """ # try the middle chip middle_chip_x = math.ceil(machine.max_chip_x / 2) middle_chip_y = math.ceil(machine.max_chip_y / 2) chip = machine.get_chip_at(middle_chip_x, middle_chip_y) # if middle chip don't exist. search for the closest chip. if chip is None: distance_from_middle = sys.maxsize closest_chip = None # compare each chip loc to the middle. don't need to be majorly # precise, all we're looking for is a chip nearby. for chip in machine.chips: x_diff = abs(middle_chip_x - chip.x) y_diff = abs(middle_chip_y - chip.y) diff_total = x_diff + y_diff if distance_from_middle > diff_total: distance_from_middle = diff_total closest_chip = chip # if you find a chip that's next door, then quit early if distance_from_middle == 1: break # set correct middle chip middle_chip_x = closest_chip.x middle_chip_y = closest_chip.y # return the radial list from this middle point return list(self._generate_radial_chips( machine, resource_tracker=None, start_chip_x=middle_chip_x, start_chip_y=middle_chip_y))