A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs

• Type: Article in International Scientific Journal
• Date: 2016

Authors

Miguel Areias (Author) FCUP; Ricardo Rocha (Author) FCUP

Journal

Title: International Journal of Parallel Programming

Vol. 44

Pages: 386-406

ISSN: 0885-7458

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 8 Citations

Scopus - 9 Citations

Other information

Authenticus ID: P-00F-YAG

DOI: 10.1007/s10766-014-0346-1

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 21