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).
- route : {
-
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
-
classmethod
core
(num)[source]¶ Get the
Routes
for the numbered core.Raises: - ValueError
If the core number isn’t in the range 0-17 inclusive.
-
is_link
¶ True iff a Routes object represents a chip to chip link.
-
is_core
¶ True iff a Routes object represents a route to a core.
-
core_num
¶ Get the core number being routed to.
Raises: - ValueError
If the route is not to a core.
-
opposite
¶ Get the route going in the opposing direction.
Raises: - ValueError
If the Route is not a link.
-
initial
¶ Get a shorter string representation of the Route.
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`, …]
- routes : {net:
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.
- routing_tables : {(x, y): [
-
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.
- 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.Parameters: - routing_table : [
RoutingTableEntry
, …] Routing entries to be merged.
Returns: - [:py:class:`~rig.routing_table.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.
Other Parameters: - 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.
Raises: - MinimisationFailedError
If the smallest table that can be produced is larger than
target_length
andtarget_length
is not None.
- 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.
- entries_a : [
-
rig.routing_table.
expand_entries
(entries, ignore_xs=None)[source]¶ Turn all Xs which are not ignored in all entries into
0
s and1
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.
- entries : [
-
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
and001X
both match the keys0010
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
- 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.