pacman.operations.router_compressors.ordered_covering_router_compressor package

Module contents

Ordered Covering

An novel algorithm for the minimisation of SpiNNaker’s multicast routing tables devised by Andrew Mundy.

Background

SpiNNaker routing tables consist of entries made up of a 32-bit key, a 32-bit mask and a 24-bit route value. The key and mask of every entry act as a sieve for the keys found on incoming multicast packets. Each bit of the key-mask pair can be considered as matching 0, 1 or 2 values in the same bit of a multicast packet key:

Key

Mask

Matches Key Values

Written

0

0

0 or 1

X

0

1

0

0

1

1

1

1

1

0

Nothing

!

If a packet matches the key-mask of an entry then the packet is transmitted to the cores and links indicated by the route field.

For example, if the table were:

Key

Mask

Route

0000

1111

North, North East

0111

0111

South

Which, from now on, will be written as:

0000 -> N NE
X111 -> S

Then any packets with the key 0000 would be sent out of the north and north-east links. Any packets with the keys 0111 or 1111 would be sent out of the south link only.

Entries in table are ordered, with entries at the top of the table having higher priority than those lower down the table. Only the highest priority entry which matches a packet is used. If, for example, the table were:

0000 -> N NE
1111 -> 1 2
X111 -> S

Then packets with the keys 0000 and 0111 would be treated as before. However, packets with the key 1111 would be sent to cores 1 and 2 as only the higher priority entry has effect.

Merging routing table entries

Routing tables can be minimised by merging together entries with equivalent routes. This is done by creating a new key-mask pair with an X wherever the key-mask pairs of any of the original entries differed.

For example, merging of the entries:

0000 -> N
0001 -> N

Would lead to the new entry:

000X -> N

Which would match any of the keys matched by the original entries but no more. In contrast the merge of 0001 and 0010 would generate the new entry 00XX which would match keys matched by either of the original entries but also 0000 and 0011.

Clearly, if we are to attempt to minimise tables such as:

0001 -> N
0010 -> N
0000 -> S, SE
0011 -> SE

We need a set of rules for:

  1. Where merged entries are to be inserted into the table

  2. Which merges are allowed

“Ordered Covering”

The algorithm implemented here, “Ordered Covering”, provides the following rule:

  • The only merges allowed are those which:

    1. would not cause one of the entries in the merge to be “hidden” below an entry of lesser generality than the merged entry but which matched any of the same keys. For example, merging 0010 and 0001 would not be allowed if the new entry would be placed below the existing entry 000X as this would “hide” 0001.

    2. would not cause an entry “contained” within an entry of higher generality to be hidden by the insertion of a new entry. For example, if the entry XXXX had been formed by merging the entries 0011 and 1100 then merging of the entries 1101 and 1110 would not be allowed as it would cause the entry 11XX to be inserted above XXXX in the table and would hide 1100.

Following these rules ensures that the minimised table will be functionally equivalent to the original table provided that the original table was invariant under reordering OR was provided in increasing order of generality.

As a heuristic:

  • Routing tables are to be kept sorted in increasing order of “generality”, that is the number of X``s in the entry. An entry with the key-mask pair ``00XX must be placed below any entries with fewer X``s in their key-mask pairs (e.g., below ``0000 and 000X).

    1. New entries must also be inserted below any entries of the same generality. If XX00 were already present in the table the new entry 0XX0 must be inserted below it.

based on https://github.com/project-rig/rig/blob/master/rig/routing_table/ordered_covering.py

Implementation API

pacman.operations.router_compressors.ordered_covering_router_compressor.get_generality(key: int, mask: int) → int

Count the number of Xs in the key-mask pair.

For example, there are 32 Xs in 0x00000000/0x00000000:

>>> get_generality(0x0, 0x0)
32

And no Xs in 0xffffffff/0xffffffff:

>>> get_generality(0xffffffff, 0xffffffff)
0
Parameters:

  • key (int) – Routing key

  • mask (int) – Routing mask

Return type:

int

pacman.operations.router_compressors.ordered_covering_router_compressor.intersect(key_a: int, mask_a: int, key_b: int, mask_b: int) → bool

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 (int)

  • mask_a (int) – The first key-mask pair

  • key_b (int)

  • mask_b (int) – The second key-mask pair

Return type:

bool

Returns:

True if the two key-mask pairs intersect, otherwise False.

pacman.operations.router_compressors.ordered_covering_router_compressor.ordered_covering(routing_table: Iterable[MulticastRoutingEntry], target_length: int | None, aliases: Dict[Tuple[int, int], FrozenSet[Tuple[int, int]]], *, no_raise: bool = False, time_to_run_for: float | None = None) → Tuple[List[MulticastRoutingEntry], Dict[Tuple[int, int], FrozenSet[Tuple[int, int]]]]

Reduce the size of a routing table by merging together entries where possible.

Warning

The input routing table must also include entries which could be removed and replaced by default routing.

Warning

It is assumed that the input routing table is not in any particular order and may be reordered into ascending order of generality (number of don’t cares/Xs in the key-mask) without affecting routing correctness. It is also assumed that if this table is unordered it is at least orthogonal (i.e., there are no two entries which would match the same key) and reorderable.

Parameters:

  • routing_table (iterable(MulticastRoutingEntry)) – Routing entries to be merged.

  • target_length (int or None) – Target length of the routing table; the minimisation procedure will halt once either this target is reached or no further minimisation is possible. If None then the table will be made as small as possible.

  • aliases (dict(tuple(int, int), set(tuple(int, int))) – Dictionary of which keys and masks in the routing table are combinations of other (now removed) keys and masks; this allows us to consider only the keys and masks the user actually cares about when determining if inserting a new entry will break the correctness of the table. This should be supplied when using this method to update an already minimised table, and should be an empty dictionary when compressing an uncompressed routing table.

  • no_raise (bool) – If False (the default) then an error will be raised if the table cannot be minimised to be smaller than target_length and target_length is not None. If True then a table will be returned regardless of the size of the final table.

  • time_to_run_for (float) – If supplied, a maximum number of seconds to run for before giving an error. May only be obeyed approximately.

Returns:

new routing table, A new _aliases dictionary.

Return type:

tuple(list(MulticastRoutingEntry), dict(tuple(int,int), set(tuple(int,int))))

Raises:

MinimisationFailedError – If the smallest table that can be produced is larger than target_length.

pacman.operations.router_compressors.ordered_covering_router_compressor.ordered_covering_compressor() → MulticastRoutingTables

Compressor from rig that has been tied into the main tool chain stack.

Return type:

MulticastRoutingTables

pacman.operations.router_compressors.ordered_covering_router_compressor.remove_default_routes(table: List[MulticastRoutingEntry], target_length: int | None, check_for_aliases: bool = True) → List[MulticastRoutingEntry]

Remove from the routing table any entries which could be replaced by default routing.

Parameters:

  • table (list(router_table.multicast_routing_entries)) – Routing entries to be merged.

  • target_length (int or None) – Target length of the routing table; the minimisation procedure will halt once either this target is reached or no further minimisation is possible. If None then the table will be made as small as possible.

  • check_for_aliases (bool) –

    If True (the default), default-route candidates are checked for aliased entries before suggesting a route may be default routed. This check is required to ensure correctness in the general case but has a runtime complexity of O(N2) in the worst case for N-entry tables.

    If False, the alias-check is skipped resulting in O(N) runtime. This option should only be used if the supplied table is guaranteed not to contain any aliased entries.

Return type:

list(MulticastRoutingEntry)

Raises:

MinimisationFailedError – If the smallest table that can be produced is larger than target_length.