research-article

Exact multi-pattern string matching on the cell/b.e. processor

Authors:

Daniele Paolo Scarpazza,

Fabrizio PetriniAuthors Info & Claims

CF '08: Proceedings of the 5th conference on Computing frontiers

Pages 33 - 42

https://doi.org/10.1145/1366230.1366237

Published: 05 May 2008 Publication History

Abstract

String searching is the computationally intensive kernel of many security and network applications like search engines, intrusion detection systems, virus scanners and spam filters. The growing size of on-line content and the increasing wire speeds push the need for fast --and often real-time, string searching solutions.

Multi-core processors are gaining increasing popularity, thanks to their unprecedented computing power, but they are also bringing new programming challenges.

This paper describes a class of high-performance exact string searching solutions that we have optimized for the IBM Cell/B.E. processor using the well known Aho-Corasick algorithm. This class provides several trade-offs between performance and dictionary size. When dictionaries are small enough to fit in the local memories of the processing cores, the throughput reaches 40 Gbps per processor. With larger dictionaries (as many as hundreds of thousands patterns), the typical throughput is between 1.6 and 2.2 Gbps per processor.

References

[1]

IDC Corporation. The expanding digital universe. White Paper, March 2007.

[2]

Martin Roesch. Snort: Lightweight intrusion detection for networks. In Proc. 13th USENIX Conf. on Systems Administration (LISA-99), Seattle, WA, pages 229-?238, 1999.

Digital Library

[3]

Sarang Dharmapurikar, Praveen Krishnamurthy, Todd S. Sproull, and John W. Lockwood. Deep packet inspection using parallel Bloom filters. IEEE Micro, 24(1):52?-61, 2004.

Digital Library

[4]

John W. Lockwood, Naji Naufel, Jon S. Turner, and David E. Taylor. Reprogrammable network packet processing on the field programmable port extender (FPX). In Proceedings of the ACM International Symposium on Field Programmable Gate Arrays (FPGA 2001), pages 87?-93, 2001.

Digital Library

[5]

James Moscola, John Lockwood, Ronald Loui, and Michael Pachos. Implementation of a Content-Scanning Module for an Internet Firewall. In Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), pages 31?-38, Napa, CA, USA, April 2003.

Digital Library

[6]

Dinesh C. Suresh, Zhi Guo, Betul Buyukkurt, and Walid A. Najjar. Automatic compilation framework for Bloom filter based intrusion detection. In Koen Bertels, João M. P. Cardoso, and Stamatis Vassiliadis, editors, ARC, volume 3985 of Lecture Notes in Computer Science, pages 413?-418. Springer, 2006.

[7]

Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422?-426, 1970.

Digital Library

[8]

A. Broder and M. Mitzenmacher. Network applications of Bloom filters: A survey, 2002.

[9]

M. V. Ramakrishna, E. Fu, and E. Bahcekapili. Efficient hardware hashing functions for high performance computers. IEEE Trans. Comput., 46(12):1378?-1381, 1997.

Digital Library

[10]

Long Bu and John A. Chandy. A cam-based keyword match processor architecture. Microelectronics Journal, 37(8):828?-836, 2006.

[11]

I. Sourdis and D. Pnevmatikatos. Pre-decoded CAMs for efficient and high-speed NIDS pattern matching, 2004.

[12]

C. Chang and R. Paige. From regular expressions to DFA?s using compressed NFA?s. In In Proceedings of CPM ?92, A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, editors, Lecture Notes in Computer Science, No. 644, pages 88-?108. Springer-Verlag, 1992.

Digital Library

[13]

R. Sidhu and V. K. Prasanna. Fast regular expression matching using FPGAs. In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM01), April 2001.

Digital Library

[14]

B. L. Hutchings, R. Franklin, and D. Carver. Assisting network intrusion detection with reconfigurable hardware. In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM ?02), page 111, Washington, DC, USA, 2002.

Digital Library

[15]

Hong-Jip Jung, Z. K. Baker, and V. K. Prasanna. Performance of FPGA implementation of bit-split architecture for intrusion detection systems. In Proceedings of the 20th IEEE International Symposium on Parallel and Distributed Processing Symposium (IPDPS?06), April 2001.

Digital Library

[16]

Alfred V. Aho and Margaret J. Corasick. Efficient string matching: an aid to bibliographic search. Communications of the ACM, 18(6):333?-340, 1975.

Digital Library

[17]

Donald E. Knuth, J.H. Morris, and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal of Computing, 6(2):323-?350, 1977.

[18]

Robert S. Boyer and J. Strother Moore. A fast string searching algorithm. Communications of the ACM, 20(10):62?-72, 1977.

Digital Library

[19]

Richard M. Karp and Michael O. Rabin. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, 31(2):249?-260, 1987.

Digital Library

[20]

Beate Commentz-Walter. A string matching algorithm fast on the average. In H.A. Maurer, editor, Proceedings of the Sixth International Colloquium on Automata, Languages and Programming, pages 118?-131. Springer-Verlag, 1979.

Digital Library

[21]

S. Wu and U. Manber. Fast text searching with errors. Technical Report TR-91-11, University of Arizona. Dept. of Computer Science, 1991.

[22]

S. Antonatos, K. Anagnostakis, M. Polychronakis, and E. Markatos. Performance analysis of content matching intrusion detection systems, 2004.

[23]

Y. H. Cho and W. H. Mangione-Smith. Deep packet filter with dedicated logic and read only memories. In Field-Programmable Custom Computing Machines (FCCM 2004), 12th Annual IEEE Symposium on, pages 125?-134, April 2004.

Digital Library

[24]

Ioannis Sourdis and Dionisios Pnevmatikatos. Fast, large-scale string match for a 10 Gbps FPGA-based network intrusion. In Proceedings of the 13th Conference on Field Programmable Logic and Applications (FPL?03)., September 2003.

[25]

Yutaka Sugawara, Mary Inaba, and Kei Hiraki. Over 10 Gbps string matching mechanism for multi-stream packet scanning systems. Lecture Notes in Computer Science, Field Programmable Logic and Application, 3203/2004:484?-493, 2004.

[26]

Toshihiro Katashita, Atusi Maeda, Kenji Toda, and Yoshinori Yamaguchi. Highly efficient string matching circuit for IDS with FPGA. Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM?06), 0:285-?286, 2006.

Digital Library

[27]

Daniele Paolo Scarpazza, Oreste Villa, and Fabrizio Petrini. Peak-performance DFA-based string matching on the Cell processor. In In Proc. SMTPS ?07, 2007.

[28]

Bruce W. Watson. The performance of single-keyword and multiple-keyword pattern matching algorithms. Technical Report 19, Eindhoven University of Technology, 1994.

Cited By

T VP PKamath BVivek SManjunatha P S N(2024)A Mathematical Framework for Optimizing Lexical Analysis on Multi-Core Architectures2024 4th International Conference on Sustainable Expert Systems (ICSES)10.1109/ICSES63445.2024.10763002(1151-1156)Online publication date: 15-Oct-2024
https://doi.org/10.1109/ICSES63445.2024.10763002
T VS SP S N(2024)Revolutionizing Compilation: Lexical Analysis Approaches for Parallel Multi-Core Processing2024 International Conference on Inventive Computation Technologies (ICICT)10.1109/ICICT60155.2024.10544729(142-149)Online publication date: 24-Apr-2024
https://doi.org/10.1109/ICICT60155.2024.10544729
Pai T VJayanthila Devi AAithal P(2020)A Systematic Literature Review of Lexical Analyzer Implementation Techniques in Compiler DesignInternational Journal of Applied Engineering and Management Letters10.47992/IJAEML.2581.7000.0087(285-301)Online publication date: 31-Dec-2020
https://doi.org/10.47992/IJAEML.2581.7000.0087
Show More Cited By

Index Terms

Exact multi-pattern string matching on the cell/b.e. processor
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

High-performance regular expression scanning on the Cell/B.E. processor
ICS '09: Proceedings of the 23rd international conference on Supercomputing

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 ...
Power-Conscious Design of the CELL Processor's Synergistic Processor Element

The authors describe the low-power design of the synergistic processor element (SPE) of CELL processor developed by SONY, Toshiba and IBM. CMOS static gates implement most of the logic, and dynamic circuits are used in critical areas. Tight coupling of ...
Multi-pattern string matching algorithms

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '08: Proceedings of the 5th conference on Computing frontiers

May 2008

334 pages

ISBN:9781605580777

DOI:10.1145/1366230

General Chair:
Alex Ramirez
UPC, Spain
,
Program Chairs:
Gianfranco Biliardi
University of Padova, Italy
,
Michael Gschwind
IBM TJ Watson Research Center, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CF '08

Sponsor:

CF '08: Computing Frontiers Conference

May 5 - 7, 2008

Ischia, Italy

Acceptance Rates

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
573
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

T VP PKamath BVivek SManjunatha P S N(2024)A Mathematical Framework for Optimizing Lexical Analysis on Multi-Core Architectures2024 4th International Conference on Sustainable Expert Systems (ICSES)10.1109/ICSES63445.2024.10763002(1151-1156)Online publication date: 15-Oct-2024
https://doi.org/10.1109/ICSES63445.2024.10763002
T VS SP S N(2024)Revolutionizing Compilation: Lexical Analysis Approaches for Parallel Multi-Core Processing2024 International Conference on Inventive Computation Technologies (ICICT)10.1109/ICICT60155.2024.10544729(142-149)Online publication date: 24-Apr-2024
https://doi.org/10.1109/ICICT60155.2024.10544729
Pai T VJayanthila Devi AAithal P(2020)A Systematic Literature Review of Lexical Analyzer Implementation Techniques in Compiler DesignInternational Journal of Applied Engineering and Management Letters10.47992/IJAEML.2581.7000.0087(285-301)Online publication date: 31-Dec-2020
https://doi.org/10.47992/IJAEML.2581.7000.0087
Lee CYang T(2017)A Flexible Pattern-Matching Algorithm for Network Intrusion Detection Systems Using Multi-Core ProcessorsAlgorithms10.3390/a1002005810:2(58)Online publication date: 24-May-2017
https://doi.org/10.3390/a10020058
Lin YLee CChen Y(2017)Length-Bounded Hybrid CPU/GPU Pattern Matching Algorithm for Deep Packet InspectionAlgorithms10.3390/a1001001610:1(16)Online publication date: 18-Jan-2017
https://doi.org/10.3390/a10010016
Lee CLin YChen Y(2015)A Hybrid CPU/GPU Pattern-Matching Algorithm for Deep Packet InspectionPLOS ONE10.1371/journal.pone.013930110:10(e0139301)Online publication date: 5-Oct-2015
https://doi.org/10.1371/journal.pone.0139301
Abdellatif MTalhi CHamou-Lhadj ADagenais M(2015)On the Use of Mobile GPU for Accelerating Malware Detection Using Trace AnalysisProceedings of the 2015 IEEE 34th Symposium on Reliable Distributed Systems Workshop (SRDSW)10.1109/SRDSW.2015.18(42-46)Online publication date: 28-Sep-2015
https://dl.acm.org/doi/10.1109/SRDSW.2015.18
Bremler-Barr ADavid SHarchol YHay D(2015)Leveraging traffic repetitions for high-speed deep packet inspection2015 IEEE Conference on Computer Communications (INFOCOM)10.1109/INFOCOM.2015.7218648(2578-2586)Online publication date: Apr-2015
https://doi.org/10.1109/INFOCOM.2015.7218648
Kushalnagar RLasecki WBigham J(2014)Accessibility Evaluation of Classroom CaptionsACM Transactions on Accessible Computing10.1145/25435785:3(1-24)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2543578
Webster GHanson V(2014)Technology for Supporting Care Staff in Residential HomesACM Transactions on Accessible Computing10.1145/25435775:3(1-23)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2543577
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents