On-the-fly parallel data shuffling for graph processing on OpenCL-based FPGAs

Xinyu Chen, Ronak Bajaj, Yao Chen, Jiong He, Bingsheng He, Weng Fai Wong, Deming Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Graph processing has attracted much attention recently due to its popularity in many big data analytic applications. With high performance and energy efficiency, FPGAs can be an attractive architecture for graph processing. A number of techniques such as caching using block RAMs (BRAMs) to reduce random accesses of global memory and multiple processing element (PE) instances for high throughput have been explored. OpenCL-based FPGAs natively support a high-level programming paradigm, providing good programmability to developers. However, challenges remain because the run-time dependency introduced by multiple PEs usually cannot be handled efficiently by OpenCL's high-level control granularity. In this paper, we propose a novel on-the-fly parallel data shuffling technique that can be implemented in OpenCL to solve this problem. We have integrated our shuffling technique to an edge-centric graph processing framework which achieves a throughput of more than 1,000 million traversed edges per second (MTEPS) on PageRank, SpMV, BFS and SSSP applications and is even better than existing RTL-based designs.

Original languageEnglish (US)
Title of host publicationProceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019
EditorsIoannis Sourdis, Christos-Savvas Bouganis, Carlos Alvarez, Leonel Antonio Toledo Diaz, Pedro Valero, Xavier Martorell
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages67-73
Number of pages7
ISBN (Electronic)9781728148847
DOIs
StatePublished - Sep 2019
Event29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019 - Barcelona, Spain
Duration: Sep 9 2019Sep 13 2019

Publication series

NameProceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019

Conference

Conference29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019
CountrySpain
CityBarcelona
Period9/9/199/13/19

Keywords

  • FPGA
  • Graph processing
  • On the fly
  • OpenCL
  • Shuffle

ASJC Scopus subject areas

  • Instrumentation
  • Artificial Intelligence
  • Computer Science Applications
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'On-the-fly parallel data shuffling for graph processing on OpenCL-based FPGAs'. Together they form a unique fingerprint.

Cite this