2. Головна
  3. АРХІВ НОМЕРІВ
  4. 2020 рік
  5. Том 42, № 1 (2020)
  6. c. 33-50

АППАРАТНО-ПРОГРАММНАЯ ОБРАБОТКА XML-ДОКУМЕНТОВ

А.М. Сергиенко, М.М. Орлова, О.А. Молчанов

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

АНОТАЦІЯ

Рассмотрены существующие алгоритмы и средства обработки XML-документов. Обос­нована необходимость использования высокопроизводительных устройств анализа XML-запросов, способных быстро перенастраиваться на другие грамматики. Разра­бо­тано процессорное ядро SM16, которое эффективно выполняет стековые алгоритмы парсинга XML-документов и реализуется в программируемых логических интегральных схемах (ПЛИС). Процессорное ядро имеет архитектуру стекового процессора, к которому добавлено три блока стековой памяти, хеш-таблица и команды, ускоряющие выполнение операций парсинга. Предложена аппаратно-программная система на основе ПЛИС, имеющая ведущий процессор и от десятков до сотен исполнительных процессорных элементов SM16. Эта система не только эффективно обрабатывает XML-документы, но и быстро перенастраивается на обработку доку­ментов с другими грамматиками.

КЛЮЧОВІ СЛОВА:

XML, парсер, стековый процессор, грамматика, сте­ковый автомат.

СПИСОК ЛІТЕРАТУРИ

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

СЕРГІЄНКО Анатолій Михайлович, д-р техн. наук, професор, професор кафедри обчис­лювальної техніки Національного технічного університету України «Київський полі­технічний інститут ім. Ігоря Сікорського». У 1981 р. закінчив Київський полі­технічний інститут. Область наукових досліджень — цифрова обробка сигналів, архітектура комп'ютерів, високорівневий синтез.

ОРЛОВА Марія Миколаївна, канд. техн. наук, доцент, доцент кафедри системного програмування і спеціалізованих комп'ютерних систем Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського». У 1978 р. закінчила Київський політехнічний інститут. Область наукових досліджень — комп'ютерні мережі, сучасні напрямки розвитку комп'ютерних мереж, мережні інформаційні технології, безпроводові комп'ютерні мережі 5G та 6G.

МОЛЧАНОВ Олексій Андрійович, аспірант кафедри системного програмування і спеціалізованих комп'ютерних систем Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського», котрий закінчив у 2016 р. Область наукових досліджень — архітектура комп'ютерів, компілятори.

Повний текст: PDF