Source code for pacman.utilities.algorithm_utilities.element_allocator_algorithm

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

import math
from spinn_utilities.abstract_base import AbstractBase
from pacman.model.resources import ElementFreeSpace
from pacman.exceptions import PacmanElementAllocationException


[docs]class ElementAllocatorAlgorithm(object, metaclass=AbstractBase): """ Abstract element allocator algorithm which allocates elements from\ a pool of a given size """ __slots__ = [ # the space object for memory allocation "_free_space_tracker" ] def __init__(self, size_begin, size_end): """ :param int size_begin: :param int size_end: """ self._free_space_tracker = list() self._free_space_tracker.append(ElementFreeSpace(size_begin, size_end)) def _allocate_elements(self, base_element_id, n_elements): """ Handle the allocating of space for a given set of elements :param int base_element_id: the first element ID to allocate :param int n_elements: the number of elements to allocate :raises PacmanRouteInfoAllocationException: when the ID cannot be assigned due to the number of elements """ index = self._find_slot(base_element_id) if index is None: raise PacmanElementAllocationException( "Space for {} elements starting at {} has already " "been allocated".format(n_elements, base_element_id)) # base element should be >= slot element at this point self.__do_allocation(index, base_element_id, n_elements) def _find_slot(self, base_element_id, lo=0): """ Find the free slot with the closest base element ID <= base element using a binary search :param int base_element_id: :param int lo: :rtype: int or None """ hi = len(self._free_space_tracker) - 1 while lo < hi: mid = int(math.ceil(float(lo + hi) / 2.0)) free_space_slot = self._free_space_tracker[mid] if free_space_slot.start_address > base_element_id: hi = mid - 1 else: lo = mid # If we have gone off the end of the array, we haven't found a slot if (lo >= len(self._free_space_tracker) or hi < 0 or self._free_space_tracker[lo].start_address > base_element_id): return None return lo def __do_allocation(self, index, base_element_id, n_elements): """ Allocate a given base element ID and number of elements into the\ space at the given slot :param int index: The index of the free space slot to check :param int base_element_id: The element ID to start with; must be inside the slot :param int n_elements: The number of elements to be allocated; should be power of 2 :raises PacmanElementAllocationException: """ free_space_slot = self._free_space_tracker[index] if free_space_slot.start_address > base_element_id: raise PacmanElementAllocationException( "Trying to allocate a element in the wrong slot!") # Check if there is enough space to allocate space = self._check_allocation(index, base_element_id, n_elements) if space is None: raise PacmanElementAllocationException( "Not enough space to allocate {} elements starting at {}" .format(n_elements, hex(base_element_id))) if (free_space_slot.start_address == base_element_id and free_space_slot.size == n_elements): # If the slot exactly matches the space, remove it del self._free_space_tracker[index] elif free_space_slot.start_address == base_element_id: # If the slot starts with the element ID, reduce the size self._free_space_tracker[index] = ElementFreeSpace( free_space_slot.start_address + n_elements, free_space_slot.size - n_elements) elif space == n_elements: # If the space at the end exactly matches the spot, reduce the size self._free_space_tracker[index] = ElementFreeSpace( free_space_slot.start_address, free_space_slot.size - n_elements) else: # Otherwise, the allocation lies in the middle of the region: # First, reduce the size of the space before the allocation self._free_space_tracker[index] = ElementFreeSpace( free_space_slot.start_address, base_element_id - free_space_slot.start_address) # Then add a new space after the allocation self._free_space_tracker.insert(index + 1, ElementFreeSpace( base_element_id + n_elements, free_space_slot.start_address + free_space_slot.size - (base_element_id + n_elements))) def _check_allocation(self, index, base_element_id, n_elements): """ Check if there is enough space for a given set of element IDs\ starting at a base element ID inside a given slot :param int index: The index of the free space slot to check :param int base_element_id: The element ID to start with; must be inside the slot :param int n_elements: The number of elements to be allocated; should be power of 2 :rtype: int or None :raises PacmanElementAllocationException: """ free_space_slot = self._free_space_tracker[index] space = (free_space_slot.size - (base_element_id - free_space_slot.start_address)) if free_space_slot.start_address > base_element_id: raise PacmanElementAllocationException( "Trying to allocate a element ID in the wrong slot!") # Check if there is enough space for the elements if space < n_elements: return None return space