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
Tópicos
de interesse
Detalhes

Detalhes

  • Nome

    Miguel Gonçalves Areias
  • Cluster

    Informática
  • Cargo

    Investigador
  • Desde

    16 maio 2011
Publicações

2021

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

Autores
Areias, M; Rocha, R;

Publicação
J. Parallel Distributed Comput.

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. © 2021 Elsevier Inc.

2021

On the Implementation of Memory Reclamation Methods in a Lock-Free Hash Trie Design

Autores
Moreno, P; Areias, M; Rocha, R;

Publicação
Journal of Parallel and Distributed Computing

Abstract

2021

Towards an Elastic Lock-Free Hash Trie Design

Autores
Areias, M; Rocha, R;

Publicação
20th International Symposium on Parallel and Distributed Computing, ISPDC 2021, Cluj-Napoca, Romania, July 28-30, 2021

Abstract

2020

A compression-based design for higher throughput in a lock-free hash map

Autores
Moreno, P; Areias, M; Rocha, R;

Publicação
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Abstract
Lock-free implementation techniques are known to improve the overall throughput of concurrent data structures. A hash map is an important data structure used to organize information that must be accessed frequently. A key role of a hash map is the ability to balance workloads by dynamically adjusting its internal data structures in order to provide the fastest possible access to the information. This work extends a previous lock-free hash map design to also support lock-free compression. The main goal is to significantly reduce the depth of the internal hash levels within the hash map, in order to minimize cache misses and increase the overall throughput. To materialize our design, we redesigned the existent search, insert, remove and expand operations in order to maintain the lock-freedom property of the whole design. Experimental results show that lock-free compression effectively improves the search operation and, in doing so, it outperforms the previous design, which was already quite competitive when compared against the concurrent hash map design supported by Intel. © Springer Nature Switzerland AG 2020.

2019

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

Autores
Areias, M; Rocha, R;

Publicação
Concurrency and Computation: Practice and Experience

Abstract