Распараллеливание OpenMP на рекурсивной функции

Question

Я пытаюсь использовать распараллеливание для улучшения частоты обновления при рисовании трехмерной сцены с иерархически упорядоченными объектами. Алгоритм рисования сцены сначала рекурсивно пересекает дерево объектов, и из этого строит упорядоченный массив важных данных, необходимых для рисования сцены. Затем он проходит этот массив несколько раз для рисования объектов / оверлеев и т. Д. Поскольку из того, что я прочитал, OpenGL не является потокобезопасным API, я предполагаю, что код прохождения массива / рисования должен выполняться в основном потоке, но Я думаю, что я мог бы распараллелить рекурсивную функцию, которая заполняет массив. Ключевым моментом является то, что массив должен заполняться в порядке появления объектов в сцене, поэтому все функции, которые связывают данный объект с индексом массива, должны выполняться в правильном порядке, но как только индекс массива был назначен, Я могу заполнить данные этого элемента массива (что не обязательно тривиальная операция), используя рабочие потоки. Итак, вот псевдокод, который я пытаюсь получить. Я надеюсь, вы поняли синтаксис потока xml-ish.

recursivepopulatearray(theobject)
{
  <main thread>
  for each child of theobject
  {
     assign array index
     <child thread(s)>
       populate array element for child object
     </child thread(s)>
     recursivepopulatearray(childobject)
  }
  </main thread>
}

Итак, возможно ли это сделать с помощью OpenMP, и если да, то как? Существуют ли другие библиотеки распараллеливания, которые бы справились с этим лучше?

Добавление: В ответ на просьбу Давиде о дополнительных разъяснениях позвольте мне объяснить немного подробнее. Допустим, сцена упорядочена так:

-Bicycle Frame
  - Handle Bars 
  - Front Wheel
  - Back Wheel
-Car Frame
  - Front Left Wheel
  - Front Right Wheel
  - Back Left Wheel
  - Back Right Wheel

Теперь каждый из этих объектов имеет много данных, связанных с ним, то есть местоположение, поворот, размер, различные параметры рисования и т. Д. Кроме того, мне нужно сделать несколько проходов по этой сцене, чтобы правильно нарисовать ее. Один проход рисует формы объектов, другой проход рисует текст, описывающий объекты, другой проход рисует связи / ассоциации между объектами, если они есть. В любом случае, получение всех данных чертежа из этих различных объектов происходит довольно медленно, если мне нужно обращаться к ним несколько раз, поэтому я решил использовать один проход для кэширования всех этих данных в одномерный массив, а затем все фактические данные. рисование проходит просто посмотрите на массив. Уловка в том, что, поскольку мне нужно делать нажатия / выталкивания OpenGL в правильном порядке, массив должен быть в правильном порядке поиска в глубину, который представляет иерархию дерева. В приведенном выше примере массив должен быть упорядочен следующим образом:

index 0: Bicycle Frame
index 1: Handle Bars 
index 2: Front Wheel
index 3: Back Wheel
index 4: Car Frame
index 5: Front Left Wheel
index 6: Front Right Wheel
index 7: Back Left Wheel
index 8: Back Right Wheel

Итак, порядок массива должен быть правильно сериализован, но как только я назначу этот порядок правильно, я могу распараллелить заполнение массива. Например, как только я назначил Bicycle Frame для индекса 0 и Handle Bars для индекса 1, один поток может взять заполнение элемента массива для Bicycle Frame, а другой - заполнение элемента массива для Handle Bars.

Хорошо, я думаю, что разъясняя это, я ответил на свой вопрос, так что спасибо Давиде. Итак, я опубликовал свой ответ .

Answer 1

Я думаю, вам следует лучше уточнить свой вопрос (например, что именно должно быть сделано последовательно и почему)

OpenMP (как и многие другие библиотеки распараллеливания) не гарантирует порядок, в котором будут выполняться различные параллельные секции, и, поскольку они действительно параллельны (на многоядерном компьютере), могут возникнуть условия гонки, если разные разделы пишут одни и те же данные. Если это нормально для вашей проблемы, конечно, вы можете использовать его.

Answer 2

Как упомянул gbjbaanb , вы можете сделать это легко - для распараллеливания этого требуется просто выражение прагмы.

Однако есть несколько вещей, на которые стоит обратить внимание:

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

Кроме того, распараллеливание рекурсивных функций имеет много проблем. Возьмем крайний случай - скажем, у вас есть двухъядерный компьютер, и у вас есть дерево, в котором у каждого «родительского» узла есть 4 дочерних элемента. Если дерево глубокое, вы очень и очень быстро «перепараллеливаете» проблему, обычно ухудшая, а не улучшая производительность.

Если вы собираетесь это сделать, вам, вероятно, следует указать параметр уровня и распараллеливать только первые пару уровней. Возьмите мой пример «4 дочерних на родителя». Если вы распараллеливаете первые 2 уровня, вы уже разбиваете это на 16 параллельных блоков (называемых из 4 параллельных блоков).

Из того, что вы упомянули, я бы оставил эту часть серийной и сосредоточился вместо второй, где вы упомянули:

«Затем он проходит этот массив несколько раз для рисования объектов / наложений и т. Д.»

Звучит как идеальное место для распараллеливания.

Answer 3

Вот модифицированный фрагмент псевдокода, который должен работать.

populatearray(thescene)
{
  recursivepopulatearray(thescene)

  #pragma omp parallel for
  for each element in array
    populate array element based on associated object
}

recursivepopulatearray(theobject)
{
  for each childobject in theobject
  {
     assign array index and associate element with childobject
     recursivepopulatearray(childobject)
  }
}

Answer 4

, чтобы распараллелить дочерний поток, просто поместите прагму перед циклом:

#pragma omp parallel for
for (i=0; i < elements; i++) 
{
}

Работа выполнена.

Теперь вы совершенно правы, вы не можете заставить какую-либо потоковую библиотеку выполнять один бит перед другим полностью параллельным способом (очевидно!), И openMP не имеет функции «блокировки» или «ожидания» (это имеет ключевое слово «ждать все до конца» - Barrier), оно не предназначено для эмуляции библиотеки потоков, но позволяет хранить значения «вне» параллельного раздела и помечать определенные разделы как «только однопоточные» Упорядоченное ключевое слово), так что это может помочь вам назначить индексы в параллельном цикле, в то время как другие потоки присваивают элементы.

Взгляните на руководство по началу работы .

Если вы используете Visual C ++, вам также необходимо установить флаг / omp в настройках компилятора.