Le thread de l'algorithme union/find normal est-il sûr sans travail supplémentaire?

Question

La structure de données standard union/find or Disjoint-set a de très bons temps de fonctionnement (effectivement O(1)) pour les boîtiers à un seul filetage. Cependant, quelle est sa validité/performance sous des cas multi-threadés? Je pense qu'il est totalement valide même sans verrouillage ou toutes les opérations atomiques en dehors des écritures de taille atomique pointeur.

Est-ce que quelqu'un voit des problèmes avec la logique suivante?

D'abord, je suppose que les écritures de taille de pointeur sont atomiques. De cela, il n'est pas difficile d'argumenter que vous pouvez exécuter la fonction find en toute sécurité dans plusieurs threads car les seules mises à jour qui se produiront sont tous les jeux à la même valeur. Si vous autorisez la fonction find à renvoyer la réponse qui était vraie quand elle a été appelée (par opposition à quand elle est retournée), il n'est pas difficile d'argumenter que beaucoup de find et un seul union peuvent être exécutés en même temps; l'argument pour le find ne change pas et le union ne met à jour que les racines et les find ne mettent jamais à jour les racines. Comme pour le cas restant (plusieurs union s), je pense que cela fonctionne aussi bien mais je ne suis pas si sûr de lui.

BTW: Je ne demande pas que la solution soit aussi efficace que la version à un seul filetage. (Afin d'éviter les serrures/atomiques, je suis également prêt à rejeter globalement état cohérent.)

---

modifier: prendre un autre regard, les cas de nombreux syndiqués ne fonctionne pas parce que si le côté qui n'est pas la nouvelle racine est unie avec autre chose (pas aussi comme une racine), alors vous pourriez le couper de l'autre côté de la deuxième union.

A = find(a) // union 1 
B = find(b) // union 1 
---- 
X = find(x) // union 2 (x == a) -> (X == A) -> (X.par aliases A.par) 
Y = find(y) // union 2 
X.par = Y // union 2 
---- 
A.par = B // union 1 

cela peut être évité avec un CAS:

while(!CAS(A == A.par, B)) A = find(A); 

Answer 1

Le type de synchronisation que vous pouvez utiliser pour cette structure est similaire à la Readers-writers problem. La performance dépendra du nombre de syndicats qui seront exécutés car l'opération de recherche sera alors arrêtée.

Je ne suis pas sûr que vous pouvez exécuter plusieurs trouvailles et une seule union dans le même temps parce que le dernier cas d'une opération d'union n'est pas atomique.

Answer 2

Un peu en retard mais pour référence future. Avec les opérations atomiques, vous pouvez créer une structure de données set disjointe. L'invariant est que chaque ensemble est représenté par son plus petit membre, ce qui permet d'éviter les boucles dues aux conditions de course.

// atomic_compare_and_exchange(unsigned int *data, unsigned int new_value, unsigned int comparator) 


// "The result used to be the root of v once" 
static unsigned int GetSet(volatile unsigned int *H_RESTRICT set, const unsigned int v) 
{ 
    unsigned int next; 
    unsigned int root = v; 
    unsigned int prev = v; 

    while (root != (next = set[root])) 
    { 
    /* Update set[prev] to point to next instead of root. 
     * If it was updated by some other thread in the meantime, or if this 
     * is the first step (where set[prev]==next, not root), ignore. */ 
    atomic_compare_and_exchange(set + prev, next, root); 

    prev = root; 
    root = next; 
    } 

    /* Update the path to the root */ 

    return root; 
} 

// FALSE == "They used not to be in the same set" 
// TRUE == "They are in the same set, and will be forever" 
static HBOOL IsInSameSet(volatile unsigned int *H_RESTRICT set, unsigned int v1, unsigned int v2) 
{ 
    do 
    { 
    v1 = GetSet(set, v1); 
    v2 = GetSet(set, v2); 
    } while (set[v1] != v1 || set[v2] != v2); 

    return v1 == v2; 
} 

static void Union(volatile unsigned int *H_RESTRICT set, unsigned int v1, unsigned int v2) 
{ 
    unsigned int result; 

    do 
    { 
    v1 = GetSet(set, v1); 
    v2 = GetSet(set, v2); 
    if (v1 == v2) 
    { 
     /* Already same set. This cannot be changed by a parallel operation. */ 
     break; 
    } 
    if (v1 < v2) 
    { 
     /* Make sure we connect the larger to the smaller set. This also avoids 
     * cyclic reconnections in case of race conditions. */ 
     unsigned int tmp = v1; 
     v1 = v2; 
     v2 = tmp; 
    } 

    /* Make v1 point to v2 */ 
    result = atomic_compare_and_exchange(set + v1, v2, v1); 
    } while (result != v1); 
}