In this paper we present a set of techniques that enable the synthesis of efficient custom accelerators for memory intensive, irregular applications. To address the challenges of irregular applications (large memory footprint, unpredictable fine-grained data accesses, and high synchronization intensity), and exploit their opportunities (thread level parallelism, memory level parallelism), we propose a novel accelerator design that employs an adaptive and Distributed Controller (DC) architecture, and a Memory Interface Controller (MIC) that supports concurrent and atomic memory operations on a multi-ported/multi-banked shared memory. Among the multitude of algorithms that may benefit from our solution, we focus on the acceleration of graph analytics applications and, in particular, on the synthesis of SPARQL queries on Resource Description Framework (RDF) databases. We achieve this objective by incorporating the synthesis techniques into Bambu, an Open Source high-level synthesis tools, and interfacing it with GEMS, the Graph database Engine for Multithreaded Systems. The GEMS' front-end generates optimized C implementations of the input queries, modeled as graph pattern matching algorithms, which are then automatically synthesized by Bambu. We validate our approach by synthesizing several SPARQL queries from the Lehigh University Benchmark (LUBM).

High level synthesis of RDF queries for graph analytics

CASTELLANA, VITO GIOVANNI;TUMEO, ANTONINO;LATTUADA, MARCO;FERRANDI, FABRIZIO
2015

Abstract

In this paper we present a set of techniques that enable the synthesis of efficient custom accelerators for memory intensive, irregular applications. To address the challenges of irregular applications (large memory footprint, unpredictable fine-grained data accesses, and high synchronization intensity), and exploit their opportunities (thread level parallelism, memory level parallelism), we propose a novel accelerator design that employs an adaptive and Distributed Controller (DC) architecture, and a Memory Interface Controller (MIC) that supports concurrent and atomic memory operations on a multi-ported/multi-banked shared memory. Among the multitude of algorithms that may benefit from our solution, we focus on the acceleration of graph analytics applications and, in particular, on the synthesis of SPARQL queries on Resource Description Framework (RDF) databases. We achieve this objective by incorporating the synthesis techniques into Bambu, an Open Source high-level synthesis tools, and interfacing it with GEMS, the Graph database Engine for Multithreaded Systems. The GEMS' front-end generates optimized C implementations of the input queries, modeled as graph pattern matching algorithms, which are then automatically synthesized by Bambu. We validate our approach by synthesizing several SPARQL queries from the Lehigh University Benchmark (LUBM).
Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, ICCAD
978-1-4673-8388-2
978-1-4673-8388-2
graph theory;high level synthesis;memory architecture;multi-threading;query languages;shared memory systems;Bambu;DC architecture;GEMS;LUBM;Lehigh University Benchmark;MIC;RDF databases;RDF queries;SPARQL queries;accelerator design;adaptive architecture;atomic memory operations;concurrent memory operations;distributed controller architecture;graph analytics;graph database engine;graph pattern matching algorithms;memory intensive irregular applications;memory interface controller;multiported/multibanked shared memory;multithreaded systems;open source high-level synthesis tools;resource description framework databases;Acceleration;Computer architecture;Databases;Field programmable gate arrays;Parallel processing;Program processors;Resource description framework
File in questo prodotto:
File Dimensione Formato  
iccad15.pdf

accesso aperto

Descrizione: Articolo principale
: Pre-Print (o Pre-Refereeing)
Dimensione 327.89 kB
Formato Adobe PDF
327.89 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/977866
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact