Changeset 1325 for docs


Ignore:
Timestamp:
Aug 19, 2011, 11:43:28 AM (8 years ago)
Author:
lindanl
Message:

multi-thread section

Location:
docs/HPCA2011
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • docs/HPCA2011/09-pipeline.tex

    r1320 r1325  
    55Moreover, using mulitiple cores, we can further improve the performance of Parabix while keeping the energy consumption at the same level.
    66
    7 The typical approach to parallelizing software (data parallelism)
    8 requires nearly independent data, which is a difficult task
    9 for dividing XML data. A simple division determined by the
    10 segment size can easily make most of the segments illegal
    11 according to the parsing rules while the data as a whole is legal.
    12 Therefore, instead of dividing the data into segments and
    13 assigning different data segments to different cores,
    14 we divide the process into several stages and let each core work with one single stage.
     7A typical approach to parallelizing software, data parallelism, requires nearly independent data,
     8However, the nature of XML files makes them hard to partition nicely for data parallelism.
     9Several approaches have been used to address this problem.
     10A preparsing phase has been proposed to help partition the XML document \cite{dataparallel}.
     11The goal of this preparsing is to determine the tree structure of the XML document
     12so that it can be used to guide the full parsing in the next phase.
     13Another data parallel algorithm is called ParDOM \cite{Shah:2009}.
     14It first builds partial DOM node tree structures for each data segments and then link them
     15using preorder numbers that has been assigned to each start element to determine the ordering among siblings
     16and a stack to manage the parent-child relationship between elements.
     17
     18Theses data parallelism approaches introduce a lot of overheads to solve the data dependencies between segments.
     19Therefore, instead of partitioning the data and assigning different data segments to different cores,
     20we propose a pipeline parallelism strategy that partitions the process into several stages and let each core work with one single stage.
    1521
    1622The interface between stages is implemented using a circular array,
  • docs/HPCA2011/main.aux

    r1320 r1325  
    118118\@writefile{toc}{\contentsline {subsection}{\numberline {7.3}Performance Results}{9}}
    119119\@writefile{toc}{\contentsline {section}{\numberline {8}Parabix2 on GT-P1000M}{9}}
     120\citation{dataparallel}
     121\citation{Shah:2009}
    120122\@writefile{lof}{\contentsline {figure}{\numberline {21}{\ignorespaces Parabix2 Performance on GT-P1000M (y-axis: CPU Cycles per kB)\relax }}{10}}
    121123\newlabel{arm_processing_time}{{21}{10}}
     
    131133\bibcite{bellosa2001}{1}
    132134\bibcite{bertran2010}{2}
    133 \bibcite{bircher2007}{3}
    134 \bibcite{TR:XML}{4}
    135 \bibcite{Cameron2009}{5}
    136135\@writefile{lot}{\contentsline {table}{\numberline {6}{\ignorespaces Relationship between Each Pass and Data Structures\relax }}{11}}
    137136\newlabel{pass_structure}{{6}{11}}
     
    140139\@writefile{lof}{\contentsline {figure}{\numberline {24}{\ignorespaces Average Power (watts)\relax }}{11}}
    141140\newlabel{power}{{24}{11}}
    142 \@writefile{toc}{\contentsline {section}{\numberline {10}Conclusion}{11}}
    143141\@writefile{lof}{\contentsline {figure}{\numberline {25}{\ignorespaces Energy Consumption (nJ per byte)\relax }}{11}}
    144142\newlabel{energy}{{25}{11}}
     143\@writefile{toc}{\contentsline {section}{\numberline {10}Conclusion}{11}}
    145144\@writefile{toc}{\contentsline {section}{\numberline {11}References}{11}}
     145\bibcite{bircher2007}{3}
     146\bibcite{TR:XML}{4}
     147\bibcite{Cameron2009}{5}
    146148\bibcite{Cameron2008}{6}
    147149\bibcite{Cameron2010}{7}
     
    159161\bibcite{Leventhal2009}{19}
    160162\bibcite{LiWangLiuLi2009}{20}
    161 \bibcite{NicolaJohn03}{21}
    162 \bibcite{ParaDOM2009}{22}
    163 \bibcite{ZhangPanChiu09}{23}
     163\bibcite{dataparallel}{21}
     164\bibcite{NicolaJohn03}{22}
     165\bibcite{ParaDOM2009}{23}
     166\bibcite{Shah:2009}{24}
     167\bibcite{ZhangPanChiu09}{25}
  • docs/HPCA2011/main.bbl

    r1302 r1325  
    124124  Technologies, International Conference on}, 0:439--444, 2009.
    125125
     126\bibitem{dataparallel}
     127W.~Lu, Y.~Pan, , and K.~Chiu.
     128\newblock A parallel approach to xml parsing.
     129\newblock {\em The 7th IEEE/ACM International Conference on Grid Computing},
     130  2006.
     131
    126132\bibitem{NicolaJohn03}
    127133{Matthias Nicola and Jasmi John}.
     
    137143  Science}, pages 75--90. Springer Berlin / Heidelberg, 2009.
    138144
     145\bibitem{Shah:2009}
     146B.~Shah, P.~R. Rao, B.~Moon, and M.~Rajagopalan.
     147\newblock A data parallel algorithm for xml dom parsing.
     148\newblock In {\em Proceedings of the 6th International XML Database Symposium
     149  on Database and XML Technologies}, XSym '09, pages 75--90, Berlin,
     150  Heidelberg, 2009. Springer-Verlag.
     151
    139152\bibitem{ZhangPanChiu09}
    140153Y.~Zhang, Y.~Pan, and K.~Chiu.
  • docs/HPCA2011/reference.bib

    r1302 r1325  
    480480}
    481481
     482@inproceedings{Shah:2009,
     483 author = {Shah, Bhavik and Rao, Praveen R. and Moon, Bongki and Rajagopalan, Mohan},
     484 title = {A Data Parallel Algorithm for XML DOM Parsing},
     485 booktitle = {Proceedings of the 6th International XML Database Symposium on Database and XML Technologies},
     486 series = {XSym '09},
     487 year = {2009},
     488 isbn = {978-3-642-03554-8},
     489 location = {Lyon, France},
     490 pages = {75--90},
     491 numpages = {16},
     492 publisher = {Springer-Verlag},
     493 address = {Berlin, Heidelberg},
     494}
     495
     496@article{dataparallel,
     497 author = {Wei Lu and Yinfei Pan and and Kenneth Chiu},
     498 title = {A Parallel Approach to XML Parsing},
     499 journal = {The 7th IEEE/ACM International Conference on Grid Computing},
     500 year = {2006}
     501 }
Note: See TracChangeset for help on using the changeset viewer.