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
    • Ordered Covering
      • Background
      • Merging routing table entries
      • “Ordered Covering”
  • 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

Bases: object

MAX_SUPPORTED_LENGTH = 1023

compress_table(router_table)

compress_tables(router_tables, progress)

Compress all the unordered routing tables

Tables who start of smaller than target_length are not compressed

Parameters:

• router_tables (MulticastRoutingTables) – 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)

Return if key-mask pairs intersect (i.e., would both match some of

the same keys).

For example, the key-mask pairs 00XX and 001X both match the

keys``0010`` and 0011 (i.e., they do intersect):

>>> intersect(0b0000, 0b1100, 0b0010, 0b1110)

True

But the key-mask pairs 00XX and 11XX do not match any of the

same keys (i.e., they do not intersect):

>>> intersect(0b0000, 0b1100, 0b1100, 0b1100)

False

Parameters:key_a – The key of first key-mask pair

:type key_a : int :param mask_a: The mask of first key-mask pair :type key_b: int :param key_b: The key of second key-mask pair :type key_b : int :param mask_b: The mask of second key-mask pair :type key_b: int :return: True if the two key-mask pairs intersect otherwise False.

merge(entry1, entry2)

Merges two entries/triples into one that covers both

The assumption is that they both have the same known spinnaker_route

Parameters:

• entry1 (Entry) – Key, Mask, defaultable from the first entry
• entry2 (Entry) – Key, Mask, defaultable from the second entry

Returns:

Key, Mask, defaultable from merged entry

Return type:

(int, int, bool)

pacman.operations.router_compressors.basic_route_merger module

class pacman.operations.router_compressors.basic_route_merger.BasicRouteMerger

Bases: object

Merges routing tables entries via different masks and an exploration process

pacman.operations.router_compressors.checked_unordered_compressor module

class pacman.operations.router_compressors.checked_unordered_compressor.CheckedUnorderedCompressor

Bases: pacman.operations.router_compressors.unordered_compressor.UnorderedCompressor

verify_lengths(compressed)

pacman.operations.router_compressors.clash_compressor module

class pacman.operations.router_compressors.clash_compressor.ClashCompressor

Bases: pacman.operations.router_compressors.abstract_compressor.AbstractCompressor

compress_by_route(route_entries)

compress_ignore_clashers(router_table, top_entries)

compress_table(router_table)

find_merge(an_entry, route_entries)

pacman.operations.router_compressors.entry module

class pacman.operations.router_compressors.entry.Entry(key, mask, defaultable, spinnaker_route)

Bases: object

defaultable

static from_MulticastRoutingEntry(mre)

key

mask

spinnaker_route

to_MulticastRoutingEntry()

pacman.operations.router_compressors.malloc_based_route_merger module

class pacman.operations.router_compressors.malloc_based_route_merger.MallocBasedRouteMerger

Bases: object

Routing table entry merging function, that merges based off a malloc memory style.

pacman.operations.router_compressors.pair_compressor module

class pacman.operations.router_compressors.pair_compressor.PairCompressor

Bases: pacman.operations.router_compressors.abstract_compressor.AbstractCompressor

Routing Table compressor based on brute force. Finds mergable pairs to replace.

This algorithm assumes unordered rounting tables and returns

a possiibly 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 usings 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 highg. The results are considered ordered so previous routes are not

considered.

The advatange 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 ferequency.

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)

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

update_frequency(route)

pacman.operations.router_compressors.unordered_compressor module

class pacman.operations.router_compressors.unordered_compressor.UnorderedCompressor

Bases: pacman.operations.router_compressors.pair_compressor.PairCompressor

Module contents

class pacman.operations.router_compressors.AbstractCompressor

Bases: object

MAX_SUPPORTED_LENGTH = 1023

compress_table(router_table)

compress_tables(router_tables, progress)

Compress all the unordered routing tables

Tables who start of smaller than target_length are not compressed

Parameters:

• router_tables (MulticastRoutingTables) – 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)

Return if key-mask pairs intersect (i.e., would both match some of

the same keys).

For example, the key-mask pairs 00XX and 001X both match the

keys``0010`` and 0011 (i.e., they do intersect):

>>> intersect(0b0000, 0b1100, 0b0010, 0b1110)

True

But the key-mask pairs 00XX and 11XX do not match any of the

same keys (i.e., they do not intersect):

>>> intersect(0b0000, 0b1100, 0b1100, 0b1100)

False

Parameters:key_a – The key of first key-mask pair

:type key_a : int :param mask_a: The mask of first key-mask pair :type key_b: int :param key_b: The key of second key-mask pair :type key_b : int :param mask_b: The mask of second key-mask pair :type key_b: int :return: True if the two key-mask pairs intersect otherwise False.

merge(entry1, entry2)

Merges two entries/triples into one that covers both

The assumption is that they both have the same known spinnaker_route

Parameters:

• entry1 (Entry) – Key, Mask, defaultable from the first entry
• entry2 (Entry) – Key, Mask, defaultable from the second entry

Returns:

Key, Mask, defaultable from merged entry

Return type:

(int, int, bool)

class pacman.operations.router_compressors.CheckedUnorderedCompressor

Bases: pacman.operations.router_compressors.unordered_compressor.UnorderedCompressor

verify_lengths(compressed)

class pacman.operations.router_compressors.Entry(key, mask, defaultable, spinnaker_route)

Bases: object

defaultable

static from_MulticastRoutingEntry(mre)

key

mask

spinnaker_route

to_MulticastRoutingEntry()

class pacman.operations.router_compressors.PairCompressor

Bases: pacman.operations.router_compressors.abstract_compressor.AbstractCompressor

Routing Table compressor based on brute force. Finds mergable pairs to replace.

This algorithm assumes unordered rounting tables and returns

a possiibly 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 usings 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 highg. The results are considered ordered so previous routes are not

considered.

The advatange 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 ferequency.

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)

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

update_frequency(route)

class pacman.operations.router_compressors.UnorderedCompressor

Bases: pacman.operations.router_compressors.pair_compressor.PairCompressor