skip to main content
research-article

Complex event detection at wire speed with FPGAs

Published:01 September 2010Publication History
Skip Abstract Section

Abstract

Complex event detection is an advanced form of data stream processing where the stream(s) are scrutinized to identify given event patterns. The challenge for many complex event processing (CEP) systems is to be able to evaluate event patterns on high-volume data streams while adhering to real-time constraints. To solve this problem, in this paper we present a hardware-based complex event detection system implemented on field-programmable gate arrays (FPGAs). By inserting the FPGA directly into the data path between the network interface and the CPU, our solution can detect complex events at gigabit wire speed with constant and fully predictable latency, independently of network load, packet size, or data distribution. This is a significant improvement over CPU-based systems and an architectural approach that opens up interesting opportunities for hybrid stream engines that combine the flexibility of the CPU with the parallelism and processing power of FPGAs.

References

  1. J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. Efficient Pattern Matching over Event Streams. In SIGMOD '08, New York, NY, USA, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. C. Clark and D. Schimmel. Scalable Pattern Matching for High Speed Networks. In FCCM '04, Washington, DC, USA, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. N. Dindar, B. Güç, P. Lau, A. Özaland M. Soner, and N. Tatbul. Deja Vu: Declarative Pattern Matching over Live and Archived Streams of Events. In SIGMOD'09, Providence, RI, USA, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. EsperTech Inc. http://esper.codehaus.org/.Google ScholarGoogle Scholar
  5. R. W. Floyd and J. Ullman. The Compilation of Regular Expressions into Integrated Circuits. J. ACM, 29(3), 1982. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. D. Gyllstrom, E. Wu, H. Chae, Y. Diao, P. Stahlberg, and G. Anderson. SASE: Complex Event Processing over Streams. In CIDR'07, Asilomar, CA, USA, 2007.Google ScholarGoogle Scholar
  7. J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison Wesley, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Kickfire. http://www.kickfire.com/.Google ScholarGoogle Scholar
  9. R. McNaughton and H. Yamada. Regular Expressions and State Graphs for Automata. IEEE Transactions on Electronic Computers, 9, 1960.Google ScholarGoogle Scholar
  10. A. Mitra, W. Najjar, and L. Bhuyan. Compiling PCRE to FPGA for accelerating SNORT IDS. In ANCS'07, New York, NY, USA, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. A. Mitra, M. R. Vieira, P. Bakalov, V. J. Tsotras, and W. A. Najjar. Boosting XML Filtering Through a Scalable FPGA-Based Architecture. In CIDR'09, Asilomar, CA, USA, 2009.Google ScholarGoogle Scholar
  12. R. Müller, J. Teubner, and G. Alonso. Streams on Wires - A Query Compiler for FPGAs. In VLDB'09, Lyon, France, 2009.Google ScholarGoogle Scholar
  13. Netezza Corp. http://www.netezza.com/.Google ScholarGoogle Scholar
  14. M. Sadoghi, M. Labrecque, H. Singh, W. Shum, and H. Jacobsen. Efficient Event Processing through Reconfigurable Hardware for Algorithmic Trading. In VLDB'10, Singapore, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. R. Sidhu and V. Prasanna. Fast Regular Expression Matching Using FPGAs. In FCCM'01, Los Alamitos, CA, USA, 2001. Google ScholarGoogle ScholarCross RefCross Ref
  16. J. Teubner, R. Müller, and G. Alonso. FPGA Acceleration for the Frequent Item Problem. In ICDE'10, Long Beach, CA, USA, 2010.Google ScholarGoogle Scholar
  17. K. Thompson. Programming Techniques: Regular Expression Search Algorithm. Commun. ACM, 11(6), 1968. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. P. Vaidya, J. Lee, F. Bowen, Y. Du, C. Nadungodage, and Y. Xia. Symbiote: A Reconfigurable Logic Assisted data Stream Management System (RLADSMS). In SIGMOD'10, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. XtremeData, Inc. http://www.xtremedata.com/.Google ScholarGoogle Scholar
  20. Y. Yang, W. Jiang, and V. Prasanna. Compact Architecture for High-Throughput Regular Expression Matching on FPGA. In ANCS'08, San Jose, CA, USA, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. F. Zemke, A. Witkowski, M. Cherniack, and L. Colby. Pattern Matching in Sequences of Rows. In Technical Report ANSI Standard Proposal, 2007.Google ScholarGoogle Scholar

Recommendations

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Sign in

Full Access

  • Published in

    cover image Proceedings of the VLDB Endowment
    Proceedings of the VLDB Endowment  Volume 3, Issue 1-2
    September 2010
    1658 pages

    Publisher

    VLDB Endowment

    Publication History

    • Published: 1 September 2010
    Published in pvldb Volume 3, Issue 1-2

    Qualifiers

    • research-article

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader