pacman.operations.router_compressors package¶
Subpackages¶
Module contents¶

class
pacman.operations.router_compressors.
AbstractCompressor
(ordered=True)[source]¶ Bases:
object

MAX_SUPPORTED_LENGTH
= 1023¶

__call__
(router_tables, target_length=None)[source]¶ Parameters:  router_tables (MulticastRoutingTables) –
 target_length (int) –
Return type:

compress_table
(router_table)[source]¶ Parameters: router_table (UnCompressedMulticastRoutingTable) – Original routing table for a single chip Returns: Raw compressed routing table entries for the same chip Return type: list(Entry)

compress_tables
(router_tables, progress)[source]¶ Compress all the unordered routing tables
Tables who start of smaller than target_length are not compressed
Parameters:  router_tables (MulticastRoutingTables) – Routing tables
 progress (ProgressBar) – Progress bar to show while working
Returns: The compressed but still unordered routing tables
Return type: Raises: MinimisationFailedError – on failure

static
intersect
(key_a, mask_a, key_b, mask_b)[source]¶ Return if keymask pairs intersect (i.e., would both match some of the same keys).
For example, the keymask pairs
00XX
and001X
both match the keys0010
and0011
(i.e., they do intersect):>>> intersect(0b0000, 0b1100, 0b0010, 0b1110) True
But the keymask pairs
00XX
and11XX
do not match any of the same keys (i.e., they do not intersect):>>> intersect(0b0000, 0b1100, 0b1100, 0b1100) False
Parameters: Returns: True if the two keymask pairs intersect otherwise False.
Return type:

merge
(entry1, entry2)[source]¶ Merges two entries/triples into one that covers both
The assumption is that they both have the same known spinnaker_route
Parameters: Returns: Key, Mask, defaultable from merged entry
Return type:

ordered
¶


class
pacman.operations.router_compressors.
CheckedUnorderedPairCompressor
[source]¶ Bases:
pacman.operations.router_compressors.unordered_pair_compressor.UnorderedPairCompressor
A version of the pair compressor that does not consider order but does check the lengths
There is no known case where this would generate a better result than the standard (ordered) Pair Compressor. This class is purely for expirimental purposes.
The results are checked for length so an error is raised if any table is too big.

__call__
(router_tables)[source]¶ Parameters: router_tables (MulticastRoutingTables) – Return type: MulticastRoutingTables Raises: PacmanElementAllocationException – if the compressed table won’t fit

verify_lengths
(compressed)[source]¶ Parameters: compressed (MulticastRoutingTables) – Raises: PacmanElementAllocationException – if the compressed table won’t fit


class
pacman.operations.router_compressors.
Entry
(key, mask, defaultable, spinnaker_route)[source]¶ Bases:
object
Parameters: 
defaultable
¶

static
from_MulticastRoutingEntry
(mre)[source]¶ Parameters: mre (MulticastRoutingEntry) – Return type: Entry

key
¶

mask
¶

spinnaker_route
¶

to_MulticastRoutingEntry
()[source]¶ Return type: MulticastRoutingEntry


class
pacman.operations.router_compressors.
PairCompressor
(ordered=True)[source]¶ Bases:
pacman.operations.router_compressors.abstract_compressor.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
 If they have the same spinnaker_route
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
 For each other entry in the bucket
 When the bucket is empty the result list becomes the bucket
 For each entry in the buckets
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
 The array is split into 6 parts.
 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

compress_table
(router_table)[source]¶ Compresses all the entries for a single table.
Compressed the entries for this unordered table returning a new table with possibly fewer entries
The resulting table may be ordered or unordered depending on the value of ordered passed into the init method. Ordered tables may be shorted than unordered ones.
Parameters: router_table (UnCompressedMulticastRoutingTable) – Original Routing table for a single chip Returns: Compressed routing table for the same chip Return type: list(Entry)
 For every pair of entries in the table

class
pacman.operations.router_compressors.
UnorderedPairCompressor
[source]¶ Bases:
pacman.operations.router_compressors.pair_compressor.PairCompressor
A version of the pair compressor that does not consider order or length
The resulting entries are unordered, which allows the use of a second follow on compressor.
The results are not checked for length so the results may be too big to be used unless compressed again.