Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform

Zheming Jin; Hal Finkel

doi:10.1109/IA351965.2020.00014

Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform

Zheming Jin, Hal Finkel

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

2 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Proceedings of IA3 2020
Subtitle of host publication	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
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	63-67
Number of pages	5
ISBN (Electronic)	9780738110905
DOIs	https://doi.org/10.1109/IA351965.2020.00014
State	Published - Nov 2020
Externally published	Yes
Event	10th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2020 - Virtual, Atlanta, United States Duration: Nov 11 2020 → …

Publication series

Name	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

Conference

Conference	10th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2020
Country/Territory	United States
City	Virtual, Atlanta
Period	11/11/20 → …

Funding

ACKNOWLEDGMENT This research was supported by and used resources of the Argonne Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC02-06CH11357.

Keywords

FPGA
Irregular memory access
OpenCL
binary search

Access to Document

10.1109/IA351965.2020.00014

Cite this

Jin, Z., & Finkel, H. (2020). Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform. In 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 (pp. 63-67). Article 9407263 (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). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IA351965.2020.00014

Jin, Zheming ; Finkel, Hal. / Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform. 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. Institute of Electrical and Electronics Engineers Inc., 2020. pp. 63-67 (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).

@inproceedings{f33d245535ed458f869e1959d93dbd34,

title = "Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform",

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

keywords = "FPGA, Irregular memory access, OpenCL, binary search",

author = "Zheming Jin and Hal Finkel",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 10th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2020 ; Conference date: 11-11-2020",

year = "2020",

month = nov,

doi = "10.1109/IA351965.2020.00014",

language = "English",

series = "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",

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

pages = "63--67",

booktitle = "Proceedings of IA3 2020",

}

Jin, Z & Finkel, H 2020, Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform. in 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., 9407263, 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, Institute of Electrical and Electronics Engineers Inc., pp. 63-67, 10th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2020, Virtual, Atlanta, United States, 11/11/20. https://doi.org/10.1109/IA351965.2020.00014

Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform. / Jin, Zheming; Finkel, Hal.
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. Institute of Electrical and Electronics Engineers Inc., 2020. p. 63-67 9407263 (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).

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

TY - GEN

T1 - Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform

AU - Jin, Zheming

AU - Finkel, Hal

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 -

Jin Z, Finkel H. Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform. In 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. Institute of Electrical and Electronics Engineers Inc. 2020. p. 63-67. 9407263. (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). doi: 10.1109/IA351965.2020.00014

Performance Evaluation of the Vectorizable Binary Search Algorithms on an FPGA Platform

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this