Browse wiki

Jump to: navigation, search
High-performance regular expression scanning on the cell/B.E. processor
Abstract Matching regular expressions (regexps) is 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-81x 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. Copyright 2009 ACM.n architecture design. Copyright 2009 ACM.
Abstractsub Matching regular expressions (regexps) is 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-81x 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. Copyright 2009 ACM.n architecture design. Copyright 2009 ACM.
Bibtextype inproceedings  +
Doi 10.1145/1542275.1542284  +
Has author Scarpazza D.P. + , Russell G.F. +
Has extra keyword Architecture designs + , Cell chips + , CELL processor + , Clock cycles + , Data volume + , Dedicated hardware + , Execution time + , General trends + , Multi core + , Multicore architectures + , Multiple threads + , Processing power + , Programming language + , Proof of concept + , Regular expression + , Resource utilizations + , SIMD instructions + , Tokenization + , Wikipedia + , Hardware + , Indexing (materials working) + , Information retrieval + , Intelligent control + , Markup languages + , Parallel algorithms + , Program compilers + , Search engine + , World Wide Web + , Computer architecture +
Has keyword Cell processor + , Multi-core + , Regular expression +
Isbn 9781605584980  +
Language English +
Number of citations by publication 0  +
Number of references by publication 0  +
Pages 14–25  +
Published in Proceedings of the International Conference on Supercomputing +
Title High-performance regular expression scanning on the cell/B.E. processor +
Type conference paper  +
Year 2009 +
Creation dateThis property is a special property in this wiki. 7 November 2014 19:32:54  +
Categories Publications without license parameter  + , Publications without remote mirror parameter  + , Publications without archive mirror parameter  + , Publications without paywall mirror parameter  + , Conference papers  + , Publications without references parameter  + , Publications  +
Modification dateThis property is a special property in this wiki. 7 November 2014 19:32:54  +
DateThis property is a special property in this wiki. 2009  +
hide properties that link here 
High-performance regular expression scanning on the cell/B.E. processor + Title
 

 

Enter the name of the page to start browsing from.