Toggle Main Menu Toggle Search

Open Access padlockePrints

Language and hardware acceleration backend for graph processing

Lookup NU author(s): Dr Andrey Mokhov, Alessandro de Gennaro, Dr Ghaith Tarawneh, Georgy Lukyanov, Serhii Mileiko, Joe Scott, Professor Alex Yakovlev

Downloads


Licence

This is the authors' accepted manuscript of a conference proceedings (inc. abstract) that has been published in its final definitive form by Springer Verlag, 2018.

For re-use rights please refer to the publisher's terms and conditions.


Abstract

© Springer Nature Switzerland AG 2019. Graphs are important in many applications. However, their analysis on conventional computer architectures is generally inefficient because it involves highly irregular access to memory when traversing vertices and edges. As an example, when finding a path from a source vertex to a target one the performance is typically limited by the memory bottleneck whereas the actual computation is trivial. This paper presents a methodology for embedding graphs into silicon, where graph vertices become finite state machines communicating via the graph edges. With this approach many common graph analysis tasks can be performed by propagating signals through the physical graph and measuring signal propagation time using the on-chip clock distribution network. This eliminates the memory bottleneck and allows thousands of vertices to be processed in parallel. We present a domain-specific language for graph description and transformation, and demonstrate how it can be used to translate application graphs into an FPGA board, where they can be analyzed up to 1000× faster than on a conventional computer.


Publication metadata

Author(s): Mokhov A, De Gennaro A, Tarawneh G, Wray J, Lukyanov G, Mileiko S, Scott J, Yakovlev A, Brown A

Editor(s): Daniel Große, Sara Vinco, Hiren Patel

Publication type: Conference Proceedings (inc. Abstract)

Publication status: Published

Conference Name: Languages, Design Methods, and Tools for Electronic System Design

Year of Conference: 2018

Pages: 71-88

Online publication date: 20/12/2018

Acceptance date: 02/04/2016

Date deposited: 05/03/2019

ISSN: 1876-1100

Publisher: Springer Verlag

URL: https://doi.org/10.1007/978-3-030-02215-0_4

DOI: 10.1007/978-3-030-02215-0_4

Library holdings: Search Newcastle University Library for this item

Series Title: Lecture Notes in Electrical Engineering

ISBN: 9783030022143


Actions

Find at Newcastle University icon    Link to this publication


Share