High-performance regular expression scanning on the Cell/B.E. processor

ABSTRACT

Matching regular expressions (regexps) is a very common work-load. For example, tokenization, which consists of recognizing words or keywords in a character stream, appears in every search engine indexer. Tokenization also consumes 30% or more of most XML processors' execution time and represents the first stage of any programming language compiler.

Despite the multi-core revolution, regexp scanner generators like flex haven't changed much in 20 years, and they do not exploit the power of recent multi-core architectures (e.g., multiple threads and wide SIMD units). This is unfortunate, especially given the pervasive importance of search engines and the fast growth of our digital universe. Indexing such data volumes demands precisely the processing power that multi-cores are designed to offer.

We present an algorithm and a set of techniques for using multi-core features such as multiple threads and SIMD instructions to perform parallel regexp-based tokenization.

As a proof of concept, we present a family of optimized kernels that implement our algorithm, providing the features of flex on the Cell/B.E. processor at top performance. Our kernels achieve almost-ideal resource utilization (99.2% of the clock cycles are non-NOP issues). They deliver a peak throughput of 14.30 Gbps per Cell chip, and 9.76 Gbps on Wikipedia input: a remarkable performance, comparable to dedicated hardware solutions. Also, our kernels show speedups of 57-81× over flex on the Cell.

Our approach is valuable because it is easily portable to other SIMD-enabled processors, and there is a general trend toward more and wider SIMD instructions in architecture design.

REFERENCES

• 1: comScore Releases 2007 U.S. Internet Year in Review, Press Release, Jan. 2008.
• 2: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 3: S. Antonatos, K. Anagnostakis, M. Polychronakis, and E. Markatos. Performance analysis of content matching intrusion detection systems. In 4th IEEE/IPSJ Symp. on Applications and the Internet (SAINT 2004)., 2004.
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: L. Bu and J. A. Chandy. A CAM-based keyword match processor architecture. Microelectronics Jnl., 37(8):828--836, 2006.
• 6: Peter Bumbulis , Donald D. Cowan, RE2C: a more versatile scanner generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.70-84, March–Dec. 1993 [doi>10.1145/176454.176487]
• 7: Robert D. Cameron, A case study in SIMD text processing with parallel bit streams: UTF-8 to UTF-16 transcoding, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345222]
• 8: R. D. Cameron. Method and apparatus for processing character streams, U.S. Patent 7400271, July 2008.
• 9: Chia-Hsiang Chang , Robert Paige, From Regular Expressions to DFA's Using Compressed NFA's, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.90-110, April 29-May 01, 1992
• 10: J. Degener. ANSI C grammar, lex specification, http://www.lysator.liu.se/c/ANSI-C-grammar-l.html.
• 11: Sarang Dharmapurikar , Praveen Krishnamurthy , Todd S. Sproull , John W. Lockwood, Deep Packet Inspection using Parallel Bloom Filters, IEEE Micro, v.24 n.1, p.52-61, January 2004 [doi>10.1109/MM.2004.1268997]
• 12: N. Firasta, M. Buxton, P. Jinbo, K. Nasri, and S. Kuo. Intel AVX: New Frontiers in Performance Improvements and Energy Efficiency, Mar. 2008.
• 13: T. A. S. Foundation. Lucene, http://lucene.apache.org.
• 14: N. Goyal, J. Ormont, R. Smith, K. Sankaralingam, and C. Estan. Signature matching in network processing using SIMD/GPU architectures. Technical Report 1628, University of Wisconsin at Madison, Jan. 2008.
• 15: J. Grosch, Efficient generation of lexical analyzers, Software—Practice & Experience, v.19 n.11, p.1089-1103, Nov. 1989 [doi>10.1002/spe.4380191106]
• 16: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 17: H. Peter Hofstee, Power Efficient Processor Architecture and The Cell Processor, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.258-262, February 12-16, 2005 [doi>10.1109/HPCA.2005.26]
• 18: B. L. Hutchings , R. Franklin , D. Carver, Assisting Network Intrusion Detection with Reconfigurable Hardware, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.111, September 22-24, 2002
• 19: IDC Corporation. The expanding digital universe. White Paper, March 2007.
• 20: Intel Corp. Tera-scale research prototype - connecting 80 simple cores on a single test chip, October 2006.
• 21: Intel Corp. Intel SSE4 Programming Reference, Reference Number: D91561-001, Apr. 2007.
• 22: F. Iorio and J. V. Lunteren. Fast pattern matching on the Cell Broadband Engine. In 2008 Workshop on Cell Systems and Applications (WCSA), affiliated with the 2008 Intl. Symp. on Computer Architecture (ISCA'08), Beijing, China, June 2008.
• 23: J. A. Kahle , M. N. Day , H. P. Hofstee , C. R. Johns , T. R. Maeurer , D. Shippy, Introduction to the cell multiprocessor, IBM Journal of Research and Development, v.49 n.4/5, p.589-604, July 2005
• 24: Michael Kistler , Michael Perrone , Fabrizio Petrini, Cell Multiprocessor Communication Network: Built for Speed, IEEE Micro, v.26 n.3, p.10-23, May 2006 [doi>10.1109/MM.2006.49]
• 25: Janghaeng Lee , Sung Ho Hwang , Neungsoo Park , Seong-Won Lee , Sunglk Jun , Young Soo Kim, A high performance NIDS using FPGA-based regular expression matching, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244259]
• 26: John W. Lockwood , Naji Naufel , Jon S. Turner , David E. Taylor, Reprogrammable network packet processing on the field programmable port extender (FPX), Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.87-93, February 2001, Monterey, California, United States [doi>10.1145/360276.360304]
• 27: James Moscola , John Lockwood , Ronald P. Loui , Michael Pachos, Implementation of a Content-Scanning Module for an Internet Firewall, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.31, April 09-11, 2003
• 28: John Nickolls , Ian Buck , Michael Garland , Kevin Skadron, Scalable Parallel Programming with CUDA, Queue, v.6 n.2, March/April 2008 [doi>10.1145/1365490.1365500]
• 29: Matthias Nicola , Jasmi John, XML parsing: a threat to database performance, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956898]
• 30: V. Paxson. flex - a fast lexical analyzer generator, 1988.
• 31: E. Perkins, M. Kostoulas, A. Heifets, M. Matsa, and N. Mendelsohn. Performance analysis of XML APIs. In XML 2005 Conf. and Exposition, Nov. 2005.
• 32: D.P. Scarpazza, O. Villa, and F. Petrini. Peak-performance DFA-based string matching on the Cell processor. In Third Intl. Workshop on System Management Techniques, Processes, and Services (SMTPS), held in conjunction with IPDPS, Mar. 2007.
• 33: D.P. Scarpazza, O. Villa, and F. Petrini. High-Speed String Searching against Large Dictionaries on the Cell/B.E. Processor. In 22nd IEEE Intl. Parallel & Distributed Processing Symp. (IPDPS'08), Miami, Florida, Apr. 2008.
• 34: Larry Seiler , Doug Carmean , Eric Sprangle , Tom Forsyth , Michael Abrash , Pradeep Dubey , Stephen Junkins , Adam Lake , Jeremy Sugerman , Robert Cavin , Roger Espasa , Ed Grochowski , Toni Juan , Pat Hanrahan, Larrabee: a many-core x86 architecture for visual computing, ACM SIGGRAPH 2008 papers, August 11-15, 2008, Los Angeles, California
• 35: I. Sourdis and D. Pnevmatikatos. Fast, large-scale string match for a 10 Gbps FPGA-based network intrusion. In 13th Conf. on Field Programmable Logic and Applications (FPL'03)., September 2003.
• 36: I. Sourdis and D. Pnevmatikatos. Pre-decoded CAMs for efficient and high-speed NIDS pattern matching, 2004.
• 37: D. C. Suresh, Z. Guo, B. Buyukkurt, and W. A. Najjar. Automatic compilation framework for bloom filter based intrusion detection. In Second Intl. Workshop on Reconfigurable Computing: Architectures and Applications (ARC'06), pages 413--418, 2006.
• 38: A. D. Thurston. Parsing computer languages with an automaton compiled from a single regular expression. In O. H. Ibarra and H.-C. Yen, editors, CIAA, volume 4094 of Lecture Notes in Computer Science, pages 285--286. Springer, 2006.
• 39: J. van Lunteren. High-performance pattern-matching for intrusion detection. In 25th IEEE Intl. Conf. on Computer Communications (INFOCOM 2006), pages 1--13, Apr. 2006.
• 40: O. Villa, D. Chavarria, and K. Maschhoff. Input-independent, scalable and fast string matching on the Cray XMT. In 23nd IEEE Intl. Parallel & Distributed Processing Symp. (IPDPS'09), 2009.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Algorithms, Design, Performance

Keywords:
cell processor, multi-core, regular expressions