Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs

Pilz S, Porrmann F, Kaiser M, Hagemeyer J, Hogan JM, Rückert U (2020)
Algorithms 13(2): 47.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA 1.70 MB
Abstract / Bemerkung
This paper is concerned with Field Programmable Gate Arrays (FPGA)-based systems for energy-efficient high-throughput string comparison. Modern applications which involve comparisons across large data sets—such as large sequence sets in molecular biology—are by their nature computationally intensive. In this work, we present a scalable FPGA-based system architecture to accelerate the comparison of binary strings. The current architecture supports arbitrary lengths in the range 16 to 2048-bit, covering a wide range of possible applications. In our example application, we consider DNA sequences embedded in a binary vector space through Locality Sensitive Hashing (LSH) one of several possible encodings that enable us to avoid more costly character-based operations. Here the resulting encoding is a 512-bit binary signature with comparisons based on the Hamming distance. In this approach, most of the load arises from the calculation of the O ( m ∗ n ) Hamming distances between the signatures, where m is the number of queries and n is the number of signatures contained in the database. Signature generation only needs to be performed once, and we do not consider it further, focusing instead on accelerating the signature comparisons. The proposed FPGA-based architecture is optimized for high-throughput using hundreds of computing elements, arranged in a systolic array. These core computing elements can be adapted to support other string comparison algorithms with little effort, while the other infrastructure stays the same. On a Xilinx Virtex UltraScale+ FPGA (XCVU9P-2), a peak throughput of 75.4 billion comparisons per second—of 512-bit signatures—was achieved, using a design with 384 parallel processing elements and a clock frequency of 200 MHz. This makes our FPGA design 86 times faster than a highly optimized CPU implementation. Compared to a GPU design, executed on an NVIDIA GTX1060, it performs nearly five times faster.
Stichworte
FPGA; bioinformatics; multiple string matching; parallel computing; Hamming distance; locality sensitive hashing; hardware acceleration; parallel system architecture
Erscheinungsjahr
2020
Zeitschriftentitel
Algorithms
Band
13
Ausgabe
2
Art.-Nr.
47
eISSN
1999-4893
Page URI
https://pub.uni-bielefeld.de/record/2941646

Zitieren

Pilz S, Porrmann F, Kaiser M, Hagemeyer J, Hogan JM, Rückert U. Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs. Algorithms. 2020;13(2): 47.
Pilz, S., Porrmann, F., Kaiser, M., Hagemeyer, J., Hogan, J. M., & Rückert, U. (2020). Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs. Algorithms, 13(2), 47. doi:10.3390/a13020047
Pilz, S., Porrmann, F., Kaiser, M., Hagemeyer, J., Hogan, J. M., and Rückert, U. (2020). Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs. Algorithms 13:47.
Pilz, S., et al., 2020. Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs. Algorithms, 13(2): 47.
S. Pilz, et al., “Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs”, Algorithms, vol. 13, 2020, : 47.
Pilz, S., Porrmann, F., Kaiser, M., Hagemeyer, J., Hogan, J.M., Rückert, U.: Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs. Algorithms. 13, : 47 (2020).
Pilz, Sarah, Porrmann, Florian, Kaiser, Martin, Hagemeyer, Jens, Hogan, James M., and Rückert, Ulrich. “Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs”. Algorithms 13.2 (2020): 47.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Creative Commons Namensnennung 4.0 International Public License (CC-BY 4.0):
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2020-04-20T11:37:31Z
MD5 Prüfsumme
35f5e1a25aaea68678839e04e485cc02

Link(s) zu Volltext(en)
Access Level
OA Open Access