Top

The Journal of Supercomputing

Published in:

20-06-2018

Hardware-aided update acceleration in a hybrid Semantic Web database system

Authors: Dennis Heinrich, Stefan Werner, Christopher Blochwitz, Thilo Pionteck, Sven Groppe

Published in: The Journal of Supercomputing | Issue 10/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we focus on update optimizations in a Semantic Web database system aided by a field programmable gate array (FPGA). Many databases utilize B\(^+\)-tree index structures for querying data. In this scenario, the B\(^+\)-tree levels are distributed between the host system with the lower inner levels including the leaves and the FPGA with the upper inner levels including the root. In this way we can perform a parallel search inside the nodes of the FPGA by exploiting its parallel nature. Since update operations presuppose a search for the correct position inside a B\(^+\)-tree leaf, these operations can benefit from these parallel searches. We present our scheduler ideas to estimate the expected benefit against the setup of the system and further adjustments made necessary by performed updates. In a best, average and worst-case scenario, we show how our scheduler would calculate the possible acceleration of such a system.

previous article An emulation scheme for OpenGL SC 2.0 over OpenGL

next article Efficient processing of recommendation algorithms on a single-machine-based graph engine

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Bayer R, McCreight E (1970) Organization and maintenance of large ordered indices. In: Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, ACM, New York, NY, USA, SIGFIDET ’70, pp 107–141. https://doi.org/10.1145/1734663.1734671

Berners-Lee T (1989) Information Management: A Proposal. [Online] https://www.w3.org/History/1989/proposal.html. Accessed 19 Jun 2018

Berners-Lee T, Hendler J, Lassila O (May 2001) “The semantic web”. In: Scientific American, pp 29–37

Blochwitz C, Joseph JM, Pionteck T, Backasch R, Werner S, Heinrich D, Groppe S (2015) An optimized radix-tree for hardware-accelerated index generation for Semantic Web Databases. In: International Conference on ReConFigurable Computing and FPGAs (ReConFig), Cancun, Mexico

Casper J, Olukotun K (2014) Hardware acceleration of database operations. In: Proceedings of the 2014 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, ACM, New York, NY, USA, FPGA ’14, pp 151–160. https://doi.org/10.1145/2554688.2554787

Cheng X, He B, Lau CT (2015) Energy-efficient query processing on embedded CPU–GPU architectures. In: Proceedings of the 11th International Workshop on Data Management on New Hardware, ACM, New York, NY, USA, DaMoN’15, pp 10:1–10:7. https://doi.org/10.1145/2771937.2771939

Comer D (1979) Ubiquitous B-tree. ACM Comput Surv 11(2):121–137. https://doi.org/10.1145/356770.356776MathSciNetCrossRefMATH

Dell (2015) Product website. [Online] http://www.dell.com/de/unternehmen/p/precision-t3610-workstation/pd. Accessed 19 Jun 2018

DeWitt DJ (1978) Direct—a multiprocessor organization for supporting relational data base management systems. In: Proceedings of the 5th Annual Symposium on Computer Architecture, ACM, New York, NY, USA, ISCA ’78, pp 182–189. https://doi.org/10.1145/800094.803046

10.

Do J, Kee YS, Patel JM, Park C, Park K, DeWitt DJ (2013) Query processing on smart SSDs: Opportunities and challenges. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, USA, SIGMOD ’13, pp 1221–1230. https://doi.org/10.1145/2463676.2465295

11.

Fang W, He B, Luo Q (2010) Database compression on graphics processors. Proc VLDB Endow 3(1–2):670–680. https://doi.org/10.14778/1920841.1920927CrossRef

12.

Francisco P (2010) IBM PureData System for Analytics Architecture: A Platform for High Performance Data Warehousing and Analytics. http://www.redbooks.ibm.com/redpapers/pdfs/redp4725.pdf. Accessed 19 Jun 2018

13.

Govindaraju N, Gray J, Kumar R, Manocha D (2006) GPUTeraSort: high performance graphics co-processor sorting for large database management. In: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, USA, SIGMOD ’06, pp 325–336. https://doi.org/10.1145/1142473.1142511

14.

Groppe S (2011) Data Management and Query Processing in Semantic Web Databases, 2011th edn. Springer. http://amazon.com/o/ASIN/3642193560/. Accessed 19 Jun 2018

15.

Groppe S (2013) LUPOSDATE Open Source. [Online] https://github.com/luposdate. Accessed 19 Jun 2018

16.

He B, Yu JX (2011) High-throughput transaction executions on graphics processors. Proc VLDB Endow 4(5):314–325. https://doi.org/10.14778/1952376.1952381CrossRef

17.

He B, Yang K, Fang R, Lu M, Govindaraju N, Luo Q, Sander P (2008) Relational joins on graphics processors. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, USA, SIGMOD ’08, pp 511–524. https://doi.org/10.1145/1376616.1376670

18.

He B, Lu M, Yang K, Fang R, Govindaraju NK, Luo Q, Sander PV (2009) Relational query coprocessing on graphics processors. ACM Trans Database Syst 34(4):21:1–21:39. https://doi.org/10.1145/1620585.1620588CrossRef

19.

He J, Zhang S, He B (2014) In-cache query co-processing on coupled CPU–GPU architectures. Proc VLDB Endow 8(4):329–340. https://doi.org/10.14778/2735496.2735497CrossRef

20.

Heinrich D, Werner S, Stelzner M, Blochwitz C, Pionteck T, Groppe S (2015) Hybrid FPGA approach for a B+ tree in a semantic web database system. In: 2015 10th International Symposium on Reconfigurable Communication-Centric Systems-on-Chip (ReCoSoC), pp 1–8. https://doi.org/10.1109/ReCoSoC.2015.7238093

21.

Heinrich D, Werner S, Blochwitz C, Pionteck T, Groppe S (2017) Search and update optimization of a B+ tree in a hardware aided semantic web database system. In: Proceedings of the 7th International Conference on Emerging Databases (EDB)

22.

IBM (2015) Website. [online] http://www.ibm.com. Accessed 19 Jun 2018

23.

Kang Y, Kee Y, Miller EL, Park C (2013) Enabling cost-effective data processing with smart SSD. In: 2013 IEEE 29th Symposium on Mass Storage Systems and Technologies (MSST), pp 1–12. https://doi.org/10.1109/MSST.2013.6558444

24.

Lee CY (1961) An algorithm for path connections and its applications. IRE Trans Electron Comput EC–10(3):346–365. https://doi.org/10.1109/TEC.1961.5219222MathSciNetCrossRef

25.

Lee SW, Moon B, Park C (2009) Advances in flash memory SSD technology for enterprise database applications. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, USA, SIGMOD ’09, pp 863–870. https://doi.org/10.1145/1559845.1559937

26.

Manegold S, Boncz AP, Kersten LM (2000) Optimizing database architecture for the new bottleneck: memory access. VLDB J 9(3):231–246. https://doi.org/10.1007/s007780000031CrossRefMATH

27.

Moore E (1959) The Shortest Path Through a Maze. Bell Telephone System. Technical Publications. Monograph, Bell Telephone System

28.

Mueller R, Teubner J (2009) FPGA: What’s in it for a database? In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, USA, SIGMOD ’09, pp 999–1004. https://doi.org/10.1145/1559845.1559965

29.

Mueller R, Teubner J (2010) FPGAs: a new point in the database design space. In: Proceedings of the 13th International Conference on Extending Database Technology, ACM, New York, NY, USA, EDBT ’10, pp 721–723. https://doi.org/10.1145/1739041.1739137

30.

Mueller R, Teubner J, Alonso G (2009a) Data processing on FPGAs. Proc VLDB Endow 2(1):910–921. https://doi.org/10.14778/1687627.1687730CrossRef

31.

Mueller R, Teubner J, Alonso G (2009b) Streams on wires: a query compiler for FPGAs. Proc VLDB Endow 2(1):229–240. https://doi.org/10.14778/1687627.1687654CrossRef

32.

Mueller R, Teubner J, Alonso G (2010) Glacier: a query-to-hardware compiler. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, USA, SIGMOD ’10, pp 1159–1162. https://doi.org/10.1145/1807167.1807307

33.

Mueller R, Teubner J, Alonso G (2012) Sorting networks on FPGAs. VLDB J 21(1):1–23. https://doi.org/10.1007/s00778-011-0232-zCrossRef

34.

Neumann T, Weikum G (2008) RDF-3X: a RISC-style engine for RDF. Proc VLDB Endow 1(1):647–659. https://doi.org/10.14778/1453856.1453927CrossRef

35.

Plessl C (2012) Accelerating Scientific Computing with Massively Parallel Computer Architectures. http://www.imprs-dynamics.mpg.de/pdfs/Plessl_talk.pdf. Accessed 19 Jun 2018

36.

Rao J, Ross KA (1999) Cache conscious indexing for decision-support in main memory. In: Proceedings of the 25th International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, VLDB ’99, pp 78–89. http://dl.acm.org/citation.cfm?id=645925.671362. Accessed 19 Jun 2018

37.

Rao J, Ross KA (2000) Making B+-trees cache conscious in main memory. SIGMOD Rec 29(2):475–486. https://doi.org/10.1145/335191.335449CrossRef

38.

Seshadri S, Gahagan M, Bhaskaran S, Bunker T, De A, Jin Y, Liu Y, Swanson S (2014) Willow: a user-programmable SSD. In: Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, USENIX Association, Berkeley, CA, USA, OSDI’14, pp 67–80. http://dl.acm.org/citation.cfm?id=2685048.2685055

39.

Torp K, Mark L, Jensen CS (1998) Efficient differential timeslice computation. IEEE Trans Knowl Data Eng 10(4):599–611. https://doi.org/10.1109/69.706059CrossRef

40.

(W3C) WWWC (2014) RDF 1.1 concepts and abstract syntax. W3C Recommendation. [Online] https://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/. Accessed 19 Jun 2018

41.

Weiss C, Karras P, Bernstein A (2008) Hexastore: sextuple indexing for semantic web data management. Proc VLDB Endow 1(1):1008–1019. https://doi.org/10.14778/1453856.1453965CrossRef

42.

Werner S, Heinrich D, Groppe S, Blochwitz C, Pionteck T (2016) Runtime adaptive hybrid query engine based on fpgas. Open J Databases (OJDB) 3(1):21–41. http://www.ronpub.com/publications/OJDB_2016v3i1n02_Werner.pdf

43.

World Wide Web Consortium (W3C) (2013) SPARQL 1.1 Overview. http://www.w3.org/TR/sparql11-overview/. Accessed 19 Jun 2018

44.

Xilinx (2012) Data sheet virtex family. [online] http://www.xilinx.com/support/documentation/data_sheets/ds150.pdf. Accessed 19 Jun 2018

45.

Zuse K (1972) Der Plankalkül. Berichte der Gesellschaft für Mathematik und Datenverarbeitung, Gesellschaft für Mathematik und Datenverarbeitung

Title: Hardware-aided update acceleration in a hybrid Semantic Web database system
Authors: Dennis Heinrich
Stefan Werner
Christopher Blochwitz
Thilo Pionteck
Sven Groppe
Publication date: 20-06-2018
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 10/2020
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-018-2462-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 10/2020

Comparative studies on machine learning for paralinguistic signal compression and classification

Power saving with CoMP transmission for densely deployed small cell networks

Discovery of topic flows of authors

Dynamic cooperative caching strategy for delay-sensitive applications in edge computing environment

An emulation scheme for OpenGL SC 2.0 over OpenGL

Pseudo-random number generation using LSTMs

Premium Partner