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

Question

При работе над имитацией взаимодействий частиц я наткнулся на индексацию сетки в Мортон-порядке (Z-порядок) (Wikipedia link), который считается эффективным для поиска ближайших соседей. Основная причина, по которой я читал, - почти последовательный порядок пространственно близких ячеек в памяти.

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

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

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

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

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

---

EDIT:
Спасибо за разъяснение пункта 1! Таким образом, при Z-упорядочении скорость попадания в кэш увеличивается в среднем для соседних ячеек, что интересно. Есть ли способ профилировать рейтинг хитов/пропусков?

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

// 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

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

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

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

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

Точка Мортон упорядочения для поддержки схем, где осуществляется доступ к данным два размерно вместо один одномерно. Другими словами, после доступа к элементу (x, y) вы можете перейти к доступу (x + 1, y) или (x, y + 1) или тому подобное.

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

---

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

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

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

Answer 2

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

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

Однако, если вы загрузите A [1023], процессор должен загрузить этот кусок. Затем он должен загрузить A [12] - который он еще не загрузил и, следовательно, должен загрузить новый кусок. Et cetera, et cetera. Однако я понятия не имею о остальном вашем вопросе.