2019
Authors
Moreno, P; Areias, M; Rocha, R;
Publication
2019 31ST INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD 2019)
Abstract
Hash tries are a trie-based data structure with nearly ideal characteristics for the implementation of hash maps. Starting from a particular lock-free hash map data structure, named Lock-Free Hash Tries (LFHT), we focus on solving the problem of memory reclamation without losing the lock-freedom property. We propose an approach that explores the characteristics of the LFHT structure in order to achieve efficient memory reclamation with low and well-defined memory bounds. Experimental results show that our approach obtains better results when compared with other state-of-the-art memory reclamation methods and provides a competitive and scalable hash map implementation, if compared to lock-based implementations.
2020
Authors
Moreno, P; Areias, M; Rocha, R;
Publication
Euro-Par 2020: Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Warsaw, Poland, August 24-28, 2020, Proceedings
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.
2021
Authors
Moreno, P; 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. Starting from a particular lock-free hash map data structure, named Lock-Free Hash Tries, we focus on solving the problem of memory reclamation without losing the lock-freedom property. To the best of our knowledge, outside garbage collected environments, there is no current implementation of hash maps that is able to reclaim memory in a lock-free manner. To achieve this goal, we propose an approach for memory reclamation specific to Lock-Free Hash Tries that explores the characteristics of its structure in order to achieve efficient memory reclamation with low and well-defined memory bounds. We present and discuss in detail the key algorithms required to easily reproduce our implementation by others. Experimental results show that our approach obtains better results when compared with other state-of-the-art memory reclamation methods and provides a competitive and scalable hash map implementation, if compared to lock-based implementations.
2024
Authors
Leite, I; Cabral, A; Santos, N; Silva, A; Oliveira, A; Wehbe, B; Alves, D; Martins, J; Abreu, M; Monteiro, M; Moreno, P; Gafeira, R;
Publication
GROUND-BASED AND AIRBORNE INSTRUMENTATION FOR ASTRONOMY X
Abstract
There are currently important challenges imposed by stellar noise often associated with the discovery and characterization of exoplanets similar to Earth. In particular, various physical processes occurring on the stellar photosphere modify stellar spectra, severely challenging the detection and characterization of low-mass planets. A detailed study of the Sun can be used as a spectral proxy to a better understanding of the variable noise sources present in solartype stars. By obtaining full integrations of the solar disk (sun-as-a-star observations) in combination with high resolution, spatially resolved observations of smaller areas, the acquired spectra will help in the identification of individual stellar features responsible for the observed spectral deformations. The Instituto de Astrofisica e Ciencias do Espaco (Portugal) is currently developing an instrument to approach this challenge. In conjunction with the high-resolution spectrograph ESPRESSO (spectral resolutions of R similar to 140 000 and similar to 190 000, HR and UHR modes, respectively), the Paranal solar ESPRESSO Telescope (PoET) will have two dedicated telescopes to map the Sun's surface through disk-resolved and disk-integrated measurements, with respective telescope diameters of 600 and 75 millimeters. PoET has the requirement to perform disk-resolved observations from 1 to 60 arcseconds in conjunction with the full disk. In this work, a summary of the current configuration of the system - PoET's telescopes and their frontends - will be given, as well as the preliminary assumptions made to build PoET, with consideration for the light requirements of the ESPRESSO spectrograph.
2025
Authors
Moreno, P; Areias, M; Rocha, R;
Publication
PARALLEL COMPUTING
Abstract
Lock-free data structures have become increasingly significant due to their algorithmic advantages in multi-core cache-based architectures. Safe Memory Reclamation (SMR) is a technique used in concurrent programming to ensure that memory can be safely reclaimed without causing data corruption, dangling pointers, or access to freed memory. The ERA theorem states that any SMR method for concurrent data structures can only provide at most two of the three main desirable properties: Ease of use, Robustness, and Applicability. This fundamental trade-off influences the design of efficient lock-free data structures at an early stage. This work redesigns a previous lock-free hash map to fully exploit the properties of the ERA theorem and to leverage the characteristics of multi-core cache-based architectures by minimizing the number of cache misses, which are a significant bottleneck in multi-core environments. Experimental results show that our design outperforms the previous design, which was already quite competitive when compared against the Concurrent Hash Map design of the Intel's TBB library.
2025
Authors
Moreno, P; Areias, M; Rocha, R;
Publication
EURO-PAR 2024: PARALLEL PROCESSING WORKSHOPS, PT II
Abstract
Lock-freedom offers significant advantages in terms of algorithm design, performance and scalability. A fundamental building block in software development is the usage of hash map data structures. This work extends a previous lock-free hash map to support a new simplified design that is able to take advantage of most state-of-the-art safe memory reclamation methods, thus outperforming the previous design.
The access to the final selection minute is only available to applicants.
Please check the confirmation e-mail of your application to obtain the access code.