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
About

About

I'm an Associate Professor at the Department of Computer Science, Faculty of Sciences, University of Porto and a researcher at the CRACS & INESC TEC research unit.

I received my PhD degree in Computer Science from the University of Porto in 2001 and my main research topics are the Design and Implementation of Logic Programming Systems, Tabling in Logic Programming and Parallel and Distributed Computing. Another areas of interest include Lock-Free Data Structures, Inductive Logic Programming, Probabilistic Logic Programming and Deductive Databases. I'm also one of the main developers of the Yap Prolog system with particular focus on the execution models that support tabling and parallel evaluation.

I've published more than 100 refereed papers in international journals and conferences, served more than 50 events as PC chair or PC member, served the ALP Board as executive committee member and the ALP Newsletter as area co-editor for the Implementations and Systems track, served the INForum Board as president, supervised several PhD/MSc students and had leading role in two national projects. Currently, I'm the coordinator of the CRACS center at INESC TEC.

Interest
Topics
Details

Details

  • Name

    Ricardo Rocha
  • Role

    Centre Coordinator
  • Since

    01st January 2009
  • Nationality

    Portugal
  • Contacts

    +351220402963
    ricardo.rocha@inesctec.pt
004
Publications

2024

Yet Another Lock-Free Atom Table Design for Scalable Symbol Management in Prolog

Authors
Moreno, P; Areias, M; Rocha, R; Costa, VS;

Publication
INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING

Abstract
Prolog systems rely on an atom table for symbol management, which is usually implemented as a dynamically resizeable hash table. This is ideal for single threaded execution, but can become a bottleneck in a multi-threaded scenario. In this work, we replace the original atom table implementation in the YAP Prolog system with a lock-free hash-based data structure, named Lock-free Hash Tries (LFHT), in order to provide efficient and scalable symbol management. Being lock-free, the new implementation also provides better guarantees, namely, immunity to priority inversion, to deadlocks and to livelocks. Performance results show that the new lock-free LFHT implementation has better results in single threaded execution and much better scalability than the original lock based dynamically resizing hash table.

2023

Releasing Memory with Optimistic Access: A Hybrid Approach to Memory Reclamation and Allocation in Lock-Free Programs

Authors
Moreno, P; Rocha, R;

Publication
PROCEEDINGS OF THE 35TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2023

Abstract
Lock-free data structures are an important tool for the development of concurrent programs as they provide scalability, low latency and avoid deadlocks, livelocks and priority inversion. However, they require some sort of additional support to guarantee memory reclamation. The Optimistic Access (OA) method has most of the desired properties for memory reclamation, but since it allows memory to be accessed after being reclaimed, it is incompatible with the traditional memory management model. This renders it unable to release memory to the memory allocator/operating system, and, as such, it requires a complex memory recycling mechanism. In this paper, we extend the lock-free general purpose memory allocator LRMalloc to support the OA method. By doing so, we are able to simplify the memory reclamation method implementation and also allow memory to be reused by other parts of the same process. We further exploit the virtual memory system provided by the operating system and hardware in order to make it possible to release reclaimed memory to the operating system.

2022

On the correctness of a lock-free compression-based elastic mechanism for a hash trie design

Authors
Areias, M; Rocha, R;

Publication
COMPUTING

Abstract
A key aspect of any hash map design is the problem of dynamically resizing it in order to deal with hash collisions. Compression in tree-based hash maps is the ability of reducing the depth of the internal hash levels that support the hash map. In this context, elasticity refers to the ability of automatically resizing the internal data structures that support the hash map operations in order to meet varying workloads, thus optimizing the overall memory consumption of the hash map. This work extends a previous lock-free hash trie map design to support elastic hashing, i.e., expand saturated hash levels and compress unused hash levels, such that, at each point in time, the number of levels in a path is adjusted, as closely as possible, to the set of keys that is stored in the data structure. To materialize our design, we introduce a new compress operation for hash levels, which requires redesigning the existing search, insert, remove and expand operations in order to maintain the lock-freedom property of the data structure. Experimental results show that elasticity effectively improves the search operation and, in doing so, our design becomes very competitive when compared to other state-of-the-art designs implemented in Java.

2022

Parallel Logic Programming: A Sequel

Authors
Dovier, A; Formisano, A; Gupta, G; Hermenegildo, MV; Pontelli, E; Rocha, R;

Publication
THEORY AND PRACTICE OF LOGIC PROGRAMMING

Abstract
Multi-core and highly connected architectures have become ubiquitous, and this has brought renewed interest in language-based approaches to the exploitation of parallelism. Since its inception, logic programming has been recognized as a programming paradigm with great potential for automated exploitation of parallelism. The comprehensive survey of the first twenty years of research in parallel logic programming, published in 2001, has served since as a fundamental reference to researchers and developers. The contents are quite valid today, but at the same time the field has continued evolving at a fast pace in the years that have followed. Many of these achievements and ongoing research have been driven by the rapid pace of technological innovation, that has led to advances such as very large clusters, the wide diffusion of multi-core processors, the game-changing role of general-purpose graphic processing units, and the ubiquitous adoption of cloud computing. This has been paralleled by significant advances within logic programming, such as tabling, more powerful static analysis and verification, the rapid growth of Answer Set Programming, and in general, more mature implementations and systems. This survey provides a review of the research in parallel logic programming covering the period since 2001, thus providing a natural continuation of the previous survey. In order to keep the survey self-contained, it restricts its attention to parallelization of the major logic programming languages (Prolog, Datalog, Answer Set Programming) and with an emphasis on automated parallelization and preservation of the sequential observable semantics of such languages. The goal of the survey is to serve not only as a reference for researchers and developers of logic programming systems but also as engaging reading for anyone interested in logic and as a useful source for researchers in parallel systems outside logic programming.

2021

On the correctness and efficiency of a novel lock-free hash trie map design

Authors
Areias, M; Rocha, R;

Publication
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING

Abstract
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 scalable hash trie map design that fully supports the concurrent search, insert and remove operations on hash maps. To the best of our knowledge, our proposal is the first that puts together the following characteristics: (i) be lock free; (ii) use fixed size data structures; and (iii) maintain the access to all internal data structures as persistent memory references. Our design is modular enough to allow different types of configurations aimed for different performances in memory usage and execution time and can be easily implemented in any type of language, library or within other complex data structures. We discuss in detail the key algorithms required to easily reproduce our implementation by others and we present a proof of correctness showing that our proposal is linearizable and lock-free for the search, insert and remove operations. Experimental results show that our proposal is quite competitive when compared against other state-of-the-art proposals implemented in Java.

Supervised
thesis

2022

Memory Reclamation for an Elastic Lockfree Hash Trie Map

Author
João Miguel Chamiça Pereira

Institution
UP-FCUP

2022

Generic Lock-Free Memory Reclamation

Author
Pedro Carvalho Moreno

Institution
UP-FCUP

2021

Elasticidade em Lock-Free Hash-Tries

Author
João Miguel Chamiça Pereira

Institution
UP-FCUP

2021

Generic Lock-Free Memory Reclamation

Author
Pedro Carvalho Moreno

Institution
UP-FCUP

2020

Generic Lock-Free Memory Reclamation

Author
Pedro Carvalho Moreno

Institution
UP-FCUP