Canal-U

Mon compte
Inria

Concurrent Disjoint Set Union


Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/concurrent_disjoint_set_union.26077?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Auteur(s) :
Tarjan Robert E.

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

Concurrent Disjoint Set Union

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.

  •  
  •  
    Date de réalisation : 9 Décembre 2016
    Durée du programme : 61 min
    Classification Dewey : Algorithmes, Théorie des graphes. Construction des graphes, Structure des données
  •  
    Catégorie : Conférences
    Niveau : niveau Master (LMD), niveau Doctorat (LMD), Recherche, L3
    Disciplines : Informatique
    Collections : Séminaires scientifiques
    ficheLom : Voir la fiche LOM
  •  
    Auteur(s) : Tarjan Robert E.
    producteur : INRIA (Institut national de recherche en informatique et automatique)
    Editeur : INRIA (Institut national de recherche en informatique et automatique) , CNRS - Centre National de la Recherche Scientifique , UNS
  •  
    Langue : Anglais
    Mots-clés : structure de données
 

commentaires


Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)
 
FMSH
 
Facebook Twitter Google+
Mon Compte