Set a barrier within task parallel region

General OpenMP discussion

Set a barrier within task parallel region

Postby eisteetuete » Sat Nov 18, 2017 6:46 am

Hello,
i tried to parallize ann n-ary Tree by using OpenMP tasks. Unfortunately i ran into another problem with race conditions.
After creating a Tree i want every Node to have the values of its childs added. This should start at the
leaves and progress to the root.
I have an Entry function which initializes some threads and calls one of two recursive functions. One of them
spawns more threads and the other one computes sequentially.
Up to this point it seem to work correct, yet i get wrong results because of racing conditions. I would need to
set a barrier for each Tree level.
I read the OpenMP manpage again and found no option to set a barrier within a task section.
I could only set a barrier and the end of the whole task.
Could you image a possibility to set the barrier or to change the structure accordingly?

Code: Select all
#include <omp.h>
#include <bits/stdc++.h>
using namespace std;
int tnbr=0;
int nths=0;

// Represents a node of an n-ary tree
struct Node
{
    int value;
    char name;
    vector<Node *>child;
};

// Utility function to create a new tree node
Node *newNode(int value,const char * name)
{
    Node *temp = new Node;
    temp->value = value;
    temp->name = *name;
    return temp;
}

// Prints the n-ary tree level wise
void LevelOrderTraversal(Node * root)
{
    if (root==NULL){
        return;
    }
    queue<Node *> q;
    q.push(root);
    while (!q.empty()){
        int n = q.size();
        // If this node has children
        while (n > 0){
            // Dequeue an item from queue and print it
            Node * p = q.front();
            q.pop();
            cout << p->value << " ";
              // Enqueue all children of the dequeued item
              for (int i=0; i<p->child.size(); i++){
                  q.push(p->child[i]);
              }
              n--;
          }
        cout << endl;
      }
}

void ComputeValueSumSingle(Node * root)
{
    if (root==NULL){
        return;
    }
    //  DFS to reach deepest node recursively
    for (int i=0; i<root->child.size(); i++){
    if(root->child.size()!=0){
        ComputeValueSumSingle(root->child[i]);
    }
    // Node has no child, therefore increase parent value
    #pragma omp critical
          {
            root->value=root->value+root->child[i]->value;
          }
    int id=omp_get_thread_num();
    }
}

void ComputeValueSumMultiple(Node * root)
{
    if (root==NULL){
    return;
    }
    #pragma omp critical
    {
        tnbr++;
    }
    //  DFS to reach deepest node recursively
    for (int i=0; i<root->child.size(); i++){
        if(root->child.size()!=0){
            #pragma omp task
            {
                if(tnbr>=nths){
                    ComputeValueSumSingle(root->child[i]);}
                else{
                    #pragma omp critical
                    {
                        tnbr++;
                    }
                    ComputeValueSumMultiple(root->child[i]);}
            }
        }
        #pragma omp barrier
        // Node has no child, therefore increase parent value
        #pragma omp critical
            {
                root->value=root->value+root->child[i]->value;
            }
    }
}

// Compute new Value of nodes
void ComputeValueSum(Node * root)
{
    if (root==NULL){
    return;
    }
    #pragma omp parallel
    {
        #pragma omp single nowait
        {
            nths = omp_get_num_threads();
            //  Spread Tasks across all Workers
            for (int i=0; i<root->child.size(); i++){
              if(root->child.size()!=0){
                  #pragma omp task shared(tnbr)
                  {
                      //After nths threads are spawned start computing serial
                      if(tnbr>=nths){
                          ComputeValueSumSingle(root->child[i]);}
                      else{
                          #pragma omp critical
                          {
                            tnbr++;
                          }
                          ComputeValueSumMultiple(root->child[i]);}
                  }
              }
               // Node has no child, therefore increase parent value
              #pragma omp critical
                    {
                        root->value=root->value+root->child[i]->value;
                        printf("I wrote the value %d\n",root->value);
                    }
            }
        }
    }
}

int main()
{
    Node *root = newNode(1,"top");
    (root->child).push_back(newNode(3,"foo"));
    (root->child).push_back(newNode(5,"bar"));
    (root->child[0]->child).push_back(newNode(-1,"foo1"));
    (root->child[0]->child).push_back(newNode(4,"bar1"));
    (root->child[1]->child).push_back(newNode(9,"foo2"));
    cout << "Level order traversal\n";
    LevelOrderTraversal(root);
    cout << "Computed Valuesum\n";
    ComputeValueSum(root);
    LevelOrderTraversal(root);
    return 0;
}
eisteetuete
 
Posts: 3
Joined: Fri Nov 10, 2017 7:51 pm

Re: Set a barrier within task parallel region

Postby MarkB » Tue Nov 21, 2017 3:37 am

Have you considered using taskwait instead of a barrier? I think that should do what you want (i.e. wait for child tasks to complete).
MarkB
 
Posts: 768
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Set a barrier within task parallel region

Postby eisteetuete » Tue Nov 21, 2017 6:18 am

Exactly what i was looking for, thank you very much :) My code ist running in parallel and scaling quite well.
eisteetuete
 
Posts: 3
Joined: Fri Nov 10, 2017 7:51 pm


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 5 guests

cron