OpenMP для вложенных циклов?

Question

Я пытаюсь использовать OpenMP в моем проекте, который содержит N агентов в симуляции.Каждый агент имеет вектор позиции.Внутри моей программы я делаю что-то вроде следующего:

for(int i=0;i<agents.size();i++){
 for(int j=0;j<agents.size();j++){
   if(i==j) continue;
   if(distance_between(i,j)<10){
     //do a lot of calculations for interaction between i and j,
     //and a bunch of changes to variables of the Agents stored in the list
   }
 }
}

Могу ли я просто добавить «#pragma omp parallel for» перед первым циклом для распределения работы?Если я это сделаю, моя программа будет работать намного быстрее, но я обеспокоен тем, что выполняемые ею вычисления могут быть неточными.

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

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

Answer 1

Да, добавление прагмы будет правильным. Память считается неявно общей для всех потоков. Тем не менее, это не значит, что он будет работать быстрее. Есть несколько вопросов, которые необходимо рассмотреть:

• сколько процессоров в вашей системе?
• вы используете целое число или число с плавающей точкой? Для целых чисел порядок не имеет значения, но это не так для плавающей запятой
• к каким переменным обращается только самый внутренний цикл? Вы можете объявить их частными, чтобы получить лучшую производительность.

Answer 2

Убедитесь, что взаимодействия i,j и j,i, которые влияют на одни и те же данные, не вызывают гонок данных. Вы можете сделать это, тщательно настраивая распределение работы или используя omp critical или omp atomic конструкции, где это необходимо.

Кроме того, нет проблем с тем, чтобы заставить ваш код работать быстрее, просто используя конструкции omp parallel for во внешнем цикле. Имейте в виду, что если количество процессорных блоков (ядер, многопоточных и т. Д.) Имеет ваш процессор, или если вы используете компьютер ccNUMA, было бы неплохо сделать некоторые дополнительные действия, поскольку масштабируемость вашего кода будет не так хорошо, как могло бы.

Самое простое улучшение - добавить collapse(2) к вашему предложению omp for. Это скажет OpenMP, что вы хотите распределить итерации обоих этих циклов.

#pragma omp parallel for collapse(2)
for(int i=0;i<agents.size();i++){
 for(int j=0;j<agents.size();j++){
   if(i==j) continue;
   if(distance_between(i,j)<10){
     //do a lot of calculations for interaction between i and j,
     //and a bunch of changes to variables of the Agents stored in the list
   }
  }
}

Как только вы достигнете огромного количества частиц (или агентов, как вы их называете), было бы разумно отсортировать их все в соответствии с их положением. Это приведет к тому, что ваше условие if внутри самого внутреннего цикла будет иметь более стабильное поведение, что позволит лучше прогнозировать ветви (см. , почему это быстрее для обработки отсортированного массива ).

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

Подобные проблемы очень хорошо известны, и, как вы, возможно, уже знаете, они называются проблемами n-тела . Версия оптимизации корзины называется имитация Барнса-Хата , хотя вы можете обнаружить, что другие подходы работают намного быстрее (хотя их труднее распараллелить, но в большинстве случаев они все еще более эффективны), такие как Fast Multipole Метод , который более или менее состоит в сокращении числа вычислений путем решения обоих взаимодействий i,j и j,i за один шаг.

Answer 3

Могу ли я просто добавить «#pragma omp parallel for» перед первым циклом, чтобы распределить работу?

Это зависит от того, что вы будете делать в параллельном разделе. Чтобы повысить производительность, вы можете изменить алгоритм вашего параллельного кода, а не просто указывать #pragma omp parallel в коде последовательности. Помните, что ключом параллельного программирования являются общие переменные. В некоторых случаях было бы лучше использовать код последовательности, чем параллельный.

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

Действительно, вы должны убедиться, что в вашем коде нет ничего расового условия, чтобы получить правильный результат вычисления.