# source:docs/Working/icGrep/architecture.tex@4562

Last change on this file since 4562 was 4501, checked in by nmedfort, 4 years ago

Strip unicode agnostic optimizations

File size: 7.0 KB
RevLine
[4446]1\section{Architecture}\label{sec:architecture}
[4493]2\paragraph{Regular Expression Preprocessing.}
[4446]3
[4466]4\input{fig-compiler}
[4446]5
[4476]6As shown in Figure \ref{fig:compiler},
[4499]7compilation in \icGrep{} comprises three logical layers: \RegularExpression{},
8\Pablo{} and the LLVM layer, each with their own intermediate representation
[4466]9(IR), transformation and compilation modules.
10%
[4499]11As we traverse the layers, the IR becomes more complex as it begins to mirror the final machine code.
[4466]12%
[4499]13The layering enables further optimization based on information available at each stage.
[4466]14%
[4501]15The \REParser{} validates and transforms the input \RegularExpression{} into an abstract syntax tree (AST).
[4499]16%
[4493]17%The AST is a minimalistic representation that, unlike traditional \RegularExpression{}, is not converted into a NFA or DFA for further processing.
[4466]18%
[4493]19%Instead, \icGrep{} passes the AST into the transformation module, which includes a set of \RegularExpression{} specific optimization passes.
[4466]20%
[4501]21Successive \RegularExpression{} Transformations exploit domain
[4499]22knowledge to optimize the regular expressions.
[4466]23%
[4501]24%An initial \emph{Nullable} pass, determines whether the \RegularExpression{}
25%contains prefixes or suffixes that may be removed or
26%modified whilst matching the same lines of text as the original expression.
[4499]27%
[4501]28%For example, \verb|a*bc+|'' is equivalent to \verb|bc|'' because the Kleene Star (Plus) operator matches zero (one) or more instances of a
29%specific character.
[4466]30%
[4499]31The aforementioned \texttt{toUTF8} transformation also applies during this phase to generate code unit classes.
32%The \emph{toUTF8} pass converts the Unicode character classes in the input \RegularExpression{} into equivalent expression(s) that represent sequences
33%of 8-bit code units necessary to identify occurrences of the class.
34%
[4476]35%Since some characters have multiple logically equivalent representations, such as \textcolor{red}{\textbf{????}}, this may produce nested sequences or alternations.
[4466]36%
[4476]37%This is described in more detail in \S\ref{sec:Unicode:toUTF8}.
[4466]38%
[4501]39%A final \emph{Simplification} pass flattens nested structures into their simplest legal form.
[4466]40%
[4501]41%For example, \verba(b((c|d)|e))'' becomes \verbab(c|d|e)'' and \verb([0-9]{3,5}){3,5}'' becomes \verb[0-9]{9,25}''.
[4466]42%
[4446]43
[4466]44%% DISCUSS ANALYSIS MODULE?
45
46
[4499]47The next layer transforms this AST into the instructions in the \Pablo{} IR.
[4466]48%
[4499]49%has two compilers: the \CodeUnitCompiler{} and \RegularExpressionCompiler{}, both of which produce \Pablo{} IR.
50%
[4466]51Recall that the \Pablo{} layer assumes a transposed view of the input data.
52%
[4499]53The \emph{\RegularExpressionCompiler{}} first transforms all input code unit classes,
54analogous to non-Unicode character classes,
55into a series of equations over these transposed bitstreams.
56It next transforms the AST into \Pablo{} instructions that use the
57results of these equations.
58For instance, it converts alternations into a sequence of calculations that
59are merged with \verb|OR|s.
60The results of these passes are combined and transformed through typical
61optimization passes including dead code elimination
62(DCE), common subexpression elimination (CSE) and constant folding.
63These optimizations exploit redundancies that are harder to recognize in
64the \RegularExpression{} AST itself.
[4466]65%
[4499]66%The \emph{\CodeUnitCompiler{}} transforms the input code unit classes,
67%either extracted from the \RegularExpression{} or produced by the \emph{toUTF8} transformation,
68%into a series of bit stream equations.
[4466]69%
[4499]70%The \emph{\RegularExpressionCompiler{}}
71%assumes that these have been calculated and
72%transforms the \RegularExpression{} AST into
73%a sequence of instructions.
74%\Pablo{} instructions that use the results of these equations.
[4466]75%
[4499]76%For instance, it converts alternations into a sequence of calculations that are merged with \verb|OR|s.
[4466]77%
[4499]78%The results of these passes are combined and transformed through a series of typical optimization passes, including dead code elimination
79%(DCE), common subexpression elimination (CSE), and constant folding.
[4466]80%
[4499]81%These optimizations exploit redundancies that are harder to recognize in the \RegularExpression{} AST itself.
82%These are necessary at this stage because the \RegularExpression{} AST may include common subsequences that are costly to recognize in
83%that form.
84%
85%Similarly, to keep the \CodeUnitCompiler{} a linear time function, it may introduce redundant IR instructions as it applies traditional Boolean
86%algebra transformations, such as de Morgan's law, to the computed streams.
[4466]87%
[4499]88%An intended side-effect of these passes is that they eliminate the need to analyze the data-dependencies inherent in the carry-bit logic,
89%which is necessary for some \Pablo{} instructions but problematic for optimizers to reason about non-conservatively.
[4466]90%
[4499]91
92The \PabloCompiler{} then directly converts the \Pablo{} IR into LLVM IR.
[4466]93%
[4499]94%This is a relatively straightforward conversion:
[4466]95%
[4499]96%the only complexities it introduces is the generation of Phi nodes, linking of statically-compiled functions, and assignment of carry variables.
[4466]97%
[4499]98The LLVM Compiler framework provides flexible APIs for compilation and linking.
99Using these, \icGrep{} dynamically generates a match function for identifying
100occurrences of the \RegularExpression{}.
[4466]101
[4493]102\paragraph{Dynamic Grep Engine.}
[4466]103\input{fig-executor}
[4479]104Figure~\ref{fig:execution} shows the structure of the \icGrep{} matching engine.
105The input data is transposed into 8 parallel bit streams through the Transposition module.
106Using the 8 basis bits streams, the Required Streams Generator computes the
107line break streams, UTF-8 validation streams and the Initial and NonFinal streams
108needed to support ScanThru and MatchStar with UTF-8 data.
[4476]109The Dynamic Matcher, dynamically compiled via LLVM, retrieves the 8 basis bits and the required streams from their memory addresses and starts the matching process.
[4479]110During the matching process, any references to named Unicode properties generate calls to the appropriate routine in the Named Property Library.
111The Dynamic Matcher returns one bitstream that marks all the positions that fully match the compiled regular expression.
112Finally, a Match Scanner scans through the returned bitstream to select the matching lines and generate the normal grep output.
[4466]113
[4472]114We can also apply a pipeline parallelism strategy to further speed up the process of \icGrep{}.
[4479]115Transposition and the Required Streams Generator can be performed in a separate thread which can start even before the dynamic compilation starts.
[4476]116The output of Transposition and the Required Streams Generator, that is the 8 basis bits streams and the required streams,
[4499]117are stored in a shared memory buffer for subsequent processing by the Dynamic Matcher once compilation is complete.
[4479]118A single thread performs both compilation and matching using the computed basis and required streams.
119To avoid L2 cache contention, we allocate only a limited amount of space for the shared data in a circular buffer.
120The performance is dependent on the slowest thread.
[4466]121In the case that the cost of transposition and required stream generation is more than the matching process,
[4499]122we can further divide up the work and assign two threads for Transposition and the Required Streams Generator.
[4466]123
124
Note: See TracBrowser for help on using the repository browser.