Thread safety of tree structures in OpenMP

Question

I have an N-Body simulator based on the Barnes-Hut algorithm which I've multithreaded using OpenMP. Most of the program was made parallel by simply adding #pragma omp parallel for in a few key places. This provides a healthy speedup, which scales nicely with the number of cores when the number of gravitational bodies is under a couple thousand.

Because my program uses the Barnes-Hut algorithm, at its heart is a tree structure, in 2d this is a quadtree, and in my case an octree. I'm running into trouble multithreading the process of populating the tree. Making this step single threaded prevents the program from making full use of my processor. My CPU utilization actually goes down the more bodies I add, because more time is spent adding all the bodies to the octree using only one core.

Right now the method for adding a single body to the octree looks like this:

void octant::addBody(vec3 newPosition, float newMass) {

    // Making room for new bodies by dividing if the node is a leaf
    if (isLeaf) {

        // Subdividing the octant
         divide();

        // Moving the body already contained
        subdivisionEnclosing(this->position)->addBody(this->position, this->mass);
    }

    // Adding the body to the appropriate subdivision if the node is divided
    if (divided) {

        // Adding the new body to the appropriate octant
        subdivisionEnclosing(newPosition)->addBody(newPosition, newMass);

        return;
    }

    // If the node doesnt yet contain any bodies at all, add the new one
    this->position = newPosition;
    this->mass = newMass;

    // This node only contains one body, so the center of mass is accurate
    isLeaf = true;
    calculatedCOM = true;
}

This works just fine when called in series, but naturally breaks down when I try to add multiple bodies to the same root node simultaneously. This code doesn't include any measures to make the octant object thread safe.

Ideally I'd like to be able to call the addBody method in parallel using something like this:

#pragma omp parallel for
for (int b = 0; b < bodies.size(); ++b) {
    octree->addBody(bodies[b]->getPosition(), bodies[b]->getMass());
}

I've experimented with adding #pragma omp critical(name) to parts of the method where data is changed and #pragma omp single where the node is subdivided. Nothing I tried prevented an immediate segfault.

I also built a method which adds the bodies in batches. It took in a vector of body objects, sorted them into vectors based on what subdivision they fit into, and passed those vectors into their respective subdivisions. Each subdivision got its own thread, and the process was recursive. This functioned and used all my cores, but it was significantly slower. I think putting the bodies into vectors added a ton of overhead.

I'm pretty new to OpenMP and even newer to the concept of thread safety. What would the best way to solve this problem? I cant seem to find very many examples of thread-safe tree structures online, and none using OpenMP. What is the ideal approach to populating a tree using multiple threads? At the very least, what tools do you think would be useful in making this kind of thing work?

Edit: Does anyone know of any examples of a completely thread-safe tree structure? Even if it's not in OpenMP, I'm primarily interested in how a tree can be added to/generated/filled in a thread-safe way.

user_5433651 · Answer

To make a tree thread-safe for write operations (like add a node in your example) I can think of only the locking algorithms - e.g. Two-phase locking. These structures are used in Databases for instance. The idea would be to go down the tree, figure out where the node needs to be added, which (all) other parent nodes it will affect, wait for a lock on those, lock them, do the add operation and unlock. This will always keep the tree in a consistent state while allowing concurrent add operations in different parts of the tree. Therefore, before you even consider to implement this, take a look at how you add the data into the tree. If most additions would be conflicting then the overhead from locking wouldn't outweigh the gains in speed-up.

A few more comments. What @Joseph Franciscus meant with doing the bulk of your computations in parallel and then sequentially add all nodes to the tree should work well if you aren't expecting the amount of nodes in order of billions.

You could, however, expand on his idea. You can implement something similar to the parallel Produce-Consume pattern. An arbitrary number of worker threads would work on creating the bodies and put the results in a thread-safe queue and one thread only (!) would be adding them. This way you can make both jobs intertwine with each other and get even more work done in parallel.

PS. The barrier after omp parallel for is implicit, you don't need to put it there AFAIK.

Edit: I was thinking maybe a bit of pseudo-C-code could help:

#pragma omp parallel sections num_threads(2)
{
  #pragma omp section
  {
    while (true) {
      if (queue_notEmpty()){
        if (node is last) break;
        node = queue_front(); queue_pop();
        tree->addNode(node);
      }
    }
  }
  #pragma omp section
  {
     #pragma omp parallel for
     for (int i = 0; i < N; ++i) {
        node = init_node(...);
        queue_push(node);
     }
  }
}

This will first result in two threads, each taking one of the sections. Then in the second section further threads will be spawned, you could also control that with a num_thread property. The only caveat here I can think of is how to make the thread putting nodes into the tree end. You could put like a special node into the queue that signalizes that no more nodes will be added.

The pseudocode I wrote also does so called active waiting. It asks the queue all the time whether it is or isn't empty. You could get rid of it by signaling the consumer thread with a semaphore. Depends on how much the thread needs to wait for data. you can experiment with that, too.

The standard library queues/deques aren't thread-safe so make sure to either implement your own or use a library made for usage in parallel scenarios. Hope it works out!

user_8137872 · Answer

This is simply a recommendation on how to go about implementing this. I am sure there are a multitude of ways one can go about solving this problem.

void octant::addBody(Body);
Body octant::create_body(vec3 newPosition, float newMass);

int main() { 

    int thread_count = omp_get_num_threads();
    std::vector> body_list(thread_count);  //each thread gets its own list of bodies

    #pragma omp parallel for
    for (int b = 0; b < bodies.size(); ++b) {
        int index = omp_get_thread_num();
        Body tmp = octant::create_body(bodies[b]->getPosition(), bodies[b]->getMass());

        body_list[index].push_back(tmp); 
    }
    #pragma omp barrier    //make sure to add barrier (as openmp is asynchronous to host thread)

    for (int i = 0; i < thread_count; ++i) {
        for (int j = 0; j < body_list[i].size(); ++j) 
             bodies.add_body(body_list[i][j]);
    }
}

Basically you create the bodies first, and add them after the parallel section. This ensure you won't segfault and gives an approximate speed linear speed up (assuming the bulk of the cost is creating the bodies, and not adding them).

Thread safety of tree structures in OpenMP

2 Answers