# 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 .abstract_compressor import AbstractCompressor
from .entry import Entry
[docs]class PairCompressor(AbstractCompressor):
""" Routing Table compressor based on brute force. \
Finds mergable pairs to replace.
This algorithm assumes unordered routing tables and returns \
a possibly ordered routing tables. If unordered it can be used \
as a precompressor for another that makes use of order.
In the simplest format the algorithm is:
#. For every pair of entries in the table
#. If they have the same spinnaker_route
#. Create a merged entry
#. Check that does not intersect any entry with a different route
#. Remove the two original entries
#. Add the merged entry
#. Start over
A slightly optimised algorithm is:
#. Split the entries into buckets based on spinnaker route
#. Process the buckets one at a time
#. For each entry in the buckets
#. For each other entry in the bucket
#. Create a merge entry
#. Make sure there is no clash with an entry in another bucket
#. Replace the two entries and add the merge
#. Start the bucket over
#. If no merge found move the entry from the bucket to the result\
list
#. When the bucket is empty the result list becomes the bucket
A farther optimisation is to do the whole thing in place in a single list:
#. Step 1 is sort the list by route in place
#. Step 2 do the compression route by route using indexes into the array
#. The array is split into 6 parts.
#. 0 to _previous_pointer(-1): \
Entries in buckets that have already been compressed
#. _previous_pointer to _write_pointer(-1): \
Finished entries for the current bucket
#. _write_pointer to left(-1): \
Unused space due to previous merges
#. left to right: \
Not yet finished entries from the current bucket
#. right(+ 1) to _remaining_index(-1): \
Unused space due to previous merges
#. _remaining_index to max_index(-1): \
Entries in buckets not yet compressed
#. Step 3 use only the entries up to _write_pointer(-1)
A farther optimisation is to uses order.
The entries are sorted by route frequency from low to high.
The results are considered ordered so previous routes are not \
considered.
The advantage is this allows all the entries from the most frequent \
route to be merged into a single entry. And the second most \
frequent only has to consider the most frequent routes.
Step 1 requires the counting of the frequency of routes and the \
sorting the routes based on this frequency.
The current tie break between routes with the same frequency is \
the route but this is arbitrary at the algorithm level.
This code does not use a dictionary to keep the code the same as \
the C.
Step 2 is change in that the previous entries \
(0 to _previous_pointer(-1)) are not considered for clash checking
"""
__slots__ = [
# A list of all entries which may be sorted
# of entries represented as (key, mask, defautible)
"_all_entries",
# The next index to write a merged/unmergable entry to
"_write_index",
# Inclusive index of last entry in the array (len in python)
"_max_index",
# Exclusive pointer to the end of the entries for previous buckets
"_previous_index",
# Inclusive index to the first entry for later buckets
"_remaining_index",
# C does not support dict so to get the histogram we use arrays
# In python a dict implementation is only marginally faster so not used
# to keep c and python code as similar as possible
# List of the routes to match with the frequencies
"_routes",
# List of the frequencies. Match index for index with routes
"_routes_frequency",
# Number of unique routes found so far
"_routes_count",
]
def _compare_routes(self, route_a, route_b):
"""
Compares two routes for sorting based on the frequency of each route.
The assumption here is that self._routes has been sorted with the
highest frequency at the top of the tables.
So stop as soon as 1 of the routes is found.
For two different routes but with the same frequency order is based on
the (currently arbitrary) order they are in the self._routes table
:param route_a:
:param route_b:
:return: ordering value (-1, 0, 1)
"""
if route_a == route_b:
return 0
for i in range(self._routes_count):
if self._routes[i] == route_a:
return 1
if self._routes[i] == route_b:
return -1
raise Exception("Apply Gibbs slap!")
def _three_way_partition_table(self, low, high):
"""
Partitions the entries between low and high into three parts
based on: https://en.wikipedia.org/wiki/Dutch_national_flag_problem
:param low: Inclusive Lowest index to consider
:param high: Inclusive Highest index to consider
:return: (last_index of lower, last_index_of_middle)
"""
check = low + 1
pivot = self._all_entries[low].spinnaker_route
while check <= high:
compare = self._compare_routes(
self._all_entries[check].spinnaker_route, pivot)
if compare < 0:
temp = self._all_entries[low]
self._all_entries[low] = self._all_entries[check]
self._all_entries[check] = temp
low += 1
check += 1
elif compare > 0:
temp = self._all_entries[high]
self._all_entries[high] = self._all_entries[check]
self._all_entries[check] = temp
high -= 1
else:
check += 1
return low, check
def _quicksort_table(self, low, high):
"""
Sorts the entries in place based on frequency of their route
:param low: Inclusive lowest index to consider
:param high: Inclusive highest index to consider
"""
if low < high:
left, right = self._three_way_partition_table(low, high)
self._quicksort_table(low, left - 1)
self._quicksort_table(right, high)
def _swap_routes(self, index_a, index_b):
"""
Helper function to swap BOTH the routes and routes frequency tables
:param index_a:
:param index_b:
:return:
"""
temp = self._routes_frequency[index_a]
self._routes_frequency[index_a] = self._routes_frequency[index_b]
self._routes_frequency[index_b] = temp
temp = self._routes[index_a]
self._routes[index_a] = self._routes[index_b]
self._routes[index_b] = temp
def _three_way_partition_routes(self, low, high):
"""
Partitions the routes and frequencies into three parts
based on: https://en.wikipedia.org/wiki/Dutch_national_flag_problem
:param low: Lowest index to consider
:param high: Highest index to consider
:return: (last_index of lower, last_index_of_middle)
"""
check = low + 1
pivot = self._routes_frequency[low]
while check <= high:
if self._routes_frequency[check] > pivot:
self._swap_routes(low, check)
low += 1
check += 1
elif self._routes_frequency[check] < pivot:
self._swap_routes(high, check)
high -= 1
else:
check += 1
return low, check
def _quicksort_routes(self, low, high):
"""
Sorts the routes in place based on frequency
:param low: Inclusive lowest index to consider
:param high: Inclusive highest index to consider
"""
if low < high:
left, right = self._three_way_partition_routes(low, high)
self._quicksort_routes(low, left - 1)
self._quicksort_routes(right, high)
def _find_merge(self, left, index):
"""
Attempt to find a merge between the left entry and the index entry
Creates a merge and then checks it does not intersect with entries \
with different routes.
If no intersect detected entry[left] is replaced with the merge
:param left: Index of Entry to merge and replace if possible
:param index: Index of entry to merge with
:return: True if and only if a merge was found and done
"""
m_key, m_mask, defaultable = self.merge(
self._all_entries[left], self._all_entries[index])
if not self.ordered:
for check in range(self._previous_index):
if self.intersect(
self._all_entries[check].key,
self._all_entries[check].mask,
m_key, m_mask):
return False
for check in range(self._remaining_index, self._max_index + 1):
if self.intersect(
self._all_entries[check].key,
self._all_entries[check].mask,
m_key, m_mask):
return False
self._all_entries[left] = Entry(
m_key, m_mask, defaultable,
self._all_entries[left].spinnaker_route)
return True
def _compress_by_route(self, left, right):
"""
Compresses the entries between left and right
:param left: Inclusive index of first entry to merge
:param right: Inclusive index of last entry to merge
"""
while left < right:
index = left + 1
while index <= right:
merged = self._find_merge(left, index)
if merged:
self._all_entries[index] = self._all_entries[right]
# Setting None not needed but easier when debugging
# self._all_entries[right] = None
right -= 1
break
index += 1
if not merged:
self._all_entries[self._write_index] = self._all_entries[left]
self._write_index += 1
left += 1
if left == right:
self._all_entries[self._write_index] = self._all_entries[left]
# Setting None not needed but easier when debugging
# if left != self._write_pointer:
# self._all_entries[left] = None
self._write_index += 1
[docs] def update_frequency(self, route):
for i in range(self._routes_count):
if self._routes[i] == route:
self._routes_frequency[i] += 1
return
self._routes[self._routes_count] = route
self._routes_frequency[self._routes_count] = 1
self._routes_count += 1
[docs] def compress_table(self, router_table):
"""
Compresses all the entries for a single table.
Compressed the entries for this unordered table \
returning a new table with possibly fewer entries but still unordered
:param router_table: Original Routing table for a single chip
:type router_table: ~pacman.model.routing_tables.MulticastRoutingTable
:return: Compressed routing table for the same chip
:rtype: ~pacman.model.routing_tables.MulticastRoutingTable
"""
# Split the entries into buckets based on spinnaker_route
self._all_entries = []
self._routes_count = 0
# Imitate creating fixed size arrays
self._routes = self.MAX_SUPPORTED_LENGTH * [None]
self._routes_frequency = self.MAX_SUPPORTED_LENGTH * [None]
for entry in router_table.multicast_routing_entries:
self._all_entries.append(
Entry.from_MulticastRoutingEntry(entry))
self.update_frequency(entry.spinnaker_route)
self._quicksort_routes(0, self._routes_count - 1)
self._quicksort_table(0, len(self._all_entries) - 1)
self._write_index = 0
self._max_index = len(self._all_entries) - 1
self._previous_index = 0
left = 0
while left <= self._max_index:
right = left
while (right < len(self._all_entries) - 1 and
self._all_entries[right+1].spinnaker_route
== self._all_entries[left].spinnaker_route):
right += 1
self._remaining_index = right + 1
self._compress_by_route(left, right)
left = right + 1
self._previous_index = self._write_index
return self._all_entries[0:self._write_index]