• Accueil
  • Accueil
  • Accueil
  • Accueil

CNRS

Rechercher




Accueil > Équipes > ACMES > Séminaires ACMES > Séminaires 2022 ACMES

[PDS/HPDA Seminar] 7/1/2022 from 10:00 to 12:30 at 4A312 - Frambot Paul (reading group) and Albuquerque Silva Igor (reading group)

[PDS/HPDA Seminar] 7/1/2022 from 10:00 to 12:30 at 4A312 - Frambot Paul (reading group) and Albuquerque Silva Igor (reading group)

Fast Arrays : Atomic Arrays with Constant Time Initialization

Reading group : Albuquerque Silva Igor will present "Fast Arrays : Atomic Arrays with Constant Time Initialization" (DISC’21) at 4A301 (visio link) the 7/1/2022 at 10h30.

Webconference : https://webconf.imt.fr/frontend/fra-vcg-byn-fxd

Abstract

Some algorithms require a large array, but only operate on a small fraction of its indices. Examples include adjacency matrices for sparse graphs, hash tables, and van Emde Boas trees. For such algorithms, array initialization can be the most time-consuming operation. Fast arrays were invented to avoid this costly initialization. A fast array is a software implementation of an array, such that the entire array can be initialized in just constant time. While algorithms for sequential fast arrays have been known for a long time, to the best of our knowledge, there are no previous algorithms for concurrent fast arrays. We present the first such algorithms in this paper. Our first algorithm is linearizable and wait-free, uses only linear space, and supports all operations – initialize, read, and write – in constant time. Our second algorithm enhances the first to additionally support all the read-modify-write operations available in hardware (such as compare-and-swap) in constant time.