Changeset 3870 for docs


Ignore:
Timestamp:
Jun 14, 2014, 5:26:39 PM (5 years ago)
Author:
cameron
Message:

Formatting, PACT publication template

Location:
docs/Working/re
Files:
1 added
1 deleted
3 edited
1 copied
1 moved

Legend:

Unmodified
Added
Removed
  • docs/Working/re/avx2.tex

    r3868 r3870  
    135135
    136136As shown in Figure \ref{fig:AVXSpeedup} the reduction in
    137 instruction count was reflected in a significant speed-up
     137instruction count was reflected in a significant speedup
    138138in the bitstreams implementation in all cases except
    139 StarHeight.  However, the speed-up was
     139StarHeight.  However, the speedup was
    140140considerably less than expected. 
    141141The bitstreams code  on AVX2 has suffered from a considerable
     
    155155in the overhead cost of the Parabix transform.
    156156
     157Table \ref{Xfactors} shows the final performance results
     158showing the speedup factors achieved by the Parabix/AVX2 implementation
     159vs nrgrep and gre2p.
     160\begin{table}
     161\begin{center}
     162\begin{tabular}{|c|c|c|} \hline
     163\multirow{2}{*}{Expression} & \multicolumn{2}{c|}{Bitstream grep Speedup} \\ \cline{2-3}
     164& vs. nrgrep & vs. gre2p \\ \hline \hline
     165At & 3.5X & 34X \\ \hline
     166Date & 0.76X & 13X \\ \hline
     167Email & 9.5X & 28X \\ \hline
     168URIorEmail & 6.6X & 27X \\ \hline
     169HexBytes & 8.1X & 105X \\ \hline
     170StarHeight & 1.9X & 7.6X \\ \hline
     171\end{tabular}
     172\end{center}
     173\caption{Speedups Obtained}\label{Xfactors}
     174\end{table}
  • docs/Working/re/conclusion.tex

    r3866 r3870  
    9999intrusion detection for example.   Additional GPGPU implementation
    100100work could take advantage of specialized instructions available
    101 on particular platforms but not generally avaiable through CUDA.
    102 For both multicore and GPGPU implementations, improved
    103 support for data-parallel division of input streams using
     101on particular platforms but not generally avaiable through OpenCL.
     102For both multicore and GPGPU implementations,
     103data-parallel division of input streams could benefit from
    104104techniques such as the principled speculation of Zhao et al
    105105\cite{DBLP:conf/asplos/ZhaoWS14},
  • docs/Working/re/pact051-cameron.tex

    r3868 r3870  
    1 \documentclass[pageno]{jpaper}
    2 
    3 %replace XXX with the submission number you are given from the PACT submission site.
    4 \newcommand{\pactsubmissionnumber}{XXX}
    5 
     1\documentclass{sig-alternate-2013}
     2
     3\newfont{\mycrnotice}{ptmr8t at 7pt}
     4\newfont{\myconfname}{ptmri8t at 7pt}
     5\let\crnotice\mycrnotice%
     6\let\confname\myconfname%
     7
     8\permission{Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.}
     9\conferenceinfo{PACT'14,}{August 24--27, 2014, Edmonton, AB, Canada. \\
     10{\mycrnotice{Copyright is held by the owner/author(s). Publication rights licensed to ACM.}}}
     11\copyrightetc{ACM \the\acmcopyr}
     12\crdata{978-1-4503-2809-8/14/08\ ...\$15.00.\\
     13http://dx.doi.org/10.1145/2628071.2628079}
     14
     15\clubpenalty=10000
     16\widowpenalty = 10000
    617\usepackage[normalem]{ulem}
    718\usepackage{amssymb}
     
    920\usepackage{graphicx}
    1021\usepackage{tikz}
     22\usepackage{multirow}
    1123\usepackage{pgfplots}
    1224
     
    1426
    1527\title{Bitwise Data Parallelism in Regular Expression Matching}
     28
     29\numberofauthors{7} %  in this sample file, there are a *total*
     30% of EIGHT authors. SIX appear on the 'first-page' (for formatting
     31% reasons) and the remaining two appear in the \additionalauthors section.
     32%
     33\author{
     34% You can go ahead and credit any number of authors here,
     35% e.g. one 'row of three' or two rows (consisting of one row of three
     36% and a second row of one, two or three).
     37%
     38% The command \alignauthor (no curly braces needed) should
     39% precede each author name, affiliation/snail-mail address and
     40% e-mail address. Additionally, tag each line of
     41% affiliation/address with \affaddr, and tag the
     42% e-mail address with \email.
     43%
     44% 1st. author
     45\alignauthor
     46Rob Cameron\\
     47       \affaddr{School of Computing Science}\\
     48       \affaddr{Simon Fraser University}\\
     49       \affaddr{Surrey, British Columbia}\\
     50       \email{cameron@cs.sfu.ca}
     51% 2nd. author
     52\alignauthor
     53Tom Shermer\\
     54       \affaddr{School of Computing Science}\\
     55       \affaddr{Simon Fraser University}\\
     56       \affaddr{Surrey, British Columbia}\\
     57       \email{shermer@cs.sfu.ca}
     58% 3rd. author
     59\alignauthor Arrvindh Shriraman\\
     60       \affaddr{School of Computing Science}\\
     61       \affaddr{Simon Fraser University}\\
     62       \affaddr{Surrey, British Columbia}\\
     63       \email{ashriram@cs.sfu.ca}
     64\and  % use '\and' if you need 'another row' of author names
     65% 4th. author
     66\alignauthor Ken Herdy\\
     67       \affaddr{School of Computing Science}\\
     68       \affaddr{Simon Fraser University}\\
     69       \affaddr{Surrey, British Columbia}\\
     70       \email{ksherdy@sfu.ca}
     71% 5th. author
     72\alignauthor Dan Lin\\
     73       \affaddr{School of Computing Science}\\
     74       \affaddr{Simon Fraser University}\\
     75       \affaddr{Surrey, British Columbia}\\
     76       \email{lindanl@sfu.ca}
     77% 6th. author
     78\alignauthor Ben Hull\\
     79       \affaddr{School of Computing Science}\\
     80       \affaddr{Simon Fraser University}\\
     81       \affaddr{Surrey, British Columbia}\\
     82       \email{bhull@sfu.ca}
     83% 7th. author
     84\alignauthor Meng Lin\\
     85       \affaddr{School of Computing Science}\\
     86       \affaddr{Simon Fraser University}\\
     87       \affaddr{Surrey, British Columbia}\\
     88       \email{linmengl@sfu.ca}
     89}
     90% There's nothing stopping you putting the seventh, eighth, etc.
     91% author on the opening page (as the 'third row') but we ask,
     92% for aesthetic reasons that you place these 'additional authors'
     93% in the \additional authors block, viz.
     94%\additionalauthors{Additional authors: John Smith (The Th{\o}rv{\"a}ld Group,
     95%email: {\texttt{jsmith@affiliation.org}}) and Julius P.~Kumquat
     96%(The Kumquat Consortium, email: {\texttt{jpkumquat@consortium.net}}).}
     97%\date{30 July 1999}
     98% Just remember to make sure that the TOTAL number of authors
     99% is the number that will appear on the first page PLUS the
     100% number that will appear in the \additionalauthors section.
    16101
    17102
     
    375460input data  & \verb`a453z--b3z--az--a12949z--ca22z7--`\\
    376461$M_1$ & \verb`.1...........1...1.........1.....`\\
    377 $D = \text{\tt [0-9]}$ & \verb`.111....1........11111.....11.1..`\\
    378 $T_0 = M_1 \wedge D$ & \verb`.1...............1.........1.....`\\
    379 $T_1 = T_0 + D$ & \verb`....1...1.............1......11..`\\
    380 $T_2 = T_1 \oplus D$ & \verb`.1111............111111....111...`\\
    381 $M_2 = T_2 \, | \, M_1$ & \verb`.1111........1...111111....111...`
     462$C = \text{\tt [0-9]}$ & \verb`.111....1........11111.....11.1..`\\
     463$T_0 = M_1 \wedge C$ & \verb`.1...............1.........1.....`\\
     464$T_1 = T_0 + C$ & \verb`....1...1.............1......11..`\\
     465$T_2 = T_1 \oplus C$ & \verb`.1111............111111....111...`\\
     466$M_2 = T_2 \vee M_1$ & \verb`.1111........1...111111....111...`
    382467\end{tabular}
    383468
    384469\end{center}
    385 \caption{$M_2 = \text{MatchStar}(M_1, D)$}
     470\caption{$M_2 = \text{MatchStar}(M_1, C)$}
    386471\label{fig:matchstar}
    387472\end{figure}
     
    405490In general, given a marker stream $M$ and a character class stream $C$,
    406491the operation of MatchStar is defined by the following equation. 
    407 \[\text{MatchStar}(M, C) = (((M \wedge C) + C)  \oplus C) | M\]
     492\[\text{MatchStar}(M, C) = (((M \wedge C) + C)  \oplus C) \vee M\]
    408493Given a set of initial marker positions, the result stream marks
    409494all possible positions that can be reached by 0 or more occurrences
  • docs/Working/re/sse2.tex

    r3868 r3870  
    1111Date            & \verb`([0-9][0-9]?)/([0-9][0-9]?)/([0-9][0-9]([0-9][0-9])?)`          \\ \hline     
    1212Email           & \verb`([^ @]+)@([^ @]+)`              \\ \hline
    13 URIOrEmail      & \verb`'(([a-zA-Z][a-zA-Z0-9]*)://|mailto:)([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)'`               \\ \hline     
    14 HexBytes                & \verb`[ ](0x)?([a-fA-F0-9][a-fA-F0-9])+[.:,?! ]'`             \\ \hline
    15 StarHeight              & \verb`'[A-Z]((([a-zA-Z]*a[a-zA-Z]*[ ])*[a-zA-Z]*e[a-zA-Z]*[ ])*[a-zA-Z]*s[a-zA-Z]*[ ])*[.?!]'`                \\ \hline
     13URIOrEmail      & \verb`(([a-zA-Z][a-zA-Z0-9]*)://|mailto:)([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)`         \\ \hline     
     14HexBytes                & \verb`[ ](0x)?([a-fA-F0-9][a-fA-F0-9])+[.:,?! ]`              \\ \hline
     15StarHeight              & \verb`[A-Z]((([a-zA-Z]*a[a-zA-Z]*[ ])*[a-zA-Z]*e[a-zA-Z]*[ ])*[a-zA-Z]*s[a-zA-Z]*[ ])*[.?!]`          \\ \hline
    1616\end{tabular}
    1717}
     
    4747The NFA class is represented by nrgrep, one of the
    4848strongest competitors in regular expression matching performance.
    49 We also considered GNU grep 2.10, agrep 3.41 as and alternative NFA-based implementation
     49We also considered GNU grep 2.10, agrep 3.41 as an alternative NFA-based implementation
    5050and pcregrep 8.12 as a backtracking implementation, but do not
    5151report data for them. 
Note: See TracChangeset for help on using the changeset viewer.