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.
- J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. Efficient Pattern Matching over Event Streams. In SIGMOD '08, New York, NY, USA, 2008. Google ScholarDigital Library
- C. Clark and D. Schimmel. Scalable Pattern Matching for High Speed Networks. In FCCM '04, Washington, DC, USA, 2004. Google ScholarDigital Library
- 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 ScholarDigital Library
- EsperTech Inc. http://esper.codehaus.org/.Google Scholar
- R. W. Floyd and J. Ullman. The Compilation of Regular Expressions into Integrated Circuits. J. ACM, 29(3), 1982. Google ScholarDigital Library
- 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 Scholar
- J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison Wesley, 2000. Google ScholarDigital Library
- Kickfire. http://www.kickfire.com/.Google Scholar
- R. McNaughton and H. Yamada. Regular Expressions and State Graphs for Automata. IEEE Transactions on Electronic Computers, 9, 1960.Google Scholar
- A. Mitra, W. Najjar, and L. Bhuyan. Compiling PCRE to FPGA for accelerating SNORT IDS. In ANCS'07, New York, NY, USA, 2007. Google ScholarDigital Library
- 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 Scholar
- R. Müller, J. Teubner, and G. Alonso. Streams on Wires - A Query Compiler for FPGAs. In VLDB'09, Lyon, France, 2009.Google Scholar
- Netezza Corp. http://www.netezza.com/.Google Scholar
- 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 ScholarDigital Library
- R. Sidhu and V. Prasanna. Fast Regular Expression Matching Using FPGAs. In FCCM'01, Los Alamitos, CA, USA, 2001. Google ScholarCross Ref
- J. Teubner, R. Müller, and G. Alonso. FPGA Acceleration for the Frequent Item Problem. In ICDE'10, Long Beach, CA, USA, 2010.Google Scholar
- K. Thompson. Programming Techniques: Regular Expression Search Algorithm. Commun. ACM, 11(6), 1968. Google ScholarDigital Library
- 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 ScholarDigital Library
- XtremeData, Inc. http://www.xtremedata.com/.Google Scholar
- 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 ScholarDigital Library
- F. Zemke, A. Witkowski, M. Cherniack, and L. Colby. Pattern Matching in Sequences of Rows. In Technical Report ANSI Standard Proposal, 2007.Google Scholar
Recommendations
Large-scale wire-speed packet classification on FPGAs
FPGA '09: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arraysMulti-field packet classification is a key enabling function of a variety of network applications, such as firewall processing, Quality of Service differentiation, traffic billing, and other value added services. Although a plethora of research has been ...
Boolean matching for complex PLBs in LUT-based FPGAs with application to architecture evaluation
FPGA '98: Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arraysIn this paper, we developed Boolean matching techniques for complex programmable logic blocks (PLBs) in LUT-based FPGAs. A complex PLB can not only be used as a K-input LUT, but also can implement some wide functions of more than K variables. We apply ...
Comments