Changeset 3890 for docs


Ignore:
Timestamp:
Jun 24, 2014, 5:24:54 AM (4 years ago)
Author:
cameron
Message:

Classification; IPC discussion

Location:
docs/Working/re
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/re/pact051-cameron.tex

    r3889 r3890  
    6161\input{abstract}
    6262\end{abstract}
    63 
     63\category{D.1.3}{Programming Techniques}{Concurrent Programming}[parallel programming]
     64\category{F.2.2}{Theory of Computation}{Nonnumerical Algorithms and Problems}[pattern matching]
     65\keywords{regular expression matching, parallel bit streams}
    6466\section{Introduction}
    6567
  • docs/Working/re/sse2.tex

    r3889 r3890  
    209209
    210210Figure \ref{fig:SSEInstructionsPerCycle} shows the efficiency of
    211 processor utilization
     211processor resource usage
    212212achieved by the three programs on each of the test expression in
    213213terms of instructions per cycle (IPC).
     
    218218structures in processing the Hex and StarHeight expressions, branch
    219219mispredictions increase considerably and there is a noticeable
    220 drop-off in IPC.  Both the gre2p and nrgrep suffer from significant
    221 penalties due to 
     220drop-off in IPC.   The gre2p program suffers from significant penalties
     221for the smaller expressions, but otherwise achieves a good IPC rate.
     222On the other hand, nrgrep IPC drops off with expression complexity,
     223suffering from significant penalties due to 
    222224mispredictions in the character-skipping logic and cache misses in
    223 table lookups.  The performance of nrgrep, in particular drops off
    224 with the growth in regulare expression complexity.
    225 
    226 Overall, the bitstreams implementation significantly outperformed
     225table lookups.
     226
     227Overall, the bitstreams SSE2 implementation significantly outperformed
    227228both nrgrep and gre2p. In addition, the performance of bitstreams
    228 scales well with regular expression complexity.
    229 
    230 
     229generally scales well with regular expression complexity, although
     230nested Kleene closures are an issue.
     231
Note: See TracChangeset for help on using the changeset viewer.