Потоковая безопасность древовидных структур в OpenMP

Question

У меня есть симулятор N-Body, основанный на алгоритме Барнса-Хата, который я многопоточный с использованием OpenMP. Большая часть программы была сделана параллельной, просто добавив #pragma omp parallel for в нескольких ключевых местах. Это обеспечивает здоровое ускорение, которое хорошо масштабируется с количеством ядер, когда число гравитационных тел меньше пары тысяч.

Поскольку моя программа использует алгоритм Барнса-Хата , в его основе лежит древовидная структура, в 2d - это квадродерево, а в моем случае - октодерево. Я сталкиваюсь с проблемой многопоточности процесса заполнения дерева. Выполнение этого шага в однопоточном режиме не позволяет программе полностью использовать мой процессор. Моя загрузка ЦП фактически снижается при добавлении большего количества тел, потому что больше времени затрачивается на добавление всех тел в октре с использованием только одного ядра.

Прямо сейчас метод добавления одного тела к октодереву выглядит следующим образом:

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;
}

Это прекрасно работает, когда вызывается последовательно, но естественно ломается, когда я пытаюсь добавить несколько тел к одному корневому узлу одновременно. Этот код не содержит каких-либо мер по обеспечению безопасности потока объекта-октанта.

В идеале я хотел бы иметь возможность вызывать метод addBody параллельно, используя что-то вроде этого:

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

Я экспериментировал с добавлением #pragma omp critical(name) к частям метода, где изменяются данные, и #pragma omp single, где узел делится. Ничто из того, что я пробовал, не могло предотвратить немедленное падение.

Я также создал метод, который добавляет тела партиями. Он взял вектор объектов тела, отсортировал их по векторам в зависимости от того, в какое подразделение они вписываются, и передал эти векторы в свои соответствующие подразделения. Каждое подразделение получило свой собственный поток, и процесс был рекурсивным. Это работало и использовало все мои ядра, но было значительно медленнее. Я думаю, что размещение тел в векторах добавило тонну накладных расходов.

Я довольно новичок в OpenMP и даже новее в концепции безопасности потоков. Как лучше всего решить эту проблему? Я не могу найти очень много примеров потоковых безопасных древовидных структур в Интернете, и ни один из них не использует OpenMP. Каков идеальный подход к заполнению дерева с использованием нескольких потоков? По крайней мере, какие инструменты, по вашему мнению, были бы полезны для работы такого рода вещей

Редактировать: Кто-нибудь знает какие-либо примеры полностью поточно-ориентированной древовидной структуры? Даже если это не в OpenMP, меня прежде всего интересует, как дерево можно добавлять / генерировать / заполнять потокобезопасным способом.

Answer 1

Чтобы сделать дерево потокобезопасным для операций записи (например, добавить узел в вашем примере), я могу думать только о алгоритмах блокировки - например, Двухфазная блокировка . Эти структуры используются, например, в базах данных. Идея состоит в том, чтобы пойти вниз по дереву, выяснить, где нужно добавить узел, на какие (все) другие родительские узлы он будет влиять, дождаться блокировки на них, заблокировать их, выполнить операцию добавления и разблокировать. Это всегда будет поддерживать дерево в согласованном состоянии, позволяя одновременно выполнять операции добавления в разных частях дерева. Поэтому, прежде чем вы даже подумаете об этом, посмотрите, как вы добавляете данные в дерево. Если большинство дополнений будут противоречивыми, накладные расходы на блокировку не будут перевешивать выгоды от ускорения.

Еще несколько комментариев. То, что @Joseph Franciscus имел в виду, выполняя большую часть ваших вычислений параллельно, а затем последовательно добавляя все узлы в дерево, должно работать хорошо, если вы не ожидаете количество узлов порядка миллиардов.

Вы могли бы, однако, расширить его идею. Вы можете реализовать нечто похожее на параллельный шаблон Produce-Consume. Произвольное количество рабочих потоков будет работать над созданием тел и помещать результаты в потокобезопасную очередь, и только один поток (!) Будет добавлять их. Таким образом, вы можете заставить обе работы переплетаться друг с другом и параллельно выполнять еще больше работы.

PS. Барьер после omp parallel for неявный, вам не нужно ставить его там, AFAIK.

Редактировать : Я думал, может быть, немного псевдо-C-кода может помочь:

#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);
     }
  }
}

Сначала это приведет к двум потокам, каждый из которых будет занимать один из разделов. Затем во втором разделе будут создаваться дополнительные потоки, вы также можете управлять этим с помощью свойства num_thread. Единственное предостережение, о котором я могу подумать, - как заставить поток поместить узлы в конец дерева. Вы можете поместить как специальный узел в очередь, который сигнализирует, что больше узлов не будет добавлено.

Псевдокод, который я написал, также выполняет так называемое активное ожидание. Он постоянно спрашивает очередь, пуста она или нет. Вы можете избавиться от этого, сигнализируя поток потребителя семафором. Зависит от того, сколько поток должен ждать данных. с этим тоже можно поэкспериментировать.

Стандартные очереди / запросы библиотеки не являются поточно-ориентированными, поэтому обязательно реализуйте свою собственную или используйте библиотеку, предназначенную для использования в параллельных сценариях. Надеюсь, это сработает!

Answer 2

Это просто рекомендация о том, как это осуществить. Я уверен, что есть множество способов решить эту проблему.

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

int main() { 

    int thread_count = omp_get_num_threads();
    std::vector<std::vector<Body>> 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]);
    }
}

В основном вы сначала создаете тела, а затем добавляете их после параллельного раздела. Это гарантирует, что вы не будете сегрегировать, и даст приблизительную линейную скорость (если предположить, что основная часть затрат - это создание тел, а не их добавление).