Concurrent Disjoint Set Union

Durée : 01:00:54 -Réalisation : 9 décembre 2016 -Mise en ligne : 9 décembre 2016
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

The disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is ongoing joint work with Siddhartha Jayanti, an undergraduate at Princeton.

Langue :
CNRS - Centre National de la Recherche Scientifique (Publication), INRIA (Institut national de recherche en informatique et automatique) (Production), INRIA (Institut national de recherche en informatique et automatique) (Publication), UNS (Publication), Robert Endre Tarjan (Intervenant)
Conditions d'utilisation
Droit commun de la propriété intellectuelle
Citer cette ressource :
Robert Endre Tarjan. Inria. (2016, 9 décembre). Concurrent Disjoint Set Union. [Vidéo]. Canal-U. (Consultée le 5 juin 2023)

Sur le même thème