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

doi:10.1109/FPL.2019.00020

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 proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019
Editors	Ioannis Sourdis, Christos-Savvas Bouganis, Carlos Alvarez, Leonel Antonio Toledo Diaz, Pedro Valero, Xavier Martorell
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	67-73
Number of pages	7
ISBN (Electronic)	9781728148847
DOIs	https://doi.org/10.1109/FPL.2019.00020
State	Published - Sep 2019
Event	29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019 - Barcelona, Spain Duration: Sep 9 2019 → Sep 13 2019

Publication series

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

Conference

Conference	29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019
Country/Territory	Spain
City	Barcelona
Period	9/9/19 → 9/13/19

Keywords

FPGA
Graph processing
On the fly
OpenCL
Shuffle

ASJC Scopus subject areas

Instrumentation
Artificial Intelligence
Computer Science Applications
Hardware and Architecture

Online availability

10.1109/FPL.2019.00020

Library availability

Discover UIUC Full Text

Cite this

Chen, X., Bajaj, R., Chen, Y., He, J., He, B., Wong, W. F., & Chen, D. (2019). On-the-fly parallel data shuffling for graph processing on OpenCL-based FPGAs. In I. Sourdis, C.-S. Bouganis, C. Alvarez, L. A. Toledo Diaz, P. Valero, & X. Martorell (Eds.), Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019 (pp. 67-73). Article 8892034 (Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/FPL.2019.00020

On-the-fly parallel data shuffling for graph processing on OpenCL-based FPGAs. / Chen, Xinyu; Bajaj, Ronak; Chen, Yao et al.
Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019. ed. / Ioannis Sourdis; Christos-Savvas Bouganis; Carlos Alvarez; Leonel Antonio Toledo Diaz; Pedro Valero; Xavier Martorell. Institute of Electrical and Electronics Engineers Inc., 2019. p. 67-73 8892034 (Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chen, X, Bajaj, R, Chen, Y, He, J, He, B, Wong, WF & Chen, D 2019, On-the-fly parallel data shuffling for graph processing on OpenCL-based FPGAs. in I Sourdis, C-S Bouganis, C Alvarez, LA Toledo Diaz, P Valero & X Martorell (eds), Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019., 8892034, Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019, Institute of Electrical and Electronics Engineers Inc., pp. 67-73, 29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019, Barcelona, Spain, 9/9/19. https://doi.org/10.1109/FPL.2019.00020

Chen X, Bajaj R, Chen Y, He J, He B, Wong WF et al. On-the-fly parallel data shuffling for graph processing on OpenCL-based FPGAs. In Sourdis I, Bouganis CS, Alvarez C, Toledo Diaz LA, Valero P, Martorell X, editors, Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 67-73. 8892034. (Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019). doi: 10.1109/FPL.2019.00020

Chen, Xinyu ; Bajaj, Ronak ; Chen, Yao et al. / On-the-fly parallel data shuffling for graph processing on OpenCL-based FPGAs. Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019. editor / Ioannis Sourdis ; Christos-Savvas Bouganis ; Carlos Alvarez ; Leonel Antonio Toledo Diaz ; Pedro Valero ; Xavier Martorell. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 67-73 (Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019).

@inproceedings{cd8e12a169ee40c885ee550bca56bc66,

title = "On-the-fly parallel data shuffling for graph processing on OpenCL-based FPGAs",

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.",

keywords = "FPGA, Graph processing, On the fly, OpenCL, Shuffle",

author = "Xinyu Chen and Ronak Bajaj and Yao Chen and Jiong He and Bingsheng He and Wong, {Weng Fai} and Deming Chen",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019 ; Conference date: 09-09-2019 Through 13-09-2019",

year = "2019",

month = sep,

doi = "10.1109/FPL.2019.00020",

language = "English (US)",

series = "Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "67--73",

editor = "Ioannis Sourdis and Christos-Savvas Bouganis and Carlos Alvarez and {Toledo Diaz}, {Leonel Antonio} and Pedro Valero and Xavier Martorell",

booktitle = "Proceedings - 29th International Conference on Field-Programmable Logic and Applications, FPL 2019",

address = "United States",

}

TY - GEN

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

AU - Chen, Xinyu

AU - Bajaj, Ronak

AU - Chen, Yao

AU - He, Jiong

AU - He, Bingsheng

AU - Wong, Weng Fai

AU - Chen, Deming

PY - 2019/9

Y1 - 2019/9

N2 - 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.

AB - 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.

KW - FPGA

KW - Graph processing

KW - On the fly

KW - OpenCL

KW - Shuffle

UR - http://www.scopus.com/inward/record.url?scp=85075632023&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075632023&partnerID=8YFLogxK

U2 - 10.1109/FPL.2019.00020

DO - 10.1109/FPL.2019.00020

M3 - Conference contribution

AN - SCOPUS:85075632023

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

SP - 67

EP - 73

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

A2 - Sourdis, Ioannis

A2 - Bouganis, Christos-Savvas

A2 - Alvarez, Carlos

A2 - Toledo Diaz, Leonel Antonio

A2 - Valero, Pedro

A2 - Martorell, Xavier

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 29th International Conferenceon Field-Programmable Logic and Applications, FPL 2019

Y2 - 9 September 2019 through 13 September 2019

ER -

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this