OpenMP ordenação árvore

votos
0

Eu estou classificando um array utilizando o algoritmo de ordenação árvore:

  1. Construa a árvore de matriz.
  2. Inorder percorrer a árvore e escrever de volta à matriz.

A versão de série do código está funcionando bem, mas eu quero tentar e melhorar o desempenho usando OpenMP. Eu sei que existem algoritmos como merge sort que são mais adequados para paralelismo, mas eu ainda quero tentar resolver isso com tipo de árvore, se possível.

Eu tentei implementar a travessia inorder como o código abaixo, mas a sua mais lento do que a versão original.

// Serial inorder traversal of binary tree
void inorder_v1(const tree* t, unsigned* arr, int &i) {
    if(t == NULL)
        return;
    inorder_v1(t->left, arr, i);
    arr[i++] = t->value;
    inorder_v1(t->right, arr, i);
}

//Parallel inorder traversal of binary tree
void inorder_v2(const tree* t, unsigned* arr, int &i) {
    if(t->left != NULL) {
        #pragma omp task shared(i)
        inorder_v2(t->left, arr, i);        
    }
    #pragma omp taskwait

    arr[i++] = t->value;

    if(t->right != NULL) {
        #pragma omp task shared(i)
        inorder_v2(t->right, arr, i);
    }
    #pragma omp taskwait
}

Então eu tentei paralelizar a construção da árvore em vez mas que também foi mais lento do que o original, e nem sempre resultam na árvore correta.

tree* t = (tree*)calloc(1, sizeof(tree));
t->value = arr[0];

#pragma omp parallel for
for(int i = 1; i < n; i++) {
    tree *current = t; // Iterator
    tree *parent = t; // Trailing iterator
    tree *node = (tree*)calloc(1, sizeof(tree)); // Node to insert
    node->value = arr[i];
    bool flag = true;

    // traverse the tree and find parent node of the value
    while (flag) {
        parent = current;
        if (node->value < current->value)
            current = current->left;
        else
            current = current->right;

        #pragma omp critical
        {
            if(current == nullptr) {
                // construct a new node and assign to appropriate parent pointer
                if (node->value < parent->value)
                    parent->left = node;
                else
                    parent->right = node;
                flag = false;
            }
        }
    }
}

Eu sou um novato com programação paralela assim quaisquer sugestões ou dicas sobre como resolver este seria muito apreciada.

Publicado 27/11/2018 em 18:08
fonte usuário
Em outras línguas...                            

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more