David Sidler
Gustavo Alonso
ABSTRACT
Taking advantage of recently released hybrid multicore architectures, such as the Intel's Xeon+FPGA machine, where the FPGA has coherent access to the main memory through the QPI bus, we explore the benefits of specializing operators to hardware. We focus on two commonly used SQL operators for strings: LIKE, and REGEXP_LIKE, and provide a novel and efficient implementation of these operators in reconfigurable hardware. We integrate the hardware accelerator into MonetDB, a main-memory column store, and demonstrate a significant improvement in response time and throughput. Our Hardware User Defined Function (HUDF) can speed up complex pattern matching by an order of magnitude in comparison to the database running on a 10-core CPU. The insights gained from integrating hardware based string operators into MonetDB should also be useful for future designs combining hardware specialization and databases.
- Altera. Programming FPGAs with OpenCL. https://www.altera.com/content/dam/altera-www/global/en_US/pdfs/literature/wp/wp-01173-opencl.pdf.Google Scholar
- R. S. Boyer and J. S. Moore. A fast string searching algorithm. Communications of the ACM, 20(10):762--772, 1977. Google ScholarDigital Library
- R. Chen and V. K. Prasanna. Accelerating Equi-Join on a CPU-FPGA Heterogeneous Platform. FCCM'16.Google Scholar
- C. Clark and D. Schimmel. Scalable pattern matching for high speed networks. In FCCM'04. Google ScholarDigital Library
- C. Dennl, D. Ziener, and J. Teich. Acceleration of SQL restrictions and aggregations through FPGA-based dynamic partial reconfiguration. In FCCM'13. Google ScholarDigital Library
- J. Do, Y.-S. Kee, J. M. Patel, et al. Query processing on Smart SSDs: Opportunities and challenges. In SIGMOD'13. Google ScholarDigital Library
- Y. Fang, T. T. Hoang, M. Becchi, and A. A. Chien. Fast support for unstructured data processing: The unified automata processor. In MICRO-48'15. Google ScholarDigital Library
- D. Ficara, S. Giordano, G. Procissi, et al. An improved DFA for fast regular expression matching. ACM SIGCOMM, 38(5):29--40, 2008. Google ScholarDigital Library
- R. W. Floyd and J. Ullman. The compilation of regular expressions into integrated circuits. J. ACM, 29(3), 1982. Google ScholarDigital Library
- E. S. Fukuda, H. Inoue, T. Takenaka, et al. Caching memcached at reconfigurable network interface. In FPL'14.Google Scholar
- R. J. Halstead, B. Sukhwani, H. Min, M. Thoennes, P. Dube, S. Asaad, and B. Iyer. Accelerating join operation for relational databases with FPGAs. In FCCM'13. Google ScholarDigital Library
- M. Hutton. Architectural paths to faster and more robust FPGAs. http://www.fpl2015.org/pdf/keynotes/3.pdf.Google Scholar
- Z. István, D. Sidler, and G. Alonso. Runtime parameterizable regular expression operators for databases. In FCCM'16.Google Scholar
- Z. Istvan, L. Woods, and G. Alonso. Histograms as a side effect of data movement for big data. In SIGMOD'14. Google ScholarDigital Library
- Y. Kaneta, S.-i. Minato, and H. Arimura. Fast bit-parallel matching for network and regular expressions. In SPIRE'10. Google ScholarDigital Library
- T. Karnagel, R. Müller, and G. M. Lohman. Optimizing GPU-accelerated Group-By and aggregation. In ADMS'15.Google Scholar
- D. E. Knuth, J. H. Morris, Jr, and V. R. Pratt. Fast pattern matching in strings. SIAM journal on computing, 6(2):323--350, 1977.Google Scholar
- C.-H. Lin, C.-H. Liu, and S.-C. Chang. Accelerating regular expression matching using hierarchical parallel machines on GPU. In GLOBECOM'11.Google Scholar
- F. Marass and C. Upton. Sequence searcher: A Java tool to perform regular expression and fuzzy searches of multiple DNA and protein sequences. BMC research notes, 2(1):14, 2009.Google Scholar
- A. Mitra, W. Najjar, and L. Bhuyan. Compiling PCRE to FPGA for accelerating snort ids. In ANCS'07. Google ScholarDigital Library
- R. Mueller, J. Teubner, and G. Alonso. Streams on wires: a query compiler for FPGAs. PVLDB, 2(1):229--240, 2009. Google ScholarDigital Library
- M. Najafi, M. Sadoghi, and H.-A. Jacobsen. Configurable hardware-based streaming architecture using online programmable-blocks. In ICDE'15.Google Scholar
- M. Najafi, M. Sadoghi, and H.-A. Jacobsen. Flexible query processor on FPGAs. PVLDB, 6(12):1310--1313, 2013. Google ScholarDigital Library
- H. Noyes et al. Microns automata processor architecture: Reconfigurable and massively parallel automata processing. In HEART'14.Google Scholar
- N. Oliver, R. Sharma, S. Chang, et al. A reconfigurable computing system based on a cache-coherent fabric. In ReConFig'11. Google ScholarDigital Library
- V. Paxson. Bro: a system for detecting network intruders in real-time. Computer networks, 31(23):2435--2463, 1999. Google ScholarDigital Library
- H. Pirk. Efficient cross-device query processing. In The VLDB PhD Workshop, 2012.Google Scholar
- P.K. Gupta. Accelerating datacenter workloads. http://www.fpl2016.org/slides/Gupta%20--%20Accelerating%20Datacenter%20Workloads.pdf.Google Scholar
- A. Putnam, A. M. Caulfield, E. S. Chung, D. Chiou, et al. A reconfigurable fabric for accelerating large-scale datacenter services. In ISCA'14. Google ScholarDigital Library
- M. Roesch. Snort - lightweight intrusion detection for networks. In LISA'99. Google ScholarDigital Library
- M. Sadoghi, R. Javed, N. Tarafdar, H. Singh, R. Palaniappan, and H.-A. Jacobsen. Multi-query stream processing on FPGAs. In ICDE'12. Google ScholarDigital Library
- R. Sidhu and V. Prasanna. Fast regular expression matching using FPGAs. In FCCM'01. Google ScholarDigital Library
- E. Sitaridi, O. Polychroniou, and K. A. Ross. SIMD-accelerated regular expression matching. In DAMON'16. Google ScholarDigital Library
- E. A. Sitaridi and K. A. Ross. GPU-accelerated string matching for database applications. PVLDB, 25(5):719--740, Oct. 2016. Google ScholarDigital Library
- J. Stuecheli, B. Blaner, C. Johns, and M. Siegel. CAPI: A coherent accelerator processor interface. IBM J. Research and Development, 59(1), Jan 2015.Google ScholarDigital Library
- J. Teubner and L. Woods. Data Processing on FPGAs. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2013. Google ScholarDigital Library
- J. Teubner, L. Woods, and C. Nie. Skeleton automata for FPGAs: reconfiguring without reconstructing. In SIGMOD'12. Google ScholarDigital Library
- W. S. Todd Mytkowicz, Madan Musuvathi. Data-parallel finite-state machines. ASPLOS'14. Google ScholarDigital Library
- T. Ueda, M. Ito, and M. Ohara. A Dynamically Reconfigurable Equi-Joiner on FPGA. IBM Tehnical Report RT0969, 2015.Google Scholar
- L. Woods, Z. István, and G. Alonso. Ibex - an intelligent storage engine with support for advanced SQL off-loading. PVLDB, 7(11), July 2014. Google ScholarDigital Library
- L. Woods, J. Teubner, and G. Alonso. Complex event detection at wire speed with FPGAs. PVLDB, 3(1--2):660--669, 2010. Google ScholarDigital Library
- Xilinx Inc. Vivado Design Suite User Guide: High-Level Synthesis.Google Scholar
- Y.-H. E. Yang, W. Jiang, and V. K. Prasanna. Compact architecture for high-throughput regular expression matching on FPGA. In ANCS'08. Google ScholarDigital Library
Index Terms
- Accelerating Pattern Matching Queries in Hybrid CPU-FPGA Architectures
Recommendations
Compact architecture for high-throughput regular expression matching on FPGA
ANCS '08: Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications SystemsIn this paper we present a novel architecture for high-speed and high-capacity regular expression matching (REM) on FPGA. The proposed REM architecture, based on nondeterministic finite automaton (RE-NFA), efficiently constructs regular expression ...
High-Performance and Compact Architecture for Regular Expression Matching on FPGA
We present the design, implementation and evaluation of a high-performance architecture for regular expression matching (REM) on field-programmable gate array (FPGA). Each regular expression (regex) is first parsed into a concise token list ...
Pattern-unit based regular expression matching with reconfigurable function unit
ICCSA'10: Proceedings of the 2010 international conference on Computational Science and Its Applications - Volume Part IVRegular Expression (RE) is widely used in many aspects due to its high expressiveness, flexibility and compactness, which requires a high-performance and efficient matching method. A novel approach to accelerate RE pattern matching based on Pattern-Unit ...
Comments