Changeset 1302


Ignore:
Timestamp:
Aug 8, 2011, 4:43:21 PM (8 years ago)
Author:
lindanl
Message:

Create a directory for HPCA

Location:
docs
Files:
49 added
4 edited

Legend:

Unmodified
Added
Removed
  • docs/EuroPar2011/Demo/europar.py

    r1189 r1302  
    5858                              ('$M_0 + D$',  bitutil.bitstream2stringLE(temp, lgth, zero_ch)),
    5959                              ('$M_1 = (M_0 + D) \\wedge \\neg D$', bitutil.bitstream2stringLE(cursor2, lgth, zero_ch))])
     60
     61def latex_csv_parse(chardata):
     62        lgth = len(chardata)
     63        (bit, EOF_mask) = bitutil.transpose_streams(chardata)
     64        (u8, control, lex) = byteclass.classify_bytes(bit)
     65        p2 = lex.DQuote^(lex.DQuote<<1);
     66        p4 = p2^(p2<<2);
     67        p8 = p4^(p4<<4);
     68        p16 = p8^(p8<<8);
     69        p32 = p16^(p16<<16);
     70        p64 = p32^(p32<<32);
     71        quote_mask = p64^(p64<<64);
     72        return bitutil.latex_streams([('source', chardata[::-1]),
     73                                ('Quote', bitutil.bitstream2stringLE(lex.DQuote, lgth, zero_ch)),
     74                                ('LF', bitutil.bitstream2stringLE(control.LF, lgth, zero_ch)),
     75                                ('p2=DQuote^(DQuote<<1)', bitutil.bitstream2stringLE(p2, lgth, zero_ch)),
     76                                ('p4=p2^(p2<<2)', bitutil.bitstream2stringLE(p4, lgth, zero_ch)),
     77                                ('p8=p4^(p4<<4)', bitutil.bitstream2stringLE(p8, lgth, zero_ch)),
     78                                ('p16=p8^(p8<<8)', bitutil.bitstream2stringLE(p16, lgth, zero_ch)),
     79                                ('p32=p16^(p16<<16)', bitutil.bitstream2stringLE(p32, lgth, zero_ch)),
     80                                ('p64=p32^(p32<<32)', bitutil.bitstream2stringLE(p64, lgth, zero_ch)),
     81                                ('quote mask', bitutil.bitstream2stringLE(quote_mask, lgth, zero_ch)),
     82                                ('new line', bitutil.bitstream2stringLE(control.LF&~quote_mask, lgth, zero_ch))])
     83
    6084
    6185def europar1():
     
    471495
    472496if __name__ == "__main__":
    473         print demo_transpose_ascii('xmlwf')
    474 
     497        print latex_csv_parse('1996,"Jeep","Grand","SELL!\nair"\n')
     498
     499
     500
     501
     502
     503
     504
     505
     506
     507
     508
     509
     510
     511
     512
     513
     514
  • docs/EuroPar2011/europar-cameron.tex

    r1186 r1302  
    187187
    188188A bitstream is simply a sequence of $0$s and $1$s, where there is one such bit in the bitstream for each character in a source data stream.
    189 For parsing, and other text processing tasks, we need to consider multiple properties of characters at different stages during the parsing process. A bitstream can be associated with each of these properties, and hence there will be multiple (parallel) bitstreams associated with a source data stream of characters.
     189For parsing, and other text processing tasks, we need to consider multiple properties of characters at different stages during the parsing process.
     190A bitstream can be associated with each of these properties, and hence there will be multiple (parallel) bitstreams associated with a source data stream of characters.
    190191
    191192The starting point for bitstream methods are \emph{basis} bitstreams
  • docs/Working/parlensort.tex

    r1187 r1302  
    8989be implemented using our existing Pablo language, avoiding low-level C programming.
    9090
     91\section{DIV2 grouping}
     92Given streams $S$ and $E$ that mark the starts and ends of Names.
     93We can partition $E$ into length-sorted groups using div2-length strategy: $G_i = n(E_{i*2-1})|E_{i*2}$
     94
     95First we calculate $T$, which marks the two positions after each name.
     96Then we can get $G_1$ as follows.
     97\begin{eqnarray*}
     98T & = & E | n(E)\\
     99S_2 & = & n(n(S))\\
     100G_1 & = & S_2 \wedge T \\
     101\end{eqnarray*}
     102
     103$G_i (i>1)$ can be similarly determined as follows.
     104
     105\begin{eqnarray*}
     106S_{i*2} & = & n(n(S_{(i-1)*2} \wedge \neg T)) \\
     107G_i & = & S_{i*2} \wedge T \\
     108\end{eqnarray*}
     109
     110Once the length sorting above has completed, then we can process
     111names using bitscan techniques.
     112
     113For each $G_i (i>0)$:
     114\begin{enumerate}
     115\item Sequentially scan $G_i$ to find positions $P_i = \{p_{i,0},p_{i,1},...,p_{i,n},\}$.
     116\item For each $k$ in $\{1,2...,n\}$, calculate hash value for name $N[p_{i,k-i*2}]...N[p_{i,k-1}]$
     117\item Look up hash table. If the name exist, process next name.
     118Otherwise, if $N[p_{i,k-1}]$ is a delimiter (name length is odd), lookup name $N[p_{i,k-i*2}]...N[p_{i,k-2}] (i>1)$ or name $N[p_{1,k-2}]$.
     119If it exists, get its GID $g$ and insert $N[p_{i,k-i*2}]...N[p_{i,k-1}]$ with GID $g$.
     120If it dosen't exist, insert this name with a new GID and insert $N[p_{i,k-i*2}]...N[p_{i,k-1}]$ with the same GID.
     121If $N[p_{i,k-1}]$ is not a delimiter (name length is even), insert $N[p_{i,k-i*2}]...N[p_{i,k-1}]$ with a new GID.
     122\end{enumerate}
     123
     124% \section{Grouping Strategies}
     125% \subsection{Length Grouping}
     126% \subsubsection{ID grouping}
     127%
     128% \subsubsection{LOG grouping}
     129%
     130% \subsubsection{DIV grouping}
     131%
     132% \subsection{Length + hash Grouping}
     133%
     134% \section{Sorting Algorithms}
     135% \subsection{Sequential Sorting}
     136%
     137% \subsection{Parallel Sorting}
     138%
     139% \section{Group Processing Strategies}
     140%
     141% \subsection{Linear SIMD Search}
     142%
     143% \subsection{Trie}
     144%
     145% \subsection{Hash}
     146
    91147\end{document}
    92148
Note: See TracChangeset for help on using the changeset viewer.