Вычислительно эффективные трехмерные массивы в C

Question

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

Чтобы написать эффективный код, мне нужно, чтобы точки в трех измерениях были близки в одномерном пространстве памяти, чтобы каждое значение вызывалось из памяти только один раз.

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

Answer 1

Одна альтернатива древовидному методу: используйте Morton-Order для кодирования ваших данных.

В трех измерениях это выглядит так: взять компоненты координат и перемежать каждый бит двумя нулевыми битами. Здесь показано в двоичном виде: 11111b становится 1001001001b

C-функция для этого выглядит следующим образом (показана для ясности и только для 11 битов):

int morton3 (int a)
{
  int result = 0;
  int i;
  for (i=0; i<11; i++)
  {
     // check if the i'th bit is set.
     int bit = a&(1<<i);
     if (bit)
     {
       // if so set the 3*i'th bit in the result:
       result |= 1<<(i*3);
     }
  }
  return result;
}

Вы можете использовать эту функцию, чтобы объединить ваши позиции следующим образом:

index = morton3 (position.x) + 
        morton3 (position.y)*2 +
        morton3 (position.z)*4;

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

Для morton3 вам лучше не использовать код выше. Используйте небольшую таблицу, чтобы найти 4 или 8 бит за раз и объединить их вместе.

Надеюсь, это поможет, Nils

Answer 2

октре - это путь. Вы делите массив на 8 октантов:

1 2
3 4

---

5 6
7 8

А затем выложить их в память в порядке 1, 2, 3, 4, 5, 6, 7, 8, как указано выше. Вы повторяете это рекурсивно в пределах каждого октанта, пока не достигнете некоторого базового размера, вероятно, около 128 байт или около того (это всего лишь предположение - убедитесь, что для определения оптимальной точки отсечения требуется профиль). Это имеет намного, намного лучшую согласованность кэша и местность ссылки, чем наивный макет.

Answer 3

Книга Основы многомерных и метрических структур данных может помочь вам решить, какая структура данных является самой быстрой для запросов диапазона: октреи, деревья kd, R-деревья, ... В нем также описаны макеты данных для хранения точек в памяти.