Efficient, Distributed, and Non-Speculative Multi-Address Atomic Operations

Gómez-Hernández, Eduardo José; Titos-Gil, Rubén; Cebrián González, Juan Manuel; Kaxiras, Stefanos; Ros, Alberto

Publication:
Efficient, Distributed, and Non-Speculative Multi-Address Atomic Operations

dc.contributor.author	Gómez-Hernández, Eduardo José
dc.contributor.author	Titos-Gil, Rubén
dc.contributor.author	Cebrián González, Juan Manuel
dc.contributor.author	Kaxiras, Stefanos
dc.contributor.author	Ros, Alberto
dc.contributor.department	Ingeniería y Tecnología de Computadores
dc.date.accessioned	2021-12-02T20:17:46Z
dc.date.available	2021-12-02T20:17:46Z
dc.date.issued	2021-10
dc.description.abstract	Critical sections that read, modify, and write (RMW) a small set of addresses are common in parallel applications and concurrent data structures. However, to escape from the intricacies of fine-grained locks, which require reasoning about all possible thread interleavings, programmers often resort to coarse-grained locks to ensure atomicity. This results in atomic protection of a much larger set of potentially conflicting addresses, and, consequently, increased lock contention and unneeded serialization. As many before us have observed, these problems would be solved if only general RMW multi-address atomic operations were available, but current proposals are impractical because of deadlock scenarios that appear due to resource limitations. Alternatively, transactional memory can detect conflicts at run-time aiming to maximize concurrency, but it has significant overheads in highly-contended critical sections. In this work, we propose multi-address atomic operations (MAD atomics). MAD atomics achieve complexity-effective, non-speculative, non-deadlocking, fine-grained locking for multiple addresses, relying solely on the coherence protocol and a predetermined locking order. Unlike prior works, MAD atomics address the challenge of enabling atomic modification over a set of cachelines with arbitrary addresses, simultaneously locking all of them while sidestepping deadlock. MAD atomics only require a small storage per core (around 68 bytes), while significantly outperforming typical lock implementations. Indeed, our evaluation using gem5-20 shows that MAD atomics can improve performance by up to 18×(3.4×, on average, for the applications and concurrent data structures evaluated in this work) over a baseline implemented with locks running on 16 cores. More importantly, the improvement still reaches 2.7×, on average, compared to an Intel hardware transactional memory implementation running on 16 cores.	es
dc.format	application/pdf	es
dc.format.extent	13	es
dc.identifier.doi	10.1145/3466752.3480073
dc.identifier.eissn	978-1-4503-8557-2
dc.identifier.uri	http://hdl.handle.net/10201/114646
dc.language	eng	es
dc.relation	European Research Council (ERC) under the European Union s Horizon 2020 research and innovation programme (ECHO: Extending Coherence for Hardware-Driven Optimizations in Multicore Architectures, grant agreement No 819134, Consolidator Grant, 2018).	es
dc.relation.ispartof	54th International Symposium on Microarchitecture (MICRO)	es
dc.rights	info:eu-repo/semantics/openAccess	es
dc.rights	Atribución 4.0 Internacional	*
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/	*
dc.subject	Mutli-address atomics	es
dc.subject	Read-Modity-Write	es
dc.subject	Deadlock-free	es
dc.subject	Non-speculative	es
dc.title	Efficient, Distributed, and Non-Speculative Multi-Address Atomic Operations	es
dc.type	info:eu-repo/semantics/article	es
dspace.entity.type	Publication	es