A Simple and Efficient Lock-Free Hash Trie Design for Concurrent Tabling
Miguel Areias and Ricardo Rocha
July 2014
Abstract
A critical component in the implementation of a concurrent tabling
system is the design of the table space. One of the most successful
proposals for representing tables is based on a two-level trie data
structure, where one trie level stores the tabled subgoal calls and
the other stores the computed answers. In this work, we present a
simple and efficient lock-free design where both levels of the tries
can be shared among threads in a concurrent environment. To implement
lock-freedom we took advantage of the CAS atomic instruction that
nowadays can be widely found on many common architectures. CAS reduces
the granularity of the synchronization when threads access concurrent
areas, but still suffers from low-level problems such as false sharing
or cache memory side-effects. In order to be as effective as possible
in the concurrent search and insert operations over the table space
data structures, we based our design on a hash trie data structure in
such a way that it minimizes potential low-level synchronization
problems by dispersing as much as possible the concurrent
areas. Experimental results in the Yap Prolog system show that our new
lock-free hash trie design can effectively reduce the execution time
and scale better than previous designs.
Bibtex
@InProceedings{areias-iclp14,
author = {M. Areias and R. Rocha},
title = {{A Simple and Efficient Lock-Free Hash Trie Design for Concurrent Tabling}},
booktitle = {Technical Communications of the 30th International Conference on Logic Programming (ICLP 2014)},
editor = {M. Leuschel and T. Schrijvers},
month = {July},
year = {2014},
address = {Vienna, Austria},
}
Download Paper
PDF file
Computing Research Repository (CoRR)