Cookies
O website necessita de alguns cookies e outros recursos semelhantes para funcionar. Caso o permita, o INESC TEC irá utilizar cookies para recolher dados sobre as suas visitas, contribuindo, assim, para estatísticas agregadas que permitem melhorar o nosso serviço. Ver mais
Aceitar Rejeitar
  • Menu
Publicações

Publicações por Miguel Gonçalves Areias

2017

Towards an Automated Test Bench Environment for Prolog Systems

Autores
Gonçalves, R; Areias, M; Rocha, R;

Publicação
6th Symposium on Languages, Applications and Technologies, SLATE 2017, June 26-27, 2017, Vila do Conde, Portugal

Abstract
Software testing and benchmarking is a key component of the software development process. Nowadays, a good practice in big software projects is the Continuous Integration (CI) software development technique. The key idea of CI is to let developers integrate their work as they produce it, instead of doing the integration at the end of each software module. In this paper, we extend a previous work on a benchmark suite for the Yap Prolog system and we propose a fully automated test bench environment for Prolog systems, named Yet Another Prolog Test Bench Environment (YAPTBE), aimed to assist developers in the development and CI of Prolog systems. YAPTBE is based on a cloud computing architecture and relies on the Jenkins framework and in a set of new Jenkins plugins to manage the underneath infrastructure. We present the key design and implementation aspects of YAPTBE and show its most important features, such as its graphical user interface and the automated process that builds and runs Prolog systems and benchmarks. © Ricardo Gonçalves, Miguel Areias, and Ricardo Rocha

2016

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

Autores
Areias, M; Rocha, R;

Publicação
INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING

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.

2014

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

Autores
Areias, M; Rocha, R;

Publicação
CoRR

Abstract

2018

Table space designs for implicit and explicit concurrent tabled evaluation

Autores
Areias, M; Rocha, R;

Publicação
THEORY AND PRACTICE OF LOGIC PROGRAMMING

Abstract
One of the main advantages of Prolog is its potential for the implicit exploitation of parallelism and, as a high-level language, Prolog is also often used as a means to explicitly control concurrent tasks. Tabling is a powerful implementation technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant subcomputations. Given these advantages, the question that arises is if tabling has also the potential for the exploitation of concurrency/parallelism. On one hand, tabling still exploits a search space as traditional Prolog but, on the other hand, the concurrent model of tabling is necessarily far more complex, since it also introduces concurrency on the access to the tables. In this paper, we summarize Yap's main contributions to concurrent tabled evaluation and we describe the design and implementation challenges of several alternative table space designs for implicit and explicit concurrent tabled evaluation that represent different tradeoffs between concurrency and memory usage. We also motivate for the advantages of using fixed-size and lock freedata structures, elaborate on the key role that the engine's memory allocator plays on such environments, and discuss how Yap's mode-directed tabling support can be extended to concurrent evaluation. Finally, we present our future perspectives toward an efficient and novel concurrent framework which integrates both implicit and explicit concurrent tabled evaluation in a single Prolog engine.

2019

Multi-dimensional lock-free arrays for multithreaded mode-directed tabling in Prolog

Autores
Areias, M; Rocha, R;

Publicação
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE

Abstract
This work proposes a new design for the supporting data structures used to implement multithreaded tabling in Prolog systems. Tabling is an implementation technique that improves the expressiveness of traditional Prolog systems in dealing with recursion and redundant computations. Mode-directed tabling is an extension to the tabling technique that supports the definition of alternative criteria for specifying how answers are aggregated, thus being very suitable for problems where the goal is to dynamically calculate optimal or selective answers. In this work, we leverage the intrinsic potential that mode-directed tabling has to express dynamic programming problems by creating a new design that improves the representation of multi-dimensional arrays in the context of multithreaded tabling. To do so, we introduce a new mode for indexing arguments in mode-directed tabled evaluations, named dim, where each dim argument features a uni-dimensional lock-free array. Experimental results using well-known dynamic programming problems on a 32-core machine show that the new design introduces less overheads and clearly improves the execution time for sequential and multithreaded tabled evaluations.

2018

On Extending a Fixed Size, Persistent and Lock-Free Hash Map Design to Store Sorted Keys

Autores
Areias, M; Rocha, R;

Publicação
2018 IEEE INT CONF ON PARALLEL & DISTRIBUTED PROCESSING WITH APPLICATIONS, UBIQUITOUS COMPUTING & COMMUNICATIONS, BIG DATA & CLOUD COMPUTING, SOCIAL COMPUTING & NETWORKING, SUSTAINABLE COMPUTING & COMMUNICATIONS

Abstract
Searching is a crucial time-consuming part of many programs, and using a good search method instead of a bad one often leads to a substantial increase in performance. Hash tries are a trie-based data structure with nearly ideal characteristics for the implementation of hash maps. In this paper, we present a novel, simple and concurrent hash map design that fully supports the concurrent search, insert and remove operations on hash tries designed to store sorted keys. To the best of our knowledge, our design is the first concurrent hash map design that puts together the following characteristics: (i) use fixed size data structures; (ii) use persistent memory references; (iii) be lock-free; and (iv) store sorted keys. Experimental results show that our design is quite competitive when compared against other state-of-the-art designs implemented in Java.

  • 2
  • 5