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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2024

Autores

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

Revista

Título: International Journal of Parallel Programming

Vol. 52

Páginas: 187-206

ISSN: 0885-7458

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 1 Citação

Classificação Científica

CORDIS: Ciências Tecnológicas > Engenharia > Engenharia de computadores

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

Outras Informações

ID Authenticus: P-010-5J0

DOI: 10.1007/s10766-024-00766-z

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

Idioma: Inglês

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

Nº de páginas: 20