\documentclass[runningheads,a4paper]{llncs} \usepackage{tikz} \usetikzlibrary{shapes,positioning,arrows,calc,fadings} \usepackage{pgfplots} \usepackage{pgfplotstable} \usepackage{booktabs,siunitx,ragged2e} \usepackage{subfig} \usepackage{amsmath} \newcommand{\BigO}[1]{\ensuremath{\operatorname{O}\bigl(#1\bigr)}} \usepackage[official]{eurosym} \usepackage[utf8]{inputenc} \usepackage{listings} \lstset{breaklines=true,basicstyle=\small\ttfamily} \usepackage{bbding} \newcommand{\comment}[1]{} \newcommand{\icGrep}[1]{icGrep} \def\RegularExpression{RegEx} \def\Pablo{Parabix} \def\CodeUnit{Code Unit} \def\REParser{\RegularExpression{} Parser} \def\CodeUnitCompiler{\CodeUnit{} Compiler} \def\RegularExpressionCompiler{\RegularExpression{} Compiler} \def\PabloCompiler{\Pablo{} Compiler} \pagestyle{empty} \begin{document} \title{Bitwise Data Parallelism with LLVM: The icGrep Case Study} \author{Robert D. Cameron\inst{1 (}\Envelope\inst{)} \and Nigel Medforth\inst{1} \and Dan Lin\inst{1} \and Dale Denis\inst{1} \and William N. Sumner\inst{1} } \institute{School of Computing Science, Simon Fraser University} \maketitle \begin{abstract} Bitwise data parallelism using short vector (SIMD) instructions has recently been shown to have considerable promise as the basis for a new, fundamentally parallel, style of regular expression processing. This paper examines the application of this approach to the development a full-featured Unicode-capable open-source grep implementation. Constructed using a layered architecture combining Parabix and LLVM compiler technologies, icGrep is the first instance of a potentially large class of text processing applications that achieve high performance text processing through the combination of dynamic compilation and bitwise data parallelism. In performance comparisons with several contemporary alternatives, 10$\times$ or better speedups are often observed. \end{abstract} \input{introduction.tex} \input{background.tex} \input{unicode-re.tex} \input{architecture.tex} \input{evaluation.tex} \input{conclusion.tex} \bibliographystyle{splncs} \bibliography{bitgrep} \end{document}