# Changeset 4452 for docs

Ignore:
Timestamp:
Feb 3, 2015, 2:47:09 PM (4 years ago)
Message:

Intro

Location:
docs/Working/icGrep
Files:
4 edited

Unmodified
Added
Removed
• ## docs/Working/icGrep/background.tex

 r4450 to support high-performance streaming text processing based on a bit-parallel transform represenation of text.  In this representation, a text $T$ is represented as a set of parallel bit streams $B_i$, such that bit $j$ of stream $B_i$ is the $i^{\text{th}}$ bit of bit streams $B_i$, such that bit $j$ of stream $B_i$ is the $i^{\mbox{th}}$ bit of character code unit $j$ of $T$.  The Parabix methods have been used to accelerate Unicode transcoding \cite{cameron2008case}, protein search \cite{green2009modeling}, XML parsing \cite{cameron2011parallel}, and, most recently, regular expression search \cite{cameron2014bitwise}.
• ## docs/Working/icGrep/bitgrep.bib

 r4448 } @inproceedings{mytkowicz2014data, title={Data-parallel finite-state machines}, author={Mytkowicz, Todd and Musuvathi, Madanlal and Schulte, Wolfram}, booktitle={Proceedings of the 19th international conference on Architectural support for programming languages and operating systems}, pages={529--542}, year={2014}, organization={ACM} } @article{scarpazza2011top, title={Top-performance tokenization and small-ruleset regular expression matching}, author={Scarpazza, Daniele Paolo}, journal={International Journal of Parallel Programming}, volume={39}, number={1}, pages={3--32}, year={2011}, publisher={Springer} } @inproceedings{salapura2012accelerating, title={Accelerating business analytics applications}, author={Salapura, Valentina and Karkhanis, Tejas and Nagpurkar, Priya and Moreira, Jose}, booktitle={High Performance Computer Architecture (HPCA), 2012 IEEE 18th International Symposium on}, pages={1--10}, year={2012}, organization={IEEE} } @inproceedings{zu2012gpu, title={GPU-based NFA implementation for memory efficient high speed regular expression matching}, author={Zu, Yuan and Yang, Ming and Xu, Zhonghu and Wang, Lin and Tian, Xin and Peng, Kunyang and Dong, Qunfeng}, booktitle={ACM SIGPLAN Notices}, volume={47}, number={8}, pages={129--140}, year={2012}, organization={ACM} }
• ## docs/Working/icGrep/introduction.tex

 r4448 \section{Introduction} The venerable Unix {\tt grep} program is an everyday tool widely used to search for lines in text files matching a given regular expression parallelization have generally concentrated on the use of SIMD, multicore or GPU technologies to accelerate multiple instances of independent matching problems.   Brief review ... matching problems. Scarpazza \cite{scarpazza2011top} used SIMD and multicore parallelism to accelerate small ruleset tokenization applications on the Cell Broadband Engine while Valaspura \cite{salapura2012accelerating} built on these techniques to accelerate business analytics applications using SSE instructions on commodity processors. Zu et al \cite{zu2012gpu} use GPU technology to implement NFA-based regular expression matching with parallelism devoted both to processing a compressed active state array as well as to handling matching of multiple packet instances. These works have not generally tackled Unicode matching problems. Using parallel methods to accelerate matching of a single pattern on a single input stream is more difficult.  Indeed, the finite state machines (FSMs) underlying are considered the hardest to parallelize (embarassingly sequential) of the 13 dwarves identified in the Berkeley landscape of parallel computing research \cite{asanovic2006landscape}. single input stream is more difficult.  Indeed, of the 13 dwarves identified in the Berkeley overview of parallel computing research, finite state machines (FSMs) are considered the hardest to parallelize (embarassingly sequential) \cite{asanovic2006landscape}. However, some success has been reported recently along two independent lines of research.   Mytkowicz...   Cameron/Parabix.... These works do not address Unicode issues. research.   Mytkowicz et al \cite{mytkowicz2014data} use SIMD shuffle operations to implement composable DFA transitions using dynamic convergence to reduce the number of states in play at any one time and range coalescing to compact the transition tables.   Unfortunately, the method seems unlikely to apply well to Unicode regular expression matching problems, which routinely require thousands of DFA states for named Unicode properties. Building on the Parabix framework, Cameron at al \cite{cameron2014bitwise} introduce regular expression matching using the bitwise data parallel approach together with the MatchStar primitive for efficient implementation of Kleene-* character-class repetitions. In this paper, we report on the use of the implementation of a full to classical grep implementations, ICgrep offers dramatic performance acceleration in ASCII-based and Unicode matching performance alike. The remainder of this paper is organized as follows.   Section \ref{sec:background}
Note: See TracChangeset for help on using the changeset viewer.