On-chip order-exploiting routing table minimization for a multicast supercomputer network

Andrew Mundy, Jonathan Heathcote, Jim D. Garside

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

SpiNNaker is a many-core supercomputer - designed for the simulation of large neural-networks - in which cores communicate with multicast packets. Routing within SpiNNaker is controlled by Ternary Content Addressable Memories (TCAMs) of quite limited size. As not all neural-network applications will result in routing tables sufficiently small to fit in TCAM some minimization is necessary. In this paper we argue that existing techniques neither result in sufficiently minimized tables nor can be implemented within the small code and memory footprint available to a SpiNNaker core. To resolve these issues we present a new algorithm, Ordered-Covering (OC), which exploits the ordered nature of TCAMs to achieve good compression of routing tables while meeting the code-space and memory constraints of the SpiNNaker platform. We show that, for one benchmark, on-chip routing table minimization using OC results in a 64.5 χ speed-up compared with performing the minimization off-chip. For a second, more challenging, benchmark we show that a 2.8 χ speed-up in table minimization time is achieved by combined on- and off-chip minimization.

Original languageEnglish
Title of host publicationIEEE 17th International Conference on High Performance Switching and Routing, HPSR 2016
PublisherIEEE Computer Society
Pages148-154
Number of pages7
Volume2016-July
ISBN (Electronic)9781479989508
DOIs
Publication statusPublished - 28 Jul 2016
Event17th IEEE International Conference on High Performance Switching and Routing, HPSR 2016 - Yokohama, Japan
Duration: 14 Jun 201617 Jun 2016

Publication series

NameIEEE Workshop on High Performance Switching and Routing
PublisherIEEE
ISSN (Electronic)2325-5609

Conference

Conference17th IEEE International Conference on High Performance Switching and Routing, HPSR 2016
Country/TerritoryJapan
CityYokohama
Period14/06/1617/06/16

Fingerprint

Dive into the research topics of 'On-chip order-exploiting routing table minimization for a multicast supercomputer network'. Together they form a unique fingerprint.

Cite this