Ressource pédagogique : Concurrent Disjoint Set Union
Présentation de: Concurrent Disjoint Set Union
Informations pratiques sur cette ressource
Droits réservés à l'éditeur et aux auteurs.
Description de la ressource pédagogique
Description (résumé)
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.
"Domaine(s)" et indice(s) Dewey
- Algorithmes (518.1)
- Théorie des graphes. Construction des graphes (511.5)
- Structure des données (005.73)
Thème(s)
Intervenants, édition et diffusion
Intervenants
Éditeur(s)
-
INRIA (Institut national de recherche en informatique et automatique)
Voir toutes les ressources pédagogiques
Diffusion
Document(s) annexe(s) - Concurrent Disjoint Set Union
- Cette ressource fait partie de
AUTEUR(S)
-
Robert E. Tarjan
ÉDITION
INRIA (Institut national de recherche en informatique et automatique)
EN SAVOIR PLUS
-
Identifiant de la fiche
26077 -
Identifiant
oai:canal-u.fr:26077 -
Schéma de la métadonnée
- LOMv1.0
- LOMFRv1.0
- Voir la fiche XML
-
Entrepôt d'origine
-
Date de publication
09-12-2016