Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
Publications

Publications by Miguel Gonçalves Areias

2015

Batched Evaluation of Full-Sharing Multithreaded Tabling

Authors
Areias, M; Rocha, R;

Publication
LANGUAGES, APPLICATIONS AND TECHNOLOGIES, SLATE 2015

Abstract
Tabling is a technique that overcomes some limitations of traditional Prolog systems in dealing with redundant sub-computations and recursion. When tabling is combined with multithreading, we have the best of both worlds, since we can exploit the combination of higher declarative semantics with higher procedural control. To support this combination, the Yap Prolog system has, at engine level, multiple designs that vary from a No-Sharing design, where each thread allocates fully private tables, to a Full-Sharing (FS) design, where threads share the complete table space. In this work, we propose an extension to the table space data structures, which we named Private Answer Chaining (PAC), as way to support batched scheduling evaluation with the FS design. Batched scheduling is one of the most successful tabling scheduling strategies, known to be useful when a tabled logic program requires an eager propagation of answers and/or do not requires the complete set of answers to be found. Experimental results show that PAC is a good first approach, since with it the FS design remains quite competitive.

2013

Batched Evaluation of Linear Tabled Logic Programs

Authors
Areias, M; Rocha, R;

Publication
COMPUTER SCIENCE AND INFORMATION SYSTEMS

Abstract
Logic Programming languages, such as Prolog, provide a high-level, declarative approach to programming. Despite the power, flexibility and good performance that Prolog systems have achieved, some deficiencies in Prolog's evaluation strategy - SLD resolution - limit the potential of the logic programming paradigm. Tabled evaluation is a recognized and powerful technique that overcomes SLD's susceptibility in dealing with recursion and redundant sub-computations. In a tabled evaluation, there are several points where we may have to choose between different tabling operations. The decision on which operation to perform is determined by the scheduling algorithm. The two most successful tabling scheduling algorithms are local scheduling and batched scheduling. In previous work, we have developed a framework, on top of the Yap Prolog system, that supports the combination of different linear tabling strategies for local scheduling. In this work, we propose the extension of our framework to support batched scheduling. In particular, we are interested in the two most successful linear tabling strategies, the DRA and DRE strategies. To the best of our knowledge, no other Prolog system supports both strategies simultaneously for batched scheduling. Our experimental results show that the combination of the DRA and DRE strategies can effectively reduce the execution time for batched evaluation.

2017

On scaling dynamic programming problems with a multithreaded tabling, Prolog system

Authors
Areias, M; Rocha, R;

Publication
JOURNAL OF SYSTEMS AND SOFTWARE

Abstract
Tabling is a powerful implementation technique that improves the declarativeness and expressiveness of traditional Prolog systems in dealing with recursion and redundant computations. It can be viewed as a natural tool to implement dynamic programming problems, where a general recursive strategy divides a problem in simple sub-problems that are often the same. When tabling is combined with multithreading, we have the best of both worlds, since we can exploit the combination of higher declarative semantics with higher procedural control. However, at the engine level, such combination for dynamic programming problems is very difficult to exploit in order to achieve execution scalability as we increase the number of running threads. In this work, we focus on two well-known dynamic programming problems, the Knapsack and the Longest Common Subsequence problems, and we discuss how we were able to scale their execution by using the multithreaded tabling engine of the Yap Prolog system. To the best of our knowledge, this is the first work showing a Prolog system to be able to scale the execution of multithreaded dynamic programming problems. Our experiments also show that our system can achieve comparable or even better speedup results than other parallel implementations of the same problems.

2014

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

Authors
Areias, M; Rocha, R;

Publication
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Abstract
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.

2017

On the implementation of a cloud-based computing test bench environment for prolog systems

Authors
Goncalves, R; Areias, M; Rocha, R;

Publication
Information (Switzerland)

Abstract
Software testing and benchmarking are key components of the software development process. Nowadays, a good practice in large 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 performing 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 as well as a new Jenkins plugin to manage the underlying infrastructure. We present the key design and implementation aspects of YAPTBE and show its most important features, such as its graphical user interface (GUI) and the automated process that builds and runs Prolog systems and benchmarks. © 2017 by the authors.

2017

Towards a Lock-Free, Fixed Size and Persistent Hash Map Design

Authors
Goncalves Areias, MJ; da Rocha, RJGL;

Publication
2017 29th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)

Abstract

  • 1
  • 4