pacman.operations.router_compressors package¶
Subpackages¶
- pacman.operations.router_compressors.mundys_router_compressor package
- Submodules
- pacman.operations.router_compressors.mundys_router_compressor.ordered_covering module
- pacman.operations.router_compressors.mundys_router_compressor.remove_default_routes module
- pacman.operations.router_compressors.mundys_router_compressor.routing_table_condenser module
- pacman.operations.router_compressors.mundys_router_compressor.utils module
- Module contents
Submodules¶
pacman.operations.router_compressors.abstract_compressor module¶
based on https://github.com/project-rig/
-
class
pacman.operations.router_compressors.abstract_compressor.
AbstractCompressor
(ordered=True)[source]¶ Bases:
object
-
MAX_SUPPORTED_LENGTH
= 1023¶
-
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 (MulticastRoutingTable) – Routing tables
- progress – Progress bar to show while working
Tpye progress: ProgressBar
Returns: The compressed but still unordered routing tables
-
static
intersect
(key_a, mask_a, key_b, mask_b)[source]¶ Return if key-mask pairs intersect (i.e., would both match some of the same keys).
For example, the key-mask pairs
00XX
and001X
both match the keys``0010`` and0011
(i.e., they do intersect):>>> intersect(0b0000, 0b1100, 0b0010, 0b1110) True
But the key-mask pairs
00XX
and11XX
do not match any of the same keys (i.e., they do not intersect):>>> intersect(0b0000, 0b1100, 0b1100, 0b1100) False
Parameters: - key_a (int) – The key of first key-mask pair
- mask_a – The mask of first key-mask pair
- key_b (int) – The key of second key-mask pair
- mask_b – The mask of second key-mask pair
Returns: True if the two key-mask pairs intersect otherwise False.
Return type: bool
-
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: (int, int, bool)
-
ordered
¶
-
pacman.operations.router_compressors.basic_route_merger module¶
pacman.operations.router_compressors.checked_unordered_compressor module¶
-
class
pacman.operations.router_compressors.checked_unordered_compressor.
CheckedUnorderedCompressor
[source]¶ Bases:
pacman.operations.router_compressors.unordered_compressor.UnorderedCompressor
pacman.operations.router_compressors.clash_compressor module¶
-
class
pacman.operations.router_compressors.clash_compressor.
ClashCompressor
(ordered=True)[source]¶ Bases:
pacman.operations.router_compressors.abstract_compressor.AbstractCompressor
pacman.operations.router_compressors.entry module¶
pacman.operations.router_compressors.malloc_based_route_merger module¶
pacman.operations.router_compressors.pair_compressor module¶
-
class
pacman.operations.router_compressors.pair_compressor.
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 but still unordered
Parameters: router_table (MulticastRoutingTable) – Original Routing table for a single chip Returns: Compressed routing table for the same chip Return type: MulticastRoutingTable
- For every pair of entries in the table
pacman.operations.router_compressors.unordered_compressor module¶
-
class
pacman.operations.router_compressors.unordered_compressor.
UnorderedCompressor
[source]¶ Bases:
pacman.operations.router_compressors.pair_compressor.PairCompressor
Module contents¶
-
class
pacman.operations.router_compressors.
AbstractCompressor
(ordered=True)[source]¶ Bases:
object
-
MAX_SUPPORTED_LENGTH
= 1023¶
-
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 (MulticastRoutingTable) – Routing tables
- progress – Progress bar to show while working
Tpye progress: ProgressBar
Returns: The compressed but still unordered routing tables
-
static
intersect
(key_a, mask_a, key_b, mask_b)[source]¶ Return if key-mask pairs intersect (i.e., would both match some of the same keys).
For example, the key-mask pairs
00XX
and001X
both match the keys``0010`` and0011
(i.e., they do intersect):>>> intersect(0b0000, 0b1100, 0b0010, 0b1110) True
But the key-mask pairs
00XX
and11XX
do not match any of the same keys (i.e., they do not intersect):>>> intersect(0b0000, 0b1100, 0b1100, 0b1100) False
Parameters: - key_a (int) – The key of first key-mask pair
- mask_a – The mask of first key-mask pair
- key_b (int) – The key of second key-mask pair
- mask_b – The mask of second key-mask pair
Returns: True if the two key-mask pairs intersect otherwise False.
Return type: bool
-
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: (int, int, bool)
-
ordered
¶
-
-
class
pacman.operations.router_compressors.
CheckedUnorderedCompressor
[source]¶ Bases:
pacman.operations.router_compressors.unordered_compressor.UnorderedCompressor
-
class
pacman.operations.router_compressors.
Entry
(key, mask, defaultable, spinnaker_route)[source]¶ Bases:
object
-
defaultable
¶
-
key
¶
-
mask
¶
-
spinnaker_route
¶
-
-
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 but still unordered
Parameters: router_table (MulticastRoutingTable) – Original Routing table for a single chip Returns: Compressed routing table for the same chip Return type: MulticastRoutingTable
- For every pair of entries in the table
-
class
pacman.operations.router_compressors.
UnorderedCompressor
[source]¶ Bases:
pacman.operations.router_compressors.pair_compressor.PairCompressor