2. Home
  3. ARCHIVE
  4. 2020
  5. VOL 42, NO 1 (2020)
  6. pp. 33-50

HARDWARE-SOFTWARE XML-DOCUMENTS PROCESSING

A.M. Sergiyenko, M.M. Orlova, O.A. Molchanov

Èlektron. model. 2020, 42(1):33-50
https://doi.org/10.15407/emodel.42.01.033

ABSTRACT

Existing algorithms and tools for XML-documents processing are reviewed in this article. A need in highly productive devices that analyze XML-requests and that can be easily reconfigured for different grammars is determined. SM16 processor core is developed. Its architecture effectively evaluates stack-based parsing algorithms and is implemented on field programmable gate arrays (FPGA). Processor architecture is based on stack processor architecture with three additional stack memory blocks, hash-table and instructions that accelerate execution of parsing operations. We propose hardware-software FPGA-based system, which has main processor and tens to hundreds of SM16 executive processor elements. This system efficiently processes XML-documents and can be easily reconfiguration to process documents with different grammars.

KEYWORDS

XML, parser, stack processor, grammar, stack automaton.

REFERENCES

  1. Head, M.R., Govindaraju, M., van Engelen, R. and Zhang, W. (2006), “Benchmarking XML processors for applications in grid Web services”, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, available at: https://www.doi.org/1109/ SC.2006.14 (accessed: 1 January 2020).
    https://doi.org/10.1109/SC.2006.14
  2. Driscoll, D. and Mensch, A. (2009), “Devices profile for web services version 1.1”, available at: http://docs.oasis-open.org/ws-dd/dpws/wsdd-dpws-1.1-spec.html (accessed 9 November 2019).
  3. Schneider, J. and Kamiya, T. (2011), “Efficient XML Interchange (EXI) Format 1.0”, available at: http://www.w3.org/TR/exi/ (accessed 9 November 2019).
  4. Apparao, P. and Bhat, M. (2004), “A detailed look at the characteristics of XML parsing”, BEACON-1: 1st Workshop on Building Block Engine Architectures for Computers and Networks.
  5. Mattias, N. and Jasmi, J. (2003), “XML Parsing: A Threat to Database Performance”, Proceedings of the 20th International Conference on Information and Knowledge Management CIKM '03, pp. 175-178.
  6. (2002), “SAX Parsing Model”, available at: http://sax.sourceforge.net (accessed 11 November 2019).
  7. W3C. (2000), “Document object model (DOM) level 2 core specification”, available at: http://www.w3.org/TR/DOM-Level-2-Core (accessed 11 November 2019).
  8. Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Lueding, C., Tison, S. and Tommasi, M. (2008), “Tree Automata Techniques and Applications”, available at: http://tata.gforge.inria.fr/ (accessed 11 November 2019).
  9. Murata, M., Lee, D., Mani, M. and Kawaguchi, K. (2005), “Taxonomy of XML schema languages using  formal language  theory”,  ACM  Transactions  on  Internet  Technology, Vol. 5, Iss. 4, pp. 660-704.
    https://doi.org/10.1145/1111627.1111631
  10. (1999), “XML Path Language Version 1.0”, available at: http://www.w3.org/TR/ xpath (accessed 11 November 2019).
  11. Chiu K., Devadithya T., Lu W. and Slominski A. (2005), “A binary XML for scientific applications”, Proceedings of the IEEE 1st International Conference on e-Science and Grid Computing (e-Science'05), pp. 336-343.
    https://doi.org/10.1109/E-SCIENCE.2005.1
  12. Lu, W., Chiu, K. and Pan, Y. (2006), “A Parallel Approach to XML Parsing”, Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, pp. 223-230.
    https://doi.org/10.1109/ICGRID.2006.311019
  13. Head, M.R. and Govindaraju, M. (2007), “Approaching a Parallelized XML Parser Optimized for Multi-Core Processor”, Proceedings of the 2007 Workshop on Service-Oriented Computing Performance: Aspects Issues and Approaches (SOCP’07), pp. 17-22.
    https://doi.org/10.1145/1272457.1272460
  14. Altinel, M. and Franklin, M.J. (2000), “Efficient Filtering of XML Documents for Selective Dissemination of Information”, Proceedings of the 26th International Conference on Very Large Data Bases (VLDB’00), pp. 53-64.
  15. Diao, Y., Altinel, M., Franklin, M.J., Zhang, H. and Fischer, P. (2003), “Path sharing and predicate evaluation for high-performance XML filtering”, ACM Trans. on Database Systems (TODS), Vol. 28, pp. 467-516.
    https://doi.org/10.1145/958942.958947
  16. Green, T. J., Gupta, A., Miklau, G., Onizuka, M. and Suciu, D. (2004), “Processing XML streams with deterministic automata and stream indexes”, ACM Trans.on Database Systems (TODS), pp. 752-788.
    https://doi.org/10.1145/1042046.1042051
  17. Silvasti, P. (2008), “XML-Document-Filtering Automaton”, Proceedings of the Very Large Data Base Endowment (VLDB Endowment '08), Vol. 1, Iss. 2, pp. 1666-1671.
    https://doi.org/10.14778/1454159.1454245
  18. Lunteren, J.V., Engbersen, T., Bostian, J., Carey, B. and Larsson, C. (2004), “XML accelerator engine”, Proceeding of the 1st International Workshop on High Performance XML, available at: http://wam.irialpes.fr/www-workshop2004/ZuXA_final_paper.pdf (accessed 1 January 2020).
  19. El-Hassan, F. and Ionescu, D. (2009), “SCBXP: An efficient hardware-based XML parsing technique”, Proceeding of the 5th Southern Conference on Programmable Logic (SPL), pp. 45-50.
    https://doi.org/10.1109/SPL.2009.4914917
  20. Mueller, R., Teubner, J. and Alonso, G. (2009), “Streams on wires — a query compiler for FPGAs”, Proceedings of the Very Large Data Base Endowment (VLDB Endowment '09), Vol. 1, Iss. 2, pp. 229-240.
    https://doi.org/10.14778/1687627.1687654
  21. Moussalli, R., Salloum, M., Najjar, W. and Tsotras, V. (2011), “Massively Parallel XML Twig Filtering Using Dynamic Programming on FPGAs”, Proceedings of the IEEE 27th International Conference on Data Engineering (ICDE’11), pp. 948-959.
    https://doi.org/10.1109/ICDE.2011.5767899
  22. Mitra, A., Vieira, M., Bakalov, P., Najjar, W. and Tsotras, V. (2009), “Boosting XML Filtering with a Scalable FPGA-based Architecture”, Proceedings of the CIDR 2009 - 4th Biennal Conference on Innovative Data Systems Research, available at: https://arxiv.org/abs/0909.1781 (accessed: 1 January 2020).
  23. Teubner, J., Woods, L. and Nie, C. (2013), “XLynx — an FPGA-based XML filter for hybrid XQuery processing”, ACM Transactions on Database Systems (TODS), Vol. 38, Iss. 4.
    https://doi.org/10.1145/2536800
  24. Woods, L., Alonso, G. and Teubner, J. (2015), “Parallelizing data processing on FPGAs with shifter lists”, ACM Transactions on Reconfigurable Technology and Systems (TRETS) - Special Section on FPL 2013, Vol. 8, Iss. 2.
    https://doi.org/10.1145/2629551
  25. Letz, S., Zedler, M., Thierer, T., Schutz, M., Roth, J. and Seiffert, R. (2006), “XML offload and acceleration with Cell broadband engine”, XTech: Building Web 2.0, available at: https://doi.org/10.1007/978-3-642-11515-8_12 (accessed: 1 January 2020).
  26. Moussalli, R., Halstead, R., Solloum, M., Najjar, W. and Tsotras, V. (2011), “Efficient XML Path Filtering Using GPUs”, Proceedings of the 2nd International Workshop on Accelerating Data Management Systems (ADMS 2011), available at: https://www.net/publication/257631377_Efficient_XML_Path_Filtering_Using_GPUs (accessed: 1 January 2020).
  27. Fischer, P. and Teubner, J. (2012), “MXQuery with hardware acceleration”, Proceedings of the IEEE 28th International Conference on Data Engineering (ICDE), pp. 1293-1296.
    https://doi.org/10.1109/ICDE.2012.130
  28. Koopman, P. (1989), Stack computers: the new wave, Ellis Horwood, Mountain View Press.
  29. Paysan, B. (2006), “b16-small — Less is More”, Proceedings of the EuroForth 2004, pp. 1-8.
  30. Bowman, J. and Garage, W. (2010), “J1: a small Forth CPU Core for FPGAs”, Proceedings of the EuroForth’2010, pp. 1-4.
  31. Kale, V. (2016), “Using the MicroBlaze Processor to Accelerate Cost-Sensitive Embedded System Development”, Xilinx, WP469 (v1.0.1), available at: https://www.xilinx.com/ products/design-tools/microblaze.html#documentation (accessed 11 November 2019).
  32. Sergiyenko, A., Molchanov, O. and Orlova, M. (2019), “Nano-Processor for the Small Tasks”, Proceeding of the 39th 2019 IEEE International Conference on Electronics and Nanotechnology (ELNANO), pp. 674-677.
    https://doi.org/10.1109/ELNANO.2019.8783555
  33. Girard, O. (2013), “OpenMSP430”, OpenCores, Rev. 1.13, available at: http:// org (accessed 11 November 2019).
  34. Molchanov, O., Orlova, M. and Sergiyenko, A. (2020), “Software/Hardware Co-design of the Microprocessor for the Serial Port Communications”, Springer, pp. 238-246.
    https://doi.org/10.1007/978-3-030-16621-2_22
  35. Altmann, V., Skodzik, J., Danielis, P., Van, N.P., Golatowski, F. and Timmermann, D. (2014), “Real-Time Capable Hardware-based Parser for Efficient XML Interchange”, Proceedings of the 9th International Symposium on Communication Systems, Networks & Digital Sign (CSNDSP), pp. 415-420.
    https://doi.org/10.1109/CSNDSP.2014.6923861

Full text: PDF