TY - GEN
T1 - Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform
AU - Jin, Zheming
AU - Finkel, Hal
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/11
Y1 - 2020/11
N2 - Field-programmable gate arrays (FPGAs) are becoming promising heterogeneous computing components. In the meantime, high-level synthesis has been pushing the FPGA-based development from a register-transfer level to a high-level-language design flow using the OpenCL and C/C++ programming languages. The performance of binary search applications is often associated with irregular memory access patterns to off-chip memory. In this paper, we implement the binary search algorithms using OpenCL, and evaluate their performance on an Intel Arria 10 based FPGA platform. Based on the evaluation results, we optimize the grid search in XSBench by vectorizing and replicating the binary search kernel. We identify the computational overhead in the implementations of the vectorizable binary search algorithms, and overcome it by grouping work-items into work-groups. Our optimizations improve the performance of the grid search using the classic binary search by a factor of 1.75 on the FPGA.
AB - Field-programmable gate arrays (FPGAs) are becoming promising heterogeneous computing components. In the meantime, high-level synthesis has been pushing the FPGA-based development from a register-transfer level to a high-level-language design flow using the OpenCL and C/C++ programming languages. The performance of binary search applications is often associated with irregular memory access patterns to off-chip memory. In this paper, we implement the binary search algorithms using OpenCL, and evaluate their performance on an Intel Arria 10 based FPGA platform. Based on the evaluation results, we optimize the grid search in XSBench by vectorizing and replicating the binary search kernel. We identify the computational overhead in the implementations of the vectorizable binary search algorithms, and overcome it by grouping work-items into work-groups. Our optimizations improve the performance of the grid search using the classic binary search by a factor of 1.75 on the FPGA.
KW - FPGA
KW - Irregular memory access
KW - OpenCL
KW - binary search
UR - http://www.scopus.com/inward/record.url?scp=85105518589&partnerID=8YFLogxK
U2 - 10.1109/IA351965.2020.00014
DO - 10.1109/IA351965.2020.00014
M3 - Conference contribution
AN - SCOPUS:85105518589
T3 - Proceedings of IA3 2020: 10th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2020: The International Conference for High Performance Computing, Networking, Storage and Analysis
SP - 63
EP - 67
BT - Proceedings of IA3 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 10th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2020
Y2 - 11 November 2020
ER -