Performance enhancement with speculative execution based parallelism for processing large-scale xml-based application data

ABSTRACT

We present the design and implementation of a toolkit for processing large-scale XML datasets that utilizes the capabilities for parallelism that are available in the emerging multi-core architectures. Multi-core processors are expected to be widely available in research clusters and scientific desktops, and it is critical to harness the opportunities for parallelism in the middleware, instead of passing on the task to application programmers. An emerging trend is the use of XML as the data format for many distributed/grid applications, with the size of these documents ranging from tens of megabytes to hundreds of megabytes. Our earlier benchmarking results revealed that most of the widely available XML processing toolkits do not scale well for large sized XML data. A significant transformation is necessary in the design of XML processing for distributed applications so that the overall application turn-around time is not negatively affected by XML processing. We discuss XML processing using PiXiMaL, a parallel processing library for large-scale XML datasets. The parallelization approach is to build a DFA-based parser that recognizes a useful subset of the XML specification, and convert the DFA into an NFA that can be applied to an arbitrary subset of the input. Speculative NFAs are scheduled on available cores in a node to effectively utilize the processing capabilities and achieve overall performance gains. We evaluate the efficacy of this approach in terms of potential speedup that can be achieved for representative XML datasets. We also evaluate the effect of two different memory allocation libraries to quantify the memory-bottleneck as different cores access shared data structures.

REFERENCES

• 1: Nayef Abu-Ghazaleh , Michael J. Lewis, Differential Deserialization for Optimized SOAP Performance, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.21, November 12-18, 2005 [doi>10.1109/SC.2005.24]
• 2: Alfred V. Aho , Jeffrey D. Ullman, The theory of parsing, translation, and compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, 1972
• 3: Kenneth Chiu , Madhusudhan Govindaraju , Randall Bramley, Investigating the Limits of SOAP Performance for Scientific Computing, Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, p.246, July 24-26, 2002
• 4: J. Clark. Expat is an XML parser library written in C. http://expat.sourceforge.net/.
• 5: Jacques Cohen , Timothy Hickey , Joel Katcoff, Upper Bounds for Speedup in Parallel Parsing, Journal of the ACM (JACM), v.29 n.2, p.408-428, April 1982 [doi>10.1145/322307.322316]
• 6: On Building Parallel & Grid Applications: Component Technology and Distributed Services, Proceedings of the 2nd International Workshop on Challenges of Large Applications in Distributed Environments, p.44, June 07-07, 2004
• 7: Madhusudhan Govindaraju , Aleksander Slominski , Venkatesh Choppella , Randall Bramley , Dennis Gannon, Requirements for and evaluation of RMI protocols for scientific computing, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.61-es, November 04-10, 2000, Dallas, Texas, United States
• 8: T. Gross , A. Sobel , M. Zolg, Parallel compilation for a parallel machine, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.91-100, June 19-23, 1989, Portland, Oregon, United States
• 9: Michael R. Head , Madhusudhan Govindaraju, Parallel Processing of Large-Scale XML-Based Application Documents on Multi-core Architectures with PiXiMaL, Proceedings of the 2008 Fourth IEEE International Conference on eScience, p.261-268, December 07-12, 2008 [doi>10.1109/eScience.2008.77]
• 10: Michael R. Head , Madhusudhan Govindaraju , Aleksander Slominski , Pu Liu , Nayef Abu-Ghazaleh , Robert van Engelen , Kenneth Chiu , Michael J. Lewis, A Benchmark Suite for SOAP-based Communication in Grid Web Services, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.19, November 12-18, 2005 [doi>10.1109/SC.2005.2]
• 11: Michael R. Head , Madhusudhan Govindaraju , Robert van Engelen , Wei Zhang, Benchmarking XML processors for applications in grid web services, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188581]
• 12: Howard P. Katseff, Using data partitioning to implement a parallel assembler, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.66-76, July 19-21, 1988, New Haven, Connecticut, United States
• 13: Wei Lu , Kenneth Chiu , Yinfei Pan, A Parallel Approach to XML Parsing, Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, p.223-230, September 28-29, 2006 [doi>10.1109/ICGRID.2006.311019]
• 14: Y. Oren. Piccolo is a small, extremely fast XML parser for Java, 2006. http://piccolo.sourceforge.net/.
• 15: Yinfei Pan , Ying Zhang , Kenneth Chiu , Wei Lu, Parallel XML Parsing Using Meta-DFAs, Proceedings of the Third IEEE International Conference on e-Science and Grid Computing, p.237-244, December 10-13, 2007 [doi>10.1109/E-SCIENCE.2007.55]
• 16: R Development Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2007.
• 17: Gurmeet Singh , Shishir Bharathi , Ann Chervenak , Ewa Deelman , Carl Kesselman , Mary Manohar , Sonal Patil , Laura Pearlman, A Metadata Catalog Service for Data Intensive Applications, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.33, November 15-21, 2003
• 18: Trolltech. API Documentation for QtXml Module, 2007. http://doc.trolltech.com/4.2/trolltech.html.
• 19: R. van Engelen. Constructing Finite State Automata for High Performance XML Web Services. In International Symposium on Web Services, pages 975--981, 2004.
• 20: R. van Engelen. gSOAP: C/C++ Web Services and Clients, 2007. http://www.cs.fsu.edu/~engelen/soap.html.
• 21: D. Veillard. The XML C parser and toolkit of Gnome, 2006. http://xmlsoft.org/.
• 22: Xerces-J. Xerces2 Java Parser 2.9.0 Release, 2006. http://xerces.apache.org/xerces2-j/.
• 23: J. Zhang. Project Homepage of VTD-XML, 2007. http://vtd-xml.sourceforge.net/.
• 24: Wei Zhang , Robert van Engelen, A Table-Driven Streaming XML Parsing Methodology for High-Performance Web Services, Proceedings of the IEEE International Conference on Web Services, p.197-204, September 18-22, 2006 [doi>10.1109/ICWS.2006.15]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Languages, Performance

Keywords:
chip-level multiprocessing, parallel techniques, xml datasets