Source author record

Miguel Areias

Miguel Areias appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Programming Languages Logic in Computer Science

Catalog footprint

What is connected

3works

2topics

1close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2014arXiv

A Simple and Efficient Lock-Free Hash Trie Design for Concurrent Tabling

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.

preprint2012arXiv

Towards Multi-Threaded Local Tabling Using a Common Table Space

Multi-threading is currently supported by several well-known Prolog systems providing a highly portable solution for applications that can benefit from concurrency. When multi-threading is combined with tabling, we can exploit the power of higher procedural control and declarative semantics. However, despite the availability of both threads and tabling in some Prolog systems, the implementation of these two features implies complex ties to each other and to the underlying engine. Until now, XSB was the only Prolog system combining multi-threading with tabling. In XSB, tables may be either private or shared between threads. While thread-private tables are easier to implement, shared tables have all the associated issues of locking, synchronization and potential deadlocks. In this paper, we propose an alternative view to XSB's approach. In our proposal, each thread views its tables as private but, at the engine level, we use a common table space where tables are shared among all threads. We present three designs for our common table space approach: No-Sharing (NS) (similar to XSB's private tables), Subgoal-Sharing (SS) and Full-Sharing (FS). The primary goal of this work was to reduce the memory usage for the table space but, our experimental results, using the YapTab tabling system with a local evaluation strategy, show that we can also achieve significant reductions on running time.

preprint2011arXiv

On Combining Linear-Based Strategies for Tabled Evaluation of Logic Programs

Tabled evaluation is a recognized and powerful technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant sub-computations. We can distinguish two main categories of tabling mechanisms: suspension-based tabling and linear tabling. While suspension-based mechanisms are considered to obtain better results in general, they have more memory space requirements and are more complex and harder to implement than linear tabling mechanisms. Arguably, the SLDT and DRA strategies are the two most successful extensions to standard linear tabled evaluation. In this work, we propose a new strategy, named DRS, and we present a framework, on top of the Yap system, that supports the combination of all these three strategies. Our implementation shares the underlying execution environment and most of the data structures used to implement tabling in Yap. We thus argue that all these common features allows us to make a first and fair comparison between these different linear tabling strategies and, therefore, better understand the advantages and weaknesses of each, when used solely or combined with the others.