source: docs/Working/icGrep/architecture.tex @ 4493

Last change on this file since 4493 was 4493, checked in by cameron, 4 years ago

Updates

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