Changeset 4786


Ignore:
Timestamp:
Sep 22, 2015, 12:29:29 PM (3 years ago)
Author:
cameron
Message:

More formatting for LNCS requirements

Location:
docs/Working/icGrep
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/icGrep/Paper88.tex

    r4782 r4786  
    2525\def\PabloCompiler{\Pablo{} Compiler}
    2626
    27 \pagestyle{empty}
     27%\pagestyle{empty}
    2828
    2929\begin{document}
    3030
    3131\title{Bitwise Data Parallelism with LLVM: The icGrep Case Study}
    32 \author{Robert D. Cameron\inst{1 (}\Envelope\inst{)}
    33 \and Nigel Medforth\inst{1}
    34 \and Dan Lin\inst{1}
    35 \and Dale Denis\inst{1}
    36 \and William N. Sumner\inst{1}
     32\author{Robert D. Cameron\Envelope
     33\and Nigel Medforth
     34\and Dan Lin
     35\and Dale Denis
     36\and William N. Sumner
    3737}
    3838\institute{School of Computing Science, Simon Fraser University}
     39\authorrunning{Cameron, Medforth, Lin, Denis and Sumner}
    3940\maketitle
    4041
  • docs/Working/icGrep/bitgrep.bib

    r4550 r4786  
    99  publisher={Elsevier}
    1010}
    11 
    12 
    13 @inproceedings{atasu2013hardware,
    14   title={Hardware-accelerated regular expression matching for high-throughput text analytics},
    15   author={Atasu, Kubilay and Polig, Raphael and Hagleitner, Christoph and Reiss, Frederick R},
    16   booktitle={Field Programmable Logic and Applications (FPL), 2013 23rd International Conference on},
    17   pages={1--7},
    18   year={2013},
    19   organization={IEEE}
    20 }
    21 @incollection{valgenti2012gpp,
    22   title={GPP-Grep: high-speed regular expression processing engine on general purpose processors},
    23   author={Valgenti, Victor C and Chhugani, Jatin and Sun, Yan and Satish, Nadathur and Kim, Min Sik and Kim, Changkyu and Dubey, Pradeep},
    24   booktitle={Research in Attacks, Intrusions, and Defenses},
    25   pages={334--353},
    26   year={2012},
    27   publisher={Springer}
    28 }
    29 @inproceedings{kumar2007curing,
    30   title={Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia},
    31   author={Kumar, Sailesh and Chandrasekaran, Balakrishnan and Turner, Jonathan and Varghese, George},
    32   booktitle={Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems},
    33   pages={155--164},
    34   year={2007},
    35   organization={ACM}
    36 }
    37 }
    38 @article{nieminen2007efficient,
    39   title={Efficient implementation of {A}ho--{C}orasick pattern matching automata using {U}nicode},
    40   author={Nieminen, Janne and Kilpel{\"a}inen, Pekka},
    41   journal={Software: Practice and Experience},
    42   volume={37},
    43   number={6},
    44   pages={669--690},
    45   year={2007},
    46   publisher={Wiley Online Library}
    47 }
    48 @incollection{le2011regular,
    49   title={Regular expressions at their best: a case for rational design},
    50   author={Le Maout, Vincent},
    51   booktitle={Implementation and Application of Automata},
    52   pages={310--320},
    53   year={2011},
    54   publisher={Springer}
    55 }
    56 @incollection{stewart2011searching,
    57   title={Searching massive data streams using multipattern regular expressions},
    58   author={Stewart, Jon and Uckelman, Joel},
    59   booktitle={Advances in Digital Forensics VII},
    60   pages={49--63},
    61   year={2011},
    62   publisher={Springer}
    63 }
    64 @incollection{bille2009faster,
    65   title={Faster regular expression matching},
    66   author={Bille, Philip and Thorup, Mikkel},
    67   booktitle={Automata, Languages and Programming},
    68   pages={171--182},
    69   year={2009},
    70   publisher={Springer}
    71 }
    72 @article{yang2011fast,
    73   title={Fast, memory-efficient regular expression matching with {NFA-OBDDs}},
    74   author={Yang, Liu and Karim, Rezwana and Ganapathy, Vinod and Smith, Randy},
    75   journal={Computer Networks},
    76   volume={55},
    77   number={15},
    78   pages={3376--3393},
    79   year={2011},
    80   publisher={Elsevier}
    81 }
    82 
    83 }
    8411@inproceedings{lin2012parabix,
    8512  title={Parabix: Boosting the efficiency of text processing on commodity processors},
    8613  author={Lin, Dan and Medforth, Nigel and Herdy, Kenneth S and Shriraman, Arrvindh and Cameron, Rob},
    87   booktitle={HPCA}, 
    88   pages={1--12},
    89   year={2012},
     14  booktitle={High Performance Computer Architecture}, 
     15  year = {2012},  pages={1--12},
    9016  organization={IEEE}
    91 }
    92 @inproceedings{cameron2008high,
    93   title={High performance {XML} parsing using parallel bit stream technology},
    94   author={Cameron, Robert D and Herdy, Kenneth S and Lin, Dan},
    95   booktitle={Proceedings of the 2008 conference of the center for advanced studies on collaborative research: meeting of minds},
    96   pages={17},
    97   year={2008},
    98   organization={ACM}
    99 }
    100 @inproceedings{cameron2009parallel,
    101   title={Parallel bit stream technology as a foundation for {XML} parsing performance},
    102   author={Cameron, Rob and Herdy, Ken and Amiri, Ehsan},
    103   booktitle={International Symposium on Processing {XML} Efficiently: Overcoming Limits on Space, Time, or Bandwidth},
    104   volume={8},
    105   year={2009}
    106 }
    107 @inproceedings{cameron2008case,
    108   title={A case study in SIMD text processing with parallel bit streams: {UTF-8} to {UTF-16} transcoding},
    109   author={Cameron, Robert D},
    110   booktitle={Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming},
    111   pages={91--98},
    112   year={2008},
    113   organization={ACM}
    11417}
    11518@incollection{cameron2011parallel,
    11619  title={Parallel scanning with bitstream addition: An {XML} case study},
    11720  author={Cameron, Robert D and Amiri, Ehsan and Herdy, Kenneth S and Lin, Dan and Shermer, Thomas C and Popowich, Fred P},
    118   booktitle={Euro-Par 2011 Parallel Processing},
     21  booktitle={Euro-Par},
     22  year = {2011},
    11923  pages={2--13},
    120   year={2011},
    12124  publisher={Springer}
    12225}
    123 @inproceedings{medforth2013icxml,
    124   title={icXML: Accelerating a Commercial {XML} Parser Using {SIMD} and Multicore Technologies},
    125   author={Medforth, Nigel and Lin, Dan and Herdy, Kenneth and Cameron, Rob and Shriraman, Arrvindh},
    126   booktitle={Proceedings of Balisage: The Markup Conference 2013},
    127   year={2013}
    128 
     26
    12927@inproceedings{cameron2014bitwise,
    13028 author = {Cameron, Robert D. and Shermer, Thomas C. and Shriraman, Arrvindh and Herdy, Kenneth S. and Lin, Dan and Hull, Benjamin R. and Lin, Meng},
    13129 title = {Bitwise Data Parallelism in Regular Expression Matching},
    13230 booktitle = {PACT},
    133  series = {PACT '14},
    13431 year = {2014},
    135  isbn = {978-1-4503-2809-8},
    136  location = {Edmonton, AB, Canada},
    13732 pages = {139--150},
    138  numpages = {12},
    139  url = {http://doi.acm.org/10.1145/2628071.2628079},
    140  doi = {10.1145/2628071.2628079},
    141  acmid = {2628079},
    14233 publisher = {ACM},
    143  address = {New York, NY, USA},
    144  keywords = {parallel bit streams, regular expression matching},
     34 address = {New York, NY, USA}
    14535}
    146 @inproceedings{cameron2009architectural,
    147   title={Architectural support for {SWAR} text processing with parallel bit streams: the inductive doubling principle},
    148   author={Cameron, Robert D and Lin, Dan},
    149   booktitle={ASPLOS},
    150   volume={44},
    151   pages={337--348},
    152   year={2009},
    153   organization={ACM}
    154 }
    155 @mastersthesis{huang2011idisa+,
    156   title={IDISA+: A portable model for high performance {SIMD} programming},
    157   author={Huang, Hua},
    158   year={2011},
    159   school={School of {C}omputing {S}cience, {S}imon {F}raser {U}niversity}
    160 }
    161 @mastersthesis{denis2014high,
    162   title={High-Performance Regular Expression Matching with {P}arabix and {LLVM}},
    163   author={Denis, Dale},
    164   year={2014},
    165   school={School of {C}omputing {S}cience, {S}imon {F}raser {U}niversity}
    166 }
    167 @mastersthesis{lin2014systematic,
    168   title={Systematic Support of Parallel Bit Streams in {LLVM} (in progress)},
    169   author={Lin, Meng},
    170   year={2014},
    171   school={School of {C}omputing {S}cience, {S}imon {F}raser {U}niversity}
    172 }
    173 @inproceedings{atasu2014resource,
    174   title={Resource-efficient regular expression matching architecture for text analytics},
    175   author={Atasu, Kubilay},
    176   booktitle={2014 IEEE 25th International Conference on Application-specific Systems, Architectures and Processors (ASAP)},
    177   pages={1--8},
    178   year={2014},
    179   organization={IEEE}
    180 }
    18136
    182 @article{sigrist2013new,
    183   title={New and continuing developments at {PROSITE}},
    184   author={Sigrist, Christian JA and de Castro, Edouard and Cerutti, Lorenzo and Cuche, B{\'e}atrice A and Hulo, Nicolas and Bridge, Alan and Bougueleret, Lydie and Xenarios, Ioannis},
    185   journal={Nucleic acids research online},
    186   volume={41},
    187   number={D1},
    188   pages={D344--D347},
    189   year={2013},
    190   publisher={Oxford University Press}
    191 }
    192 @article{manole2012protein,
    193   title={Protein Sequence Pattern Matching: Leveraging Application Specific Hardware Accelerators},
    194   author={Manole, Sagi and Golander, Amit and Weiss, Shlomo},
    195   year={2012},
    196   publisher={IEEE}
    197 }
    198 @incollection{wunschiers2013regular,
    199   title={Regular Expressions},
    200   author={W{\"u}nschiers, R{\"o}bbe},
    201   booktitle={Computational Biology},
    202   pages={157--174},
    203   year={2013},
    204   publisher={Springer}
    205 }
    206 @article{de2006scanprosite,
    207   title={{ScanProsite}: detection of {PROSITE} signature matches and {ProRule}-associated functional and structural residues in proteins},
    208   author={De Castro, Edouard and Sigrist, Christian JA and Gattiker, Alexandre and Bulliard, Virginie and Langendijk-Genevaux, Petra S and Gasteiger, Elisabeth and Bairoch, Amos and Hulo, Nicolas},
    209   journal={Nucleic acids research},
    210   volume={34},
    211   number={suppl 2},
    212   pages={W362--W365},
    213   year={2006},
    214   publisher={Oxford Univ Press}
    215 }
    216 @article{hulo2006prosite,
    217   title={The {PROSITE} database},
    218   author={Hulo, Nicolas and Bairoch, Amos and Bulliard, Virginie and Cerutti, Lorenzo and De Castro, Edouard and Langendijk-Genevaux, Petra S and Pagni, Marco and Sigrist, Christian JA},
    219   journal={Nucleic acids research},
    220   volume={34},
    221   number={suppl 1},
    222   pages={D227--D230},
    223   year={2006},
    224   publisher={Oxford Univ Press}
    225 }
    226 @inproceedings{green2009modeling,
    227   title={Modeling tryptic digestion on the {Cell BE} processor},
    228   author={Green, James R and Mahmoud, Hanan and Dumontier, Michel},
    229   booktitle={Canadian Conference onElectrical and Computer Engineering (CCECE '09), 2009.},
    230   pages={701--705},
    231   year={2009},
    232   organization={IEEE}
    233 }
    23437
    235 @article{asher2013hybrid,
    236   title={Hybrid type legalization for a sparse {SIMD} instruction set},
    237   author={Asher, Yosi Ben and Rotem, Nadav},
    238   journal={ACM Transactions on Architecture and Code Optimization (TACO)},
    239   volume={10},
    240   number={3},
    241   pages={11},
    242   year={2013},
    243   publisher={ACM}
    244 }
    24538@inproceedings{lattner2004llvm,
    24639  title={{LLVM}: A compilation framework for lifelong program analysis \& transformation},
    24740  author={Lattner, Chris and Adve, Vikram},
    248   booktitle={Code Generation and Optimization, 2004. CGO 2004. International Symposium on},
     41  booktitle={Code Generation and Optimization 2004},
    24942  pages={75--86},
    25043  year={2004},
     
    25245}
    25346
    254 @article{owens2009regular,
    255   title={Regular-expression derivatives re-examined},
    256   author={Owens, Scott and Reppy, John and Turon, Aaron},
    257   journal={Journal of Functional Programming},
    258   volume={19},
    259   number={02},
    260   pages={173--190},
    261   year={2009},
    262   publisher={Cambridge Univ Press}
    263 }
    264 @article{navarro2001nr,
    265   title={{NR}-grep: a fast and flexible pattern-matching tool},
    266   author={Navarro, Gonzalo},
    267   journal={Software: Practice and Experience},
    268   volume={31},
    269   number={13},
    270   pages={1265--1312},
    271   year={2001},
    272   publisher={Wiley Online Library}
    273 }
     47
    27448@article{myers1999fast,
    27549  title={A fast bit-vector algorithm for approximate string matching based on dynamic programming},
    27650  author={Myers, Gene},
    277   journal={Journal of the ACM (JACM)},
     51  journal={Journal of the ACM},
    27852  volume={46},
    27953  number={3},
     
    332106}
    333107@inproceedings{zu2012gpu,
    334   title={GPU-based NFA implementation for memory efficient high speed regular expression matching},
     108  title={{GPU-based} {NFA} implementation for memory efficient high speed regular expression matching},
    335109  author={Zu, Yuan and Yang, Ming and Xu, Zhonghu and Wang, Lin and Tian, Xin and Peng, Kunyang and Dong, Qunfeng},
    336110  booktitle={PPoPP},
  • docs/Working/icGrep/evaluation.tex

    r4782 r4786  
    5858and {\tt icgrep} provide systematic support for all property expressions
    5959at Unicode Level 1 as well as set union, intersection and difference.
    60 Unfortunately, {\tt pcre2grep} does not support the set intersection and difference operators directly.
    61 However, these operators can be expressed using a regular expression
    62 feature known as a lookbehind assertion.   Set intersection involves a
    63 regular expression formed with a one of the property expressions and a
    64 positive lookbehind assertion on the other, while set difference uses
    65 a negative lookbehind assertion. 
     60However, in order to implement these operators with {\tt pcre2grep}, we
     61translated them into an equivalent form using lookbehind assertions.
     62%Unfortunately, {\tt pcre2grep} does not support the set intersection and difference operators directly.
     63%However, these operators can be expressed using a regular expression
     64%feature known as a lookbehind assertion.   Set intersection involves a
     65%regular expression formed with a one of the property expressions and a
     66%positive lookbehind assertion on the other, while set difference uses
     67%a negative lookbehind assertion. 
    6668
    6769We generated a set of regular expressions involving all Unicode values of
     
    7981most of the world's major language families as a test corpus.
    8082For each program under test, we performed searches for each regular expression against each XML document.
     83Test cases were ranked by the percentage of matching lines found in the XML document and grouped in 5\% increments. 
    8184Performance is reported in CPU cycles per byte on an Intel i7-2600 machine.   
    8285The results are presented in Fig.~\ref{fig:property_test}.
    83 They were ranked by the percentage of matching lines found in the XML document and grouped in 5\% increments. 
    84 When comparing the three programs, \icGrep{} exhibits dramatically better performance, particularly when searching for rare items.
    85 The performance of both pcre2grep and ugrep improves (has a reduction in CPU cycles per byte) as the percentage of matching lines increases.
    86 This occurs because each match allows them to bypass processing the rest of the line.
    87 On the other hand, \icGrep{} shows a slight drop-off in performance with the number of matches found.   
    88 This is primarily due to property classes that include large numbers of codepoints.   
    89 These classes require more bitstream equations for calculation and also have a greater probability of matching.   
    90 Nevertheless, the performance of \icGrep{} in matching the defined property expressions is stable and well ahead of the competitors in all cases.
    91 
    9286\begin{figure}
    9387\vspace{-0.5em}
     
    122116\end{figure}
    123117
     118When comparing the three programs, \icGrep{} exhibits dramatically better performance, particularly when searching for rare items.
     119The performance of both pcre2grep and ugrep improves (CPU cycles per byte decreases) as the percentage of matching lines increases.
     120This occurs because each match allows them to bypass processing the rest of the line.
     121On the other hand, \icGrep{} shows a slight drop-off in performance with the number of matches found.   
     122This is primarily due to property classes that include large numbers of codepoints.   
     123These classes require more bitstream equations for calculation and also have a greater probability of matching.   
     124Nevertheless, the performance of \icGrep{} in matching the defined property expressions is stable and well ahead of the competitors in all cases.
     125
     126
    124127\subsection{Complex Expressions}
    125128
    126 This study evaluates the comparative performance of the matching engines on a
    127 series of more complex expressions, shown in Table \ref{table:regularexpr}.
     129This study evaluates the comparative performance of the matching engines on a set of
     130more complex expressions, shown in Table \ref{table:regularexpr}.
    128131The first two are alphanumeric (\AN{}) expressions, differing only in that the first
    129132one is anchored to match the entire line.
    130133The third searches for lines consisting of text in Arabic script.
    131134The fourth expression is a published currency expression taken from
    132 Stewart and Uckelman~\cite{stewart2013unicode}.
     135Stewart and Uckelman\cite{stewart2013unicode}.
    133136An expression matching runs of six or more Cyrillic script characters enclosed
    134137in initial/opening and final/ending punctuation is fifth in the list.
    135 The final expression is an email expression that allows internationalized names.
     138The last expression matches internationalized email names.
    136139
    137140\begin{table}\centering % requires booktabs
    138 \small\vspace{-2em}
     141\caption{Regular expressions}\label{table:regularexpr}
     142\small%\vspace{-2em}
    139143\begin{tabular}{@{}p{2cm}p{9.8cm}@{}}
    140144\textbf{Name}&\textbf{Regular Expression}\\
     
    155159\bottomrule
    156160\end{tabular}
    157 \caption{Regular expressions}\label{table:regularexpr}
    158 \vspace{-2em}
    159161\end{table}
    160162
    161 In Table \ref{table:complexexpr}, we show the performance results obtained
    162 from an Intel i7-2600 using generic 64-bit binaries for each engine.
    163 We limit the SIMD ISA within \icGrep{} to SSE2 which is available
    164 on all Intel/AMD 64-bit machines.
    165 In each case, we report seconds taken per GB of input averaged over 10
     163Table \ref{table:complexexpr} shows the performance results
     164on our Intel i7-2600 test machine, reporting seconds taken per GB of input averaged over 10
    166165runs each on our Wikimedia document collection.
    167166
    168167\begin{table}[ht]\centering % requires booktabs
     168\caption{Matching times for complex expressions (s/GB)}\label{table:complexexpr}
    169169\newcolumntype{T}{c}
    170 \small\vspace{-2em}
     170\small%\vspace{-2em}
    171171\begin{tabular}{@{}p{2cm}r@{~--~}rp{4pt}r@{~--~}rp{4pt}r@{~--~}rp{4pt}r@{~--~}rp{4pt}@{}}
    172172&\multicolumn{6}{c}{\textbf{\icGrep{}}}\\
     
    184184\bottomrule
    185185\end{tabular}
    186 \caption{Matching times for complex expressions (s/GB)}\label{table:complexexpr}
    187 \vspace{-2em}
    188186\end{table}
    189187
     
    211209
    212210\begin{table}[h]\centering % requires booktabs,siunitx
    213 \small\vspace{-2em}
     211\caption{Speedup of complex expressions on i7-4700MQ $(\sigma)$}\label{table:relperf}
     212\small%\vspace{-2em}
    214213\begin{tabular}{@{}p{2cm}l@{~}r@{~~}l@{~}r@{~~}l@{~}r@{~~}l@{~}r@{~~}l@{~}r@{~~}l@{~}r@{~~}@{}}
    215214&\multicolumn{2}{c}{\textbf{Base}}&\multicolumn{4}{c}{\textbf{SEQ}}&\multicolumn{6}{c}{\textbf{MT}}\\
     
    229228\bottomrule
    230229\end{tabular}
    231 \caption{Speedup of complex expressions on i7-4700MQ $(\sigma)$}\label{table:relperf}
    232 \vspace{-2em}
    233230\end{table}
    234231
  • docs/Working/icGrep/introduction.tex

    r4782 r4786  
    7272research artifact.   From the latter perspective, \icGrep{} is significant
    7373in several ways.   First, it allows the performance results reported here to
    74 be independently replicated.  Secondly, it is a framework for further research
     74be independently replicated.  Secondly, it is a platform for further research
    7575into regular expression matching using bitwise methods and is indeed being used
    7676to investigate Unicode level 2 requirements in a project funded by Google.
    77 Thirdly, it fosters further research
     77Finally, it is working example demonstrating the Parabix+LLVM framework,
     78and useful for guiding further research
    7879into bitwise data parallel algorithms generally and how they may take advantage
    79 of evolving architectural features.   Finally, \icGrep{} has also been
    80 designed as a teaching tool with many command line options to control
    81 algorithm features and display internal representations of regular expressions and
    82 Parabix code.   
     80of evolving architectural features.   
    8381
    8482The remainder of this paper is organized as follows.   Section \ref{sec:background}
Note: See TracChangeset for help on using the changeset viewer.