SpiNNaker routing table minimisation. More...

#include <stdbool.h>
#include <debug.h>
#include "../common/routing_table.h"
#include "common/minimise.h"

Macros
#define	MAX_NUM_ROUTES 1023
	Absolute maximum number of routes that we may produce.

Functions
static entry_t	merge (const entry_t entry1, const entry_t entry2)
	Merges a single pair of route entries.

static int	transfer_next (int start_index, int n_items, uint32_t cache)

static void	cancel_dmas (void)
	Cancel any outstanding DMA transfers.

static bool	find_merge_optimised (int left, int index)
	Finds if two routes can be merged.

static bool	find_merge (int left, int index)
	Finds if two routes can be merged.

static void	compress_by_route (int left, int right)
	Does the actual routing compression.

static void	sort_routes (void)
	Implementation of insertion sort for routes based on frequency.

static bool	update_frequency (int index)
	Computes route histogram.

static uint32_t	find_route_index (uint32_t route)

void	sort_table (void)
	Implementation of insertion sort for routes based on route information.

bool	minimise_run (int target_length, bool failed_by_malloc, volatile bool stop_compressing)
	Implementation of minimise()

Variables
static uint32_t	write_index
	The index of the next place in the compressed table to write a route.

static int	remaining_index
	The index of the first route after the ones being compressed in this step.

static uint32_t	routes [MAX_NUM_ROUTES]
	Table of routes being produced.

static uint32_t	routes_frequency [MAX_NUM_ROUTES] = {0}
	Route frequency histogram.

static uint32_t	routes_count
	Count of unique routes (as opposed to routes with just different key_masks).

static entry_t	route_cache [2][MAX_NUM_ROUTES]
	Space for caching routes while going through them.

Detailed Description

SpiNNaker routing table minimisation.

Minimises a routing table loaded into SDRAM and load the minimised table into the router using the specified application ID.

the exit code is stored in the user0 register

The memory address with tag "1" is expected contain the following struct (entry_t is defined in routing_table.h but is described below).

Definition in file pair_minimize.h.

Macro Definition Documentation

◆ MAX_NUM_ROUTES

#define MAX_NUM_ROUTES 1023

Absolute maximum number of routes that we may produce.

Definition at line 36 of file pair_minimize.h.

Function Documentation

◆ merge()

static entry_t merge	(	const entry_t *	entry1,
		const entry_t *	entry2
	)

inlinestatic

Merges a single pair of route entries.

Parameters

[in]	entry1	The first route to merge.
[in]	entry2	The second route to merge.

Returns: A new merged route that will eventually replace the two inputs.

Definition at line 60 of file pair_minimize.h.

◆ transfer_next()

static int transfer_next	(	int	start_index,
		int	n_items,
		uint32_t	cache
	)

inlinestatic

Definition at line 79 of file pair_minimize.h.

◆ cancel_dmas()

static void cancel_dmas ( void )

inlinestatic

Cancel any outstanding DMA transfers.

Definition at line 92 of file pair_minimize.h.

◆ find_merge_optimised()

static bool find_merge_optimised	(	int	left,
		int	index
	)

inlinestatic

Finds if two routes can be merged.

If they are merged, the entry at the index of left is also replaced with the merged route.

Parameters

[in]	left	The index of the first route to consider.
[in]	index	The index of the second route to consider.

Returns: True if the entries were merged

Definition at line 109 of file pair_minimize.h.

◆ find_merge()

static bool find_merge	(	int	left,
		int	index
	)

inlinestatic

Finds if two routes can be merged.

If they are merged, the entry at the index of left is also replaced with the merged route.

Parameters

[in]	left	The index of the first route to consider.
[in]	index	The index of the second route to consider.

Returns: True if the entries were merged

Definition at line 182 of file pair_minimize.h.

◆ compress_by_route()

static void compress_by_route	(	int	left,
		int	right
	)

inlinestatic

Does the actual routing compression.

Parameters

[in]	left	The start of the section of table to compress
[in]	right	The end of the section of table to compress

Definition at line 206 of file pair_minimize.h.

◆ sort_routes()

static void sort_routes ( void )

static

Implementation of insertion sort for routes based on frequency.

The routes must be non-overlapping pre-minimisation routes.

Definition at line 229 of file pair_minimize.h.

◆ update_frequency()

static bool update_frequency ( int index )

inlinestatic

Computes route histogram.

Parameters

[in] index The index of the cell to update

Returns: Whether the update succeeded

Definition at line 252 of file pair_minimize.h.

◆ find_route_index()

static uint32_t find_route_index ( uint32_t route )

inlinestatic

Definition at line 275 of file pair_minimize.h.

◆ sort_table()

void sort_table ( void )

Implementation of insertion sort for routes based on route information.

Parameters

[in] table_size The size of the routing table

Definition at line 292 of file pair_minimize.h.

◆ minimise_run()

bool minimise_run	(	int	target_length,
		bool *	failed_by_malloc,
		volatile bool *	stop_compressing
	)

Implementation of minimise()

Apply the ordered covering algorithm to a routing table.

Parameters

[in]	target_length	ignored
[out]	failed_by_malloc	Never changed but required by api
[in]	stop_compressing	Variable saying if the compressor should stop and return false; set by interrupt DURING the run of this method!

Returns: Whether minimisation succeeded

Definition at line 378 of file pair_minimize.h.

Variable Documentation

◆ write_index

uint32_t write_index

static

The index of the next place in the compressed table to write a route.

Definition at line 39 of file pair_minimize.h.

◆ remaining_index

int remaining_index

static

The index of the first route after the ones being compressed in this step.

Definition at line 42 of file pair_minimize.h.

◆ routes

uint32_t routes[MAX_NUM_ROUTES]

static

Table of routes being produced.

Definition at line 45 of file pair_minimize.h.

◆ routes_frequency

uint32_t routes_frequency[MAX_NUM_ROUTES] = {0}

static

Route frequency histogram.

Definition at line 48 of file pair_minimize.h.

◆ routes_count

uint32_t routes_count

static

Count of unique routes (as opposed to routes with just different key_masks).

Definition at line 51 of file pair_minimize.h.

◆ route_cache

entry_t route_cache[2][MAX_NUM_ROUTES]

static

Space for caching routes while going through them.

Definition at line 54 of file pair_minimize.h.

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ MAX_NUM_ROUTES

Function Documentation

◆ merge()

◆ transfer_next()

◆ cancel_dmas()

◆ find_merge_optimised()

◆ find_merge()

◆ compress_by_route()

◆ sort_routes()

◆ update_frequency()

◆ find_route_index()

◆ sort_table()

◆ minimise_run()

Variable Documentation

◆ write_index

◆ remaining_index

◆ routes

◆ routes_frequency

◆ routes_count

◆ route_cache