rig.routing_table: Multicast routing table datastructures and tools

This module contains data structures and algorithms for representing and manipulating multicast routing tables for SpiNNaker.

Quick-start Examples

The following examples give quick examples of Rig’s routing table data structures and table minimisation tools.

Using the place-and-route wrapper

If you’re using the place_and_route_wrapper() wrapper function to perform place-and-route for your application, routing table minimisation is performed automatically when required. No changes are required to your application!

Manually defining and minimising individual routing tables

The brief example below illustrates how a single routing table might be defined and minimised.

>>> # Define a (trivially minimised) example routing table
>>> from rig.routing_table import Routes, RoutingTableEntry
>>> original = [
...     RoutingTableEntry({Routes.north}, 0x00000000, 0xFFFFFFFF),
...     RoutingTableEntry({Routes.north}, 0x00000001, 0xFFFFFFFF),
...     RoutingTableEntry({Routes.north}, 0x00000002, 0xFFFFFFFF),
...     RoutingTableEntry({Routes.north}, 0x00000003, 0xFFFFFFFF),
... ]

>>> # Minimise the routing table using a sensible selection of algorithms
>>> from rig.routing_table import minimise_table
>>> minimised = minimise_table(original, target_length=None)
>>> assert minimised == [
...     RoutingTableEntry({Routes.north}, 0x00000000, 0xFFFFFFFC),
... ]

Generating and loading routing tables from automatic place-and-route tools

The outline below shows how routing tables might be generated from the results of Rig’s place and route tools, minimised and then loaded onto a SpiNNaker machine.

# Interrogate the SpiNNaker machine to determine what resources are
# available (including the number of multicast routing table entries on
# each chip).
from rig.machine_control import MachineController
machine_controller = MachineController("hostname")
system_info = machine_controller.get_system_info()

# Place-and-route your application as normal and select suitable
# routing keys for each net.
from rig.place_and_route import route
routes = route(...)
net_keys = {Net: (key, mask), ...}

# Produce routing tables from the generated routes
from rig.routing_table import routing_tree_to_tables
routing_tables = routing_tree_to_tables(routes, net_keys)

# Minimise the routes (if required), trying a sensible selection of table
# minimisation algorithms.
from rig.routing_table import (
    build_routing_table_target_lengths,
    minimise_tables)
target_lengths = build_routing_table_target_lengths(system_info)
routing_tables = minimise_tables(routing_tables, target_lengths)

# Load the minimised routing tables onto SpiNNaker
machine_controller.load_routing_tables(routing_tables)

RoutingTableEntry and Routes: Routing table data structures

Routing tables in Rig are conventionally represented as a list of RoutingTableEntry objects in the order they would appear in a SpiNNaker router. Empty/unused routing table entries are not usually included in these representations.

class rig.routing_table.RoutingTableEntry[source]

Named tuple representing a single routing entry in a SpiNNaker routing table.

Parameters:
route : {Routes, …}

The set of destinations a packet should be routed to where each element in the set is a value from the enumeration Routes.

key : int

32-bit unsigned integer routing key to match after applying the mask.

mask : int

32-bit unsigned integer mask to apply to keys of packets arriving at the router.

sources : {Routes, …}

Links on which a packet may enter the router before taking this route. If the source directions are unknown {None} should be used (the default).
class rig.routing_table.Routes[source]
Enumeration of routes which a SpiNNaker packet can take after arriving

at a router.

Note that the integer values assigned are chosen to match the numbers used to identify routes in the low-level software API and hardware registers.

Note that you can directly cast from a rig.links.Links to a Routes value.

Attributes:
east = 0
north_east = 1
north = 2
west = 3
south_west = 4
south = 5
core_monitor = 6
core_1 = 7
core_2 = 8
core_3 = 9
core_4 = 10
core_5 = 11
core_6 = 12
core_7 = 13
core_8 = 14
core_9 = 15
core_10 = 16
core_11 = 17
core_12 = 18
core_13 = 19
core_14 = 20
core_15 = 21
core_16 = 22
core_17 = 23

Routing table construction utility

The routing_tree_to_tables() function is provided which constructs routing tables of the form described above from RoutingTree objects produced by an automatic routing algorithm.

rig.routing_table.routing_tree_to_tables(routes, net_keys)[source]

Convert a set of RoutingTree s into a per-chip set of routing tables.

Warning

A rig.routing_table.MultisourceRouteError will be raised if entries with identical keys and masks but with differing routes are generated. This is not a perfect test, entries which would otherwise collide are not spotted.

Warning

The routing trees provided are assumed to be correct and continuous (not missing any hops). If this is not the case, the output is undefined.

Note

If a routing tree has a terminating vertex whose route is set to None, that vertex is ignored.

Parameters:
routes : {net: RoutingTree, …}

The complete set of RoutingTrees representing all routes in the system. (Note: this is the same data structure produced by routers in the place_and_route module.)

net_keys : {net: (key, mask), …}

The key and mask associated with each net.
Returns:
{(x, y): [:py:class:`~rig.routing_table.RoutingTableEntry`, …]
exception rig.routing_table.MultisourceRouteError(key, mask, coordinate)[source]

Indicates that two nets with the same key and mask would cause packets to become duplicated.

Routing table minimisation algorithms

SpiNNaker’s multicast routing tables are a finite resource containing a maximum of 1024 entries. Certain applications may find that they exhaust this limited resource and may wish to attempt to shrink their routing tables by making better use of the SpiNNaker router’s capabilities. For example, if a packet’s key does not match any routing entries it will be “default routed” in the direction in which it was already travelling and thus no routing table entry is required. Additionally, by more fully exploiting the behaviour of the Ternary Content Addressable Memory (TCAM) used in SpiNNaker’s multicast router it is often possible to compress (or minimise) a given routing table into a more compact, yet logically equivalent, form.

This module includes algorithms for minimising routing tables for use by SpiNNaker application developers.

Common-case wrappers

For most users, the following functions can be used to minimise routing tables used by their application. Both accept a target number of routing entries and will attempt to apply routing table minimisation algorithms from this module until the supplied tables fit.

rig.routing_table.minimise_tables(routing_tables, target_lengths, methods=(<function minimise>, <function minimise>))[source]

Utility function which attempts to minimises routing tables for multiple chips.

For each routing table supplied, this function will attempt to use the minimisation algorithms given (or some sensible default algorithms), trying each sequentially until a target number of routing entries has been reached.

Parameters:
routing_tables : {(x, y): [ RoutingTableEntry, …], …}

Dictionary mapping chip co-ordinates to the routing tables associated with that chip. NOTE: This is the data structure as returned by routing_tree_to_tables().

target_lengths : int or {(x, y): int or None, …} or None

Maximum length of routing tables. If an integer this is assumed to be the maximum length for any table; if a dictionary then it is assumed to be a mapping from co-ordinate to maximum length (or None); if None then tables will be minimised as far as possible.

methods :

Each method is tried in the order presented and the first to meet the required target length for a given chip is used. Consequently less computationally costly algorithms should be nearer the start of the list. The defaults will try to remove default routes (rig.routing_table.remove_default_routes.minimise()) and then fall back on the ordered covering algorithm (rig.routing_table.ordered_covering.minimise()).
Returns:
{(x, y): [:py:class:`~rig.routing_table.RoutingTableEntry`, …], …}

Minimised routing tables, guaranteed to be at least as small as the table sizes specified by target_lengths.
Raises:
MinimisationFailedError

If no method can sufficiently minimise a table.
rig.routing_table.minimise_table(table, target_length, methods=(<function minimise>, <function minimise>))[source]

Apply different minimisation algorithms to minimise a single routing table.

Parameters:
table : [RoutingTableEntry, …]

Routing table to minimise. NOTE: This is the data structure as returned by routing_tree_to_tables().

target_length : int or None

Maximum length of the routing table. If None then all methods will be tried and the smallest achieved table will be returned.

methods :

Each method is tried in the order presented and the first to meet the required target length for a given chip is used. Consequently less computationally costly algorithms should be nearer the start of the list. The defaults will try to remove default routes (:py:meth:rig.routing_table.remove_default_routes.minimise) and then fall back on the ordered covering algorithm (:py:meth:rig.routing_table.ordered_covering.minimise).
Returns:
[:py:class:`~rig.routing_table.RoutingTableEntry`, …]

Minimised routing table, guaranteed to be at least as small as target_length, or as small as possible if target_length is None.
Raises:
MinimisationFailedError

If no method can sufficiently minimise the table.

Available algorithms

The following minimisation algorithms are currently available:

minimise() prototype

Routing table minimisation functions are always named minimise() and are contained within a Python module named after the algorithm. These minimise() functions have the signature defined below.

rig.routing_table.minimise(routing_table, target_length=1024)[source]

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.

Note

If all the keys in the table are derived from a single instance of BitField then the table is guaranteed to be orthogonal and reorderable.

Note

Use expand_entries() to generate an orthogonal table and receive warnings if the input table is not orthogonal.

routing_table : [RoutingTableEntry, …]
Routing entries to be merged.
target_length : int or None

If an int, this is the target length of the routing table; the minimisation procedure may halt once either this target is reached or no further minimisation is possible. If the target could not be reached a MinimisationFailedError will be raised.

If None then the table will be made as small as possible and is guaranteed to return a result.

MinimisationFailedError
If the smallest table that can be produced is larger than target_length and target_length is not None.
[RoutingTableEntry, …]
Reduced routing table entries. The returned routing table is guaranteed to route all entries matched by the input table in the same way. Note that the minimised table may also match keys not previously matched by the input routing table.
exception rig.routing_table.MinimisationFailedError(target_length, final_length=None, chip=None)[source]

Raised when a routing table could not be minimised to reach a specified target.

Attributes:
target_length : int

The target number of routing entries.

final_length : int

The number of routing entries reached when the algorithm completed. (final_length > target_length)

chip : (x, y) or None

The coordinates of the chip on which routing table minimisation first failed. Only set when minimisation is performed across many chips simultaneously.

Routing Table Manipulation Tools

The following functions may be useful when comparing routing tables, for example if testing or evaluating minimisation algorithms.

rig.routing_table.table_is_subset_of(entries_a, entries_b)[source]

Check that every key matched by every entry in one table results in the same route when checked against the other table.

For example, the table:

>>> from rig.routing_table import Routes
>>> table = [
...     RoutingTableEntry({Routes.north, Routes.north_east}, 0x0, 0xf),
...     RoutingTableEntry({Routes.east}, 0x1, 0xf),
...     RoutingTableEntry({Routes.south_west}, 0x5, 0xf),
...     RoutingTableEntry({Routes.north, Routes.north_east}, 0x8, 0xf),
...     RoutingTableEntry({Routes.east}, 0x9, 0xf),
...     RoutingTableEntry({Routes.south_west}, 0xe, 0xf),
...     RoutingTableEntry({Routes.north, Routes.north_east}, 0xc, 0xf),
...     RoutingTableEntry({Routes.south, Routes.south_west}, 0x0, 0xb),
... ]

is a functional subset of a minimised version of itself:

>>> from rig.routing_table.ordered_covering import minimise
>>> other_table = minimise(table, target_length=None)
>>> other_table == table
False
>>> table_is_subset_of(table, other_table)
True

But not vice-versa:

>>> table_is_subset_of(other_table, table)
False

Default routes are taken into account, such that the table:

>>> table = [
...     RoutingTableEntry({Routes.north}, 0x0, 0xf, {Routes.south}),
... ]

is a subset of the empty table:

>>> table_is_subset_of(table, list())
True
Parameters:
entries_a : [RoutingTableEntry, …]
entries_b : [RoutingTableEntry, …]

Ordered of lists of routing table entries to compare.
Returns:
bool

True if every key matched in entries_a would result in an equivalent route for the packet when matched in entries_b.
rig.routing_table.expand_entries(entries, ignore_xs=None)[source]

Turn all Xs which are not ignored in all entries into 0 s and 1 s.

For example:

>>> from rig.routing_table import RoutingTableEntry
>>> entries = [
...     RoutingTableEntry(set(), 0b0100, 0xfffffff0 | 0b1100),  # 01XX
...     RoutingTableEntry(set(), 0b0010, 0xfffffff0 | 0b0010),  # XX1X
... ]
>>> list(expand_entries(entries)) == [
...     RoutingTableEntry(set(), 0b0100, 0xfffffff0 | 0b1110),  # 010X
...     RoutingTableEntry(set(), 0b0110, 0xfffffff0 | 0b1110),  # 011X
...     RoutingTableEntry(set(), 0b0010, 0xfffffff0 | 0b1110),  # 001X
...     RoutingTableEntry(set(), 0b1010, 0xfffffff0 | 0b1110),  # 101X
...     RoutingTableEntry(set(), 0b1110, 0xfffffff0 | 0b1110),  # 111X
... ]
True

Note that the X in the LSB was retained because it is common to all entries.

Any duplicated entries will be removed (in this case the first and second entries will both match 0000, so when the second entry is expanded only one entry is retained):

>>> from rig.routing_table import Routes
>>> entries = [
...     RoutingTableEntry({Routes.north}, 0b0000, 0b1111),  # 0000 -> N
...     RoutingTableEntry({Routes.south}, 0b0000, 0b1011),  # 0X00 -> S
... ]
>>> list(expand_entries(entries)) == [
...     RoutingTableEntry({Routes.north}, 0b0000, 0b1111),  # 0000 -> N
...     RoutingTableEntry({Routes.south}, 0b0100, 0b1111),  # 0100 -> S
... ]
True

Warning

It is assumed that the input routing table is orthogonal (i.e., there are no two entries which would match the same key). If this is not the case, any entries which are covered (i.e. unreachable) in the input table will be omitted and a warning produced. As a result, all output routing tables are guaranteed to be orthogonal.

Parameters:
entries : [RoutingTableEntry…] or similar

The entries to expand.
Yields:
:py:class:`~rig.routing_table.RoutingTableEntry`

Routing table entries which represent the original entries but with all Xs not masked off by ignore_xs replaced with 1s and 0s.
Other Parameters:
 
ignore_xs : int

Mask of bits in which Xs should not be expanded. If None (the default) then Xs which are common to all entries will not be expanded.
rig.routing_table.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 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
Returns:
bool

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

Utility Functions

rig.routing_table.build_routing_table_target_lengths(system_info)[source]

Build a dictionary of target routing table lengths from a SystemInfo object.

Useful in conjunction with minimise_tables().

Returns:
{(x, y): num, …}

A dictionary giving the number of free routing table entries on each chip on a SpiNNaker system.

Note

The actual number of entries reported is the size of the largest contiguous free block of routing entries in the routing table.