OpenMP: огромное замедление в идеальном сценарии

Question

В приведенном ниже коде я пытаюсь сравнить все элементы массива со всеми другими элементами во вложенном цикле for.(Это для запуска простой симуляции n-body. Я тестирую только 4 тела для 4 потоков на 4 ядрах).Идентичная последовательная версия кода без модификаций OpenMP выполняется примерно за 15 секунд для 25M итераций.Прошлой ночью этот код работал около 30 секунд.Теперь он длится около 1 минуты!Я думаю, что проблема может заключаться в том, что потоки должны писать в массив, который передается функции через указатель.
Массив динамически размещается в другом месте и состоит из структур, которые я определил.Это всего лишь догадка.Я проверил, что 4 потока работают на 4 отдельных ядрах на 100% и что они правильно обращаются к элементам массива.Есть идеи?

void runSimulation (particle* particles, int numSteps){
  //particles is a pointer to an array of structs I've defined and allocated dynamically before calling the function
  //Variable Initializations


#pragma omp parallel num_threads(4) private(//The variables inside the loop) shared(k,particles) // 4 Threads for four cores
{
  while (k<numSteps){ //Main loop.  

    #pragma omp master //Check whether it is time to report progress.
    {
      //Some simple if statements
      k=k+1; //Increment step counter for some reason omp doesn't like k++
    }


    //Calculate new velocities
    #pragma omp for
    for (i=0; i<numParticles; i++){ //Calculate forces by comparing each particle to all others
      Fx = 0;
      Fy = 0;
      for (j=0; j<numParticles; j++){
        //Calcululate the cumulative force by comparing each particle to all others
      }
      //Calculate accelerations and set new velocities
      ax = Fx / particles[i].mass;
      ay = Fy / particles[i].mass;

                              //ARE THESE TWO LINES THE PROBLEM?!
      particles[i].xVelocity += deltaT*ax;
      particles[i].yVelocity += deltaT*ay;
    }           


    #pragma omp master
    //Apply new velocities to create new positions after all forces have been calculated.
    for (i=0; i<numParticles; i++){
      particles[i].x += deltaT*particles[i].xVelocity;
      particles[i].y += deltaT*particles[i].yVelocity;
    }

    #pragma omp barrier
  }
}
}

Answer 1

Вы копаете кеш. Все ядра записывают в одну и ту же общую структуру, которая будет непрерывно перемещаться между ядрами через L2 (в лучшем случае), L3 или шину основной памяти / памяти (в худшем случае). В зависимости от того, как происходит обмен данными, это занимает от 20 до 300 циклов, в то время как запись в частную память в L1 занимает 1 цикл или менее в идеальных условиях.

Это объясняет ваше замедление.

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

Answer 2

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

Я думаю, что более вероятным виновником является то, что накладные расходы для инициализации omp for составляют 1000 циклов http://www.ualberta.ca/CNS/RESEARCH/Courses/2001/PPandV/OpenMP.Eric.pdf, и цикл содержит только несколько вычислений. Я не удивлен, что петля медленнее всего с 4 телами. Если бы у вас было несколько сотен тел, ситуация была бы другой. Однажды я немного поработал над циклом и в итоге напрямую использовал pthreads.

Answer 3

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

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

• Выделите память для хранения всего массива частиц в каждом потоке;сделайте это один раз и сохраните все четыре новых указателя.
• В начале каждой итерации основного цикла в главном потоке глубокое копирование основного массива четыре раза в каждый из этих новых массивов.Вы можете сделать это быстро с помощью memcpy ().
• Выполните вычисления так, чтобы первый поток записывал в индексы 0 В главном потокеперед применением новых скоростей объедините четыре массива в основной массив, скопировав только соответствующие индексы.Вы можете сделать это быстро с помощью memcpy ().
• Обратите внимание, что вы можете распараллелить ваш цикл «применения новых скоростей» без проблем, потому что каждая итерация работает только с одним индексом;это, вероятно, самая простая часть для распараллеливания.

Новые операции будут только O (N) по сравнению с вашими вычислениями, которые O (N ^ 2), поэтому они не должны занимать слишком много временив долгосрочной перспективе.Определенно, есть способы оптимизировать шаги, которые я для тебя изложил, Гейб, но я оставлю их тебе.