 Timestamp:
 Feb 3, 2015, 2:47:09 PM (4 years ago)
 Location:
 docs/Working/icGrep
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

docs/Working/icGrep/background.tex
r4450 r4452 57 57 to support highperformance streaming text processing based on a bitparallel 58 58 transform represenation of text. In this representation, a text $T$ is represented as a set of parallel 59 bit streams $B_i$, such that bit $j$ of stream $B_i$ is the $i^{\ text{th}}$ bit of59 bit streams $B_i$, such that bit $j$ of stream $B_i$ is the $i^{\mbox{th}}$ bit of 60 60 character code unit $j$ of $T$. The Parabix methods have been used to 61 61 accelerate Unicode transcoding \cite{cameron2008case}, protein search \cite{green2009modeling}, 62 62 XML parsing \cite{cameron2011parallel}, and, most recently, regular expression search \cite{cameron2014bitwise}. 63 64 63 65 64 
docs/Working/icGrep/bitgrep.bib
r4448 r4452 295 295 } 296 296 297 297 @inproceedings{mytkowicz2014data, 298 title={Dataparallel finitestate machines}, 299 author={Mytkowicz, Todd and Musuvathi, Madanlal and Schulte, Wolfram}, 300 booktitle={Proceedings of the 19th international conference on Architectural support for programming languages and operating systems}, 301 pages={529542}, 302 year={2014}, 303 organization={ACM} 304 } 305 @article{scarpazza2011top, 306 title={Topperformance tokenization and smallruleset regular expression matching}, 307 author={Scarpazza, Daniele Paolo}, 308 journal={International Journal of Parallel Programming}, 309 volume={39}, 310 number={1}, 311 pages={332}, 312 year={2011}, 313 publisher={Springer} 314 } 315 @inproceedings{salapura2012accelerating, 316 title={Accelerating business analytics applications}, 317 author={Salapura, Valentina and Karkhanis, Tejas and Nagpurkar, Priya and Moreira, Jose}, 318 booktitle={High Performance Computer Architecture (HPCA), 2012 IEEE 18th International Symposium on}, 319 pages={110}, 320 year={2012}, 321 organization={IEEE} 322 } 323 @inproceedings{zu2012gpu, 324 title={GPUbased NFA implementation for memory efficient high speed regular expression matching}, 325 author={Zu, Yuan and Yang, Ming and Xu, Zhonghu and Wang, Lin and Tian, Xin and Peng, Kunyang and Dong, Qunfeng}, 326 booktitle={ACM SIGPLAN Notices}, 327 volume={47}, 328 number={8}, 329 pages={129140}, 330 year={2012}, 331 organization={ACM} 332 } 333 
docs/Working/icGrep/introduction.tex
r4448 r4452 1 1 \section{Introduction} 2 2 3 The venerable Unix {\tt grep} program is an everyday tool widely used 3 4 to search for lines in text files matching a given regular expression … … 9 10 parallelization have generally concentrated on the use of SIMD, multicore 10 11 or GPU technologies to accelerate multiple instances of independent 11 matching problems. Brief review ... 12 matching problems. 13 Scarpazza \cite{scarpazza2011top} used SIMD and multicore parallelism 14 to accelerate small ruleset tokenization applications on the Cell 15 Broadband Engine while Valaspura \cite{salapura2012accelerating} 16 built on these techniques to accelerate business analytics applications 17 using SSE instructions on commodity processors. 18 Zu et al \cite{zu2012gpu} use GPU technology to implement NFAbased regular 19 expression matching with parallelism devoted both to processing 20 a compressed active state array as well as to handling matching of 21 multiple packet instances. 12 22 These works have not generally tackled Unicode matching problems. 13 23 14 24 Using parallel methods to accelerate matching of a single pattern on a 15 single input stream is more difficult. Indeed, the finite state machines (FSMs) 16 underlying are considered the hardest to parallelize (embarassingly sequential) 17 of the 13 dwarves identified in the Berkeley landscape of parallel computing research \cite{asanovic2006landscape}. 25 single input stream is more difficult. Indeed, of the 13 dwarves identified in the Berkeley overview of parallel computing research, 26 finite state machines (FSMs) are considered the hardest to parallelize (embarassingly sequential) \cite{asanovic2006landscape}. 18 27 However, some success has been reported recently along two independent lines of 19 research. Mytkowicz... Cameron/Parabix.... 20 These works do not address Unicode issues. 28 research. Mytkowicz et al \cite{mytkowicz2014data} use SIMD shuffle operations 29 to implement composable DFA transitions using dynamic convergence to 30 reduce the number of states in play at any one time and range coalescing 31 to compact the transition tables. Unfortunately, the method seems unlikely 32 to apply well to Unicode regular expression matching problems, which routinely 33 require thousands of DFA states for named Unicode properties. 34 Building on the Parabix framework, Cameron at al \cite{cameron2014bitwise} introduce 35 regular expression matching using the bitwise 36 data parallel approach together with the MatchStar primitive 37 for efficient implementation of 38 Kleene* characterclass repetitions. 21 39 22 40 In this paper, we report on the use of the implementation of a full … … 29 47 to classical grep implementations, ICgrep offers dramatic performance 30 48 acceleration in ASCIIbased and Unicode matching performance alike. 31 32 33 49 34 50 The remainder of this paper is organized as follows. Section \ref{sec:background}
Note: See TracChangeset
for help on using the changeset viewer.