# Changeset 1186 for docs/EuroPar2011

Ignore:
Timestamp:
May 22, 2011, 7:56:57 PM (8 years ago)
Message:

Notes on parallel bitstream-based length sorting.

Location:
docs/EuroPar2011
Files:
3 edited

### Legend:

Unmodified
 r1185 % \author{Robert D. Cameron %\thanks{} \and Ehsan Amiri \and Kenneth S. Herdy \and Dan Lin \and Thomas C. Shermer \and Fred P. Popowich} % \authorrunning{Cameron {\em et al}} \authorrunning{Cameron, Amiri, Herdy, Lin, Shermer and Popowich} % the affiliations are given next; don't give your e-mail address % unless you accept that it will be published \end{abstract} \section{Introduction} of character-class streams in this way is an overhead on parallel bit stream applications, in general.   However, using the SIMD capabilities of current commodity processors, these operations are quite capabilities of current commodity processors, these operations are fast, with an amortized overhead of about 1 CPU cycle per byte for transposition and less than 1 CPU cycle per byte for all the character addition also produces some additional bits that are not involved in the scan operation. However, these are easily removed as shown in the fifth row, These are easily removed as shown in the fifth row, by applying bitwise logic to mask off any bits from the digit bitstream; these can never result of the marker advance operation $n(M_0)$ to produce the new marker bitstream $M_1$.  At this point, a hash mark is required, so the first error bitstream $E_0$ is the grammar requires a hash mark, so the first error bitstream $E_0$ is formed using a bitwise and'' operation combined with negation, to indicate violations of this condition. Following the pattern shown here, the remaining syntactic features of XML markup can similarly be parsed with bitstream based methods.   One complexity is that the bitstream based methods.   One complication is that the parsing of comments, CDATA sections and processing instructions must be within which ordinary XML markups are not parsed (i.e., within each of these types of construct.   This is handled by first performance the parsing of these structures and by first parsing these structures and then forming a {\em mask bitstream}, that is, a stream that identifies spans of text to be excluded from parsing It is too expensive to check every instance of an XML name against the full range of possible values.   However, it is possible and quite inexpensive to use parallel bitstream possible and inexpensive to use parallel bitstream techniques to verify that any ASCII characters within a name are indeed legal name start characters or name characters. it useful to define a name scan character class to include all the legal ASCII characters for names as well as all non-ASCII characters. A namecheck character class bitstream will then be defined to identify nonASCII A namecheck character class bitstream will then be defined to identify non-ASCII characters found within namescans.   In most documents this bitstream will be all $0$s; even in documents with substantial the processor carry flags and add-with-carry instructions on 64-bit general registers.  In both cases, the overall performance is quite impressive, with the increased performance is impressive, with the increased parallelism of parallel bit scans clearly paying off in improved performance for dense markup. \bibliographystyle{plain} \bibliography{xmlperf} %\bibliographystyle{plain} %\bibliography{xmlperf} \begin{thebibliography}{10} \bibitem{Asanovic:EECS-2006-183} Krste Asanovic, Ras Bodik, Bryan~Christopher Catanzaro, Joseph~James Gebis, Parry Husbands, Kurt Keutzer, David~A. Patterson, William~Lester Plishker, John Shalf, Samuel~Webb Williams, and Katherine~A. Yelick. \newblock The landscape of parallel computing research: A view from {Berkeley}. \newblock Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley, Dec 2006. \bibitem{TR:XML} Tim Bray, Jean Paoli, C.~M. Sperberg-McQueen, Eve Maler, and FranÃ§ois Yergeau. \newblock Extensible markup language ({XML}) 1.0 (fifth edition). \newblock W3C Recommendation, 2008. \bibitem{PPoPP08} Robert~D. Cameron. \newblock {A Case Study in SIMD Text Processing with Parallel Bit Streams}. \newblock In {\em {ACM Symposium on Principles and Practice of Parallel Programming (PPoPP)}}, {Salt Lake City, Utah}, 2008. \bibitem{CameronHerdyLin2008} Robert~D. Cameron, Kenneth~S. Herdy, and Dan Lin. \newblock High performance {XML} parsing using parallel bit stream technology. \newblock In {\em {CASCON} '08: Proceedings of the 2008 conference of the center for advanced studies on collaborative research}, pages 222--235, New York, NY, USA, 2008. ACM. \bibitem{DaiNiZhu2010} Zefu Dai, Nick Ni, and Jianwen Zhu. \newblock A 1 cycle-per-byte {XML} parsing accelerator. \newblock In {\em FPGA '10: Proceedings of the 18th Annual ACM/SIGDA International Symposium on Field Programmable Gate Arrays}, pages 199--208, New York, NY, USA, 2010. ACM. \bibitem{Herdy2008} Kenneth~S. Herdy, David~S. Burggraf, and Robert~D. Cameron. \newblock High performance {GML} to {SVG} transformation for the visual presentation of geographic data in web-based mapping systems. \newblock In {\em Proceedings of {SVG} Open 2008}, August 2008. \bibitem{XMLScreamer} M.~G. Kostoulas, M.~Matsa, N.~Mendelsohn, E.~Perkins, A.~Heifets, and M.~Mercaldi. \newblock {{XML} Screamer: An Integrated Approach to High Performance {XML} Parsing, Validation and Deserialization}. \newblock In {\em Proceedings of the 15th International Conference on World Wide Web (WWW '06)}, pages 93--102, 2006. \bibitem{Leventhal2009} Michael Leventhal and Eric Lemoine. \newblock The {XML} chip at 6 years. \newblock In {\em International Symposium on Processing {XML} Efficiently: Overcoming Limits on Space, Time, or Bandwidth}, August 2009. \bibitem{Shah2009} Bhavik Shah, Praveen Rao, Bongki Moon, and Mohan Rajagopalan. \newblock A data parallel algorithm for {XML DOM} parsing. \newblock In Zohra BellahsÃšne, Ela Hunt, Michael Rys, and Rainer Unland, editors, {\em Database and {XML} Technologies}, volume 5679 of {\em Lecture Notes in Computer Science}, pages 75--90. Springer Berlin / Heidelberg, 2009. \bibitem{ZhangPanChiu09} Ying Zhang, Yinfei Pan, and Kenneth Chiu. \newblock Speculative p-{DFA}s for parallel {XML} parsing. \newblock In {\em High Performance Computing (HiPC), 2009 International Conference on}, pages 388--397, December 2009. \end{thebibliography} \end{document}