Преимущества ближайшего соседа поиска с Morton-order?

Question

Работая над моделированием взаимодействий частиц, я наткнулся на индексацию сетки в Morton-order (z-order) (Википедия Ссылка) который считается эффективным поиском ближайшего соседнего сочетания. Основная причина, по которой я читал, является почти последовательным упорядочением пространственно близких клеток в памяти.

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

1. Учитывая клетку (X, Y), это тривиально получить 8 соседних индексов клеток и вычислять соответствующий Z-индекс. Хотя это обеспечивает постоянное время доступа к элементам, Z-индекс имеет либо рассчитанный или просматривать в предопределенных таблицах (отдельных для каждой оси и или или «). Как это может быть более эффективным? Это правда, что доступ к элементам в массиве A в порядке, скажем, [0] -> A1 -> А [3] -> A [4] -> ... более эффективно, чем в порядке A [1023] -> A [12] -> A [456] -> A [56] -> .. .?

2. Я ожидал, что существует более простой алгоритм, чтобы найти ближайшие соседи в Z-порядке. Что-то вдоль линий: найдите первую клетку соседей, итерации. Но это не может быть правдой, так как это хорошо работает только в течение 2 ^ 4 размеров блоков. Однако есть две проблемы: когда ячейка не находится на границе, можно легко определить первую ячейку блока и итерации через клетки в блоке, но нужно проверить, является ли ячейка ближайшим соседом. Хуже того, когда клетка лежит на границе, чем нужно учитывать 2 ^ 5 клеток. Что я здесь не хватает? Есть ли сравнительно простой и эффективный алгоритм, который будет делать то, что мне нужно?

Вопрос в пункте 1. Легко реализуемо, но я не очень знаком с основными инструкциями, что описанный шаблон доступа генерирует и действительно хотел бы понять, что происходит за кулисами.

Заранее спасибо за любую помощь, ссылки и т. Д. ...

---

РЕДАКТИРОВАТЬ:
Спасибо за разъяснение пункта 1! Таким образом, с z-упорядочением скорость попадания кеша увеличивается в среднем для соседних клеток, интересных. Есть ли путь к профилю Cache Hat / Miss Trine?

Что касается пункта 2: я должен добавить, что я понимаю, как построить, как построить Morton-заказанный массив для точечного облака в R ^ d, где индекс i = f (x1, x2, ..., xd) получается из битовой переплетки и т. Д. То, что я пытаюсь понять, есть ли лучший способ, чем следующий наивный Ansatz, чтобы получить ближайшие соседи (здесь в D = 2, «Pseudo Code»):

// Get the z-indices of cells adjacent to the cell containing (x, y) 
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2    
point = (x, y)
zindex = f(x, y)     
(zx, zy) = f^(-1)(zindex)          // grid coordinates 
nc = [(zx - 1, zy - 1), (zx - 1, zy), (zx - 1, zy + 1),  // neighbor grid 
      (zx    , zy - 1),               (zx,     zy + 1),  // coordinates
      (zx + 1, zy - 1), (zx + 1, zy), (zx + 1, zy + 1)]

ni= [f(x[0], x[1]) for x in nc]    // neighbor indices

Answer 1

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

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

Когда 1-D данные доступны последовательно, как в простой обработке изображений или обработки звука, либо итерации над структурами данных, обработанные каждый элемент, то и аранжировка элементов данных в памяти, как правило, достигает пространственной местности - т. Е. С момента доступа к элементу N + 1 сразу после доступа к элементу N, два элемента должны быть размещены рядом друг с другом в памяти.

Стандартные массивы C (и многие другие структуры данных) имеют это свойство.

Точка заказа Morton является поддержка схем, где доступны данные два вместо этого вместо один померка. Другими словами, после доступа к элементу (X, Y) вы можете включить доступ к доступу (x + 1, y) или (x, y + 1) или аналогично.

Указание Morton означает, что (x, y), (x + 1, y) и (x, y + 1) близки друг к другу в памяти. В стандарте C многомерного массива это не обязательно так. Например, в массиве MyArray [10000] [10000], (x, y) и (x, y + 1) - 10000 элементов друг от друга - слишком далеко друг от друга, чтобы воспользоваться пространственной местностью.

---

В упорядочении Morton в качестве хранилища все еще можно использовать стандартный массив C, но расчет для работы, где (x, y) больше не так просто, как магазин [x + y * rssize].

Чтобы реализовать ваше приложение, используя упорядочение MOOTON, вам необходимо выработать, как преобразовать координату (X, Y) в адрес в магазине. Другими словами, вам нужна функция f(x,y) это можно использовать для доступа к магазину как в store[f(x,y)].

Похоже, вам нужно сделать еще несколько исследований - следуйте ссылкам с страницы Википедии, особенно те на BIGMIN функция.

Answer 2

Да, доступа к элементам массива в порядке действительно быстрее. ЦП загружает память от ОЗУ в кеш в кусках. Если вы подключите к последовательному доступу, CPU может легко предварительно загрузить следующий кусок, и вы не заметите время загрузки. Если вы получаете доступ к случайным образом, он не может. Это называется Cache Coherence, а что значит, что доступ к памяти рядом с памятью, которую вы уже доходили, является быстрее.

В вашем примере при загрузке [1], [2], [3] и [4], процессор, вероятно, загрузил несколько из этих индексов сразу, что делает их очень тривиальными. Более того, если вы затем продолжаете получить доступ к [5], он может предварительно загрузить этот кусок, когда работаешь на [1] и такое, делая время нагрузки нечего.

Однако, если вы загружаете [1023], процессор должен загрузить этот кусок. Затем он должен загружать [12], которое он еще не загрузил и, таким образом, должен загрузить новый кусок. ET CETERA, ET CETERA. Однако я понятия не имею о остальной части вашего вопроса.