Changeset 954 for docs/PACT2011/00-abstract.tex

Ignore:
Timestamp:
Mar 18, 2011, 1:30:24 PM (9 years ago)
Message:

Add more charts, modified abstract and some other minor changes

File:
1 edited

Legend:

Unmodified
 r953 XML is a data format designed for documents as well as the representation of data structures. The simplicity and generality of the rules make it widely used in web services and database systems. Traditional byte-at-a time XML parsers have reach their bottleneck for further improvement to satisfy the growing demand on high performance and energy efficient XML parsing. We propose a new XML parser, Parabix, based on parallel bit stream technology, which enables parallel processing using SIMD registers. We evaluate and analyze the characteristic of our first and second version parsers, which is later referred as Parabix1 and Parabix2, as well as two other popular XML parsers, Expat and Xerces on three generations of x86 machines, Dual Core, Core i3 and Sandy Bridge. The results show that Parabix2 runs 2X to 8X faster than Expat and Xerces and performs much better in terms of data cache misses and branch misperditions. Moreover, Parabix2 scales better on the three different architectures and achieves more performance improvement on newer ones. With the same level of power consumption of all parsers we studied, Parabix2 consumes much less energy. XML is a data format designed for documents as well as the representation of data structures. The simplicity and generality of the rules make it widely used in web services and database systems. Traditional XML parsers have been built around the byte-at-a-time model, in which they process every character token in the file in a sequential fashion. Unfortunately, the byte-at-time sequential model is a fundamental hindrance on performance and and in some cases can add up 100\% overhead to the database queries themselves. In this paper, we propose a new XML parser, Parabix, based on parallel bit stream technology, which converts the character strings into bitstreams and then exploits SIMD operations prevalent on modern CPUs. The first generation parser that we developed, Parabix1, uses the bitscan and bitlevel sequencing SIMD operations to emulate much of the parsers functions. Unfortunately operations like bitscan are inherently sequential nature and Parabix1's speedup is limited. We present a second generation parser, Parabix2, that fully parallelizes the parsing operations using using parallel bitlevel logic provided in modern SIMD extensions like SSE2.  We evaluate Parabix1and Parabix2 against two widely-used XML parsers, Apache's Expat and IBM's Xerces on three generations of x86 machines, including the new Intel Sandybridge. We show that Parabix2's speedup is 2$\times$---8$\times$ over Expat and Xerces. Across the different Intel machine generations, Parabix rides the scalability curve of SIMD operations whose performance inherently scales better than traditional sequential thread performance. Comparing Intel's new Sandbrige core with the Core i3 we observed performance improvement between 20---60\% for our Parabix parsers while sequential parsers like Xerces improve by $<$20\%. We measure real CPU power to demonstrate that Parabix also brings with itself significant energy efficiency. On the core i3, Parabix consumes $\simeq$4nJ per byte parsed while Xerces consumes $\simeq$20nJ per byte parsed. Finally, we perform a case study of the Intel's new 256-bit wide AVX instructions, and demonstrate that it provides X speedup over 128 bit SSE2 instruction set.