{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,25]],"date-time":"2026-08-25T10:09:57Z","timestamp":1787652597717,"version":"build-2736575974"},"reference-count":37,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T00:00:00Z","timestamp":1582243200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020","doi-asserted-by":"publisher","award":["780681"],"award-info":[{"award-number":["780681"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2014such as large sequence sets in molecular biology\u2014are 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 \u2217 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\u2014of 512-bit signatures\u2014was 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.<\/jats:p>","DOI":"10.3390\/a13020047","type":"journal-article","created":{"date-parts":[[2020,2,21]],"date-time":"2020-02-21T10:49:16Z","timestamp":1582282156000},"page":"47","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Accelerating Binary String Comparisons with a Scalable, Streaming-Based System Architecture Based on FPGAs"],"prefix":"10.3390","volume":"13","author":[{"given":"Sarah","family":"Pilz","sequence":"first","affiliation":[{"name":"Center for Cognitive Interaction Technology (CITEC), Bielefeld University, 33619 Bielefeld, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2401-7862","authenticated-orcid":false,"given":"Florian","family":"Porrmann","sequence":"additional","affiliation":[{"name":"Center for Cognitive Interaction Technology (CITEC), Bielefeld University, 33619 Bielefeld, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Kaiser","sequence":"additional","affiliation":[{"name":"Center for Cognitive Interaction Technology (CITEC), Bielefeld University, 33619 Bielefeld, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Hagemeyer","sequence":"additional","affiliation":[{"name":"Center for Cognitive Interaction Technology (CITEC), Bielefeld University, 33619 Bielefeld, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James M.","family":"Hogan","sequence":"additional","affiliation":[{"name":"School of Computer Science, Queensland University of Technology, Brisbane City, QLD 4000, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ulrich","family":"R\u00fcckert","sequence":"additional","affiliation":[{"name":"Center for Cognitive Interaction Technology (CITEC), Bielefeld University, 33619 Bielefeld, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"key":"ref_1","unstructured":"IOPScience (2019, December 16). How to Deal with Petabytes of Data: The LHC Grid Project. Available online: https:\/\/iopscience.iop.org\/article\/10.1088\/0034-4885\/77\/6\/065902."},{"key":"ref_2","unstructured":"Wetterstrand, K.A. (2019, December 10). DNA Sequencing Costs: Data from the NHGRI Genome Sequencing Program (GSP), Available online: www.genome.gov\/sequencingcostsdata."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"EMBnet.journal (2019, December 16). Genomic Big Data Hitting the Storage Bottleneck. Available online: http:\/\/journal.embnet.org\/index.php\/embnetjournal\/article\/view\/910\/1371.","DOI":"10.14806\/ej.24.0.910"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of Common Molecular Subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2460","DOI":"10.1093\/bioinformatics\/btq461","article-title":"Search and clustering orders of magnitude faster than BLAST","volume":"26","author":"Edgar","year":"2010","journal-title":"Bioinformatics"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1093\/bib\/bbx067","article-title":"Alignment-free inference of hierarchical and reticulate phylogenomic relationships","volume":"20","author":"Bernard","year":"2019","journal-title":"Brief. Bioinform."},{"key":"ref_9","first-page":"142","article-title":"Locality-sensitive hashing for protein classification","volume":"158","author":"Nayak","year":"2014","journal-title":"Conferences in Research and Practice in Information Technology"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Buckingham, L., Chappell, T., Hogan, J.M., and Geva, S. (2017, January 24\u201327). Similarity Projection: A Geometric Measure for Comparison of Biological Sequences. Proceedings of the IEEE 13th International Conference on e-Science (e-Science), Auckland, New Zealand.","DOI":"10.1109\/eScience.2017.46"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Indyk, P., and Motwani, R. (1998, January 23). Approximate nearest neighbors: Towards removing the curse of dimensionality. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/276698.276876"},{"key":"ref_12","first-page":"518","article-title":"Similarity search in high dimensions via hashing","volume":"99","author":"Gionis","year":"1999","journal-title":"VLDB"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Manku, G.S., Jain, A., and Das Sarma, A. (2007, January 8). Detecting near-duplicates for web crawling. Proceedings of the 16th International Conference on World Wide Web, Banff, AB, Canada.","DOI":"10.1145\/1242572.1242592"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"De Vries, C.M., and Geva, S. (2012, January 5). Pairwise similarity of topsig document signatures. Proceedings of the Seventeenth Australasian Document Computing Symposium, New York, NY, USA.","DOI":"10.1145\/2407085.2407103"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/j.1538-7305.1950.tb00463.x","article-title":"Error detecting and error correcting codes","volume":"29","author":"Hamming","year":"1950","journal-title":"Bell Labs Tech. J."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Chappell, T., Geva, S., and Hogan, J.M. (2017, January 7\u20138). K-means clustering of biological sequences. Proceedings of the 22nd Australasian Document Computing Symposium, Brisbane, QLD, Australia.","DOI":"10.1145\/3166072.3166076"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Matsumura, H., Sugimura, M., Yamasaki, H., Tomita, Y., Baba, T., and Watanabe, Y. (2016, January 7\u201310). An FPGA-accelerated Partial Duplicate Image Retrieval Engine for a Document Search System. Proceedings of the 2016 IEEE Winter Conference on Applications of Computer Vision (WACV), Lake Placid, NY, USA.","DOI":"10.1109\/WACV.2016.7477662"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Liu, Y., and Schmidt, B. (2014, January 18\u201320). SWAPHI: Smith-waterman protein database search on Xeon Phi coprocessors. Proceedings of the 2014 IEEE 25th International Conference on Application-Specific Systems, Architectures and Processors, Zurich, Switzerland.","DOI":"10.1109\/ASAP.2014.6868657"},{"key":"ref_19","unstructured":"Khaire, S.A., and Wankhade, N.R. (2017, January 17\u201318). An Efficient Implementation of Smith Waterman Algorithm Using Distributed Computing. Proceedings of the 2017 International Conference on Computing, Communication, Control and Automation (ICCUBEA), Pune, India."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"de O. Sandes, E.F., Miranda, G., de Melo, A.C.M.A., Martorell, X., and Ayguad\u00e9, E. (2014, January 26\u201329). CUDAlign 3.0: Parallel Biological Sequence Comparison in Large GPU Clusters. Proceedings of the 2014 14th IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing, Chicago, IL, USA.","DOI":"10.1109\/CCGrid.2014.18"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.1109\/TPDS.2012.194","article-title":"Retrieving Smith-Waterman Alignments with Optimizations for Megabase Biological Sequences Using GPU","volume":"24","year":"2013","journal-title":"IEEE Trans. Parallel Distr. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Houtgast, E., Sima, V.-M., and Al-Ars, Z. (2017, January 23\u201325). High Performance Streaming Smith-Waterman Implementation with Implicit Synchronization on Intel FPGA using OpenCL. Proceedings of the 2017 IEEE 17th International Conference on Bioinformatics and Bioengineering (BIBE), Washington, DC, USA.","DOI":"10.1109\/BIBE.2017.000-6"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bekbolat, M., Kairatova, S., Shymyrbay, A., and Vipin, K. (2019, January 20\u201324). HBLast: An Open-Source FPGA Library for DNA Sequencing Acceleration. Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Rio de Janeiro, Brazil.","DOI":"10.1109\/IPDPSW.2019.00022"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Junid, S.A.M.A., Idros, M.F.M., Razak, A.H.A., Osman, F.N., and Tahir, N.M. (2017, January 10\u201312). Parallel processing cell score design of linear gap penalty smith-waterman algorithm. Proceedings of the 2017 IEEE 13th International Colloquium on Signal Processing & its Applications (CSPA), Batu Ferringhi, Malaysia.","DOI":"10.1109\/CSPA.2017.8064969"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"P\u00e9rez-Serrano, J., Sandes, E., de Melo, A.C.M.A., and Ujald\u00f3n, M. (2018). DNA sequences alignment in multi-GPUs: Acceleration and energy payoff. BMC Bioinform., 19.","DOI":"10.1186\/s12859-018-2389-6"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Liu, Y., Wirawan, A., and Schmidt, B. (2013). CUDASW++ 3.0: Accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions. BMC Bioinform., 14.","DOI":"10.1186\/1471-2105-14-117"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Pappalardo, F., Calonaci, C., Pennisi, M., Mastriani, E., and Motta, S. (April, January 31). HAMFAST: Fast Hamming Distance Computation. Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering, Los Angeles, CA, USA.","DOI":"10.1109\/CSIE.2009.223"},{"key":"ref_28","unstructured":"Pedroni, V.A. (2004, January 23\u201326). Compact Hamming-comparator-based rank order filter for digital {VLSI} and {FPGA} implementations. Proceedings of the 2004 IEEE International Symposium on Circuits and Systems, Vancouver, BC, Canada."},{"key":"ref_29","first-page":"167","article-title":"Efficient Hamming weight comparators for binary vectors based on accumulative and up\/down parallel counters","volume":"56","author":"Parhami","year":"2009","journal-title":"IEEE Trans. Circuits Syst. II Express Briefs"},{"key":"ref_30","first-page":"4825","article-title":"Digital Hamming weight and distance analyzers for binary vectors and matrices","volume":"9","author":"Sklyarov","year":"2013","journal-title":"Int. J. Innov. Comput. Infor. Contr."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"63","DOI":"10.4316\/AECE.2014.02011","article-title":"Hamming Weight Counters and Comparators based on Embedded DSP Blocks for Implementation in FPGA","volume":"14","author":"Sklyarov","year":"2014","journal-title":"Adv. Electr. Comput. Eng."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Sklyarov, V., Skliarova, I., and Silva, J. (2016). On-chip reconfigurable hardware accelerators for popcount computations. Int. J. Recon. Comput., 2016, Available online: http:\/\/downloads.hindawi.com\/journals\/ijrc\/2016\/8972065.pdf.","DOI":"10.1155\/2016\/8972065"},{"key":"ref_33","unstructured":"Intel (2019, December 10). Intel Xeon Prozessor E3-1226 v3. Available online: https:\/\/ark.intel.com\/content\/www\/de\/de\/ark\/products\/97463\/intel-xeon-processor-e3-1505m-v6-8m-cache-3-00-ghz.html."},{"key":"ref_34","unstructured":"Khronos Group Inc. (2019, October 10). Vector Data Types. Available online: https:\/\/www.khronos.org\/registry\/OpenCL\/sdk\/1.2\/docs\/man\/xhtml\/vectorDataTypes.html."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Hahne, E.L. (1986). Round Robin Scheduling for Fair Flow Control in Data Communication Networks. NASA STI\/Recon Technical Report N, 86.","DOI":"10.21236\/ADA166728"},{"key":"ref_36","unstructured":"Goronzy, G. (2017, December 12). VHDL-Based Round Robin Arbiter. Available online: https:\/\/bitbucket.org\/grigorig\/axisnoc_router\/src\/master\/src\/ArbiterRR.vhd."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"e5261","DOI":"10.7717\/peerj.5261","article-title":"Staphylococcus aureus viewed from the perspective of 40,000+ genomes","volume":"6","author":"Petit","year":"2018","journal-title":"PeerJ"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/47\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:59:51Z","timestamp":1760173191000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,21]]},"references-count":37,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["a13020047"],"URL":"https:\/\/doi.org\/10.3390\/a13020047","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,21]]}}}