source: docs/Working/re/ppopp-re.tex @ 3459

Last change on this file since 3459 was 3459, checked in by cameron, 6 years ago

New outline for PPoPP; use conference template

File size: 5.2 KB
Line 
1%-----------------------------------------------------------------------------
2%
3%               Template for sigplanconf LaTeX Class
4%
5% Name:         sigplanconf-template.tex
6%
7% Purpose:      A template for sigplanconf.cls, which is a LaTeX 2e class
8%               file for SIGPLAN conference proceedings.
9%
10% Guide:        Refer to "Author's Guide to the ACM SIGPLAN Class,"
11%               sigplanconf-guide.pdf
12%
13% Author:       Paul C. Anagnostopoulos
14%               Windfall Software
15%               978 371-2316
16%               paul@windfall.com
17%
18% Created:      15 February 2005
19%
20%-----------------------------------------------------------------------------
21
22
23\documentclass{sigplanconf}
24
25% The following \documentclass options may be useful:
26
27% preprint      Remove this option only once the paper is in final form.
28% 10pt          To set in 10-point type instead of 9-point.
29% 11pt          To set in 11-point type instead of 9-point.
30% authoryear    To obtain author/year citation style instead of numeric.
31
32\usepackage{amsmath}
33
34
35\begin{document}
36
37\special{papersize=8.5in,11in}
38\setlength{\pdfpageheight}{\paperheight}
39\setlength{\pdfpagewidth}{\paperwidth}
40
41\conferenceinfo{PPoPP 2014}{February 15-19, 2013, Orland, Florida, United States} 
42\copyrightyear{2013} 
43\copyrightdata{978-1-nnnn-nnnn-n/yy/mm} 
44\doi{nnnnnnn.nnnnnnn}
45
46% Uncomment one of the following two, if you are not going for the
47% traditional copyright transfer agreement.
48
49%\exclusivelicense                % ACM gets exclusive license to publish,
50                                  % you retain copyright
51
52%\permissiontopublish             % ACM gets nonexclusive license to publish
53                                  % (paid open-access papers,
54                                  % short abstracts)
55
56\titlebanner{banner above paper title}        % These are ignored unless
57\preprintfooter{short description of paper}   % 'preprint' option specified.
58
59\title{Bitwise Data Parallelism in Regular Expression Matching}
60\subtitle{Subtitle Text, if any}
61
62\authorinfo{Robert D. Cameron \and Kenneth S. Herdy \and Dan Lin \and Meng Lin \and Ben Hull \and Thomas S. Shermer \and Arrvindh Shriraman}
63           {Simon Fraser University}
64           {\{cameron,ksherdy,lindanl,linmengl,bhull,shermer,ashriram\}@cs.sfu.ca}
65
66\maketitle
67
68\begin{abstract}
69\input{abstract}
70\end{abstract}
71\category{Theory of computation}{Formal languages and automata theory}{Regular languages}
72\category{Computer systems organization}{Parallel architectures}{Single instruction, multiple data}
73
74% general terms are not compulsory anymore,
75% you may leave them out
76%\terms
77%term1, term2
78
79\keywords
80regular expression matching, grep, parallel bit stream technology
81
82\section{Introduction}
83
84
85
86
87
88
89
90
91
92Parallelism in regular expressions.
93\begin{enumerate}
94\item stream parallelism
95\item NFA state parallelism
96\item ruleset parallelism
97\item data parallelism
98\end{enumerate}
99
100
101
102The remainder of this paper is organized as follows.
103Section \ref{sec:bitwise} 
104Section \ref{sec:regexp} 
105Section \ref{sec:analysis} 
106Section \ref{sec:SSE2} 
107Section \ref{sec:AVX2} 
108Section \ref{sec:GPU} 
109Section \ref{sec:Concl} concludes the paper with a discussion of areas for future work.
110
111
112\section{Unbounded Bitwise Data Parallelism}\label{sec:bitwise}
113
114\section{Bitwise Regular Expression Matching with MatchStar}\label{sec:regexp}
115
116
117\subsection{Bitwise Data Parallelism vs. Bit-Parallel State Transition}
118The bitap algorithms use bitwise operations in an orthogonal way.
119
120\section{Analytical Comparison with DFA and NFA Implementations}\label{sec:analysis}
121
122\begin{enumerate}
123\item Operations
124\item Memory behaviour per input byte: note tables of DFA/NFA.
125
126Bille and Throup \em{Faster regular expression matching}\cite{bille2009faster}
127
128\end{enumerate}
129
130
131
132\section{Commodity SIMD Implementation and Experimental Evaluation}\label{sec:SSE2}
133\subsection{Implementation Notes}
134\subsection{Evaluation Methodology}
135\subsection{Comparison}
136
137
138
139\section{SIMD Scalability}\label{sec:AVX2}
140\subsection{AVX Stream Addition}
141  We use MatchStar for carry propagation.
142
143\section{GPU Implementation}\label{sec:GPU}
144
145\section{Miscellaneous}
146\subsection{Skipping}
147\subsection{Unicode}
148
149\section{Conclusion}\label{sec:Concl}
150\subsection{Contributions}
151\begin{enumerate}
152\item New Algorithm Class for Regular Expression Matching
153\item MatchStar for Character Class Repetition
154\item Long Stream Addition
155\item Implementations showing performance and scalability
156\end{enumerate}
157\subsection{Future Work}
158\begin{enumerate}
159\item Substring capture
160\item Unicode character classes
161\item Nonregular regexp features: zero-width assertions, backreferences
162\item Multicore for ruleset parallelism
163\end{enumerate}
164
165
166
167%\appendix
168%\section{Appendix Title}
169
170%This is the text of the appendix, if you need one.
171
172\acks
173
174This research was supported by grants from the Natural Sciences and Engineering Research Council of Canada and
175MITACS, Inc.
176
177% We recommend abbrvnat bibliography style.
178
179\bibliographystyle{abbrvnat}
180
181% The bibliography should be embedded for final submission.
182 
183\bibliography{reference}
184
185%\begin{thebibliography}{}
186%\softraggedright
187
188%\bibitem[Smith et~al.(2009)Smith, Jones]{smith02}
189%P. Q. Smith, and X. Y. Jones. ...reference text...
190%
191%\end{thebibliography}
192
193
194\end{document}
195
196
Note: See TracBrowser for help on using the repository browser.