A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs
Miguel Areias and Ricardo Rocha
July 2014
Abstract
Tabling is an implementation technique that improves the
declarativeness and expressiveness of Prolog systems in dealing with
recursion and redundant sub-computations. A critical component in the
design of a concurrent tabling system is the implementation 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 previous work, we have presented a sophisticated
lock-free design where both levels of the tries where shared among
threads in a concurrent environment. To implement lock-freedom we used
the CAS atomic instruction that nowadays is widely found on many
common architectures. CAS reduces the granularity of the
synchronization when threads access concurrent areas, but still
suffers from problems such as false sharing or cache memory
effects. In this work, we present a simpler and efficient lock-free
design based on hash tries that minimizes these problems by dispersing
the concurrent areas as much as possible. Experimental results in the
Yap Prolog system show that our new lock-free design can effectively
reduce the execution time and scales better than previous designs.
Bibtex
@InProceedings{areias-hlpp14,
author = {M. Areias and R. Rocha},
title = {{A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs}},
booktitle = {7th International Symposium on High-level Parallel Programming and Applications (HLPP 2014)},
pages = {259--278},
editor = {C. Grelck},
month = {July},
year = {2014},
address = {Amsterdam, Netherlands},
}
Download Paper
PDF file