Эффективные с точки зрения вычислений трехмерные массивы на C

StackOverflow https://stackoverflow.com/questions/76076

Вопрос

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

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

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

Это было полезно?

Решение

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

1 2
3 4

---

5 6
7 8

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

Другие советы

Одна из альтернатив древовидному методу:Используйте 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;

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top