PPoPP 2019
Sat 16 - Wed 20 February 2019 Washington, DC, United States
Wed 20 Feb 2019 10:00 - 10:25 at Salon 12/13 - Session 9: Synchronization Chair(s): Erez Petrank

Modern Datalog engines are employed in industrial applications such as graph-databases, networks, and static program analysis. To cope with vast amount of data, Datalog engines must employ parallel execution strategies, for which specialized concurrent data structures are of paramount importance.

In this paper, we introduce a specialized B-tree data structure for an open-source Datalog compiler written in C++. Our data structure has been specialized for Datalog workloads running on shared-memory multi-core computers. It features (1) an optimistic locking protocol for scalability, (2) is highly tuned, and (3) uses the notion of ``hints'' to re-use the results of previously performed tree traversals to exploit data ordering properties exhibited by Datalog evaluation. In parallel micro-benchmarks, the new data structure achieves up to 59x higher performance than state-of-the-art industrial standards, while integrated into a Datalog engine it accounts for 3x higher, overall system performance.

Wed 20 Feb (GMT-05:00) Guadalajara, Mexico City, Monterrey change

09:35 - 10:50: Main Conference - Session 9: Synchronization at Salon 12/13
Chair(s): Erez PetrankTechnion
PPoPP-2019-papers09:35 - 10:00
Martin BättigDepartment of Computer Science, ETH Zurich, Thomas GrossETH Zurich
PPoPP-2019-papers10:00 - 10:25
Herbert JordanUniversity of Innsbruck, Pavle SuboticUniversity College London, David ZhaoThe University of Sydney, Bernhard ScholzUniversity of Sydney, Australia
PPoPP-2019-papers10:25 - 10:50
Robert UtterbackMonmouth College, Kunal AgrawalWashington University in St. Louis, Jeremy Fineman, I-Ting Angelina LeeWashington University in St. Louis