On the correctness and efficiency of lock-free expandable tries for tabled logic programs

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2014

Autores

Areias, M (Autor) Outra; Rocha, R (Autor) FCUP

Ata de Conferência Internacional

Título: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Páginas: 168-183

15th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2014

San Diego, CA, 20 January 2014 through 21 January 2014

Indexação

ISI Web of Knowledge

Scopus - 7 Citações

Outras Informações

ID Authenticus: P-008-KJS

DOI: 10.1007/978-3-319-04132-2_12

Abstract (EN): Tabling is an implementation technique that improves the declarativeness and expressiveness of Prolog in dealing with recursion and redundant sub-computations. A critical component in the implementation of an efficient tabling framework is the design of the data structures and algorithms to access and manipulate tabled data. One of the most successful data structures for tabling is tries. In previous work, our initial approach to deal with concurrent table accesses, implemented on top of the Yap Prolog system, was to use lock-based trie data structures. In this work, we propose a new design based on lock-free data structures and, in particular, we focus our discussion on the correctness and efficiency of extending Yap's tabling framework to support lock-free expandable tries. Experimental results show that our new lock-free design can effectively reduce the execution time and scale better, when increasing the number of threads, than the original lock-based design. © 2014 Springer International Publishing.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 16