Распараллеливание 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, и если да, то как? Существуют ли другие библиотеки распараллеливания, которые бы справились с этим лучше?

Приложение: в ответ на Davide's просьба о дополнительных разъяснениях , позвольте мне объяснить немного подробнее. Допустим, сцена упорядочена следующим образом:

-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

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

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 2

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

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

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

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

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

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

Ознакомьтесь с руководством по началу работы .

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