Changeset 2473 for docs/Working


Ignore:
Timestamp:
Oct 17, 2012, 5:16:56 PM (7 years ago)
Author:
lindanl
Message:

Add the first subsection for multithread ICXML.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/icXML/multithread.tex

    r2453 r2473  
    11\section{Leveraging SIMD Parallelism for Multicore: Pipeline Parallelism}
    22\subsection{Pipeline Strategy for ICXML}
     3As discussed in section \ref{}, Xerces can be considered as a complex finite-state machine.
     4Finite-state machine belongs to the hardest application class to parallelize and process efficiently
     5among all presented in Berkeley study reports \cite{Asanovic:EECS-2006-183}.
     6However, ICXML reconstructs Xerces and provides logical layers between modules,
     7which naturally enables pipeline parallel processing.
    38
     9In our pipeline model, each thread is in charge of one module or one group of modules.
     10A straight forward division is to take advantage of the layer between Parabix Subsystem and Markup Processor.
     11In this case, the first thread $T_1$ will read 16k of XML input $I$ at a time
     12and process all the modules in Parabix Subsystem to generates
     13content buffer, symbol array, URI array, context ID array and store them to a pre-allocated shared data structure $S$.
     14The second thread $T_2$ reads the shared data provided by the first thread and
     15goes through all the modules in Markup Processor and writes output $O$.
     16
     17The shared data structure is implemented using a ring buffer,
     18where each entry consists of all the arrays shared between the two threads with size of 160k.
     19In the example of Figure \ref{threads_timeline1} and \ref{threads_timeline2}, the ring buffer has four entries.
     20A lock-free mechanism is applied to ensure that each entry can only be read or written by one thread at the same time.
     21In Figure \ref{threads_timeline1}, the processing time of the first thread is longer,
     22thus the second thread always wait for the first thread to finish processing one chunk of input
     23and write to the shared memory.
     24Figure \ref{threads_timeline2} illustrates a different situation where the second thread is slower
     25and the first thread has to wait for the second thread finishing reading the shared data before it can reuse the memory space.
    426
    527\begin{figure}
    628\includegraphics[width=0.50\textwidth]{plots/threads_timeline1.pdf}
    7 \label{icxml_structure}
    829\caption{}
     30\label{threads_timeline1}
    931\end{figure}
    1032
    1133\begin{figure}
    1234\includegraphics[width=0.50\textwidth]{plots/threads_timeline2.pdf}
    13 \label{icxml_structure}
    1435\caption{}
     36\label{threads_timeline2}
    1537\end{figure}
    1638
    1739\subsection{Performance Comparison}
     40
     41
    1842\begin{figure}
    1943\begin{center}
    2044\includegraphics[width=0.50\textwidth]{plots/single-multi-thread.pdf}
    21 \label{xerces_structure}
    22 \caption{Performance comparison without namespace}
     45\caption{Performance comparison of single-thread vs. multithread without namespace}
     46\label{single-multi-thread}
    2347\end{center}
    2448
     
    2650\begin{figure}
    2751\includegraphics[width=0.50\textwidth]{plots/single-multi-thread_ns.pdf}
    28 \label{icxml_structure}
    29 \caption{Performance comparison with namespace}
     52\caption{Performance comparison of single-thread vs. multithread with namespace}
     53\label{single-multi-thread_ns}
    3054\end{figure}
    3155
     
    3357\begin{center}
    3458\includegraphics[width=0.50\textwidth]{plots/threads_comp.pdf}
    35 \label{xerces_structure}
    36 \caption{}
     59\caption{Performance comparison of the two threads without namespace}
     60\label{threads_comp}
    3761\end{center}
    3862
     
    4064\begin{figure}
    4165\includegraphics[width=0.50\textwidth]{plots/threads_comp_ns.pdf}
    42 \label{icxml_structure}
    43 \caption{}
     66\caption{Performance comparison of the two threads with namespace}
     67\label{threads_comp_ns}
    4468\end{figure}
Note: See TracChangeset for help on using the changeset viewer.