Hardwarebeschleunigung von Semantic Web Datenbanken durch dynamisch rekonfigurierbare FPGAs

Funded by:

  • DFG

Runtime:

  • 2013 - 2015

Project Coordinator:

Research Associate:

  • Dennis Heinrich, M.Sc.

Motivation

The importance of the Semantic Web has steadily increased in recent years. Evidence of this includes, among other things, the increasing number of Semantic Web tools and applications developed and in use.

The core idea of ​​the Semantic Web is to make machine processing more precise by including the meaning of symbols. The required linking of different data sets is carried out using database systems. With the constantly growing size of databases, classic database systems, but also specially adapted Semantic Web database systems, are increasingly reaching their limits. Especially in the area of ​​Semantic Web databases, there are now data sets with billions of entries, which are very time-consuming to process using purely software-based solutions.

Goals and Procedure

As part of this project, a hardware/software system is to be researched and developed that outsources time-consuming operations to a programmable logic component (FPGA, Field Programmable Gate Array). The cost-intensive operations intended for hardware acceleration include both the individual steps of index creation and the actual query processing for Semantic Web databases. The functions to be outsourced to the FPGA during query processing are determined at runtime. In order to be able to provide an optimal hardware accelerator depending on the request, corresponding data paths are built from basic elements using partial dynamic reconfiguration of the FPGA at runtime.

Innovation and Prospects

The innovation of this project includes new approaches and methods for hardware-acceleration of Semantic Web databases by utilizing the unique features of FPGAs.

Project Partners

  • Institute of Information Systems (IFIS), University of Lübeck
  • Institute of Conmputer Engineering (ITI), University of Lübeck

Link to Project Details

Dissertation

Dennis Heinrich:
Parallel Execution Approaches on Data and Index Structures in the Context of Semantic Web Database Management Systems
eingereicht Mai 2018, angenommen 06. Juni 2018, mündl. Prüfung am 19.09.2018 (Doktorvater: Groppe), Thesis

Publications

2020

Dennis Heinrich, Stefan Werner, Christopher Blochwitz, Thilo Pionteck, and Sven Groppe,
Hardware-aided update acceleration in a hybrid Semantic Web database system, The Journal of Supercomputing , vol. 76, no. 10, pp. 7961--7984, 2020.
Datei: s11227-018-2462-y
Bibtex: BibTeX
@article{heinrich20hardware,
  author    = {Dennis Heinrich and Stefan Werner and Christopher Blochwitz and Thilo Pionteck and Sven Groppe},
  title     = {Hardware-aided update acceleration in a hybrid Semantic Web database system},
  journal   = {The Journal of Supercomputing},
  volume    = {76},
  number    = {10},
  pages     = {7961--7984},
  year      = {2020},
  url       = {https://doi.org/10.1007/s11227-018-2462-y}
}

2018

Christopher Blochwitz, Julian Wolff, Mladen Berekovic, Dennis Heinrich, Sven Groppe, Jan Moritz Joseph, and Thilo Pionteck,
Hardware-Accelerated Index Construction for Semantic Web, in International Conference on Field-Programmable Technology ({FPT}), Naha, Okinawa, Japan , 2018. pp. 278--281.
DOI:10.1109/FPT.2018.00053
Datei: FPT.2018.00053
Bibtex: BibTeX
@inproceedings{Blochwitz2018_15,
	title = {Hardware-Accelerated Index Construction for Semantic Web},
	author = {Christopher Blochwitz and Julian Wolff and Mladen Berekovic and Dennis Heinrich and Sven Groppe and Jan Moritz Joseph and Thilo Pionteck},
	booktitle = {International Conference on Field-Programmable Technology ({FPT}),
               Naha, Okinawa, Japan},
	year = {2018},
	url = {https://doi.org/10.1109/FPT.2018.00053}
}

2017

Christopher Blochwitz, Julian Wolff, Jan Moritz Joseph, Stefan Werner, Dennis Heinrich, Sven Groppe, and Thilo Pionteck,
Hardware-Accelerated Radix-Tree Based String Sorting for Big Data Applications, in 30th International Conference on Architecture of Computing Systems ({ARCS}), Vienna, Austria , 2017. pp. 47--58.
DOI:10.1007/978-3-319-54999-6\_4
Datei: 978-3-319-54999-6\_4
Dennis Heinrich, Stefan Werner, Christopher Blochwitz, Thilo Pionteck, and Sven Groppe,
Search \& 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), Busan, Korea , Springer, 2017.
Datei: 978-981-10-6520-0_18
Stefan Werner, Dennis Heinrich, Thilo Pionteck, and Sven Groppe,
Semi-static operator graphs for accelerated query execution on FPGAs, Microprocessors and Microsystems - Embedded Hardware Design , vol. 53, pp. 178--189, 2017.
DOI:10.1016/j.micpro.2017.07.010
Datei: j.micpro.2017.07.010

2016

Stefan Werner, Dennis Heinrich, Marc Stelzner, Volker Linnemann, Thilo Pionteck, and Sven Groppe,
Accelerated join evaluation in Semantic Web databases by using FPGAs, Concurrency and Computation: Practice and Experience , vol. 28, no. 7, pp. 2031--2051, 2016.
DOI:10.1002/cpe.3502
Datei: cpe.3502
Bibtex: BibTeX
@ARTICLE{Werner2015,
  author = {Stefan Werner and Dennis Heinrich and Marc Stelzner and Volker Linnemann
	and Thilo Pionteck and Sven Groppe},
  title = {Accelerated join evaluation in Semantic Web databases by using FPGAs},
  journal = {Concurrency and Computation: Practice and Experience},
   year = {2015},
  volume =    {28},
  number =    {7},
  pages =     {2031--2051},
  month = {May 18},
  doi = {http://dx.doi.org/10.1002/cpe.3502}
}
Sven Groppe, Dennis Heinrich, Christopher Blochwitz, and Thilo Pionteck,
Constructing Large-Scale Semantic Web Indices for the Six {RDF} Collation Orders, OJBD , vol. 2, no. 1, pp. 11--25, 2016.
Datei: urn:nbn:de:101:1-201705194418
Stefan Werner, Dennis Heinrich, Sven Groppe, Christopher Blochwitz, and Thilo Pionteck,
Runtime Adaptive Hybrid Query Engine based on FPGAs, OJDB , vol. 3, no. 1, pp. 21--41, 2016. RonPub.
Datei: urn:nbn:de:101:1-201705194645
Bibtex: BibTeX
@Article{OJDB_2016v3i1n02_Werner,
        author    = {Stefan Werner and Dennis Heinrich and Sven Groppe and Christopher Blochwitz and Thilo Pionteck},
        title     = {Runtime Adaptive Hybrid Query Engine based on FPGAs},
        journal   = {Open Journal of Databases (OJDB)},
        issn      = {2199-3459},
        year      = {2016},
        volume    = {3},
        number    = {1},
        pages     = {21--41},
        url       = {http://www.ronpub.com/publications/OJDB_2016v3i1n02_Werner.pdf},
        publisher = {RonPub},
        bibsource = {RonPub},
        abstract = {This paper presents the fully integrated hardware-accelerated query engine for large-scale datasets in the context of Semantic Web databases. As queries are typically unknown at design time, a static approach is not feasible and not flexible to cover a wide range of queries at system runtime. Therefore, we introduce a runtime reconfigurable accelerator based on a Field Programmable Gate Array (FPGA), which transparently incorporates with the freely available Semantic Web database LUPOSDATE. At system runtime, the proposed approach dynamically generates an optimized hardware accelerator in terms of an FPGA configuration for each individual query and transparently retrieves the query result to be displayed to the user. During hardware-accelerated execution the host supplies triple data to the FPGA and retrieves the results from the FPGA via PCIe interface. The benefits and limitations are evaluated on large-scale synthetic datasets with up to 260 million triples as well as the widely known Billion Triples Challenge.}
    }

2015

Dennis Heinrich, Stefan Werner, Marc Stelzner, Christopher Blochwitz, Thilo Pionteck, and Sven Groppe,
Hybrid FPGA approach for a B+ tree in a Semantic Web database system, in 10th International Symposium on Reconfigurable Communication-centric Systems-on-Chip (ReCoSoC), Bremen, Germany , 2015. pp. 1--8.
DOI:10.1109/ReCoSoC.2015.7238093
Datei: ReCoSoC.2015.7238093
Sven Groppe, Dennis Heinrich, Stefan Werner, Christopher Blochwitz, and Thilo Pionteck,
PatTrieSort - External String Sorting based on Patricia Tries, OJDB , vol. 2, no. 1, pp. 36--50, 2015.
Datei: urn:nbn:de:101:1-201705194627
Christopher Blochwitz, Jan Moritz Joseph, Thilo Pionteck, Rico Backasch, Stefan Werner, and Dennis Heinrich,
{An optimized Radix-Tree for hardware-accelerated index generation for Semantic Web Databases}, in International Conference on ReConFigurable Computing and FPGAs (ReConFig) , Cancun, Mexico , 2015.
Bibtex: BibTeX
@INPROCEEDINGS{Blochwitz2015,
  author = {Christopher Blochwitz and Jan Moritz Joseph and Thilo Pionteck and
	Rico Backasch and  Stefan Werner and Dennis Heinrich and Sven Groppe},
  title = {{An optimized Radix-Tree for hardware-accelerated index generation
	for Semantic Web Databases}},
  booktitle = {International Conference on ReConFigurable Computing and FPGAs (ReConFig)},
  year = {2015},
  address = {Cancun, Mexico},
  month = {December 7 - 9},
  owner = {werner},
  timestamp = {2016.01.26}
}
Sven Groppe, Dennis Heinrich, and Stefan Werner,
Distributed Join Approaches for W3C-Conform {SPARQL} Endpoints, OJSW , vol. 2, no. 1, pp. 30--52, 2015.
Datei: urn:nbn:de:101:1-201705194910
Stefan Werner, Dennis Heinrich, Jannik Piper, Sven Groppe, Rico Backasch, Christopher Blochwitz, and Thilo Pionteck,
Automated composition and execution of hardware-accelerated operator graphs, in 10th International Symposium on Reconfigurable Communication-centric Systems-on-Chip (ReCoSoC), Bremen, Germany , 2015. pp. 1--8.
DOI:10.1109/ReCoSoC.2015.7238078
Datei: ReCoSoC.2015.7238078
Christopher Blochwitz, Jan Moritz Joseph, Rico Backasch, Thilo Pionteck, Stefan Werner, Dennis Heinrich, and Sven Groppe,
An optimized radix-tree for hardware-accelerated dictionary generation for semantic web databases, in International Conference on ReConFigurable Computing and FPGAs (ReConFig), Riviera Maya, Mexico , 2015. pp. 1--7.
DOI:10.1109/ReConFig.2015.7393291
Datei: ReConFig.2015.7393291

2014

Sven Groppe, Johannes Blume, Dennis Heinrich, and Stefan Werner,
A Self-Optimizing Cloud Computing System for Distributed Storage and Processing of Semantic Web Data, OJCC , vol. 1, no. 2, pp. 1--14, 2014.
Datei: urn:nbn:de:101:1-201705194478
Sven Groppe, Thomas Kiencke, Stefan Werner, Dennis Heinrich, Marc Stelzner, and Le Gruenwald,
P-LUPOSDATE: Using Precomputed Bloom Filters to Speed Up SPARQL Processing in the Cloud, OJSW , vol. 1, no. 2, pp. 25--55, 2014.
Datei: urn:nbn:de:101:1-201705194858
Stefan Werner, Dennis Heinrich, Marc Stelzner, Sven Groppe, Rico Backasch, and Thilo Pionteck,
Parallel and Pipelined Filter Operator for Hardware-Accelerated Operator Graphs in Semantic Web Databases, in 14th IEEE International Conference on Computer and Information Technology (CIT), Xi'an, China , 2014. pp. 539--546.
DOI:10.1109/CIT.2014.162
Datei: CIT.2014.162