Constructing Concurrent Data Structures on FPGA with Channels

H. Yan, Z. Li, L. Liu, S. Yin, S. Wei, in: Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 2019.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
; ; ; ;
Abstract
The performance of High-Level Synthesis (HLS) applications with irregular data structures is limited by its imperative programming paradigm like C/C++. In this paper, we show that constructing concurrent data structures with channels, a programming construct derived from CSP (communicating sequential processes) paradigm, is an effective approach to improve the performance of these applications. We evaluate concurrent data structure for FPGA by synthesizing a K-means clustering algorithm on the Intel HARP2 platform. A fully pipelined KMC processing element can be synthesized from OpenCL with the help of a SPSC (single-producer-single-consumer) queue and stack built from channels, achieving 15.2x speedup over a sequential baseline. The number of processing element can be scaled up by leveraging a MPMC (multiple-producer-multiple-consumer) stack with work distribution for dynamic load balance. Evaluation shows that an additional 3.5x speedup can be achieved when 4 processing element is instantiated. These results show that the concurrent data structure built with channels has great potential for improving the parallelism of HLS applications. We hope that our study will stimulate further research into the potential of channel-based HLS.
Publishing Year
Proceedings Title
Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays
LibreCat-ID

Cite this

Yan H, Li Z, Liu L, Yin S, Wei S. Constructing Concurrent Data Structures on FPGA with Channels. In: Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. ; 2019. doi:10.1145/3289602.3293921
Yan, H., Li, Z., Liu, L., Yin, S., & Wei, S. (2019). Constructing Concurrent Data Structures on FPGA with Channels. In Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. https://doi.org/10.1145/3289602.3293921
@inproceedings{Yan_Li_Liu_Yin_Wei_2019, title={Constructing Concurrent Data Structures on FPGA with Channels}, DOI={10.1145/3289602.3293921}, booktitle={Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays}, author={Yan, Hui and Li, Zhaoshi and Liu, Leibo and Yin, Shouyi and Wei, Shaojun}, year={2019} }
Yan, Hui, Zhaoshi Li, Leibo Liu, Shouyi Yin, and Shaojun Wei. “Constructing Concurrent Data Structures on FPGA with Channels.” In Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 2019. https://doi.org/10.1145/3289602.3293921.
H. Yan, Z. Li, L. Liu, S. Yin, and S. Wei, “Constructing Concurrent Data Structures on FPGA with Channels,” in Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 2019.
Yan, Hui, et al. “Constructing Concurrent Data Structures on FPGA with Channels.” Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, 2019, doi:10.1145/3289602.3293921.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search