A Compression-Based Design for Higher Throughput in a Lock-Free Hash Map

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2020

Autores

Moreno, P (Autor) Outra; Miguel Areias (Autor) FCUP; Ricardo Rocha (Autor) FCUP

Ata de Conferência Internacional

Título: Euro-Par 2020: Parallel Processing - 26th International Conference on Parallel and Distributed Computing, Warsaw, Poland, August 24-28, 2020, Proceedings

Páginas: 458-473

26th International European Conference on Parallel and Distributed Computing, Euro-Par 2020

24 August 2020 through 28 August 2020

Indexação

Scopus - 2 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-00S-M14

DOI: 10.1007/978-3-030-57675-2_29

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica