Быстрые nbody алгоритмы / решения (с opengl / c ++ / ??)

Question

Я работаю над проектом (c ++, opengl), где мне нужно иметь много частиц, которые влияют друг на друга, если я прав, это называется проблемой nbody.Кто-нибудь знает, какие существуют решения для таких алгоритмов?

Я знаю алгоритм хижины Барнса и, может быть, я могу заглянуть в openCL, хотя я не просто удивляюсь, использовали ли вы другие решения.

У кода, который я создам, будет много:

for(int i = 0; i < num_particles; ++i) {
  for(int j = i+1, j < num_particles; ++j)
     dist = distance(particles[i],particles[j]);
     if(dist > limit) {....}
  }
}

С уважением, Поллукс

Answer 1

Kd-деревья идеально подходят для поиска всех объектов (в данном случае частиц) на максимальном расстоянии.Если дерево сбалансировано, ищите O(log n).

Answer 2

Здесь пригодятся структуры данных, такие как Octrees . Они могут уменьшить ваши O(N^2) петли до O(N*log(N)), за счет потери крошечной точности.

Answer 3

Если вы хотите иметь ОГРОМНУЮ вычислительную мощь для множества довольно простых тел - заинтересуйтесь nvidia CUDA и выполняйте свою работу с шейдерными модулями GPU. Это может повысить производительность даже по сравнению с четырехъядерными процессорами с многопоточностью

Answer 4

Разделение области 1024x512 пикселей на блоки 4x4 пикселей, выделение 15 ячеек для частиц в каждом блоке, имеющих 12 тыс. Частиц для вычисления только с силами исключения, заняло не более 8 мс для Intel HD-400 (имеет 12 вычислительных блоков, черезopencl api) для:

for(each particle) // this part unfolded on N workitems of opencl
for(each neighboring box) {       
     for(each particle in selected box)
     {
         dist = distance(particles[i],particles[j]);
         if(dist < limit) {/* sqrt, mult, div, add, sub */}
      }
}

, поэтому разделение пространства и использование opencl, безусловно, увеличивает скорость.Без разделения, перебор занял 44 мс, что неплохо для бюджетного интегрированного gpu с одноканальной медленной памятью.

Кроме того, при одновременном использовании второго процессора, около 0,5 мс - 0,1 мс, но потому чтопамяти в фоновом режиме.

Answer 5

Вот, пожалуйста: GeForce Gems 3 . Он в CUDA, но легко переносим в openCL.

Однако эта версия вычисляет взаимодействия N² / 2, которые вы, возможно, не хотите.