Name
Abstract | ||
|---|---|---|
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 analysed up to 1000× faster than on a conventional computer. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/FDL.2017.8303899 | 2017 Forum on Specification and Design Languages (FDL) |
Keywords | DocType | ISBN |
finite state machines,graph edges,physical graph,on-chip clock distribution network,memory bottleneck,domain-specific language,graph description,application graphs,hardware acceleration backend,graph processing,conventional computer architectures,source vertex,graph vertices,signal propagation time,graph transformation,graph analysis tasks,FPGA board | Conference | 978-1-5386-1152-4 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
9 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrey Mokhov | 1 | 136 | 26.57 |
| Alessandro de Gennaro | 2 | 0 | 0.34 |
| Ghaith Tarawneh | 3 | 17 | 5.18 |
| Jonny Wray | 4 | 0 | 1.01 |
| Georgy Lukyanov | 5 | 0 | 1.01 |
| Sergey Mileiko | 6 | 0 | 0.34 |
| Joe Scott | 7 | 0 | 0.34 |
| Alex Yakovlev | 8 | 8 | 7.71 |
| Andrew Brown | 9 | 27 | 3.82 |